Grant: Discovery Grants Program - Individual
Université Laval
$29,000.00
Scheduling using constraint programming
EF 2015-16
Résumé
Scheduling is the process of allocating tasks to a time slot and a resource. Resources should not encounter overloaded periods and tasks are often subject to deadlines. Many additional constraints make the problem intractable. Solvers are computer programs that take the problem parameters as input, explore the solution space of the problem, and produce a solution.
This research program aims at designing more efficient solvers that are able to produce solutions in a shorter period of time. Reaching this long-term goal will impact the industry in many different ways. Industries that schedule their operations in a time critical environment will greatly beneficiate from this research since they will obtain better schedules in a shorter period of time.
We see three ways that are promising for reaching this goal. First, we want to improve key algorithms that are currently used in schedulers. Some algorithms, whose complexity has been identified as suboptimal, can be greatly improved by using simple and efficient data structures.
Second, we want to explore stronger relaxations and new global constraints that can be used in a solver. Relaxations, and their associated global constraints, limit the scope of the search and let the solver focus on the most promising candidate solutions.
Finally, we propose a new way of modeling scheduling problems that will improve the computation time. With new implicit models, solvers will ignore multiple details of a solution and rather focus on solving the hard part of a problem. An implicit model leads to a partial solution that specialized algorithms can efficiently complete.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
402227-2011
Name nom
Quimper, ClaudeGuy
Department département
Informatique et de génie logiciel
Organization id
51
Institution établissement
Université Laval
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2011
Award amount
29000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2800
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Artificial intelligence (computer vision, use2603)
Research subject fr
Intelligence artificielle (vision artificielle, utiliser 2603)
Partie
5
Nb partie
5
Application title
Scheduling using constraint programming
Keyword
NSERC
Application summary
Scheduling is the process of allocating tasks to a time slot and a resource. Resources should not encounter overloaded periods and tasks are often subject to deadlines. Many additional constraints make the problem intractable. Solvers are computer programs that take the problem parameters as input, explore the solution space of the problem, and produce a solution.
This research program aims at designing more efficient solvers that are able to produce solutions in a shorter period of time. Reaching this long-term goal will impact the industry in many different ways. Industries that schedule their operations in a time critical environment will greatly beneficiate from this research since they will obtain better schedules in a shorter period of time.
We see three ways that are promising for reaching this goal. First, we want to improve key algorithms that are currently used in schedulers. Some algorithms, whose complexity has been identified as suboptimal, can be greatly improved by using simple and efficient data structures.
Second, we want to explore stronger relaxations and new global constraints that can be used in a solver. Relaxations, and their associated global constraints, limit the scope of the search and let the solver focus on the most promising candidate solutions.
Finally, we propose a new way of modeling scheduling problems that will improve the computation time. With new implicit models, solvers will ignore multiple details of a solution and rather focus on solving the hard part of a problem. An implicit model leads to a partial solution that specialized algorithms can efficiently complete.