Paper Info
Title
Scheduling nonpreemptive jobs on parallel machines subject to exponential unrecoverable interruptions.
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. The problem of scheduling jobs on parallel machines with unrecoverable interruptions is addressed.The problem is shown to be NP-hard and a characterization of a polyno- mially solvable special case is given.An exact pseudopolynomial algorithm and a heuristic algorithm are pro-posed.A combinatorial upper bound has been presented.Experimental results show the effectiveness of the heuristic approach.
Year
DOI
Venue
2017
10.1016/j.cor.2016.10.013
Computers & OR
Keywords
Field
DocType
Unrecoverable interruptions,Parallel machines scheduling,NP-hardness,Exact and heuristic algorithms
Mathematical optimization,Heuristic,Exact algorithm,Heuristic (computer science),Scheduling (computing),Upper and lower bounds,Computer science,Real-time computing,Exponential distribution,Throughput,Special case
Journal
Volume
Issue
ISSN
79
C
0305-0548
Citations 
PageRank 
References 
0
0.34
9
Authors
3
Name
Order
Citations
PageRank
Alessandro Agnetis140830.67
Paolo Detti214419.55
P. Martineau3363.30