Abstract: To improve the quality of initial population of the genetic algorithm for the Flexible Job-shop Scheduling Problem (FJSP) solution,a machine selection initialization method based on limit scheduling completion time (Climit) minimization was proposed,in which the Climit was equal to the maximum of machine load and job process time.The double chains structure which included machine selection chain and operation sequence chain was used to encode.While initializing machine selection chains,global selection and local selection were adopted macroscopically to optimize maximum machine load and maximum job process time respectively;microscopically,the random sequence was used to select the operation.On the basis of considering the optional machine load for selecting machine,the process time was further compared,and both maximum machine load and maximum job process time were optimized.The effectiveness of proposed method was verified by analyzing the machine selection results of benchmarks and solving it based on genetic algorithm.

Key words: flexible job shop scheduling, machine selection, initial solution, genetic algorithms

摘要： 为提高柔性作业车间调度问题求解的遗传算法的初始群体质量,通过分析机器选择与调度完工时间的关系,提出一种基于极限调度完工时间(Climit)最小化的机器选择初始化方法。采用机器选择链和工序顺序链双链结构编码,初始化机器选择链时,宏观上采用全局选择和局部选择分别侧重于实现对最大机器负荷和最大工件加工时间指标的优化;微观上采用随机次序取代工件工艺顺序选择工序,在考虑可选机器负荷的基础上进一步比较加工时间选择机器,兼顾最大机器负荷和最大工件加工时间指标的优化。对基准算例机器选择结果进行分析和基于遗传算法求解,验证了所提方法的有效性。

关键词: 柔性作业车间调度, 机器选择, 初始群体, 遗传算法