Minimizing total flow time under uncertainty using optimality and stability boxes

Abstract

In this chapter, we apply the stability method to the scheduling problem under un- certain (interval) processing times. A set of n jobs has to be scheduled on a single machine to minimize the weighted sum of the job completion times. The processing time pi of each job Ji, i = 1, 2, . . . , n, is not known before scheduling. The factual time pi can take any real value between the lower bound and the upper bound, which are only known before scheduling. The applied stability approach combines a stabil- ity analysis, a multi-stage decision framework, and a solution concept of a minimal dominant set of the job permutations.