The optimality box in uncertain data for minimising the sum of the weighted job completion times. Issue 19 (2nd October 2018)

• Record Type: Journal Article
• Authors: Lai, Tsung-Chyan; Sotskov, Yuri N.; Egorova, Natalja G.; Werner, Frank
• Is Part Of: International journal of production research. Volume 56:Issue 19(2018)
• Page Start: 6336
• Page End: 6362
• Publication Date: 2018-10-02
• Subjects: scheduling -- uncertainty -- single-machine problem -- uncertain durations -- optimality box; Factory management -- Periodicals; 658.57
• DOI: 10.1080/00207543.2017.1398426
• Languages: English
• ISSNs: 0020-7543

Abstract

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 minimise 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 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.