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

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.