A Hybrid Framework for Over-Constrained Generalized Resource-Constrained Project Scheduling Problems

• Main Authors: LIM, Andrew, Rodrigues, Brian, Thangarajoo, R., Xiao, F.
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2010
• Subjects: Genetic Algorithm; project scheduling; resource constrained; Tabu Search; Operations and Supply Chain Management
• Online Access: https://ink.library.smu.edu.sg/lkcsb_research/2814; https://doi.org/10.1007/s10462-004-1286-8
• Institution: Singapore Management University

In this work we study an over-constrained scheduling problem where constraints cannot be relaxed. This problem originates from a local defense agency where activities to be scheduled are strongly ranked in a priority scheme determined by planners ahead of time and operational real-time demands require solutions to be available almost immediately. A hybrid framework is used which is composed of two levels. A high-level component explores different orderings of activities by priorities using Tabu Search or Genetic Algorithm heuristics, while in a low-level component, constraint programming and minimal critical sets are used to resolve conflicts. Real-data used to test the algorithm show that a larger number of high priority activities are scheduled when compared to a CP-based system used currently. Further tests were performed using randomly generated data and results compared with CPLEX. The approach provided in this paper offers a framework for problems where all constraints are treated as hard constraints and where conflict resolution is achieved only through the removal of variables rather than constraints.