What is it about?

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 a polynomial 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.

Featured Image

Why is it important?

Scheduling problems with uncertain data are relevant to tackle practical problems.

Perspectives

I hope that this article will stimulate further research in the field of scheduling with interval processing times.

Prof. Dr. Frank Werner
Otto von Guericke Universitat Magdeburg

Read the Original

This page is a summary of: The optimality box in uncertain data for minimising the sum of the weighted job completion times, International Journal of Production Research, November 2017, Taylor & Francis,
DOI: 10.1080/00207543.2017.1398426.
You can read the full text:

Read

Contributors

The following have contributed to this page