Basic building blocks of scheduling models
The basic building blocks of scheduling include time intervals and the constraints amongst those intervals.
In addition to constrained integer variables, CP Optimizer provides a set of modeling features for applications dealing with scheduling over time. Although in CP Optimizer, time points are represented as integers, time is effectively continuous because the range of time points is potentially very wide.
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) needs to be compactly represented in the model.
Most of the scheduling applications consist of scheduling in time a set of 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 interval decision variable.
Several types of constraints are expressed on and between interval decision variables:
to limit the possible positions of an interval decision variable (forbidden start/end or “extent” values),
to specify precedence relations between two interval decision variables and
to relate the position of an interval variable with one of a set of interval decision variables (such as with spanning, synchronization, or alternative constraints).
An important characteristic of scheduling problems is that intervals may be optional and whether to execute an interval or not may be a decision variable. In CP Optimizer, this is captured by the notion of a Boolean presence status associated with each interval decision variable. Logical relations can be expressed between the presence of interval variables, for instance to state that whenever interval a is present then interval b must also be present.
Another aspect of scheduling is the allocation of limited resources to time intervals. The evolution of a resource over time can be modeled by three types of decision variables and expressions:
The evolution of a disjunctive resource over time can be described by the sequence of intervals that represent the activities executing on the resource. 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 resource accumulated usage evolves over time. CP Optimizer provides cumul function expressions that can be used to constrain the evolution of 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 state functions. The dynamic evolution of a state function can be controlled using transition distances and constraints 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 activities execution/non-execution costs. CP Optimizer generalizes these classical cost functions and provides a set of basic expressions that can be combined together to express a large spectrum of scheduling cost functions that can be efficiently exploited by the CP Optimizer search.