CAJ | 학술논문

考虑需要安装时间的平行多功能机排序问题。在该模型中，每个工件对应机器集合的一个子集，其只能在这个子集中的任一台机器上加工，称这个子集为该工件的加工集合；工件分组，同组工件具有相同的加工时间和加工集合，不同组中的工件在同一台机器上连续加工需要安装时间，目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法：首先按照特定的规则将所有工件组都整组地安排到各台机器上，然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能，大量的计算实验表明，算法是实用而有效的。
고필수요안장시간적평행다공능궤배서문제。재해모형중，매개공건대응궤기집합적일개자집，기지능재저개자집중적임일태궤기상가공，칭저개자집위해공건적가공집합；공건분조，동조공건구유상동적가공시간화가공집합，불동조중적공건재동일태궤기상련속가공수요안장시간，목표함수위겁소화최대완공시간。대해문제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 .