Abstract: Aiming at the flexible job shop scheduling problem of fuzzy delivery,the mathematical model was established with the minimum completion time,minimum total cost and minimum penalty as the targets,and the improved double chains quantum genetic algorithm was proposed.Through analyzing the characteristic of the fuzzy delivery in actual production,the earliness/tardiness penalty coefficient along with the delivery time changes was designed.For the characteristics of flexible job shop scheduling,the double chains structure coding method and Hadamard mutation strategy based on machine allocation chain and process chain were proposed.To obtain more optimal solution,the non-dominated sorting strategy and crowding distance selection strategy were introduced.The novel method was applied to Kacem example and a mechanical mould job shop scheduling,and the effectiveness of proposed method was verified by comparing with other classical algorithms.

Key words: penalty coefficient, flexible job shop scheduling, double chains structure coding, non-dominated sorting, quantum genetic algorithm

摘要： 针对模糊交货期的柔性作业车间调度问题,以最小化完工时间、最小化总成本和最小化惩罚值为目标,建立问题的数学模型,提出改进的双链量子遗传算法。通过对实际生产交货期的模糊特点进行分析,设计了随交货时间变化的提前/拖期双惩罚系数;针对柔性作业调度问题的特点,提出基于机器分配链和工序链的双链结构编码方法和Hadamard变异策略,并在模糊集合理论的基础上引入对非支配解的优化排序策略和拥挤距离选择策略。将方法应用于Kacem算例和某机械模具车间调度,并与其他经典算法进行比较,验证了所提方法的有效性。

关键词: 惩罚系数, 柔性作业车间调度, 双链结构编码, 非支配解排序, 量子遗传算法