Optimization of schedule robustness and stability under random machine breakdowns and processing time variability
Optimization of schedule robustness and stability under random machine breakdowns and processing time variability
复制标题
DOI：
10.1080/07408170903171035
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
Selcuk Goren;I. Sabuncuoglu
中科院分区：
文献类型：
--
作者：
Selcuk Goren;I. Sabuncuoglu
在实践中，调度系统在高度动态的操作环境中具有相当大的不确定性。在调度过程中应对不确定性的能力正成为一个日益重要的问题。本文采用一种主动调度方法来研究具有两种不确定性来源的调度问题：加工时间变异性和机器故障。定义了两个鲁棒性度量（期望总流动时间和期望总延迟时间）和三个稳定性度量（作业完成时间的平方和绝对差和实现完成时间的方差和）。确定了易于优化措施的特殊情况。提出了其中一种鲁棒性度量的优势规则和两个下界，并将其用于分支定界算法中以精确地解决该问题。同时提出了一种光束搜索启发式算法来解决所有五种度量的大问题。计算结果表明，波束搜索启发式算法能够生成与最优目标函数值（通过分支定界算法获得）的平均偏差很小的鲁棒调度，并且在所有五个度量指标上的性能都明显优于文献中可用的许多启发式算法。
In practice, scheduling systems are subject to considerable uncertainty in highly dynamic operating environments. The ability to cope with uncertainty in the scheduling process is becoming an increasingly important issue. This paper takes a proactive scheduling approach to study scheduling problems with two sources of uncertainty: processing time variability and machine breakdowns. Two robustness (expected total flow time and expected total tardiness) and three stability (the sum of the squared and absolute differences of the job completion times and the sum of the variances of the realized completion times) measures are defined. Special cases for which the measures can be easily optimized are identified. A dominance rule and two lower bounds for one of the robustness measures are developed and subseqently used in a branch-and-bound algorithm to solve the problem exactly. A beam search heuristic is also proposed to solve large problems for all five measures. The computational results show that the beam search heuristic is capable of generating robust schedules with little average deviation from the optimal objective function value (obtained via the branch-and-bound algorithm) and it performs significantly better than a number of heuristics available in the literature for all five measures.