并行机调度问题的最优公共交货期和最优调度

Optimal common due date and optimal job scheduling in parallel machine scheduling problem

现有的提前／拖后调度问题主要针对单机情况，且大多采用启发式方法。为了有效地解决带有待定公共交货期的并行机提前／拖后优化调度问题，提出了一种分段编码的遗传算法，使遗传编码能同时反映调度方案和公共交货期，并对初始种群产生、交叉和变异方法作了研究。计算实例表明了该遗传算法有很好的性能，所得解的质量优于启发式算法。

The study on earliness/tarliness scheduling problem is focused on single machine situation and main methods proposed are heuristic procedures. In order to solve parallel machine earliness/tardiness scheduling problem with undetermined common due date effectively, a kind of genetic algorithm based on sectional coding was presented, the genetic code could reflect the scheduling policy and common due date simultaneously, the methods of the generation of the initial population, crossover and mutation were researched. Computational results show that the genetic algorithm proposed has good performance, and that the quality of its solution is advantageous over heuristic procedure, and that it is suitable for large scale parallel machine earliness/tarliness optimization scheduling problem.