考虑模糊质检时间的柔性作业车间动态调度问题

Flexible job shop dynamic scheduling problem withfuzzy quality control time

为解决更符合现实情形的模糊质检时间柔性作业车间动态调度问题,以最小化完工时间为目标,立足紧急插单、机器在空载运行时发生故障和机器在加工工件时发生故障的三种故障情形,建立了带模糊质检时间的机器故障、紧急插单重调度模型。设计了基于元胞自动机邻域搜索和随机重启爬坡算法的改进遗传算法求解模型,即针对车间调度问题中存在的订单排序和机器选择双决策问题特征,设计包含工序码和机器码的双层编码方案,并基于遗传算法思想对工序码和机器码设计相应的交叉、变异等遗传操作。同时,将遗传操作应用于基于元胞自动机的邻域搜索算法框架中以增强算法全局搜索能力,整合基于关键工序的随机重启爬坡算法以提高算法局部开发能力。实验选取10个柔性车间调度算例验证了所提算法的有效性,同时,测试1个模糊质检时间柔性车间调度算例验证了模型的有效性。另外,实验也测试了不同故障场景,得出该动态调度方法优于实际场景中常使用的“工件后移”调度策略。

To solve the flexible job shop dynamic scheduling problem with fuzzy quality control time,which is more realistic,this paper established two rescheduling models for machine breakdown and urgent order insertion with the objective of minimizing completion time.Two models were for three failure scenarios:emergency order insertion,machine failure during no-load operation,and machine failure during work-piece processing.To solve this model,this paper designed a novel genetic-neighborhood search algorithm that integrated cellular-automata-based neighborhood search and random restart hill-climbing.Aiming at the characteristics of dual sub-decisions involving order sequencing and machine selection,this paper designed a two-layer coding scheme including process code and machine code,and designed corresponding genetic operations such as crossover and mutation for them.After that,this paper applied the genetic operations into the framework of cellular-automata-based neighborhood search to enhance the algorithm’s global search capability,and integrated the random restart hill-climbing algorithm based on key operations to improve the algorithm’s local development capability.Experiments tested 10 flexible job shop scheduling instances and one flexible job shop scheduling instance with fuzzy quality control time to verify the effectiveness of the proposed algorithm and models.In addition,the test results under different failure scenarios show the proposed method outperforms the backward-based scheduling strategy used in practice.