Scheduling Resource-Constrained Projects Competitively at Modest Memory Requirements
We 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.
Volume (Year): 46 (2000)
Issue (Month): 5 (May)
|Contact details of provider:|| Postal: 7240 Parkway Drive, Suite 300, Hanover, MD 21076 USA|
Web page: http://www.informs.org/
More information through EDIRC
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Rainer Kolisch & Arno Sprecher & Andreas Drexl, 1995. "Characterization and Generation of a General Class of Resource-Constrained Project Scheduling Problems," Management Science, INFORMS, vol. 41(10), pages 1693-1703, October.
- Erik Demeulemeester & Willy Herroelen, 1992. "A Branch-and-Bound Procedure for the Multiple Resource-Constrained Project Scheduling Problem," Management Science, INFORMS, vol. 38(12), pages 1803-1818, December.
- Brucker, Peter & Knust, Sigrid & Schoo, Arno & Thiele, Olaf, 1998. "A branch and bound algorithm for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 107(2), pages 272-288, June.
- F. Brian Talbot & James H. Patterson, 1978. "An Efficient Integer Programming Algorithm with Network Cuts for Solving Resource-Constrained Scheduling Problems," Management Science, INFORMS, vol. 24(11), pages 1163-1174, July.
- Sprecher, Arno & Kolisch, Rainer & Drexl, Andreas, 1995. "Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 80(1), pages 94-102, January.
- Aristide Mingozzi & Vittorio Maniezzo & Salvatore Ricciardelli & Lucio Bianco, 1998. "An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation," Management Science, INFORMS, vol. 44(5), pages 714-729, May.
- Erik L. Demeulemeester & Willy S. Herroelen, 1997. "New Benchmark Results for the Resource-Constrained Project Scheduling Problem," Management Science, INFORMS, vol. 43(11), pages 1485-1492, November.
- Sprecher, Arno & Drexl, Andreas, 1998. "Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm," European Journal of Operational Research, Elsevier, vol. 107(2), pages 431-450, June.
When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:46:y:2000:i:5:p:710-723. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc)
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.