Relaxation Adaptive Memory Programming For The Resource Constrained Project Scheduling Problem

The resource constrained project scheduling problem (RCPSP) is one of the most intractable problems in operations research; it is NP-hard in the strong sense. Due to the hardness of the problem, exact solution methods can only tackle instances of relatively small size. For larger instances commonly found in real applications heuristic solution methods are necessary to find near-optimal solutions within acceptable computation time limits. In this study algorithms based on the relaxation adaptive memory programming (RAMP) method (Rego, 2005) are developed for the purpose of solving the RCPSP. The RAMP algorithms developed here combine mathematical relaxation, including Lagrangian relaxation and surrogate constraint relaxation, with tabu search and genetic algorithms. Computational tests are performed on an extensive set of benchmark instances. The results demonstrate the capability of the proposed approaches to the solution of RCPSPs of different sizes and characteristics and provide meaningful insights to the potential application of these approaches to other more complex resource-constrained scheduling problems.

Name thesis:degree_name

Ph.D. in Business Administration

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Marketing

Year dc:date.available

2014

Author dc:creator

• Riley, Robert Christopher-Lee

Contributors dc:contributor

• Cesar Rego
• Hugh Sloan
• Philip J. Rhodes

• Lagrangian Relaxation
• Pd-Ramp
• Project Scheduling
• Ramp
• Rcpsp
• Tabu Search
• Operational Research

Repository record dc:identifier

https://egrove.olemiss.edu/etd/392

OAI identifier oai:identifier

oai:egrove.olemiss.edu:etd-1391