Otto-von-Guericke-Universität Magdeburg



Measures of Problem Uncertainty for Total Weighted Flow Time Scheduling on a Single Machine

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


Preprint series: 10-17, Preprints

90B35 Scheduling theory, See also {68M20}
49K40 Sensitivity of optimal solutions in the presence of perturbations


Abstract: A single-machine scheduling problem is investigated under the assumption that the processing time of a job can take any real value from a given closed interval. The criterion is to minimize the total weighted completion time for a set of given jobs. As a measure of uncertainty for such a scheduling problem, it is reasonable to consider the cardinality of a minimal dominant set of job permutations containing an optimal permutation for each possible realization of the job processing times. We show that a minimal dominant set may be uniquely determined and demonstrate how to select a suitable solution method for the individual problem using the value of an uncertainty measure.

Keywords: Single-machine scheduling; Total weighted flow time; Uncertain processing times; Measure of uncertainty

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