We consider the problem of sequencing m copies of unreliable jobs (i.e., jobs that have a certain probability of being successfully carried out) on m parallel machines (one copy per machine). A job is carried out if at least one of its copies is successfully completed. If the copy of a job fails, the corresponding machine is blocked and cannot perform the subsequently scheduled job copies. We analyze two problems. In the first problem, each job has a certain revenue which is attained if the job is carried out, and the objective is to maximize the expected revenue. We show that for m=2 this problem is NP-hard. We propose a mathematical programming formulation and a metaheuristic approach, and we assess their computational behavior on a large set of instances. We also solve the problem for m machines and two jobs, showing that the marginal benefit of having an additional machine decreases with m. The second problem is to maximize the probability that all jobs are carried out. We show that the problem can be easily solved when m=2, as well as for m machines and two jobs.

Agnetis, A., Benini, M., Detti, P., Hermans, B., & Pranzo, M. (2022). Replication and sequencing of unreliable jobs on parallel machines. COMPUTERS & OPERATIONS RESEARCH, 139 [10.1016/j.cor.2021.105634].

Replication and sequencing of unreliable jobs on parallel machines

Agnetis A.;Benini M.;Detti P.;Pranzo M.
2022

Abstract

We consider the problem of sequencing m copies of unreliable jobs (i.e., jobs that have a certain probability of being successfully carried out) on m parallel machines (one copy per machine). A job is carried out if at least one of its copies is successfully completed. If the copy of a job fails, the corresponding machine is blocked and cannot perform the subsequently scheduled job copies. We analyze two problems. In the first problem, each job has a certain revenue which is attained if the job is carried out, and the objective is to maximize the expected revenue. We show that for m=2 this problem is NP-hard. We propose a mathematical programming formulation and a metaheuristic approach, and we assess their computational behavior on a large set of instances. We also solve the problem for m machines and two jobs, showing that the marginal benefit of having an additional machine decreases with m. The second problem is to maximize the probability that all jobs are carried out. We show that the problem can be easily solved when m=2, as well as for m machines and two jobs.
Agnetis, A., Benini, M., Detti, P., Hermans, B., & Pranzo, M. (2022). Replication and sequencing of unreliable jobs on parallel machines. COMPUTERS & OPERATIONS RESEARCH, 139 [10.1016/j.cor.2021.105634].
File in questo prodotto:
File Dimensione Formato  
Replication and sequencing of unreliable jobs on parallel machines.pdf

non disponibili

Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 526.62 kB
Formato Adobe PDF
526.62 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: http://hdl.handle.net/11365/1191823