Zurück zu den Preprints des Jahres 2010


2010-02

A Stability Approach for Minimizing Total Weighted Completion Time with Uncertain Data

by Sotskov, Y.N., Egorova, N.G., Werner, F..


Series: 2010-02, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
A single-machine scheduling problem is
investigated provided that the input data are uncertain:
The processing time of a job can take any real value from the
given segment. The criterion is to minimize the total weighted
completion time for the $n$ jobs. As a solution concept to such a
scheduling problem with an uncertain input data, it is reasonable to consider a minimal
dominant set of job permutations containing an optimal
permutation for each possible realization of the job processing
times. To find an optimal or approximate job
permutation to be realized, we look for a permutation with the
largest stability box being a
subset of the stability region. We develop a branch-and-bound
algorithm to construct a permutation with the largest volume of a
stability box. If several permutations have the same volume of a stability box,
we select one of them
due to one of two simple heuristics.
The efficiency of the constructed permutations (how close
they are to a factually optimal permutation) and the efficiency of
the developed software (average CPU-time used for an instance) are
demonstrated on a wide set of randomly generated instances with $5 \leq n \leq 100$.

Keywords:
Scheduling, Single machine problems, Total weighted completion time, Stability, Uncertainty, Interval processing times

This paper was published in:
Automation and Remote Control, Vol. 71, No. 10, 2010, 2038 - 2057 (under the title: Minimizing Total Weighted Completion Time with Uncertain Data: A Stability Approach; Russian version in Avtomatika i Telemekhanika, No. 10., 2010, 26 - 49)