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.

Agnetis, A., Detti, P., Martineau, P. (2017). Scheduling nonpreemptive jobs on parallel machines subject to exponential unrecoverable interruptions. COMPUTERS & OPERATIONS RESEARCH, 79, 109-118 [10.1016/j.cor.2016.10.013].

Scheduling nonpreemptive jobs on parallel machines subject to exponential unrecoverable interruptions

Agnetis, Alessandro;Detti, Paolo;
2017-01-01

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.
2017
Agnetis, A., Detti, P., Martineau, P. (2017). Scheduling nonpreemptive jobs on parallel machines subject to exponential unrecoverable interruptions. COMPUTERS & OPERATIONS RESEARCH, 79, 109-118 [10.1016/j.cor.2016.10.013].
File in questo prodotto:
File Dimensione Formato  
2017CAOR.pdf

non disponibili

Descrizione: Articolo
Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 839.2 kB
Formato Adobe PDF
839.2 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/998904