Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142140 | Operations Research Letters | 2016 | 5 Pages |
Abstract
We consider the problem of scheduling jobs on parallel identical machines, where only interval bounds of processing times of jobs are known. The optimality criterion of a schedule is the total completion time. In order to cope with the uncertainty, we consider the maximum regret objective and seek a schedule that performs well under all possible instantiations of processing times. We show how to compute the maximum regret, and prove that its minimization is strongly NP-hard.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Maciej Drwal, Roman Rischke,