Zurück zu den Preprints des Jahres 2017


2017-01

The optimality box in uncertain data for minimizing the sum of the weighted completion times of the given jobs

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


Series: 2017-01, Preprints

MSC:
90B36 Scheduling theory, stochastic
90C31 Sensitivity, stability, parametric optimization
68W40 Analysis of algorithms

Abstract:
An uncertain single-machine scheduling problem is considered, where the processing time of a job can take any real value from a given segment. The criterion is to minimize the total weighted completion time of the n jobs, a weight being associated with each given job. We use the optimality box as a stability measure of the optimal schedule and derive an O(n)-algorithm for
calculating the optimality box for a fixed permutation of the given jobs. We investigate properties of the optimality box using blocks of the jobs. If each job belongs to a single block, then the largest optimality box may be constructed in O(n log n) time. For the general case, we apply dynamic programming for constructing a job permutation with the largest optimality box.
The computational results for finding a permutation with the largest optimality box show that such a permutation is close to an optimal one, which can be determined after completing the jobs when their processing times became known.

Keywords:
Single-machine scheduling, Uncertain processing times, Optimality box