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.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.
https://hdl.handle.net/11365/998904