Abstract: 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 processing 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 minimization 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 gradually improved by shifting jobs between machines. Lower bound of the problem is introduced to examine the performance of the heuristic. Extensive computational experiments indicate that the heuristic algorithm is practical and effective.

Key words: scheduling, heuristic, multi-purpose machine, makespan

摘要： 考虑需要安装时间的平行多功能机排序问题。在该模型中,每个工件对应机器集合的一个子集,其只能在这个子集中的任一台机器上加工,称这个子集为该工件的加工集合;工件分组,同组工件具有相同的加工时间和加工集合,不同组中的工件在同一台机器上连续加工需要安装时间,目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。

关键词: 排序论, 启发式算法, 平行多功能机, 最大完工时间