A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem

A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20071194
Country: United States
Volume: 18
Issue: 3
Start Page Number: 377
End Page Number: 390
Publication Date: Jun 2006
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: programming: integer
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.