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

Publication Type

Journal Article

Publication Date

11-2010

Abstract

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.

Keywords

Genetic Algorithm, project scheduling, resource constrained, Tabu Search

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

Artificial Intelligence Review

Volume

22

Issue

3

First Page

211

Last Page

243

ISSN

0269-2821

Identifier

10.1007/s10462-004-1286-8

Publisher

Springer Verlag

Additional URL

https://doi.org/10.1007/s10462-004-1286-8

Link to Full Text

Share

COinS