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)