The Conference Scheduling Problem

This book studies exact solution procedures for theso-called Conference Scheduling Problem (CSP), whichseeks to minimize the duration of a conference, wheresome of the activities cannot be held concurrently.The CSP corresponds to non-preemptive scheduling ofindependent activities with dedicated resources andconstitutes a special case within the more generalResource Constraint Project Scheduling Problem(RCPSP) as well as the machine scheduling framework,and as such it is NP-hard. The core characteristicsof CSP are commonly encountered in problems ofdifferent domains and therefore the problem is ofhigh practical relevance.The book focuses on the analysis and comparison ofgraph-based solution procedures, which operate on aconstrained graph that is derived from theconfliciting acitivies to be scheduled. In particularInterval Coloring and Comparability GraphAugmentation are considered. An emphasis is put onthe investigation of variations of the latterprocedure, which exploits the structure of theconstraint graph and is therefore robust tovariations in the activity durations.