Scheduling as CSP

Jobshop scheduling

• Set of jobs
  • Each job consists of tasks in some (partial) order
• Temporal constraints on jobs
  • EST, LFT, Duration
• Contention constraints
  • Each task can be done on a subset of machines

CSP Models
• Tasks as variables
  • Time points as values
  • EST, LFT, Machine contention as constraints
• Inter-task precedences as variables

CSP Techniques
• Customized consistency enforcement techniques
  • ARC-B consistency
• Customized variable/value ordering heuristics
  • Contention-based
  • Slack-based
• MaxCSP; B&B searches

T2

T1

EST

LFT

Dur

Previous slide

Next slide

Back to first slide

View graphic version