Abstract
Scheduling problems typically deal with activity sequencing and resource allocation while the problem of activity selection is assumed to be resolved before scheduling. To increase flexibility of scheduling systems in complex environments, it is possible to include activity selection, for example decisions about alternative process routes, in the scheduling problem.
Constraint-based scheduling seems to be a good underlying technology to model problems both with traditional scheduling decisions such as activity sequencing and resource allocation, and with planning-like decisions such as selection among alternative activities. The paper describes a formal framework called Temporal Networks with Alternatives (TNA) for modeling alternative process routes.
Moreover, a constraint model based on TNA is presented together with a dedicated search strategy that assumes both sequencing decisions and selection among alternative activities.