https://libeldoc.bsuir.by/handle/123456789/27966
Title: | The optimality box in uncertain data for minimizing the sum of the weighted completion times of the given jobs |
Authors: | Tsung-Chyan Lai Sotskov, Y. N. Egorova, N. G. Werner, F. |
Keywords: | публикации ученых;scheduling;uncertainty;single-machine problem;uncertain durations;optimality box |
Issue Date: | 2017 |
Publisher: | Otto-von-Guericke-Universität |
Citation: | The optimality box in uncertain data for minimizing the sum of the weighted completion times of the given jobs / Tsung-Chyan Lai [et al.] // International Journal of Production Research. – 2017. – Volume 56, Issue 19. – P. 6336–6362. |
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. |
URI: | https://libeldoc.bsuir.by/handle/123456789/27966 |
DOI: | https://doi.org/10.1080/00207543.2017.1398426 |
Appears in Collections: | Публикации в зарубежных изданиях |
File | Description | Size | Format | |
---|---|---|---|---|
Sotskov_The.pdf | 127.79 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.