The optimality box in uncertain data for minimising the sum of the weighted job completion times

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.

Keywords:

• scheduling
• uncertainty
• single-machine problem
• uncertain durations
• optimality box

Acknowledgements

The authors are grateful to the anonymous referees for their useful suggestions on an earlier draft of this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The first and second authors was supported by the Ministry of Science and Technology, Taiwan [grant number MST 104-2410-H-002-118].