Scheduling Resource-Constrained Projects Competitively at Modest Memory Requirements
AbstractWe consider the resource-constrained project scheduling problem. The purpose of this paper is to direct the focus to a branch-and-bound concept that can, by simple adaptations, operate on a wide range of problem settings. The general approach can, e.g., deal with multimode problems, resource availability varying with time, and a wide range of objectives. Even the simple assembly line balancing problem of type-1 can be competitively approached with some modifications. Although the algorithm is the most general and simple one currently available for resource-constrained project scheduling, the computational performance can compete with the best approaches available for the single-mode problem. The algorithm uses far less memory than the state-of-the-art procedure, i.e., 256 KB versus 24 MB, for solving the standard benchmark set with projects consisting of 32 activities within comparable time. If both approaches are allowed to make limited use of memory, i.e., 256 KB, then more than 97% of the benchmark instances can be solved within fractions of the time required by the current state-of-the-art procedure. The truncated version of our algorithm achieves at 256 KB approximately the results of the truncated version of the state-of-the-art approach at 24 MB. Since in general the memory requirements exponentially grow with the number of activities the project consists of, memory will become a critical resource, and the strategy to access previously stored information will gain fundamental importance when solving larger projects.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoArticle provided by INFORMS in its journal Management Science.
Volume (Year): 46 (2000)
Issue (Month): 5 (May)
project scheduling; resource constraints; single-mode; branch-and-bound; heuristic; computational results;
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- V. Van Peteghem & M. Vanhoucke, 2009. "Using Resource Scarceness Characteristics to Solve the Multi-Mode Resource-Constrained Project Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 09/595, Ghent University, Faculty of Economics and Business Administration.
- Chen, Jiaqiong & Askin, Ronald G., 2009. "Project selection, scheduling and resource allocation with time dependent returns," European Journal of Operational Research, Elsevier, vol. 193(1), pages 23-34, February.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc).
If references are entirely missing, you can add them using this form.