The Stability Box for Minimizing Total Weighted Flow Time under Uncertain Data

Abstract

We consider an uncertain single-machine scheduling problem, in which the processing time of a job can take any real value from a given closed interval. The criterion is to minimize the sum of weighted completion times of the n jobs, a weight being associated with each job. For a job permutation, we study the stability box, which is a subset of the stability region. We derive an O(n log n) algorithm for constructing a job permutation with the largest dimension and volume of a stability box. The efficiency of such a permutation is demonstrated via a simulation on a set of randomly generated instances with 1000 ≤ n ≤ 2000. If several permutations have the largest dimension and volume of a stability box, the developed algorithm selects one of them due to a mid-point heuristic.