基于两种周期维护类型和序列准备时间的单机调度

Single machine scheduling based on two types of periodic maintenance andsequence-dependent setup times

为了更好地提高客户满意度以及更高效地进行生产调度和设备维护,研究具有序列准备时间和两种周期维护类型的单机调度问题.首先通过不同预防性维护效果定义两种周期维护类型,同时考虑序列准备时间,以最小化总延误为目标建立混合整数规划模型;然后通过分析模型结构得到有效不等式提高模型求解效率;接着设计高效的多起点算法进行求解,为了避免算法陷入局部最优,设计5种局部搜索算子进行搜索;最后通过仿真实验验证模型和算法的有效性,并对参数进行灵敏度分析.研究结果表明,在不同种维护类型之间进行权衡可以降低总延误,两种周期维护类型的总延误优于单一周期维护类型.研究结果可以为制造企业实际制定调度和维护方案时提供决策支持.

To improve customer satisfaction and to perform production scheduling and equipment maintenance more efficiently,a single-machine scheduling problem with sequence-dependent setup times and two types of periodic maintenance is tackled.Firstly,two types of periodic maintenance are defined by different preventive maintenance effects,and a mixed integer programming model is formulated to minimize the total tardiness by taking into account the sequence-dependent setup times.Then,the valid inequalities are proposed to improve the model efficiency by analyzing the model structure.Then,an efficient multi-start algorithm is also designed for the solution,and five local search operators are designed for the search to avoid the algorithm falling into local optimum.Finally,computational experiments are performed to evaluate the effectiveness of the model and algorithm,as well as to analyze the sensitivity of parameters.The result shows that the trade-off between different maintenance types can reduce the total tardiness,and the total tardiness of two types of periodic maintenance is better than that of a single type of periodic maintenance.The result can provide decision support for manufacturing enterprises to make scheduling and maintenance plans.