Optimization Online


Benders decomposition of the resource constrained project scheduling problem

SE Terblanche(fanie.terblanche***at***nwu.ac.za)
JH van Vuuren(vuuren***at***sun.ac.za)

Abstract: Problem instances found in the literature that are used in computational studies of the resource constrained project scheduling problem, typically include only a few resources. In some practical applications, however, the number of resources may be significantly higher. In this paper, problem instances with a large number of resources are considered and a Benders decomposition approach is followed to deal with the additional computational effort required. Details of a separation routine for deriving the feasibility cuts and a heuristic for computing primal feasible solutions within a branch-and-cut framework, are provided. Randomly generated problem instances are introduced, which are based on existing problem instances from the literature. The empirical results reported in this paper demonstrate the scalability of the Benders decomposition approach when considering problem instances with a large resource set.

Keywords: Resource constrained project scheduling; Mixed integer linear programming; Benders decomposition; Resource flow

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Technical Report FABWI-N-RA-2017-530, Centre for Business Mathematics & Informatics, North-West University, South Africa

Download: [PDF]

Entry Submitted: 07/28/2017
Entry Accepted: 08/01/2017
Entry Last Modified: 07/28/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society