Replication and sequencing of unreliable jobs on parallel machines. (March 2022)

• Record Type: Journal Article
• Authors: Agnetis, Alessandro; Benini, Mario; Detti, Paolo; Hermans, Ben; Pranzo, Marco
• Is Part Of: Computers & operations research. Volume 139(2022)
• Publication Date: 2022-03
• Subjects: Unreliable jobs -- Machine breakdown -- NP-hardness -- Scheduling; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105634
• Languages: English
• ISSNs: 0305-0548

Abstract

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. Highlights: We schedule unreliable jobs on parallel machines when job replication is allowed. Complexity analysis, mathematical formulation, a heuristic and a combinatorial upper bound. Assessment of the solution approaches through a thorough experimental campaign.