调度作业以最小化更改的算法

Question

我正在用Python编写一个程序，希望它能最大限度地减少与数控转塔冲床有关的工具更改。

这些信息存储在一本大词典中：

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

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

我希望能够输入我想要做的job1、job3、job5、job7和job8，以及将作业排序为“组”的程序，这些任务都可以用相同的工具集完成。

这些群体必须在“工具集”中没有冲突。也就是说，没有任何两个工具可以占据同一站。如果一个工具被用于一个以上的工作，它的特性(站，间隙，角度)都必须是相同的。等。

--我只是不知道如何在python中对字典进行排序。任何帮助或指示都将不胜感激。

还有:字典里大约有四五千个工作岗位.尽管排序所需的时间并不特别重要。

编辑:简单的示例(只有一个工具的特征)，因为我认为我不是很清楚：

Job1需要：

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

Job2需要

• 锤子-圣:2
• 钉枪-圣:6

Job3需要：

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

工作4需要：

• 扳手-圣:4
• 钉枪-圣:6

工作5需要：

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

因此，程序将输出

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

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

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

• 锤子-圣:1
• 螺丝刀- st: 4
• 枕头-圣: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)

结果：

found valid tool setup combination:
(('hammer', 2), ('nail gun', 6), ('wrench', 4))
(('hammer', 2), ('screwdriver', 4), ('pillow', 5))

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

编辑

上面有一个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

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

一般来说，这是一个优化问题，但更具体地说，我怀疑这是一个作业车间调度的实例：排程

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

Answer 3

我想用线性规划来解决你的问题。然而，我仍然不能，因为你没有适当地说明你的问题。因此，我只会给大家一个大致的答覆：

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

在你的问题陈述中仍然缺少的东西：

• 变革的代价是什么？在任意工具之间切换时，它们是相同的，还是添加/删除不同？每一次更改是否有固定的基本成本(例如停止和恢复机器)？
• 是否存在使用这些工具的成本，例如，您是否应该尽量减少配备的工具的数量，以便将其操作成本降到最低？
• 你一次能装备多少个工具？你能装备他们所有的，或只是一定的数量，或仅仅一种类型或组合？
• 是否对可以完成的批数有限制？
• 这些工作是否需要不同的时间，这些时间是否提前知道？
• ..。