Otto-von-Guericke-Universität Magdeburg



by Sotskov, Y.N.; Egorova, N.G.; Lai, T.-C.; Werner, F.


Preprint series: 11-12, Preprints

90B35 Scheduling theory, See also {68M20}
90C31 Sensitivity, stability, parametric optimization


Abstract: We consider a single-machine scheduling problem, in which the processing time of a job can take any value from a given segment. The criterion is to minimize the sum of weighted completion times of the $n$ jobs, a positive weight being associated with a 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 volume and dimension of a stability box. The efficiency of a permutation with the largest dimension and volume of a stability box is demonstrated via a simulation on a set of randomly generated instances with $1000 \leq n \leq 2000$. If several permutations have the largest volume of a stability box, the developed algorithm selects one of them due to one of three simple heuristics: a lower-point heuristic, an upper-point heuristic or a mid-point heuristic.

Keywords: Single-machine scheduling; Uncertain data; Total weighted completion time; Stability analysis

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 10.02.2016 - Ansprechpartner: Pierre Krenzlin