The optimality box in uncertain data for minimizing the sum of the weighted completion times of the given jobs / Yuri N. Sotskov, Tsung-Chyan Lai, Natalia G. Egorova, Frank Werner
Download311.16 KB
The optimality box in uncertain data for minimizing the sum of the weighted completion times of the given jobs Discovery
887738605
URN
urn:nbn:de:gbv:3:2-72561
DOI
ISBN
ISSN
Koordinaten
Skalierung
Beiträger
Körperschaft
Erschienen
[Magdeburg] : [Otto-von-Guericke-Universität Magdeburg, Fakultät für Mathematik], January 23, 2017
Umfang
1 Online-Ressource (23 Seiten = 0,3 MB) : Diagramme
Ausgabevermerk
Sprache
eng
Anmerkungen
Unterschiede zwischen dem gedruckten Dokument und der elektronischen Ressource können nicht ausgeschlossen werden
Inhaltliche Zusammenfassung
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.
Schriftenreihe
Preprints ; 2017, 01 ppn:622944983