基于组搜索算法的复杂零等待作业车间调度问题研究

As one of the hardest scheduling problems generally acknowledged by academic and industrial circle, job shop scheduling problem widely exists in the process of production planning and scheduling from manufacturing and process industries. The current theories and methods are mostly oriented to the idealized classical job shop scheduling problem, and the research on job shop scheduling with the no-wait constraint is far from enough. This project will focus on solving the no-wait job shop scheduling problem and its counterpart with flexible production environment where parallel processing machines exist. We will borrow the idea of decentralized coordination from the theory of large scale system, and decompose the corresponding problem into a timetabling sub-problem and a sequencing sub-problem. Based on the problem-decomposing strategy, we will study the feasible timetabling algorithms to transfer job sequences into effective schedules. Besides, the novel group search optimizer will be adopted to search optimal or suboptimal sequences. The group search optimizer based on discrete coding will be developed for the scheduling problems and the operators for producers, scroungers and rangers will be designed. Lastly, the performance of group search optimizer for solving the no-wait job shop scheduling problem will be analyzed and evaluated by statistical methods. This project will offer a new intelligent method for solving the complex no-wait job shop scheduling by applying the group search optimizer originally proposed for continuous optimization to discrete production scheduling problem.

作业车间调度问题广泛存在于制造业和流程工业企业生产计划和生产调度环节中，是学术界和工业界公认的最为困难的调度问题之一。目前已有的理论和方法大部分针对理想化的经典作业车间调度问题，对零等待约束相关的作业车间调度研究还比较有限。本项目考虑零等待约束下的作业车间调度问题，并进一步考虑具有并行加工机器的柔性零等待作业车间调度问题，借鉴大系统理论分散协调的思想，将相应的调度问题分解为时间窗问题和排列问题两个子问题进行求解。基于问题分解策略，一方面研究可行的时间窗算法，将工件排列转换为有效的调度方案；另一方面采用新型的组搜索算法搜索最优或次优排列，提出针对该调度问题的离散编码组搜索算法，设计组搜索算法的发现者、追随者和巡逻者操作，最后通过统计学方法对组搜索算法的求解性能进行综合分析与评价。本项目将针对连续优化问题的组搜索算法应用于离散的生产调度问题，为复杂零等待作业车间调度问题的求解提供新的智能方法。

作业车间调度问题广泛存在于化学工业、食品工业、钢铁生产、生物制药、水泥生产等制造业和流程工业过程中，是工业工程和运筹学领域面临的NP难问题。随着近年来人工智能研究的兴起，智能优化方法逐渐成为解决这类问题的热门研究方法之一。本项目分析零等待约束下的作业车间调度问题的特性，并设计组搜索等群智能算法进行有效求解。我们已经按计划开展了研究工作，分别对零等待约束下的流水车间调度问题、多产品间歇过程的零等待约束多目标调度问题、阻塞情况下的流水车间多目标调度问题、缓冲区大小有限的流水车间优化问题、零等待约束下作业车间调度问题，进行了相应的建模和算法求解。考虑零等待约束下的流水车间调度问题，以制造期为单目标，将量子编码和协同遗传算法相融合，设计了一种协同进化量子遗传算法，以制造期和总流水时间为双目标，提出了一种混合差分进化算法进行求解，均取得了较好效果。考虑多产品间歇过程的零等待约束问题，研究了其多目标调度方法，提出了一种离散组搜索进化算法进行有效求解。针对阻塞情况下的流水车间多目标调度问题，提出了一种多目标离散差分进化算法和一种多目标离散组搜索算法进行有效求解。针对缓冲区大小有限的流水车间优化问题，考虑了该问题的总流水时间的最小化问题， 提出了一种增强的离散人工蜂群算法进行有效求解。针对零等待约束下作业车间调度问题，将该问题分解为时间窗问题和排列问题两个子问题，研究了多个时间窗算法，并将时间窗算法和组搜索算法相结合，设计了混合组搜索优化算法进行有效求解；进一步地，研究了插入邻域搜索方法，给出了降低计算量的加速方法，并引入迭代贪婪算法进行求解，取得了显著效果。本项目将新型智能优化方法引入到复杂车间调度问题求解中，对新型智能算法在调度领域的应用探索具有重要意义，为制造业和流程工业的管控一体化奠定了一定的基础。