Robust scheduling to hedge against processing time uncertainty in single-stage production
Robust scheduling to hedge against processing time uncertainty in single-stage production
复制标题
DOI：
10.1287/mnsc.41.2.363
复制
发表时间：
1995-02
影响因子：
5.4
通讯作者：
R. L. Daniels;P. Kouvelis
中科院分区：
文献类型：
--
作者：
R. L. Daniels;P. Kouvelis
面临显著加工时间不确定性的调度人员经常发现，相对于确定性或随机调度模型是最优的调度方案，在根据实际加工时间进行评估时，其性能相当差。在这些环境中，调度稳健性的概念，即确定在所有作业加工时间的潜在实现情况下，与相应最优解相比具有最佳最差情况性能的调度方案，是调度选择的更合适指南。在本文中，我们针对具有不确定或可变加工时间的调度情况形式化了稳健调度概念。为了说明稳健调度问题解决方法的发展，我们考虑单机环境，其中关注的性能标准是所有作业的总流程时间。我们定义了两种调度稳健性度量，构建了稳健调度问题，确定了其复杂性，描述了最优调度的性质，并提出了精确和启发式求解程序。大量计算结果被报道以证明所提出求解程序的效率和有效性。
Schedulers confronted with significant processing time uncertainty often discover that a schedule which is optimal with respect to a deterministic or stochastic scheduling model yields quite poor performance when evaluated relative to the actual processing times. In these environments, the notion of schedule robustness, i.e., determining the schedule with the best worst-case performance compared to the corresponding optimal solution over all potential realizations of job processing times, is a more appropriate guide to schedule selection. In this paper, we formalize the robust scheduling concept for scheduling situations with uncertain or variable processing times. To illustrate the development of solution approaches for a robust scheduling problem, we consider a single-machine environment where the performance criterion of interest is the total flow time over all jobs. We define two measures of schedule robustness, formulate the robust scheduling problem, establish its complexity, describe properties of the optimal schedule, and present exact and heuristic solution procedures. Extensive computational results are reported to demonstrate the efficiency and effectiveness of the proposed solution procedures.