This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Zhu, G. Articles by Yu, G. Search for Related Content

A Branch-and-Cut Procedure for the Multimode Resource-Constrained Project-Scheduling Problem

Department of Management Science & Information Systems, McCombs School of Business, The University of Texas, Austin, Texas 78712, USA
Graduate Program in Operations Research & Industrial Engineering, 1 University Station, C2200, The University of Texas, Austin, Texas 78712, USA
Department of Management Science & Information Systems, McCombs School of Business, The University of Texas, Austin, Texas 78712, USA
Guidong.Zhu{at}phd.mccombs.utexas.edu
jbard{at}mail.utexas.edu
yu{at}uts.cc.utexas.edu

This paper considers the multimode resource-constrained project-scheduling problem (MRCPSP) with a minimum-makespan objective. An exact branch and cut algorithm is presented based on the integer linear programming (ILP) formulation of the problem. In the preprocessing stage, lower bounds on the distance between each pair of precedence-constrained activities are derived. These bounds are used to reduce the number of variables in the model and to generate cuts that tighten the linear programming relaxation. The solution process is accelerated by an adaptive branching scheme in conjunction with a bound-tightening scheme that is called iteratively after branching. To find good feasible solutions in the early stages of the computations, a high-level neighborhood search strategy known as local branching is included. Here, a neighborhood of a feasible solution is defined by the linear inequalities in the ILP model and is searched first. As implemented, the full algorithm is exact rather than heuristic in nature. Numerical results are reported for 20- and 30-activity benchmark problems. These are the largest instances available and are generally viewed to be notoriously difficult. Up until now, there were no confirmed optimal solutions for any of the 552 30-activity instances. We were able to find several better solutions and to show that at least 506 are optimal.

Key words: project scheduling; multiple resources; multimodes; integer linear programming; branch and cut
History: received March 2003; revised November 2004; accepted November 2004.