A bi-criteria approach to scheduling in the face of uncertainty: Considering robustness and stability simultaneously

Abstract

It is possible to scrutinize impacts of uncertainty on schedules from two different perspectives. The flrst one has to do with the fact that schedules are required to main- tain high performance in the face of uncertainty. In other words, it is desired that their performances are insensitive to negative impacts of disruptions. We refer to this view- point as the robustness perspective. The second viewpoint is about another quality: when a schedule is executed in the shop floor, the realized schedule is required not to deviate much from its initial version. This is because many activities besides pro- duction are planned based on the production schedule. It is important that unforeseen disruptions affect the plans for these activities as little as possible. We refer to this viewpoint as the stability perspective. Even though a considerable body of literature has emerged on hedging schedules against the negative effects of unforeseen disrup- tions in the last two decades, few studies address the problem of scheduling under uncertainty from both the robustness and the stability perspectives at the same time. The nature of the relation between robustness and stability, the trade-off between them, the circumstances under which they conflict or reconcile need to be thoroughly inves- tigated. To this end, we propose a bi-criteria approach to simultaneously investigate the robustness and stability of production schedules. We consider proactive schedul- ing in a single machine environment with random processing times. We use the total expected flow time and the total variance of job completion times as the robustness and stability measures, respectively. The proposed o-constraint variants are exact methods to generate the set of all Pareto-optimal schedules. We also develop an algorithm to generate a flxed number (set by the decision-maker) of near-Pareto-optimal schedules to deflne the characteristics and the shape of the trade-off curve without generating the entire Pareto set. Our computational experiments indicate that the proposed algorithms are efflcient.