The Conference Scheduling Problem

This book studies exact solution procedures for the
so-called Conference Scheduling Problem (CSP), which
seeks to minimize the duration of a conference, where
some of the activities cannot be held concurrently.
The CSP corresponds to non-preemptive scheduling of
independent activities with dedicated resources and
constitutes a special case within the more general
Resource Constraint Project Scheduling Problem
(RCPSP) as well as the machine scheduling framework,
and as such it is NP-hard. The core characteristics
of CSP are commonly encountered in problems of
different domains and therefore the problem is of
high practical relevance.

The book focuses on the analysis and comparison of
graph-based solution procedures, which operate on a
constrained graph that is derived from the
confliciting acitivies to be scheduled. In particular
Interval Coloring and Comparability Graph
Augmentation are considered. An emphasis is put on
the investigation of variations of the latter
procedure, which exploits the structure of the
constraint graph and is therefore robust to
variations in the activity durations.

Autorentext

Dr. Jan Krämer is a postdoctoral researcher at the Faculty of
Economics and Business Engineering at the University of
Karlsruhe, Germany, from where he also obtained a diploma degree
in Business Engineering in 2005 and a doctorate degree in
Economics in 2007.

Klappentext

This book studies exact solution procedures for the
so-called Conference Scheduling Problem (CSP), which
seeks to minimize the duration of a conference, where
some of the activities cannot be held concurrently.
The CSP corresponds to non-preemptive scheduling of
independent activities with dedicated resources and
constitutes a special case within the more general
Resource Constraint Project Scheduling Problem
(RCPSP) as well as the machine scheduling framework,
and as such it is NP-hard. The core characteristics
of CSP are commonly encountered in problems of
different domains and therefore the problem is of
high practical relevance.

The book focuses on the analysis and comparison of
graph-based solution procedures, which operate on a
constrained graph that is derived from the
confliciting acitivies to be scheduled. In particular
Interval Coloring and Comparability Graph
Augmentation are considered. An emphasis is put on
the investigation of variations of the latter
procedure, which exploits the structure of the
constraint graph and is therefore robust to
variations in the activity durations.