A Hybrid Framework for Over-Constrained Generalized |
| |
Authors: | A Lim B Rodrigues R Thangarajoo F Xiao |
| |
Affiliation: | (1) Department of IEEM, Hong Kong University of Science and Technology, Clearwater Bay;(2) School of Business, Singapore Management University, 469 Bukit Timah Road, Singapore;(3) Defense Science and Technology Agency, Singapore;(4) Department of Computer Science, National University of Singapore, 3 Science Drive 2, Singapore |
| |
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 |
本文献已被 SpringerLink 等数据库收录! |
|