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

What is it about?

This paper considers a single machine scheduling problem, in which the processing time of a job may take any value from a given interval. The objective is the minimization of the sum of the weighted completion times. For a job permutation, we investigate the stability box which is a subset of the stability region. A polynomial algorithm is given for constructing a job permutation with the largest dimension and volume of a stability box. Computational results are given for instances with up to 2000 jobs.

Featured Image