Complex production processes and infrastructure puts the optimal solution of resource allocation problems at the center of attention in decision support and management. Often, these are discrete combinatorial search problems such as time tabling, production scheduling, and staff rostering, for which no general efficient algorithm is known.
Constraint programming is an emerging research field that is characterized by moving computation with constraints to the center of a programming framework. Recently, constraint programming proved to provide successful solutions to several classes of resource allocation problems. Due to programming language support for constraints, constraint programming often results in better solutions of resource allocation problems and supports software development and maintenance more effectively than traditional approaches from Operations Research.
In this project, we strive to improve constraint programming techniques in an application-driven approach. We concentrate on a selection of resource allocation problems for which no satisfactory solution exists and investigate how constraint programming can be improved by techniques such as global constraints, novel search heuristics, and the integration of integer programming and local search in the constraint programming framework.
The application area that we currently investigate in the framework of ReAlloc is sport tournament scheduling.
The project is funded by the NUS research grant RP 3972683 of 48,000 S$. The funding period is 1/1/1998 to 31/12/1999.