In this paper, we study a scheduling problem with unreliable jobs. Each job is characterized by a success probability and by a reward earned in case of success. In case of failure, the job blocks the machine that is processing it, and the jobs subsequently sequenced on that machine cannot be performed. The objective function is to maximize the expected reward. We address the problem in the case of two parallel machines, and analyze the worst-case performance of a simple list scheduling algorithm. We show that the algorithm provides an approximation ratio of (2 + sqrt(2)) / 4 ≃ 0, 853, and that the bound is tight. We also provide a complexity result concerning the related Total Weighted Discounted Completion Time Problem on parallel machines.

Agnetis, A., Detti, P., Pranzo, M. (2014). The list scheduling algorithm for scheduling unreliable jobs on two parallel machines. DISCRETE APPLIED MATHEMATICS, 165, 2-11 [10.1016/j.dam.2012.09.014].

The list scheduling algorithm for scheduling unreliable jobs on two parallel machines

AGNETIS, ALESSANDRO;DETTI, PAOLO
;
PRANZO, MARCO
2014-01-01

Abstract

In this paper, we study a scheduling problem with unreliable jobs. Each job is characterized by a success probability and by a reward earned in case of success. In case of failure, the job blocks the machine that is processing it, and the jobs subsequently sequenced on that machine cannot be performed. The objective function is to maximize the expected reward. We address the problem in the case of two parallel machines, and analyze the worst-case performance of a simple list scheduling algorithm. We show that the algorithm provides an approximation ratio of (2 + sqrt(2)) / 4 ≃ 0, 853, and that the bound is tight. We also provide a complexity result concerning the related Total Weighted Discounted Completion Time Problem on parallel machines.
2014
Agnetis, A., Detti, P., Pranzo, M. (2014). The list scheduling algorithm for scheduling unreliable jobs on two parallel machines. DISCRETE APPLIED MATHEMATICS, 165, 2-11 [10.1016/j.dam.2012.09.014].
File in questo prodotto:
File Dimensione Formato  
DAM2014SchedProb.pdf

non disponibili

Descrizione: Articolo
Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 247.57 kB
Formato Adobe PDF
247.57 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/41599