安排工作以尽量减少变化的算法

Question

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

的信息存储在一个大辞典：

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

乔布斯通常4-8工具之间使用，但是有工作之间有很多工具的使用重叠的（因此只需要工作之间1周或2的变化） 。

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

这些组必须在'工具集'中没有冲突。即没有两个工具可以占用同一个工作站。如果一个工具被用于多个工作，它的特征（工位，间隙，角度）都必须相同。等

我只是不知道如何做这种排序到python字典。任何帮助或指针将不胜感激。

另外：词典中会有大约4-5千个工作。虽然排序花费的时间并不特别重要。

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

作业1要求：

• 锤 - ST：2
• 螺丝刀 - ST：4

作业2需要

• 锤 - ST：2
• 钉枪 - ST：6

JOB3需求：

• 锤 - ST：2
• 扳手 - ST：4

作业4需求：

• 扳手 - ST：4
• 钉枪 - ST：6

作业5层的需求：

• 螺丝刀ST：4
• 枕头ST：5

因此程序会输出

ST -

• 锤：2
• 扳手 - ST：

  乔布斯：2，3和4是可以做到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) 

结果：

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

它保存在内存中所有工具的组合，因此可以使用大量内存作为工具数量的增加。毫无疑问，它可以被优化，但应该提供一个起点。

编辑

有一个错误在上面，需要包含的工具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字典 - - 相反，可能会输出一个键值对值的排序列表）。所以我会建议将它标记为“优化”而不是排序，也可能是“调度”。

在一般情况下，这是一个最优化问题，但更具体，我怀疑这是车间调度的一个实例： http://en.wikipedia.org/wiki/Job_shop_scheduling

我还没有与该类问题的工作，所以我怕我不能给你任何关于如何建模的指导，但是从这里开始可能是值得的。

Answer 3

我想用linear programming来解决你的问题。但是，由于您没有正确指定您的问题，因此我仍然无法执行此操作。因此，我只想给你一个一般的答案：

线性规划背后的想法是，你需要指定一个任意的线性，多元成本函数和任意数量的限制（通常是不等式，如“总和所有同时使用的工具< = 5等“）。在正确指定了问题后，可以使用单纯形算法或内点法等技术来获得最小化/最大化成本函数的解决方案，并且根据您的限制（如果存在此类解决方案）是可行的。您甚至可以轻松验证您的解决方案的最佳性能（即使是手工补充松弛）。如果你需要整数解决方案（这个问题有点难），你可以使用分支定界技术来获得这些解决方案。线性规划是一个研究得很好且灵活的研究领域，它可以很容易地应用于所有类型的优化问题。

事情仍在您的问题声明丢失：

• 有什么变化的成本？在任意工具之间切换时，它们是相同的，还是添加/删除不同的工具？每次更改是否存在一些不变的基本成本（例如停止和恢复机器）？
• 使用任何这些工具是否存在成本，例如，您是否应该尽量减少配备工具的数量，以最大限度地降低运营成本？
• 一次可以装多少件工具？你可以装备他们所有的人，或者只是一定的数量，或者只是其中的一种或多种组合？
• 可以完成的批次数量是否有限制？
• 这些工作需要不同的时间，并且事先知道那些时间吗？
• ...

Answer 4

有许多参数的问题，其中一些被指出（4-8工具），但他们中的一些不（有多少个站点，在那里只有一个锤）。例如，可以通过将“工具”定义为“间隔= X和角度= Z的锤子”来简化。

我会从制作某种逆向地图开始。将工具集转换为作业或将工作站/工具转换为作业。

工具集到工作映射将允许您说“对于给定的工具集，我可以处理哪些工作”。添加一个函数来说明两个工具集是否兼容（即除了没有工具的工作站相同），另一个用于生成组合工具集作为两个兼容工具集的总和。在您的示例中，作业1和5具有兼容的工具集，就像作业2和3以及总和和4一样。然后您可以通过安装兼容工具集的组合来处理兼容工具集集合中的所有作业。

groups = {} 
for job in jobs: 
    x = ['________' for i in range(num_stations)] 
    for tool in jobs[job]: 
     x[jobs[job][tool][station]] = tool 
    y = ','.join(x) 
    if y not in groups: 
     groups[y] = [job] 
    else: 
     groups[y].append(job) 

站到工具的工作映射将允许你说“这个站，如果我安装该工具哪些工作将与帮助。”

stations = [] 
for station in range(num_stat): 
    stations.append({}) 
for job_name in sorted(jobs.keys()): 
    for tool in sorted(jobs[job_name].keys()): 
     pos = jobs[job_name][tool][station] 
     if tool not in stations[pos]: 
      stations[pos][tool] = set() 
     stations[pos][tool].add(job_name) 

总之，这里是一个黑客位在一起的：

#!/usr/bin/env python 
# vim: tabstop=8 softtabstop=4 shiftwidth=4 nocindent smartindent 
import random 
import traceback, sys 
Verbose = False 
random.seed(4) 
num_loops = 500 # Number of times to run the job-scheduling loop 
num_stat = 6 # Number of stations where tool can be loaded 
min_tools = 2 # lowest tool count for a job 
max_tools = 4 # highest tool count for a job 
num_posts = 3 # Number of stations a tool can be mounted 
num_jobs = 5000 # Number of simulated jobs 
num_tools = 6 # Number of different tool/offset/angle combinations 

# Setup the tools database 
# tool_names is a list of the names of the available tools (with offset and angle) 
# tools is a map giving a list of positions where the tool can be loaded 
tool_names = sorted(['tool%03d' % idx for idx in range(num_tools)]) 
tool_fmap = {} 
tool_rmap = {} 
for tool in tool_names: 
    tool_fmap[tool] = sorted(random.sample(xrange(num_stat), num_posts)) 
    for pos in tool_fmap[tool]: 
     if pos not in tool_rmap: 
      tool_rmap[pos] = set() 
     tool_rmap[pos].add(tool) 

for tool in sorted(tool_fmap.keys()): 
    print "%-8s" % tool, sorted(tool_fmap[tool]) 
for pos in sorted(tool_rmap.keys()): 
    print "%2d" % pos, sorted(tool_rmap[pos]) 

# Build the jobs and stations database 
def make_jobs_database(): 
    jobs = {} 
    distro = [0 for i in range(num_stat + 1)] 
    short_count = [0 for i in range(num_stat + 1)] 
    for job_num in range(num_jobs): 
     job_name = "job%04d" % job_num 
     jobs[job_name] = {} 
     num_tools_in_job = random.randrange(min_tools, max_tools + 1) 
     t_list = random.sample(tool_names, num_stat) 
     available_positions = range(num_stat) 
     num_posns_allocated = 0 
     for tool in t_list: 
      possible_positions = [x for x in tool_fmap[tool] if x in available_positions] 
      if len(possible_positions) == 0: 
       continue 
      jobs[job_name][tool] = random.choice(possible_positions) 
      available_positions.remove(jobs[job_name][tool]) 
      num_posns_allocated += 1 
      if num_posns_allocated >= num_tools_in_job: 
       break 
     if len(jobs[job_name].keys()) < num_tools_in_job: 
      short_count[len(jobs[job_name].keys())] += 1 
     distro[len(jobs[job_name].keys())] += 1 
    print "Shorts:", short_count 
    for idx, cnt in enumerate(distro): 
     print "Jobs with %d tools = %d" % (idx, distro[idx]) 
    return jobs 

def make_station_database(jobs): 
    stations = [] 
    for station in range(num_stat): 
     stations.append({}) 
    for job_name in sorted(jobs.keys()): 
     for tool in sorted(jobs[job_name].keys()): 
      pos = jobs[job_name][tool] 
      if tool not in stations[pos]: 
       stations[pos][tool] = set() 
      stations[pos][tool].add(job_name) 
    return stations 

def make_group_database(jobs): 
    groups = {} 
    for job_name in sorted(jobs.keys()): 
     x = ['_______' for i in range(num_stat)] 
     for tool in sorted(jobs[job_name].keys()): 
      pos = jobs[job_name][tool] 
      x[pos] = tool 
     z = ",".join(x) 
     if z not in groups: 
      groups[z] = [] 
     groups[z].append(job_name) 
    return groups 

def show_jobs_database(jobs): 
    print "Jobs Database:" 
    for job_name in sorted(jobs.keys()): 
     x = ['_______' for i in range(num_stat)] 
     for tool in sorted(jobs[job_name].keys()): 
      pos = jobs[job_name][tool] 
      x[pos] = tool 
     z = ",".join(x) 
     print job_name, z 

def show_station_database(stations): 
    print "Station Database:" 
    for idx, stat in enumerate(stations): 
     print idx 
     for tool in sorted(stat.keys()): 
      print ' ', tool, sorted(stat[tool]) 

def show_group_database(groups): 
    print "Groups Database:" 
    for group in sorted(groups.keys()): 
     print group, groups[group] 

def prune_station_database(stations, done_jobs): 
    for pos in range(num_stat): 
     empty_tools = [] 
     for tool in stations[pos]: 
      stations[pos][tool].difference_update(done_jobs) 
      if len(stations[pos][tool]) == 0: 
       empty_tools.append(tool) 
     for tool in empty_tools: 
      del stations[pos][tool] 

def make_selection(stations, all_possible_jobs): 
    global tools_used, posns_used 
    selections = [] 
    tools_used = {} 
    posns_used = {} 
    possible_jobs = all_possible_jobs.copy() 
    for i in range(num_stat): # select a station to populate 
     target_posn = None 
     target_tool = None 
     target_len = 0 
     for pos in range(num_stat): # inspect each station 
      if pos in posns_used: 
       continue 
      key_len = 0 
      key_pos = None 
      key_tool = None 
      for tool in stations[pos]: # inspect each tool at this station 
       if tool in tools_used: 
        continue 
       new_len = len(possible_jobs.intersection(stations[pos][tool])) 
       if new_len > key_len: 
        key_len = new_len 
        key_pos = pos 
        key_tool = tool 
      if key_len > target_len: 
       target_len = key_len 
       target_posn = key_pos 
       target_tool = key_tool 
     if target_tool is not None: 
      tools_used[target_tool] = target_posn 
     if target_posn is not None: 
      posns_used[target_posn] = target_tool 
      possible_jobs.intersection_update(stations[target_posn][target_tool]) 
      selections.append((target_posn, target_tool)) 
     if Verbose: 
      print "Jobs:", len(possible_jobs), sorted(list(possible_jobs)) 
    if not Verbose: # print it at least once 
     print "Jobs:", len(possible_jobs), sorted(list(possible_jobs)) 
    # We have all the tools we need, see if there are more we can use 
    for pos in range(num_stat): 
     extra_jobs = 0 
     best_tool = None 
     if pos not in posns_used: 
      new_posns = {pos:None} 
      for p in posns_used: 
       new_posns[p] = posns_used[p] 
      for tool in stations[pos]: 
       if tool in tools_used: 
        continue 
       key_count = 0 
       new_posns[pos] = tool 
       for job in stations[pos][tool]: 
        if job_is_ok(job, None, new_posns): 
         key_count += 1 
       if key_count > extra_jobs: 
        extra_jobs = key_count 
        best_tool = tool 
      tools_used[best_tool] = pos 
      posns_used[pos] = best_tool 
      selections.append((pos, best_tool)) 
    print "Tools:", tools_used 
    print "Stations:", posns_used 
    print "Selections:", selections 

def toolset_compatible(x, y): 
    if len(x) != len(y): 
     return False 
    for idx in range(len(x)): 
     if x[idx] == y[idx]: 
      continue 
     if x[idx] == '' and y[idx] not in x: 
      continue 
     if y[idx] == '' and x[idx] not in y: 
      continue 
     return False 
    if Verbose: 
     print "Compatible:" 
     print x 
     print y 
    return True 

def toolset_combine(x, y): 
    z = [] 
    for idx, xval in enumerate(x): 
     if xval == '': 
      z.append(y[idx]) 
     else: 
      z.append(xval) 
    if Verbose: 
     print "Combined:" 
     print x 
     print y 
     print z 
    return z 

def job_is_ok(job, tools_used, posns_used): 
    for tool in jobs[job]: 
     pos = jobs[job][tool] 
     if pos not in posns_used: 
      pass 
     elif posns_used[pos] != tool: 
      return False 
    return True 

def job_is_on(job, tools_used): 
    for tool in jobs[job]: 
     pos = jobs[job][tool] 
     if tool not in tools_used: 
      return False 
     if tools_used[tool] != pos: 
      return False 
    return True 

def use_stations(stations): 
    all_possible_jobs = set(jobs.keys()) 
    try: 
     for run in range(num_loops): 
      make_selection(stations, all_possible_jobs) 
      jobs_on = set() 
      for job in all_possible_jobs: 
       if job_is_on(job, tools_used): 
        jobs_on.add(job) 
      print "JobsOn:", len(jobs_on), sorted(jobs_on) 
      prune_station_database(stations, jobs_on) 
      count_before = len(all_possible_jobs) 
      all_possible_jobs.difference_update(set(jobs_on)) 
      count_after = len(all_possible_jobs) 
      print "Counts: run = %d, before = %d, after = %d" % (run + 1, count_before, count_after) 
      if count_before == count_after: 
       break 
      if count_after == 0: 
       break 
    except Exception, err: 
     print traceback.format_exc() 
     print "Tools:", tools_used 
     print "Stations:", posns_used 
    show_station_database(stations) 

def use_groups(groups): 
    all_possible_jobs = set(jobs.keys()) 
    try: 
     for run in range(num_loops): 
      selected_group = None 
      group_len = 0 
      for group in groups.keys(): 
       if len(groups[group]) > group_len: 
        group_len = len(groups[group]) 
        selected_group = group 
      if Verbose: 
       print "Selected:", selected_group, groups[selected_group] 
      selected_groups = [selected_group] 
      toolset = [x.strip('_') for x in selected_group.split(',')] 
      for group in groups.keys(): 
       if group in selected_groups: 
        continue 
       new_toolset = [x.strip('_') for x in group.split(',')] 
       if toolset_compatible(toolset, new_toolset): 
        toolset = toolset_combine(toolset, new_toolset) 
        selected_groups.append(group) 
      jobs_on = set() 
      tools_used = {} 
      for idx, tool in enumerate(toolset): 
       if tool != '': 
        tools_used[tool] = idx 
      print "Tools:", tools_used 
      for job in all_possible_jobs: 
       if job_is_on(job, tools_used): 
        jobs_on.add(job) 
      print "JobsOn:", len(jobs_on), sorted(jobs_on) 
      for group in selected_groups: 
       if group in groups: 
        del groups[group] 
      count_before = len(all_possible_jobs) 
      all_possible_jobs.difference_update(set(jobs_on)) 
      count_after = len(all_possible_jobs) 
      print "Counts: run = %d, before = %d, after = %d" % (run + 1, count_before, count_after) 
      if count_before == count_after: 
       break 
      if count_after == 0: 
       break 
    except Exception, err: 
     print traceback.format_exc() 
     print "Tools:", tools_used 
     print "Selected:", selected_groups 
    show_group_database(groups) 

def main_program(): 
    global jobs, stations, groups 
    jobs = make_jobs_database() 
    if Verbose: 
     show_jobs_database(jobs) 
    groups = make_group_database(jobs) 
    if Verbose: 
     show_group_database(groups) 
    stations = make_station_database(jobs) 
    if Verbose: 
     show_station_database(stations) 
    if True: 
     use_groups(groups) 
    else: 
     use_stations(stations) 

if __name__ == "__main__": 
    import cProfile 
    cProfile.run('main_program()') 

您可以尝试通过改变真到假的main_program底部的两种可供选择的方法。您可以调整顶部的主要参数。您可以通过在顶部将verbose设置为true来打印大量输出。运行需要几秒钟，其中很大一部分是建立作业数据库。