Abstract: In order to solve non-identical parallel machine earliness/tardiness scheduling problem, a hybrid genetic algorithm based on sectional extended permutation-coding scheme was suggested. The coding method could reflect the scheduling policy and common due date simultaneously, and these methods, such as the generation of the initial population, crossover and mutation, were also researched. Considering the requirements of adapting it to this kind of lager scale problem and real-time scheduling, it was parallelly implemented under the mode of master-slave control networks. The computational results show that it is efficient, and is advantageous over heuristic procedures and common genetic algorithms, and has much better parallel characteristics, and is fit for larger scale non-identical parallel machine earliness/tardiness scheduling problem

Key words: parallel machine, parallel genetic algorithm, earliness/tardiness, scheduling problem

摘要： 为有效地解决带有公共交货期的非等同并行多机提前/拖后调度问题，设计了一种分段扩展排列编码的混合遗传算法，使遗传编码能同时反映调度方案和公共交货期，并对其初始种群产生、交叉和变异方法也进行了研究。同时为了更好地适应调度实时性和解大规模此类问题的需要，基于遗传算法自然并行性特点的基础上，实现了主从式控制网络模式下并行混合遗传算法。计算结果表明，此算法是有效的，优于启发式算法和遗传算法，有着较高的并行性，并能适用于大规模非等同并行多机提前/拖后调度问题

关键词: 并行多机, 并行遗传算法, 提前/拖后, 调度问题