Scheduling unrelated machines with two types of jobs

What is it about?

This paper considers the problem of scheduling a set of jobs having only two possible processing times on a set of unrelated parallel machines to minimize the makespan. For the case when the processing times are p or 2p, a two-phase polynomial time algorithm is presented. Then a modification of this algorithm for two arbitrary processing times p and q, which is an NP-hard problem, is given and an estimation of the worst-case error is derived for this case.

Featured Image