Scheduling Partially Ordered Activities Under Resource Constraints on Parallel Machines

Bagchi Amitava, Dhavale N P and Sanjay Verma

No WP2000-04-04, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

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.

Date: 2000-04-04
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:iim:iimawp:wp01677

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by ().