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

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.