2-Approximation algorithm for a generalization of scheduling on unrelated parallel machines

In their seminal work [8], Lenstra, Shmoys, and Tardos proposed a 2-approximation algorithm to solve the problem of scheduling jobs on unrelated parallel machines with the objective of minimizing makespan. In contrast to their model, where a job is processed to completion by scheduling it on any one machine, we consider the scenario where each job j requires processing on kj different machines, independently. For this generalization, we propose a 2-approximation algorithm based on the ρ-relaxed decision procedure [8] and open cycles used in [3], [2].