需要安装时间的平行多功能机排序问题的启发式算法

摘要

考虑需要安装时间的平行多功能机排序问题。在该模型中，每个工件对应机器集合的一个子集，其只能在这个子集中的任一台机器上加工，称这个子集为该工件的加工集合；工件分组，同组工件具有相同的加工时间和加工集合，不同组中的工件在同一台机器上连续加工需要安装时间，目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法：首先按照特定的规则将所有工件组都整组地安排到各台机器上，然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能，大量的计算实验表明，算法是实用而有效的。%A multi-Purpose machine scheduling problem with setup times is considered .In this model , jobs can be processed by any machine of a prespecified subset of the machine set;this prespecified subset is called pro-cessing set .Moreover , jobs are divided into different groups and all the jobs in the same group have the same processing time and processing set .A setup time is required whenever there is a switch from processing a job of one group to another job of a different group on the same machine .The objective function of the problem is mini-mization of makespan .This problem is NP-hard generally .A heuristic algorithm is proposed , in which the entire job groups are dispatched to machines according to specific rules firstly , and then the current makespan is gradu-ally improved by shifting jobs between machines .Lower bound of the problem is introduced to examine the per-formance of the heuristic .Extensive computational experiments indicate that the heuristic algorithm is practical and effective .