Scheduling preemptive jobs with precedence constraints on parallel machines

In parallel machine scheduling problems with general precedence constraints, it is advantageous to interrupt jobs and complete them at a later time in order to minimize makespan. For general precedence constraints, we know that this problem is in the class of NP-hard combinatorial problems for which the development of efficient algorithms is unlikely. In this paper we propose two new heuristics SUPIO and INFIO which, respectively, give an upper bound and a lower bound to makespan. We show numerically that the ratio between these two bounds is very close to one. SUPIO heuristic provides an optimal solution in the following cases: P2| <,pmnt|Cmax, P| forest,pmnt|Cmax and P| interval order,pmnt|Cmax. Its absolute performance ratio is upper bounded by (2 – 2/m). We illustrate the efficiency of our heuristics by computational results associated with randomly generated problems. We show in the conclusion that this new approach could solve some non-preemptive parallel machine scheduling problems.