Replication and sequencing of unreliable jobs on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si575.svg" display="inline" id="d1e637"> <mml:mi>m</mml:mi> </mml:math> parallel machines: New results

This paper gives new results for the problem of sequencing m copies of n 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, in which case a certain revenue is earned. If the copy of a job fails, the corresponding machine is blocked and cannot perform the subsequently scheduled job copies. The problem is to sequence the n copies of each job on each of the m machines in order to maximize the expected revenue. For the case of m=2, Agnetis et al. (2022) proposed a metaheuristic approach and some upper bounding schemes. Here we address the general m-machine problem, giving a simple (1−1/e)-approximation algorithm, an even simpler algorithm, for which we show a tight logarithmic approximation guarantee, and an additional heuristic as well as an additional metaheuristic. We provide computational results, which, along with a new upper-bounding scheme, establish the effectiveness of our approaches in practice.