Scheduling nonpreemptive jobs on parallel machines subject to exponential unrecoverable interruptions. (March 2017)

• Record Type: Journal Article
• Authors: Agnetis, Alessandro; Detti, Paolo; Martineau, Patrick
• Is Part Of: Computers & operations research. Volume 79(2017)
• Page Start: 109
• Page End: 118
• Publication Date: 2017-03
• Subjects: Unrecoverable interruptions -- Parallel machines scheduling -- NP-hardness -- Exact and heuristic algorithms; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.10.013
• Languages: English
• ISSNs: 0305-0548

Abstract

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. Highlights: 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.