An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations
AbstractIn this paper we propose an exact algorithm for the Resource Constrained Project Scheduling Problem (RCPSP) with generalized precedence relationships (GPRs) and minimum makespan objective. For the RCPSP with GPRs we give a new mathematical formulation and a branch and bound algorithm exploiting such a formulation. The exact algorithm takes advantage also of a lower bound based on a Lagrangian relaxation of the same mathematical formulation. We provide an extensive experimentation and a comparison with known lower bounds and competing exact algorithms drawn from the state of the art.
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.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Bibliographic InfoArticle provided by Elsevier in its journal European Journal of Operational Research.
Volume (Year): 219 (2012)
Issue (Month): 1 ()
Contact details of provider:
Web page: http://www.elsevier.com/locate/eor
Branch and bound; Generalized precedence relationships; Lagrangian relaxation;
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.:
- Rolf H. Möhring & Andreas S. Schulz & Frederik Stork & Marc Uetz, 2003. "Solving Project Scheduling Problems by Minimum Cut Computations," Management Science, INFORMS, vol. 49(3), pages 330-350, March.
- Demeulemeester, Erik & Herroelen, Willy, 1997. "New benchmark results for the resource-constrained project scheduling problem," Open Access publications from Katholieke Universiteit Leuven urn:hdl:123456789/101250, Katholieke Universiteit Leuven.
- 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.
- Mohring, Rolf H. & Schulz, Andreas S. & Stork, Frederik & Uetz, Marc, 1999. "Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems," Open Access publications from Maastricht University urn:nbn:nl:ui:27-4904, Maastricht University.
- 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.
- Klein, Robert & Scholl, Armin, 1999. "Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 112(2), pages 322-346, January.
- Ulrich Dorndorf & Erwin Pesch & Toàn Phan-Huy, 2000. "A Time-Oriented Branch-and-Bound Algorithm for Resource-Constrained Project Scheduling with Generalised Precedence Constraints," Management Science, INFORMS, vol. 46(10), pages 1365-1384, October.
- Mohring, Rolf H. & Schulz, Andreas S. & Stork, Frederik & Uetz, Marc, 2003. "Solving project scheduling problems by minimum cut computations," Open Access publications from Maastricht University urn:nbn:nl:ui:27-4898, Maastricht University.
- Klein, Robert, 1999. "Computing lower bounds by destructive improvement - an application to resource-constrained project scheduling," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 10913, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
- De Reyck, B & Herroelen, Willy, 1998. "A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations," Open Access publications from Katholieke Universiteit Leuven urn:hdl:123456789/101157, Katholieke Universiteit Leuven.
- De Reyck, Bert & Herroelen, willy, 1998. "A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations," European Journal of Operational Research, Elsevier, vol. 111(1), pages 152-174, November.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Wendy Shamier).
If references are entirely missing, you can add them using this form.