Abstract: For a two-stage hybrid flow shop system with parallel machines at each stage,an optimization model jointed with job and maintenance scheduling was established to minimize the maximum completion time while introducing periodic machine maintenances in given time windows.Based on minimizing slack time of machine and LPT rule,a constructive algorithm LPT-MFT was proposed.The results of the numerical experiments under different scales of problems showed that the above proposed algorithms had better performance than the ones based on LPT or Johnson rules.The decisions made by the joint model demonstrated as well the superiority comparing with traditional method in which the production and maintenance scheduling decisions were separately made.

Key words: hybrid flow shop, preventive maintenance, integer linear programming, constructive algorithm

摘要： 针对两阶段且每阶段都存在并行机的混合流水线系统,考虑设备具有时间窗的周期性维护需求,以最小化最大完成时间为调度指标,建立调度与维护的联合优化模型,提出了基于最长加工时间规则和最小化机器松弛时间的构造式算法。对不同规模下的问题进行数值验证,并与基于LPT、Johnson规则的构造式算法进行对比,结果表明所提算法具有更优的性能。利用遗传算法对调度解进行搜索优化,并与传统的生产与维护独立决策的结果相比较,证明了生产调度与维护联合决策模型是有效的,更加符合生产车间的实际调度背景。

关键词: 混合流水线, 预防性维护, 整数规划, 构造式算法