并行多机成组工件调度的启发式算法

N个成组工件将在M台并行一致的机器上加工,当一个工件接在不同组的工件之后时需要装设,而接在同组工件之后时不需要重新装设,目标函数是使总的通过时间最小·利用最优解的必要条件,将单个工件组成基本运行,在研究基本运行组合规则的基础上,提出了一个基于基本运行的并行多机成组工件调度的启发式算法·在中、小规模水平问题上,将启发式算法的结果与最优解的结果进行了比较·效果令人满意·实验证明该启发式算法能够有效地解决成组工件调度的实际问题,具有解决中大规模实际问题的潜力·

Heuristic for Scheduling Grouped Jobs with Setups on Parallel Machines

A model of scheduling grouped N jobs on M identical machines in parallel was addressed. The model assumes that a setup time is incurred when a machine changes from processing one type of parts to a different type of parts. And the scheduling objective is to minimize the total sum of flow time. Based on the necessary conditions of optimal solution, jobs can be combined into fundamental runs. By studying the combinatorial rules of fundamental runs, a heuristic algorithm was developed. The efficiency of this heuristic was tested on several groups of random problems. As the number of fundamental runs is usually far less than the number of jobs, the heuristic has potential for practical application in larger scale production systems.