Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959165 | Computers & Operations Research | 2017 | 10 Pages |
Abstract
In this paper we consider the problem of scheduling n independent jobs on m parallel machines. If, while a machine is processing a job, a failure (unrecoverable interruption) occurs, the current job as well as subsequently scheduled jobs on that machine cannot be performed, and hence do not contribute to the overall revenue or throughput. The objective is to maximize the expected amount of work done before an interruption occurs. In this paper, we investigate the problem when failures are exponentially distributed. We show that the problem is NP-hard, and characterize a polynomially solvable special case. We then propose both an exact algorithm having pseudopolynomial complexity and a heuristic algorithm. A combinatorial upper bound is also proposed for the problem. Experimental results show the effectiveness of the heuristic approach.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Alessandro Agnetis, Paolo Detti, Patrick Martineau,