Please use this identifier to cite or link to this item: http://hdl.handle.net/11718/642
Title: Scheduling partially ordered activities under resource constraints on parallel machines
Authors: Verma, Sanjay
Dhavale, N. P.
Bagchi, Amitava
Keywords: Resource constrained project;Parallel machines
Issue Date: 14-Dec-2009
Series/Report no.: WP;2000-04-04/1596
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.
URI: http://hdl.handle.net/11718/642
Appears in Collections:Working Papers

Files in This Item:
File Description SizeFormat 
WP 2000_1596.pdf1.51 MBAdobe PDFView/Open


Items in IIMA Institutional Repository are protected by copyright, with all rights reserved, unless otherwise indicated.