Replication and sequencing of unreliable jobs on parallel machines. (March 2022) - Agnetis, Alessandro
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.