Approximation algorithms for makespan minimization on identical parallel machines under resource constraints

The problem of minimizing the makespan on parallel identical machines is considered in the presence of additional resources, provided that some jobs at any time of their processing require one unit of a particular resource. We establish a lower bound on the worst-case performance of any group technology algorithm, which schedules the composite jobs formed of the original jobs that require the same resource. A simple group technology algorithm is given such that in the worst case no group technology algorithm performs better. An algorithm for the two-machine case is presented which guarantees a tight worst-case performance ratio of 6/5