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
Anzeigen / Download311.16 KB
Discovery
887738605
URN
urn:nbn:de:gbv:3:2-72561
DOI
ISBN
ISSN
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