Scheduling partially ordered activities under resource constraints on parallel machines

Abstract

A four-step strategy is proposed for scheduling a set of partially ordered resource-constrained activities on a given number of identical parallel machines. For regular measures, the generated schedule is optimal. In the first step, the difficulty level of the problem instance is estimated using the problem parameters as arguments. Easy problems are solved using a best-first tree search algorithm. For harder problems, an approximate algorithm is employed to determine a good upper bound on the measure. This bound is fed to a breadth-first tree search algorithm, making the pruning more effective and reducing the memory requirement of breadth-first search. When the number of parallel machines is 2, 3, 4, 5 or unlimited, this strategy is able to solve all except a small number of the benchmark PROGEN problems on a Linux-based Pentium PC or a UNIX-based RS 6000 machine. On projects without resource constraints, the proposed method is faster than the earlier method of Chang and Jiang [1994] by orders of magnitude.