2014/12/13 by Maciej Drwal, Drwal, Maciej, Roman Rischke +1
Decision Sciences · Computer Science · #Risk and Portfolio Optimization #Optimization and Search Problems #Advanced Bandit Algorithms Research
paper · pdf · doi:10.48550/arxiv.1412.4273
In this paper, we consider the problem of scheduling jobs on parallel\nidentical machines, where the processing times of jobs are uncertain: only\ninterval bounds of processing times are known. The optimality criterion of a\nschedule is the total completion time. In order to cope with the uncertainty,\nwe consider the maximum regret objective and we seek a schedule that performs\nwell under all possible instantiations of processing times. Although the\ndeterministic version of the considered problem is solvable in polynomial time,\nthe minmax regret version is known to be weakly NP-hard even for a single\nmachine, and strongly NP-hard for parallel unrelated machines. In this paper,\nwe show that the problem is strongly NP-hard also in the case of parallel\nidentical machines.\n