解决并行多机提前/拖后调度问题的混合遗传算法方法

研究了带有公共交货期的并行多机提前/拖后调度问题.提出了一种混合遗传算法 方法,以便于确定公共交货期和每台机器上加工的任务代号及其加工顺序,即找到一个最优 公共交货期和最优调度,使加工完所有任务后交货期安排的成本、提前交货成本和拖后交货 成本的总和最小.数值计算结果表明了该混合遗传算法优于启发式算法,并能适用于较大规 模并行多机提前/拖后调度问题.算法计算量小,鲁棒性强.

HYBRID GENETIC ALGORITHM METHOD FOR IDENTICAL PARALLEL MACHINE EARLINESS/TARDINESS SCHEDULING PROBLEM

Identical parallel machine earliness/tardiness scheduling problem with common due-date is studied. A kind of hybrid genetic algorithm is presented to determine the common due date,job code.and processing orders of every processed job on each machine,that is,find an optimal common due-date and optimal scheduling policy for minimizing the total cost of assignment of due-date,early delivery and tardy delivery. Numerical computations show that the hybrid genetic algorithm has advantage over heuristic procedure ,and is fit for larger scale identical parallel machine earliness/tardiness scheduling problem. The algorithm proposed has low computational complexity and strong robustness.