Abstract: In some manufacturing scenarios, the transport time of jobs between different machines has great affects on the total tardiness of job-shop scheduling. Based on this, the model of the flexible job-shop scheduling problem with the minimum total tardiness is extended in this paper. According to the complexity of this model, a hybrid algorithm combining particle swarm optimization algorithm with genetic algorithm is proposed for solving this model. In initialization, the machines with the shortest processing time and transport time are given priority to being selected at a certain probability. Meanwhile, the most frequently scheduled machines should be excluded. Then excellent individuals are selected while the diversity of the swarm is kept. The crossover probability and mutation probability are adjusted dynamically with linear functions, leading the swarm to search with different strength at different stages. Particle swarm optimization algorithm is used to local search, which compensates the weakness of insufficient local search in genetic algorithm. Finally, the superiority of the proposed method is verified by solving flexible job-shop scheduling cases with the transport time at different levels. The total tardiness obtained by the hybrid algorithm proposed by this paper is obviously shorter than that of other algorithms.

Key words: flexible job-shop scheduling problem, total tardiness, transport time, hybrid algorithm

摘要： 在某些生产制造场景中,工件在不同机器间的传输时间对车间调度的总拖期具有重要影响,本文基于此扩展了总拖期最小的柔性作业车间调度模型。针对问题模型的复杂性,采用粒子群优化算法和遗传算法的混合算法进行求解。在初始化过程以一定概率优选加工时间和传输时间短的机器并排除调度频繁的机器,使种群在保持多样性的前提下尽量选择优化结果好的个体;采用线性调整的方式动态改变交叉概率和变异概率的值,使种群在遗传算法的不同阶段具有不同的搜索强度;采用粒子群优化算法进行局部搜索,弥补了遗传算法局部搜索能力的不足。最后采用本文方法和其他方法求解柔性作业车间调度问题实例,并对比不同水平层次传输时间下的总拖期,验证了本文方法的有效性。

关键词: 柔性作业车间调度问题, 总拖期, 传输时间, 混合算法