用python实现加工顺序问题

加工顺序问题是一个经典的排程问题，通常使用图论或动态规划算法求解。以下是一个用Python实现加工顺序问题的例子：

假设有n个工件需要在m台机器上进行加工，每个工件需要经过若干台机器进行加工，每台机器只能同时处理一个工件，每个工件在每台机器上的加工时间不同。现在需要给出一种加工顺序，使得所有工件在最短时间内完成加工。

首先，我们需要定义每个工件在每台机器上的加工时间和加工顺序。可以使用一个二维数组来表示，例如：

processing_time = [[2, 3, 1], [1, 2, 3], [3, 1, 2]]

其中processing_time[i][j]表示第i个工件在第j台机器上的加工时间。

接着，我们需要定义一个函数来计算每个工件在当前加工顺序下的完成时间。可以使用动态规划来实现，例如：

def calculate_completion_time(order):
num_jobs = len(order)
num_machines = len(processing_time[0])
completion_time = [[0] * num_machines for _ in range(num_jobs)]
for i in range(num_jobs):
for j in range(num_machines):
if i == 0 and j == 0:
completion_time[i][j] = processing_time[order[i]][j]
elif i == 0:
completion_time[i][j] = completion_time[i][j-1] + processing_time[order[i]][j]
elif j == 0:
completion_time[i][j] = completion_time[i-1][j] + processing_time[order[i]][j]
else:
completion_time[i][j] = max(completion_time[i-1][j], completion_time[i][j-1]) + processing_time[order[i]][j]
return completion_time[-1][-1]

其中order表示当前的加工顺序，completion_time[i][j]表示前i个工件在前j台机器上的加工完成时间。

最后，我们可以使用一个递归函数来枚举所有可能的加工顺序，并找到最短完成时间：

def find_shortest_completion_time(order, remaining_jobs):
if not remaining_jobs:
return calculate_completion_time(order)
shortest_time = float('inf')
for job in remaining_jobs:
new_order = order + [job]
new_remaining_jobs = remaining_jobs - {job}
completion_time = find_shortest_completion_time(new_order, new_remaining_jobs)
shortest_time = min(shortest_time, completion_time)
return shortest_time

其中order表示当前的加工顺序，remaining_jobs表示剩余未加工的工件集合。

最终，我们可以调用find_shortest_completion_time函数来求解最短完成时间：

jobs = set(range(len(processing_time)))
shortest_time = find_shortest_completion_time([], jobs)
print('Shortest completion time:', shortest_time)

这样，我们就成功地用Python实现了加工顺序问题的求解。