Introduction

OPL and CP Optimizer introduce a set of modeling features for applications that deal with scheduling over time.

In OPL and CP Optimizer, time points are represented as integers, but the possible very wide range of time points means that time is effectively continuous. A consequence of scheduling over effectively continuous time is that the evolution of some known quantities over time (for instance the instantaneous efficiency/speed of a resource or the earliness/tardiness cost for finishing an activity at a given date t) needs to be compactly represented in the model. To that end, CP Optimizer provides the notion of piecewise linear and stepwise functions.

Most scheduling applications consist in scheduling in time some activities, tasks or operations that have a start and an end time. In CP Optimizer, this type of decision variable is captured by the notion of the interval variable. Several types of constraints are expressed on and between interval variables:

  • to limit the possible positions of an interval variable (forbidden start/end or “extent” values)

  • to specify precedence relations between two interval variables

  • to relate the position of an interval variable with one of a set of interval variables (spanning, synchronization, alternative).

An important characteristic of scheduling problems is that time intervals may be optional, and whether to execute a time-interval or not is a possible decision variable. In CP Optimizer, this is captured by the notion of a boolean presence status associated with each interval variable. Logical relations can be expressed between the presence of interval variables, for example to state that whenever interval a is present then interval b must also be present.

Another aspect of scheduling is the allocation of scarce resources to time intervals. The evolution of a resource over time can be modelled by two types of variables:

  • The evolution of a disjunctive resource over time can be described by the sequence of intervals that represent the activities executing on the resource. For that, CP Optimizer introduces the notion of an interval sequence variable. Constraints and expressions are available to control the sequencing of a set of interval variables.

  • The evolution of a cumulative resource often needs a description of how the accumulated usage of the resource evolves over time. For that purpose, CP Optimizer provides the concept of the cumulative function expression that can be used to constrain the evolution of the resource usage over time.

  • The evolution of a resource of infinite capacity, the state of which can vary over time, is captured in CP Optimizer by the notion of the state function. The dynamic evolution of a state function can be controlled with the notion of transition distance, and constraints are available for specifying conditions on the state function that must be satisfied during fixed or variable intervals.

Some classical cost functions in scheduling are earliness/tardiness costs, makespan, and activity execution or non-execution costs. CP Optimizer generalizes these classical cost functions and provides a set of basic expressions that can be combined together; this allows you to express a large spectrum of scheduling cost functions that can be efficiently exploited by the CP Optimizer search.

For the description of the symbolic notation used throughout this section, see Notation.