Abstract: In the existed works on scheduling problems,it is usually assumed that machines are always available for simplification.However,preventive maintenance is planned periodically to reduce machines breakdown.For this problem,an optimization model of preventive maintenance and flexible job shop scheduling was established by taking makespan and total cost of preventive maintenance as objectives,and three scheduling strategies were designed for this model.A hyper-heuristics algorithm based on memetic algorithm was developed,which composed of two levels: the search mechanism of memetic algorithm was employed in the high level,while a global search operators pool and a local search operators pool were structured in the low level.An improved adaptive operator selection mechanism based on probability matching was proposed,and a group of experiments were conducted.The results showed that the Preventive Maintenance-and-Scheduling (PAS) scheduling strategy outperformed the others.Furthermore,the service time based model was integrated in PAS strategy,which could reduce the makespan and the total cost of preventive maintenance.

Key words: production scheduling, preventive maintenance, hyper-heuristics algorithm, memetic algorithm, integrated scheduling

摘要： 鉴于传统车间调度通常认为机器始终处于可用状态而有悖于实际生产环境的不确定性,考虑机器使用过程中需要周期性的进行预防性维修的情况,以最大完工时间和预防性维修总成本为目标,建立了机器预防性维修和柔性作业车间调度的集成优化模型。针对该模型设计了年龄模型下的3种不同的集成策略,并开发了一种超启发式文化基因算法,算法采用两层结构,顶层采用文化基因算法的搜索机制,底层是全局搜索算子库和局部搜索算子库,采用基于概率的改进的自适应算子选择机制。实验表明,该算法可以有效求解生产调度与预维修集成优化问题。通过对比可知,同步集成策略表现最优。将役龄模型应用于同步集成策略中,进一步优化了同步集成调度策略,在保证机器可靠性的前提下降低了最大完成时间和预防性维修总成本。

关键词: 生产调度, 预防性维修, 超启发式算法, 文化基因算法, 集成调度