最小化变化的作业调度算法

Question

我正在用Python编写一个程序，希望能最大限度地减少数控刀架冲床的刀具变化。在

信息存储在一个大字典中：

Data = {
  'job1' : {
    'tool1' : {'clearance' : X, 'station': Y, 'angle': Z, },
    'tool2' : ...
  },
  'job2' : ...
}

作业通常使用4-8个工具，但是作业之间有很多工具使用重叠（因此只需要在作业之间进行1到2次更改）。在

我想能够输入我要做的工作1，工作3，工作5，工作7和工作8和程序排序到'组'所有可以用相同的工具集完成。在

这些组必须在“工具集”中没有冲突。一、 e.两个工具不能占用同一工位。如果一个工具用于多个工作，它的特性（工位、间隙、角度）必须完全相同。等等

我不知道如何在python中对字典进行这种排序。任何帮助或建议将不胜感激。在

还有：字典里会有大约4-5千个工作岗位。虽然排序所需的时间并不是特别关键。在

编辑： 一个简单的例子（只有一个工具特征），因为我认为我不清楚：

工作1需要：

• 锤子-st:2
• 螺丝刀-st:4

工作2需求

• 锤子-st:2
• 射钉枪-st:6

工作3需要：

• 锤子-st:2
• 扳手-st:4

工作4需要：

• 扳手-st:4
• 射钉枪-st:6

工作5需要：

• 螺丝刀st:4
• 枕头st:5

因此程序将输出

作业：2、3和4可通过以下方式完成：

• 锤子-st:2
• 扳手-st:4
• 射钉枪-st:6

工作1和5可以通过以下方式完成：

• 锤子-st:1
• 螺丝刀-st:4
• 枕头-st:5

任何帮助都将不胜感激。在

Answer 1

下面是我如何解决这个问题。不过，这是基于您的简单示例，对于更复杂的设置可能没有意义。在

假设工具的数量有限，取所有工具的组合（称之为“设置”），并确定每个设置可以完成哪些作业。在

然后搜索可以完成所有作业的设置组合，从长度1的组合开始，然后递增。在

import itertools

num_stations = 3

tools = (
        ('hammer', 2),
        ('screwdriver', 4),
        ('nail gun', 6),
        ('wrench', 4),
        ('pillow', 5),
)

job_requirements = (
        (('hammer', 2), ('screwdriver', 4)),
        (('hammer', 2), ('nail gun', 6)),
        (('hammer', 2), ('wrench', 4)),
        (('wrench', 4), ('nail gun', 6)),
        (('screwdriver', 4), ('pillow', 5)),
)

def satisfies_job(tools, job):
    return all(tool in tools for tool in job)

setups = []
for comb in itertools.combinations(tools, num_stations):
    # store this setup if no tool conflicts
    if len(set(tool[1] for tool in comb)) == len(comb):
        setups.append(comb)

# check increasing numbers of combinations of setups until all jobs can be performed
for num_setups in range(1, len(setups)):
    for setups_comb in itertools.combinations(setups, num_setups):
        # check if all jobs can be completed with this combination of tool setups
        if all(any(satisfies_job(comb, job) for comb in setups_comb) for job in
                job_requirements):
            print 'found valid tool setup combination:'
            for comb in setups_comb:
                print comb
            exit(0)

结果：

^{pr2}$

这将所有工具组合存储在内存中，因此随着工具数量的增加，可能会使用大量内存。它无疑是可以优化的，但应该提供一个起点。在

编辑

上面有一个bug，它需要包含num_stations的工具的设置，因此对于num_stations = 5它失败了，因为只有一个组合，但是它有冲突。为了纠正这个问题，它应该允许设置最多num_stations工具：

# check increasing numbers of combinations of setups until all jobs can be performed
for num_setups in range(1, 1 + len(job_requirements)):
    print('check combinations of %d setups' % num_setups)
    setups = (c for c in chain(*(combinations(tools, i) for i in range(1, 1+num_stations)))
            if len(set(tool[1] for tool in c)) == len(c))
    for setups_comb in combinations(setups, num_setups):
        # check if all jobs can be completed with this combination of tool setups
        if all(any(satisfies_job(comb, job) for comb in setups_comb) for job in
                job_requirements):
            print 'found valid tool setup combination:'
            for comb in setups_comb:
                print comb
            exit(0)

这还通过迭代设置的生成器来消除内存使用问题。在

Answer 2

我想用linear programming来解决你的问题。但是，我还是不能，因为你没有正确地说明你的问题。因此，我给你一个大概的答案：

线性规划背后的思想是，你需要指定一个任意的线性、多元的成本函数和任意数量的限制（通常是不等式，例如“同时使用的所有工具之和<；=5等等”）。在正确地指定了问题之后，可以使用单纯形算法或内点法等技术来获得最小化/最大化成本函数的解决方案，并且根据您的限制条件是可行的（如果存在这样的解决方案）。你甚至可以很容易地验证你的解决方案的最佳性，即使是用手（互补性的懈怠）。如果您需要整数解（这个问题有点难），您可以使用诸如分支和绑定这样的技术来获得这些解。线性规划是一个被广泛研究和灵活的研究领域，它可以很容易地应用于各种优化问题。在

您的问题陈述中仍然缺少的内容：

• 改变的代价是什么？在任意工具之间切换时它们是相同的，还是添加/删除不同？每次更换是否有固定的基本成本（例如停止和恢复机器）？在
• 使用这些工具是否有成本，例如，您是否应尽量减少配备的工具数量，以尽量减少其操作成本？在
• 你一次能装备多少工具？你能装备所有的装备吗，或者只装备一定数量的装备，或者每种装备中的一种，或者它们的组合？在
• 可完成的批次有限制吗？在
• 这些工作需要不同的时间吗？这些时间是否提前知道？在
• 。。。在

Answer 3

我没有完整的答案，但这看起来不像是排序问题，因为输出的作业列表不是同一个列表（即使是这样，也不能对Python dict进行排序——相反，可以输出一个键、值对的排序列表）。所以我建议将其标记为“优化”而不是排序，也可能是“调度”。在

一般来说，这是一个优化问题，但更具体地说，我怀疑这是一个job shop调度的实例： http://en.wikipedia.org/wiki/Job_shop_scheduling

我还没有处理过这类问题，所以我恐怕不能给你任何关于如何建模的建议，但是从那里开始可能是值得的。在