Grant: Discovery Grants Program - Individual
Université Laval
$31,000.00
Strong and efficient filtering algorithms for scheduling constraints
FY 2020-21
Summary
Scheduling is the process of determining in what order a collection of operations, tasks, or activities should be executed so that the resources required for their executions are not overloaded. The tasks are generally subject to a variety of constraints and the problem comes with an optimization criteria. Scheduling problems are generally NP-Hard and require special techniques to be efficiently solved. Constraint Programming (CP) is a technique issued from artificial intelligence that proved itself very efficient to solve scheduling problems.
Despite recent advances, industrial problems remain hard to solve. Due to long computation times, solvers are halted before the optimal solution is found and therefore return sub-optimal schedules that can cause delays in airports or idle times on an assembly line. These inconveniences would be avoided if faster solvers were developed.
The success of constraint programming for solving scheduling problems comes from its filtering algorithms that reason over the scheduling constraints to prune the search space. These algorithms apply several filtering rules based on a relaxation of the scheduling problem. If the relaxed version of the scheduling problem forbids a task to start at a given time, the solver can safely discard these solutions and spend time exploring another part of the search space. By improving the relaxation used by the filtering rules, it is possible to filter larger portions of the search space and therefore to speed up the solving process.
The long-term objective of this program is to increase the speed of constraint-based schedulers to find large and complex optimal schedules in a reasonable time. This is achieved by fulfilling 3 sub-objectives.
1) Designing filtering algorithms based on stronger relaxations that achieve more filtering than existing ones;
2) Designing filtering algorithms based on relaxations that are aware of the objective criterion;
3) Designing faster filtering algorithms.
We propose a research program that will fully train 2 new Ph.D. students, 3 new master students, and allow one actual Ph.D. student to complete his thesis. Moreover, this program offers 3 internships for undergrad students.
One master and one doctoral student will develop stronger relaxations that will offer a better pruning of the search space. One new Ph.D. and one finishing Ph.D. student will work on filtering rules that are adapted to the objective criterion. Finally, two master students will work on faster algorithms that enforce existing filtering rules.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2016-05953
Name nom
Quimper, Claude-Guy
Department département
Informatique et 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
2020
Competition year année de concours
2016
Award amount
31000
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
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2715
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Optimization
Research subject fr
Optimisation
Installment
inst:5-6
Partie
2
Nb partie
6
Application title
Strong and efficient filtering algorithms for scheduling constraints
Keyword
NSERC
Application summary
Scheduling is the process of determining in what order a collection of operations, tasks, or activities should be executed so that the resources required for their executions are not overloaded. The tasks are generally subject to a variety of constraints and the problem comes with an optimization criteria. Scheduling problems are generally NP-Hard and require special techniques to be efficiently solved. Constraint Programming (CP) is a technique issued from artificial intelligence that proved itself very efficient to solve scheduling problems.
Despite recent advances, industrial problems remain hard to solve. Due to long computation times, solvers are halted before the optimal solution is found and therefore return sub-optimal schedules that can cause delays in airports or idle times on an assembly line. These inconveniences would be avoided if faster solvers were developed.
The success of constraint programming for solving scheduling problems comes from its filtering algorithms that reason over the scheduling constraints to prune the search space. These algorithms apply several filtering rules based on a relaxation of the scheduling problem. If the relaxed version of the scheduling problem forbids a task to start at a given time, the solver can safely discard these solutions and spend time exploring another part of the search space. By improving the relaxation used by the filtering rules, it is possible to filter larger portions of the search space and therefore to speed up the solving process.
The long-term objective of this program is to increase the speed of constraint-based schedulers to find large and complex optimal schedules in a reasonable time. This is achieved by fulfilling 3 sub-objectives.
1) Designing filtering algorithms based on stronger relaxations that achieve more filtering than existing ones;
2) Designing filtering algorithms based on relaxations that are aware of the objective criterion;
3) Designing faster filtering algorithms.
We propose a research program that will fully train 2 new Ph.D. students, 3 new master students, and allow one actual Ph.D. student to complete his thesis. Moreover, this program offers 3 internships for undergrad students.
One master and one doctoral student will develop stronger relaxations that will offer a better pruning of the search space. One new Ph.D. and one finishing Ph.D. student will work on filtering rules that are adapted to the objective criterion. Finally, two master students will work on faster algorithms that enforce existing filtering rules.