Abstract: Identical parallel machine scheduling problems with family setup times are studied. A three-phase heuristic algorithm is developed to minimize the total earliness and tardiness. In first phase, sequence jobs to minimize the total tardiness as on single machine problems. In second phase, assign the sorted job to the latest free machine according the sequence obtained in first phase. In the last phase, insert the optimal amount of idle time into the sequence scheduled on each machine using improved GTW algorithm. Computational results show the proposed heuristic algorithm can find approximately optimal solutions of large size problems in very short time.

Key words: Scheduling, Parallel machine, Setup time, Heuristic algorithm

摘要： 研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题，提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题，以最小化总拖后时间为优化目标排列工件的加工次序；然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上；最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。

关键词: 调度, 并行机, 调整时间, 启发式算法