基于预防维护的单机调度问题  

Single-machine scheduling problem with preventative maintenance activities

作　　者：吴慧 王冰[1] WU Hui;WANG Bing(School of Mechatronic Engineering and Automation,Shanghai University,Shanghai 200444,China;Science and Information College,Qingdao Agricultural University,Qingdao 266109,China)

机构地区：[1]上海大学机电工程与自动化学院,上海200444 [2]青岛农业大学理学与信息科学学院,山东青岛266109

出　　处：《控制与决策》2021年第2期395-402,共8页Control and Decision

摘　　要：在两种维护约束下,研究完工时间之和最小化的单机调度问题.第1种维护约束是,固定周期预防维护;第2种维护约束是,机器工作期间可连续加工的最大工件个数受限.对于这种带有约束的调度问题,根据问题的规模,采用4种方法进行求解.针对小规模问题,建立一个二值整数规划模型,并根据最优解的特性制定剪枝规则,进而给出分支定界算法.针对中、大规模问题,采用遗传算法进行求解,为缓解遗传算法中常见的早熟问题,对变异算子进行改进,采用动态变异方法,提出动态遗传算法.最后通过仿真实验对各种算法进行性能评估.This paper deals with a single-machine scheduling problem with the objective to minimize the total completion time of jobs subjects to two maintenance constraints.The first maintenance constraint is that the machine will be stopped for maintenance after a periodic interval,and the second one is the constraint on the maximum number of jobs continuously processed.Four methods are used to solve the constrained single-machine scheduling problem.To solve small-scale problems,one binary integer programming model is first proposed,then pruning rules are formulated according to the properties of optimal solutions,and the corresponding branch and bound algorithm is proposed.The genetic algorithm is used to find the near-optimal solutions for medium-scale and large-scale problems.Dynamic genetic algorithm is proposed by adopting the dynamic mutation method to alleviate the precocity problem which is a phenomenon that cannot be ignored in the genetic algorithm.Finally,computational experiments are carried out to evaluate the performance of the proposed algorithms.

关 键 词：单机调度 预防维护 二值整数规划 分支定界算法 遗传算法 动态遗传算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]