Scheduling as a Constraint Satisfaction Problem
Bistra Dilkina – bnd@cs.sfu.ca – Computing Science
Constructive Search
Partial assignment
Consistent assignment
Extension
Stack architecture
Backtracking mechanism
Completeness
Local Search
Full assignment
Inconsistent assignment
Improvement
Parallel architecture
Digression mechanism
Incompleteness
Sport Scheduling
A football League has 7 teams. Every team has to play every other team in a season of 7 weeks. Every team can play at most once a week and no team can play at home more than twice in a row.
Model: Every week each team has an opponent = one of the other 6 teams.
Complexity: Total of 7 teams * 7 weeks = 49 opponent variables. The number of possible configurations are 649  
CSP Framework
The CSP (Constraint Satisfaction Problem) paradigm is good at modeling many real-life problems: job scheduling, timetabling, vehicle routing, etc.
In CSPs the problem is stated in terms of variables, possible values for them and constraints.
The problem difficulty grows really fast (exponentially) with the number of variables to be scheduled.
Start with an empty solution
Add a queen and apply constraints
Extend the partial solution
Extend the partial solution
Until some queen cannot be placed on the board
Change the first possible previous queen and continue…
Systematicity
Memory
Inference
Completeness Boundary
Chronological Backtracking
Dependency-directed Backjumping
Random Restart
Simulated Annealing
Tabu Search
CBJ
Systematic Local Search
Full assignment
Equality between solvers
Freedom to move
heuristically
A feasible solution is found
3
2
1
0
2
3
2
1
2
0
1
3
2
3
2
1
2
2
0
3
3
2
3
2
2
0
2
3
3
1
0
2
0
2
3
1
Move one of the queens that have better available positions
1
3
1
1
2
2
2
2
3
1
3
1
1
2
2
1
5
1
1
2
1
3
2
4
1
1
1
2
1
2
0
3
1
3
2
2
Re-evaluate the conflicts to choose the next queen
2
3
0
1
2
2
3
1
3
1
2
2
1
2
2
1
4
2
1
2
1
3
3
3
1
1
2
3
2
2
0
2
0
2
2
2
Improve the solution until…
3
3
1
0
2
3
2
1
3
1
1
2
1
2
1
2
3
2
0
3
2
2
3
3
1
0
2
3
2
2
0
2
0
2
2
2
1
3
1
1
2
2
2
2
3
1
3
1
1
2
2
1
5
1
1
2
1
3
2
4
1
1
1
2
1
2
0
3
1
3
2
2
Start with a full assignment, and calculate the conflicts