Abstract: Aiming at the robustness measurement of job-shop scheduling under random machine breakdowns,according to the internal relationship among the scheduling scheme structure,the probability and downtime of machine breakdown,and the scheduling robustness,an alternative measurement method based on operation fault propagation was proposed.This method maped the machine breakdowns to the level of operation,and the propagation mechanism of operation fault between operations was analyzed.Considering the influence of operation forward correlation and its own fault,the expected completion time of the operation was solved,and then the robustness of scheduling was evaluated.Experiments of twenty-five benchmark JSPs were provided.Results showed that the proposed approach could evaluate the scheduling robustness accurately and quickly.Comparison was also made with the state-of-the-art surrogate robustness measures,which confirmed the superiority and credibly of the proposed measure for schedule robustness measurement.

Key words: random machine breakdowns, job shop scheduling, robustness measure, operation relation

摘要： 针对随机机器故障环境下作业车间调度鲁棒性测度问题,根据调度方案结构、机器故障概率、维修时间与调度鲁棒性的内在关系,提出一种基于工序故障影响传播的替代性测度方法。该方法将机器故障映射到工序层面,分析了工序关联下故障影响的传播机理,综合工序关联工序及自身故障的影响,给出了工序期望完工时间的求解方法,实现了对调度鲁棒性的评估。采用25个标准案例进行验证,结果表明,所提方法能准确、快速地评估调度方案的鲁棒性,并通过与3种替代测度方法的对比,验证了所提方法的优越性和可靠性。

关键词: 随机机器故障, 作业车间调度, 鲁棒性测度, 工序关系