Replication and sequencing of unreliable jobs on parallel machines

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.