python - 安排作业以最小化变化的算法

Question

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

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

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

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

我希望能够输入我想做的工作 1、工作 3、工作 5、工作 7 和工作 8 以及将工作分类为“组”的程序，这些工作都可以使用相同的工具集完成。

这些组在“工具集”中必须没有冲突。 IE。没有两个工具可以占据同一个工位。如果一个工具用于多个工作，它的特性(工位、间隙、角度)都必须相同。等

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

此外:字典中将有大约 4-5 千个工作。尽管排序所需的时间并不是特别重要。

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

工作 1 需要:

• 锤子 - st: 2
• Screwdriver - st:4

工作2需要

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

工作 3 需要:

• 锤子 - st:2
• Spanner - st: 4

工作 4 需要:

• Spanner - st: 4
• 钉枪 - st:6

工作 5 需要:

• Screwdriver st:4
• 枕头街:5

这样程序会输出

工作:2、3 和 4 可以用:

• 锤子 - st: 2
• Spanner - st: 4
• 钉枪 - st: 6

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

• 锤子 - st: 1
• Screwdriver - 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)

结果:

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)

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