Scheduling: Brief Overview
Jobshop scheduling
- Set of jobs
- Each job consists of tasks in some (partial) order
- Temporal constraints on jobs
- Contention constraints
- Each task can be done on a subset of machines
CSP Models
- Time point model
- Tasks as variables, Time points as values
- EST, LFT, Machine contention as constraints
- Inter-task precedences as variables (PCP model)
CSP Techniques
- Customized consistency enforcement techniques
- ARC-B consistency
- Edge-finding
- Customized variable/value ordering heuristics
- Contention-based
- Slack-based
- MaxCSP; B&B searches