Interval variables
Describes a basic building block of scheduling, the interval.
Informally speaking, an interval variable represents an interval of time during which something happens (a task, an activity is carried out) and whose position in time is an unknown of the scheduling problem. An interval is characterized by a start value, an end value and a size. An important feature of interval variables is the fact that they can be optional; that is, one can decide not to consider them in the solution schedule. This concept is crucial in applications that present at least some of the following features:
optional activities (operations, tasks) that can be left unperformed (with an impact on the cost); examples include externalized, maintenance or control tasks
activities that can execute on a set of alternative resources (machines, manpower) with possibly different characteristics (speed, calendar) and compatibility constraints
operations that can be processed in different temporal modes (for instance in series or in parallel)
alternative modes for executing a given activity, each mode specifying a particular combination of resources
alternative processes for executing a given production order, a process being specified as a sequence of operations requiring resources
hierarchical description of a project as a work-breakdown structure with tasks decomposed into sub-tasks, part of the project being optional (with an impact on the cost if unperformed), and so forth.
Formally, an interval variable a is a variable whose domain dom(a) is a subset of 
. An interval variable is said to be fixed if its domain is reduced to
a singleton; that is, if 
denotes a fixed interval variable:
interval is absent:
= 
; or interval is present:
= [s,e)
Absent interval variables have special meaning. Informally speaking, an absent interval variable is not considered by any constraint or expression on interval variables it is involved in. For example, if an absent interval variable is used in a noOverlap constraint, the constraint will behave as if the interval was never specified to the constraint. If an absent interval variable a is used in a precedence constraint between interval variables a and b this constraint does not impact interval variable b. Each constraint specifies how it handles absent interval variables.
The semantics of constraints defined over interval variables
is described by the properties that fixed intervals must have in order
the constraint to be true. If a fixed interval is present and such that = [s,
e), we will denote s( ) its integer start value s, e( ) its integer end value e and l( ) its positive integer length defined as e( )−s( ). The presence status x( ) will be equal to 1. For a fixed interval
that is absent, x( ) = 0 and the start, end and length are
undefined.
Until a solution is found it may not be known whether
an interval will be present or not. In this case we say that the interval
is optional. To be precise, an interval is said to be absent when dom(a) = {}, present when 
dom(a) and optional
in all other cases.
Intensity and size
Sometimes the intensity of “work” is not the same during the whole interval. For example let’s consider a worker who does not work during weekends (his work intensity during weekends is 0%) and on Friday he works only for half a day (his intensity during Friday is 50%). For this worker, 7 man-days of work will span for longer than just 7 days. In this example 7 man-days represents what we call the size of the interval; that is, what the length of the interval would be if the intensity function was always at 100%.
To model such situations, you can specify a range for
the size of an interval
variable and an integer stepwise intensity function F. For a fixed present interval the following relation will be enforced
at any solution between the start, end, size sz of the interval and the integer
granularity G (by
default, the intensity function is expressed as a percentage so the
granularity G is
100):
That is, the length of the interval will be at least long enough to cover the work requirements given by the interval size, taking into account the intensity function. However, any over-estimation is always strictly less than one work unit.
If no intensity is specified, it is supposed to be the
constant full intensity function 
= 100% so in that case sz(a) = l(a). Note that
the size is not defined for absent intervals.
The intensity step function F should be a stepwise function with integer values and is not allowed to exceed the granularity (100 by default).
The following figure depicts an interval variable of size 14 with its intensity function. A valid solution is represented where the interval starts at 10 and ends at 27. Indeed in this case:
OPL formulation
Typically, the problem structure will indicate if an
interval can be optional or not, and the keyword optional is used (or not) in the definition of the
interval variable. In the case where the optionality depends on input
data, you can specify a boolean parameter to the optionality field: optional(true) being equivalent
to optional and optional(false) being equivalent to the omission
of optional.
A window [StartMin,EndMax] can be specified to restrict the position of the interval variable. By default, an interval variable will start after 0 and end before maxint/2. The fixed size or the size range for the interval is specified with the size keyword. Note that these bounds are taken into account only when the interval variable is present in the final schedule, that is, they allow specifying conditional bounds on the interval variable would the interval be present in the final schedule. For absent intervals, they are just ignored.
dvar interval a [optional[(IsOptional)]]
[in StartMin..EndMax]
[size SZ | in SZMin .. SZMax]
[intensity F]
Where:
int IsOptional, StartMin, EndMax, SZ, SZMin, SZMax;
stepFunction F;
-maxint/2 + 1 <= StartMin <= maxint/2 - 1
-maxint/2 + 1 <= EndMax <= maxint/2 - 1
0 <= SZ <= maxint/2 - 1
0 <= SZMin <= maxint/2 - 1
0 <= SZMax <= maxint/2 - 1
Examples
For examples of using interval, see the CP keywords interval, optional, size, and intensity in the OPL Language Quick Reference.
Display of interval variable domain
The domain of an interval variable is displayed as shown in this example:
A1[0..1: 10..990 -- (5..10)5..990 --> 25..1000]
After the name of the interval variable (here A1), the first range (here 0..1) represents the domain of the boolean presence status of the interval variable. Thus 0..1 represents an optional interval variable whose status has still not been fixed, 0 an absent interval variable and 1 a present interval variable.
The remaining fields describe the position of the interval variable, it is omitted if the interval variable is absent as this information is not relevant in this case. Thus, an absent interval variable is displayed as:
A1[0]
When the interval variable is possibly present:
- the first range in the remaining fields represents the domain of the interval start
- the second range (between parenthesis) represents the domain of the interval size
- the third range represents the domain of the interval length
- the fourth and last range represents the domain of the interval end
Note that the second range may be omitted in case the size and length of the interval variable are necessarily equal.
When the values are fixed, the ranges min..max are replaced by a single value. For instance, the following display represents a fixed interval variable of size 5 that is present, starts at 10 and ends at 35:
A1[1: 10 -- (5)25 --> 35]