Scheduling Problems

Introduction

Resource-constrained scheduling is a key application area of constraint programming. Most constraint programming systems contain special syntactical constructs to formulate such problems, allowing the use of specialized inference algorithms. In Constraints in Constraint Programming we have already seen two examples of global constraints for scheduling: cp::SequentialSchedule and cp::ParallelSchedule. For more complex scheduling problems that contain, for example, sequence-dependent setup times between activities, or specific precedence relations, the use of more advanced scheduling algorithms is advisable. These algorithms cannot be offered by the stand-alone global constraints cp::SequentialSchedule and cp::ParallelSchedule, but can be accessed by formulating the problem using activities and resources in AIMMS.

Activities

Activities correspond to the execution of objects in scheduling problems, e.g., processing an order, working a shift, or performing a loading operation. They can be viewed as the variables of a scheduling problem, since we must decide on their position in the schedule. Common attributes associated to an activity are its begin, end, length, and size. Further, it is often convenient to distinguish mandatory and optional activities, which allows to consider the presence of an activity. In AIMMS, the properties begin, end, length, size, and presence of an activity can be used as variables in other parts of the model. It is also possible to build models using nested activities, where meta-activities group together a number of sub-activities, for example in the context of project planning.

Resources

Resources correspond to the assets that are available to execute the activities, e.g., the capacity of a machine, the volume of a truck, or the number of available employees. Resources can be viewed as the constraints of a scheduling problem. The main attributes of a resource are its capacity, its activity level, and the set of activities that require the resource in order to be executed. That is, during the execution of the schedule, we must ensure that the resource activity level is always within its capacity. Note that while a resource depends on a set of activities, an activity can impact on one or more resources at the same time.

An activity changes the resource activity level

A resource starts with a default activity level of 0, corresponding to full available capacity, or a user-specified initial value. During the execution of the schedule, activities will influence the resource activity level. The viewpoint chosen in AIMMS is that an activity changes the activity level of a resource when it begins, and/or when it ends. This enables one to model many common situations. For example, when an activity corresponds to a loading operation, and the resource corresponds to a truck load, the activity will change the activity level of the resource with the volume of the load at its start, but there is no change in the resource activity level when finishing this activity. For sequential resources the capacity is \(1\), and each activity will change the resource activity level by \(+1\) when it begins, and by \(-1\) when it ends. For example, when an activity corresponds to a visit operation, and the resource corresponds to a truck, the activity level of the resource will be decreased by 1 at the beginning of the visit, and increased by 1 at the end.

Schedule domains

The timeline on which activities are scheduled, is the so-called schedule domain. A schedule domain is a finite set of timeslots. Each activity and resource has its own schedule domain.

The problem schedule domain

The schedule domain of the entire problem, the problem schedule domain, is a named superset of each of these schedule domains. Unless overridden, it is based on the schedule domains of the activities and resources.

Handling schedule domains

An activity is only considered active during a timeslot \(t\) if \(t\) is in the schedule domain of that activity, and it is in the schedule domain of each resource for which it is scheduled. Thus, for each individual activity, AIMMS passes the intersection of these schedule domains to the constraint programming solver.

Additional restrictions

Most scheduling problems contain several side constraints in addition to the resource constraints. Examples include precedence relations between activities, release dates or deadlines, and sequence-dependent setup times. Such constraints can be specified using global scheduling constraints or in the attribute forms of activities and resources. Constraint programming solvers can take an extra algorithmic advantage of such constraints when they are presented in this manner.

Activity

On the one hand, an activity can be seen as consisting of five variables that can be accessed by the suffixes: .Begin, .End, .Length, .Size and .Present. These variables represent the begin, end, length (difference between end and begin), size (number of active slots) and presence of an activity. These variables can be used inside constraints, for example myActivity.End <= myDeadLine+1. On the other hand, an activity is defined using its attributes as presented in this table. We will first discuss the attributes of an activity, and then these suffixes in more detail.

Attribute	Value-type	See also page
IndexDomain	index-domain	Index domain for variables
ScheduleDomain	set range or expression
Property	Optional, NoSave
Length	expression
Size	expression
Priority	reference	The Priority attribute
Text	string	The Text and Comment attributes
Comment	comment string	The Text and Comment attributes

The ScheduleDomain attribute

The activity is scheduled in time slots in the ScheduleDomain. This is an expression resulting in a one-dimensional set, or a set-valued range. The resulting set need not be a subset of the predeclared set Integers; it can be any one-dimensional set, for instance a Calendar, see Calendars. Consider the following examples of the attribute schedule domain:

Activity a {
    ScheduleDomain  :  yearCal;
    Comment         : {
        "a can be scheduled during any period
        in the calendar yearCal"
     }
Activity b {
    IndexDomain     :  i;
    ScheduleDomain  :  possiblePeriods(i);
    Comment         : {
        "b(i) can be scheduled only during the
        periods possiblePeriods(i)"
     }
Activity c {
    IndexDomain     :  i;
    ScheduleDomain  : {
        {ReleaseDate(i)..PastDeadline(i)}
    }
    Comment         : {
        "c(i) must start on or after ReleaseDate(i)
         c(i) must finish before PastDeadline(i)"
     }

The ScheduleDomain attribute is mandatory.

Singleton schedule domain

An activity with a singleton schedule domain and a length of 1 can be used to model an event. Such an activity is scheduled during the single element in the schedule domain. Because the schedule domain is a single element, the value of the suffixes .Begin and .End of the activity will be set to that single element and the element thereafter respectively in a feasible solution. Note that this is possible for all elements except for the last element in the problem schedule domain; a nonzero length would then require the .End to be after the problem schedule domain. Consider the following example:

Activity weekendActivities {
    IndexDomain     : {
        d | ( TimeslotCharacteristic( d, 'weekday' ) = 6 or
        TimeslotCharacteristic( d, 'weekday' ) = 7    ) and
        d <> last( dayCalendar )
    }
    ScheduleDomain  : {
        { d .. d }
    }
    Length          :  1;
    Comment         :  "d is an index in a calendar""}

Scheduling the activity weekendActivities in a sequential resource will block other activities for that resource during the weekend.

The Property attribute

An activity can have the properties Optional, Contiguous and NoSave.

Optional

When an activity has the property Optional, it may or may not be scheduled. If the property Optional is not specified, then the activity will always be scheduled.

Contiguous

When an activity has the property Contiguous, all elements from .Begin up to but not including .End in the problem schedule domain must be in its own schedule domain.

NoSave

When an activity has the property NoSave, it will not be saved in cases.

This attribute is not mandatory.

The Length and Size attributes

When an activity is present, the Length attribute defines the length of the activity, and the Size attribute defines its size. The length of an activity is the difference between its end and its begin. The size of an activity is the number of periods, in which that activity is active from begin up to but not including its end. For example, a non-contiguous activity which .Begins on Friday, .Ends on Tuesday, and is not active during the weekend has a

• .Length of 4 days, and

• .Size of 2 days.

The numeric expressions entered at the Length and Size attributes may involve other discrete variables. These attributes are not mandatory.

For a contiguous activity we have that the .Length is equal to the .Size. Conversely, with a constraint a.Length=a.Size we have that a is contiguous, but the propagation may be less efficient.

The Priority attribute

The Priority attribute applies to all the discrete variables defined by an activity. To these variables it has the same meaning as for integer variables, see page The Priority attribute. This attribute is not mandatory.

The suffixes of activities

An activity is made up of the following suffixes .Begin, .End, .Length, .Size and .Present. Each of these suffixes is a discrete variable and can be used in constraints.

The suffixes .Begin and .End

The suffixes .Begin and .End are element valued variables. When scheduled, the activity takes place from period .Begin up to but not including period .End. For a present activity a, in a feasible solution:

• a.Begin is an element in the schedule domain of the activity. The range of this element variable is the smallest named set encompassing the activity schedule domain.

• a.End is an element in the schedule domain of the problem, and, depending on the .Length of a, with the following additional requirement:

  • When the length of activity a is zero, a.End=a.Begin holds, and they are both in the activity schedule domain.

  • When the length of activity a is greater than 0, the element before a.End is in the activity schedule domain.

  The range of this element variable is the root set of the activity schedule domain.

Comparison of the .Begin and .End suffixes of two activities a and b inside a constraint definition will take place on the problem schedule domain, for instance in a constraint like a.End <= b.Begin. Outside constraint definitions these suffixes follow the rules of element comparison specified in Set and Element Comparison.

The suffixes .Length and .Size

The suffixes .Length and .Size are nonnegative integer variables. The .Length of an activity is defined as .End - .Begin. The .Size of an activity is the number of timeslots in the schedule domain of the activity in the range [.Begin, .End). When the attribute Length or Size is non-empty, AIMMS will generate a defining constraint for the suffix .Length resp. .Size like the definition attribute of a variable, see The Definition attribute. When the schedule domain of an activity is a calendar or a subset thereof, the unit of each of the .Length and .Size suffixes is the unit of the calendar.

The suffix .Present

The suffix .Present is a binary variable with default 0. For optional activities this variable is 1 when the activity is scheduled and 0 when it is not. For non-optional activities this variable is initialized with the value 1.

suffixes of absent activities in constraints

The value of one of the suffixes .Begin, .End, .Length, and .Size is not defined when the corresponding activity is absent. However, in order to satisfy constraints where such a suffix is used for an absent activity, a value is chosen: the socalled absent value. For the suffixes .Length, and .Size, the absent value is 0. For the suffixes .Begin and .End this depends on the problem schedule domain:

• If the problem schedule domain is a subset of Integers, the absent value is 0.

• Otherwise, the absent value of the suffixes .Begin and .End is ".

To override the absent value use one of the following functions:

• cp::ActivityBegin,

• cp::ActivityEnd,

• cp::ActivityLength, or

• cp::ActivitySize.

Suffixes of optional activities in constraints

The value of the suffix .present is defined for an absent activity as 0. However the values of the other suffixes of an absent activity are not defined. To enable the constraining of the values of those suffixes in constraints several formulation alternatives are available. As an example of these alternatives, consider an activity act whereby we want to enforce its length to be 7 if it is present.

1. Enforce the length constraint conditionally on the presence of activity act:

   if  act.present then
       act.length = 7
   endif
   

2. The cp::ActivityLength function returns the length of a present activity or its second argument if it is not present:

   cp::ActivityLength( act, 7 ) = 7
   

3. If we simply want to set the value of the .Length or .Size suffix, we can use the Length or Size attribute as follows.

   Activity act {
       ScheduleDomain  :  ...;
       Property        :  optional;
       Length          :  7;
   }
   

Each of the above formulation alternatives has its own merits.

1. The merit of this alternative is that it is general and can also be used to state for instance that the length of act is 7 or 11 when present:

   if  act.present then
       act.Length = 7 or act.Length = 11
   endif
   

2. The merit of this alternative is that it allows the solver to make stronger propagations and thus potentially reduce solution time.

3. The merit of this alternative is that is does not force the model builder to take the optionality of act into account when defining its length. AIMMS will make sure the length definition is translated to alternative 1 or 2 as appropriate.

Solution values of absent activities

The value of the suffixes .Begin, .End, .Length, and .Size of an absent activity in a feasible schedule are meaningless and should not be used in further computations.

Absent versus 0-length activities

Even though no work is done for both absent and 0-length activities, there is a difference in their usage. Let us consider the following two examples:

• Selection of an activity from alternatives; Consider a collection of activities from which we need to select one. This is easily and efficiently achieved by setting the property Optional to the activity. The ones not selected become absent in a solution.

• Consider two collections of activities, whereby the \(n\) activities in the first collection all need to be completed before the \(m\) activities in the second collection can start. We can model this directly by \(n\times{}m\) precedence constrains. Another way to model this is by introducing an extra activity, say Milestone, of length zero. With this Milestone we only need \(n+m\) precedence constraints.

To facilitate above and other examples of scheduling, the suffixes .Present and .Length are supported independently.

Relation between suffixes of activities

Please note, for an activity act, the following relation is implicitly defined:

if act.Present then
   act.Begin + act.Length = act.End
endif
if act.Present then
   act.Size <= act.Length
endif

Resource

A resource schedules activities by acting as a constraint on the activities it schedules. A feasible resource requires the above implicit constraints on the suffixes of the activities it schedules and the constraints implied by its attributes as discussed below.

Attribute	Value-type	See also page
IndexDomain	index-domain	Index domain for variables
Usage	Parallel or Sequential
ScheduleDomain	set range or expression	The ScheduleDomain attribute
Activities	collection of activities
Property	NoSave
GroupSet	a reference to a set
GroupDefinition	activity : expression
GroupTransition	index domain : expression
Transition	set of reference pair : expression
FirstActivity	reference
LastActivity	reference
ComesBefore	set of reference pairs
Precedes	set of reference pairs
Unit	unit-valued expression	The Unit attribute, The Unit attribute
LevelRange	numeric range
InitialLevel	reference
LevelChange	per activity : expression
BeginChange	per activity : expression
EndChange	per activity : expression
Text	string	The Text and Comment attributes
Comment	comment string	The Text and Comment attributes

A resource is defined using the attributes presented in this table.

The Usage attribute

A resource can be used in two ways: Parallel, and Sequential, of which precisely one must be selected. The resource usage is then as follows

Sequential

Defines the resource to be used sequentially. Such a resource is also known as a unary or disjunctive resource. A sequential resource has the additional attributes Transition, FirstActivity, LastActivity, ComesBefore, and Precedes, see Sequential Resources.

Parallel

Defines the resource to be used in parallel. Such a resource is also known as a cumulative resource. A parallel resource has the additional attributes LevelRange, InitalLevel, LevelChange, BeginChange, and EndChange, see Parallel Resources.

The Usage attribute is mandatory; either Sequential or Parallel must be selected.

The ScheduleDomain attribute

The resource is affected by activities during the periods set in its schedule domain. This is an expression resulting in a one-dimensional set, or a set-valued range. AIMMS verifies that the schedule domain of the resource matches the schedule domain of all activities it is affected by. Here, two sets match if they have a common super set.

When the intersection of the schedule domain of a resource and the schedule domain of a non-optional activity are empty, the result is an infeasible schedule.

The Activities attribute

The Activities attribute details the activities affecting the resource. This adheres to the syntax:

activity-selection:

as illustrated in the example below:

Resource myMachine {
    ScheduleDomain  :  H;
    Usage           :  ...  ! sequential or parallel;
    Activities      : {
        maintenance,  ! Maintenance is scheduled between actual jobs.
        simpleJob(i), ! Every simple job can be done on this machine.
        specialJob(j) : jobpos(j) ! Only selected special jobs are allowed.
    }
}

In this example, the activities maintenance and simpleJob can affect the resource myMachine. However, the activity specialJob(j) can only affect the resource when jobpos(j) is non-zero. Only the detailed activities can be used in the attributes that follow. The Activities attribute is mandatory.

The Property attribute

A resource can have the properties: NoSave and TransitionOnlyNext.

• When the property NoSave is set, this indicates that the resource data will not be saved in cases.

• The property TransitionOnlyNext is relevant to the attributes Transition and GroupTransition of sequential resources only, and is discussed after the GroupTransition attribute below.

The attribute Property is not mandatory.

Sequential Resources

Sequential resources

Sequential resources are used to schedule activities that are not allowed to overlap. Those workers and machines that can only handle one activity at a time are typical examples. A sequential resource has only one suffix, namely .ActivityLevel. A sequential resource is active when it is servicing an activity, and then its .ActivityLevel is 1. When a sequential resource is not active, or idle, its .ActivityLevel is 0. The attributes particular to sequential resources are discussed below. The .ActivityLevel suffix cannot be used in constraint definitions.

The Transition attribute

The Transition attribute is only available to sequential resources, and then only if the GroupSet attribute has not been specified. This attribute contains a matrix between activities a and b, specifying the minimal time between a and b if a is scheduled before b. One example of using this attribute is to model traveling times, when jobs are executed at different locations. Another example of using this attribute is to model cleaning times of a paint machine, when the cleaning time depends on the color used during the previous job. All entries of this matrix are assumed to be 0 when not specified. If the schedule domain is a calendar, the unit of measurement is the time unit of the schedule domain; otherwise the unit of measurement is unitless. This matrix can, but need not, be symmetric. In the constraint programming literature, this attribute is also called sequence-dependent setup times or changeover times. The syntax for this attribute is as follows:

activity-transition:

An example of a transition specification is:

Resource myMachine {
    ScheduleDomain  :  H;
    Usage           :  sequential;
    Activities      :  acts(a), maintenance;
    Transition      : {
        (acts(a1),acts(a2))    : travelTime(a1,a2),
        (maintenance,acts(a1)) : travelTime('home',a1),
        (acts(a1),maintenance) : travelTime(a1,'home')
    }
    Comment         : {
        "activities acts are executed on location/site; yet
        maintenance is executed at home.  Transitions are
        the travel times between locations."
     }

The Transition attribute is not mandatory.

The GroupSet attribute

The GroupSet attribute is only available to sequential resources. The elements of this set name the groups into which the activities can be divided. This attribute is not mandatory.

The GroupDefinition attribute

The GroupDefinition attribute is only available when the GroupSet attribute has been specified. It contains a mapping of activities to group set elements. This mapping is essential for the GroupTransition attribute and for the intrinsic functions cp::GroupOfNext and cp::GroupOfPrevious. The syntax is as follows:

group-definition:

This attribute is mandatory when the GroupSet attribute has been specified.

The GroupTransition attribute

The GroupTransition attribute is used to specify the transition times/sequence dependent setup times between activities in a compressed manner. This attribute is only available when the GroupSet attribute has been specified. The syntax is:

activity-group-transition:

Consider an application where each city has to be visited by a car on multiple occasions, to bring goods being produced in one city to another city where they are consumed. The first product is consumed before the last product is produced:

Activity VisitCity {
    IndexDomain      :  (car,city,iter);
    ScheduleDomain   :  Timeline;
    Property         :  Optional;
}
Resource carEnRoute {
    Usage            :  sequential;
    IndexDomain      :  car;
    ScheduleDomain   :  TimeLine;
    Activities       :  VisitCity(car,city,iter);
    GroupSet         :  Cities;
    GroupDefinition  :  VisitCity(car,city,iter) : city;
    GroupTransition  :  (cityFrom,cityTo) : CityDistance(cityFrom,cityTo);
}

In this example, the group transition matrix is defined for each combination of cities, which is significantly smaller than an equivalent transition matrix defined for each possible combination of activities would have been. This not only saves memory, but may also save a significant amount of solution time as some Constraint Programming solvers check whether the triangular inequality holds at the start of the solution process in order to determine the most effective reasoning available to that solver. The GroupTransition attribute is not mandatory.

Property TransitionOnlyNext

The attributes Transition and GroupTransition specify the minimal time between two activities a1 and a2 if a1 comes before a2. By specifying the property TransitionOnlyNext, these attributes are limited to specify only the minimal distances between two activities a1 and a2 if a1 precedes a2. An activity a1 precedes a2, if there is no other activity b scheduled between a1 and a2. In the example that follows, a, b, and c are all activities of length 1.

Resource seqres {
    Usage           :  sequential;
    ScheduleDomain  :  timeline;
    Activities      :  a, b, c;
    Property        :  TransitionOnlyNext;
    Transition      :  (a,b):1, (b,c):1, (a,c):7;
    Precedes        :  (a,b), (b,c);
}

Minimizing c.End, the solution is:

a.Begin := 0 ; a.End := 1 ;
b.Begin := 2 ; b.End := 3 ;
c.Begin := 4 ; c.End := 5 ;

By omitting the TransitionOnlyNext property, the minimal distance between a and c is taken into account, and the solution becomes:

a.Begin := 0 ; a.End := 1 ;
b.Begin := 2 ; b.End := 3 ;
c.Begin := 8 ; c.End := 9 ;

The Sequencing attributes

The attributes FirstActivity, LastActivity, ComesBefore, and Precedes are collectively called sequencing attributes. They are used to place restrictions on the sequence in which the activities are scheduled. These attributes are only available to sequential resources.

FirstActivity

When specified, this has to be a reference to a single activity. When this activity is present, it will be the first activity in a feasible solution.

LastActivity

When specified, this has to be a reference to a single activity. When this activity is present, it will be the last activity in a feasible solution.

ComesBefore

This is a list of activity pairs (a,b). A pair (a,b) in this list indicates that activity a comes before activity b in a feasible solution. There may be another activity c that is scheduled between a and b in a feasible solution. This constraint is only enforced when both a and b are present.

Precedes

This is a list of activity pairs (a,b). A pair (a,b) in this list indicates that activity a precedes activity b in a feasible solution. There can be no other activity c scheduled between a and b in a feasible solution, but a gap between a and b is allowed. This constraint is only enforced when both a and b are present.

The syntax of the attributes FirstActivity and LastActivity is simply a reference to a single activity and so the syntax diagram is omitted here. The syntax diagram for the attributes ComesBefore and Precedes is more interesting:

activity-sequence:

If, following the above syntax diagram, an expression is omitted, it is taken to be 1. An example illustrating all the sequencing attributes is presented below:

Resource myMachine {
    ScheduleDomain  :  H;
    Usage           :  sequential;
    Activities      :  setup(a), finish(a);
    FirstActivity   :  setup('warmingUp');
    LastActivity    :  finish('Cleaning');
    ComesBefore     :  (setup(a1),setup(a2)) : taskbefore(a1,a2);
    Precedes        :  (setup(a),finish(a));
}

None of the sequencing attributes are mandatory.

Parallel Resources

Parallel resources model and limit the resource consumption and resource production of activities that take place in parallel. Examples of parallel resources could be monetary budget and truck load.

.ActivityLevel suffix

A parallel resource has only one suffix, namely .ActivityLevel. This suffix is only affected by scheduled activities. The limits on the .ActivityLevel suffix, its initialization, and how it is affected by executed activities is discussed below in the parallel resource specific attributes.

The LevelRange attribute

The LevelRange attribute states the range for the activity level of a parallel resource. The maximum value represents the capacity of the resource. It cannot be specified per element in the schedule domain of the resource. The syntax of this attribute is similar to the syntax of the Range attribute for bounded integer variables.

Resource myMachine {
    IndexDomain     :  m;
    ScheduleDomain  :  h;
    Usage           :  parallel;
    Activities      :  act(a);
    LevelRange      :  {
        {minlev(m) .. maxlev(m)}
    }
}

The LevelRange attribute is only applicable for parallel resources, and for such a resource it is mandatory.

The InitialLevel attribute

The InitialLevel attribute defines the initial value of the .ActivityLevel suffix. if it is not specified, the .ActivityLevel suffix is initialized to 0. The InitialLevel attribute is not mandatory.

Resource AvailableBudget {
    ScheduleDomain  :  Hor;
    Usage           :  parallel;
    Activities      :  act(a);
    LevelRange      :  {0 .. 10000};
    InitialLevel    :  5000;
    Comment         :  "we have a starting budget of 5000""}

The .ActivityLevel modification attributes

The attributes LevelChange, BeginChange, and EndChange are collectively called .ActivityLevel modification attributes.

• An activity in the LevelChange attribute generates a pulse: at the .Begin of the activity the .ActivityLevel of the resource is increased by the indicated amount; at the .End of the activity that suffix is decreased by the same amount.

• An activity in the BeginChange attribute increases the .ActivityLevel of the resource at the .Begin of the activity by the indicated amount.

• An activity in the EndChange attribute increases the .ActivityLevel of the resource at the .End of the activity by the indicated amount.

Note that not only can the indicated amount be a positive or negative integer, it can also be an integer variable. The effect of an activity on the .ActivityLevel is illustrated in the Fig. 9. The syntax of these attributes is as follows:

level-modification:

Fig. 9 Changes to the suffix .ActivityLevel of a resource

The next example illustrates the use of the .ActivityLevel modification attributes:

Resource Budget {
    ScheduleDomain  :  Days;
    Usage           :  parallel;
    Activities      :  Act(i), Alt_Act(j), Deposit_Act(d);
    LevelRange      :  [0, 100];
    LevelChange     :  Alt_Act(i)    : -alt_act_budget(i);
    BeginChange     : {
        Deposit_Act(d): Deposit(d),
        Act(i)        : -ActCost(i)
    }
    EndChange       :  Act(i)        : Profit(i);
}

In this example, Deposit_Act can be modeled as an activity with a schedule domain containing only one element (an event), see Singleton schedule domain. None of the .ActivityLevel modification attributes are mandatory, but when none of them is specified the resource is either infeasible or ineffective. When the .ActivityLevel is outside the range of a parallel resource, that resource is infeasible.

Activity level and schedule domain

The .ActivityLevel suffix is not affected by holes in the schedule domain of scheduled activities. Fig. 10 illustrates the effect of activities A and B with a level change of 1 on the resource cash. The activity A has its .Begin set to Friday, its .End set to Tuesday and it is not scheduled in the weekend. The activity B is scheduled in the weekend.

Fig. 10 Two activities scheduled on a parallel resource

Functions on Activities and Scheduling Constraints

Precedence constraints

The suffixes of an activity are variables, and they can be used in the formulation of constraints. Below there follows an example of a simple linear constraint which states that at least a pause of length restTime should be observed after activity a is completed before activity b can start.

a.End + restTime <= b.Begin

Precedence on optional activities

Consider again the inequality above, but now for optional activities a and b. When a is absent, the minimum value of a.End is meaningless but its minimum is 0 and b is present, this will enforce b to start after restTime. This may or may not be the intended effect of the constraint. Enforcing such constraints only when both activities a and b are present, the scheduling constraint cp::EndAtStart(a,b,restTime) can be used. This constraint is semantically equivalent to:

if a.Present and b.Present then
   a.End + restTime = b.Begin
endif

Here restTime is an integer valued expression that may involve variables. Note that the scheduling constraint can be exploited more effectively during the solving process than the equivalent algebraic formulation. A list of available scheduling constraints for precedence relations is given in this table.

Table 57 Constraints for scheduling

Precedence Relations
	When activities \(a\) and \(b\) are present
	and for a non-negative integer delay \(d\)
cp::BeginBeforeBegin( \(a\), \(b\), \(d\))	\(a{\texttt{.Begin}} + d \leq b{\texttt{.Begin}}\)
cp::BeginBeforeEnd( \(a\), \(b\), \(d\))	\(a{\texttt{.Begin}} + d \leq b{\texttt{.End}}\)
cp::EndBeforeBegin( \(a\), \(b\), \(d\))	\(a{\texttt{.End}} + d \leq b{\texttt{.Begin}}\)
cp::EndBeforeEnd( \(a\), \(b\), \(d\))	\(a{\texttt{.End}} + d \leq b{\texttt{.End}}\)
cp::BeginAtBegin( \(a\), \(b\), \(d\))	\(a{\texttt{.Begin}} + d = b{\texttt{.Begin}}\)
cp::BeginAtEnd( \(a\), \(b\), \(d\))	\(a{\texttt{.Begin}} + d = b{\texttt{.End}}\)
cp::EndAtBegin( \(a\), \(b\), \(d\))	\(a{\texttt{.End}} + d = b{\texttt{.Begin}}\)
cp::EndAtEnd( \(a\), \(b\), \(d\))	\(a{\texttt{.End}} + d = b{\texttt{.End}}\)
Scheduling Constraints	Interpretation
cp::Span( \(g\), \(i\), \(a_i\))	The activity \(g\) spans the activities \(a_i\)
	\(g{\texttt{.Begin}} = \min_i a_i{\texttt{.Begin}} \wedge\)
	\(g{\texttt{.End}} = \max_i a_i{\texttt{.End}}\)
cp::Alternative( \(g\), \(i\), \(a_i\))	Activity \(g\) is the single selected activity \(a_i\)
	\(\exists j: g=a_j \wedge \forall k, j\neq k: a_k{\texttt{.present}}=0\)
cp::Synchronize( \(g\), \(i\), \(a_i\))	If \(g\) is present, all present activities \(a_i\)
	are scheduled at the same time.
	\(g{\texttt{.present}} \Rightarrow (\forall i: a_i{\texttt{.present}} \Rightarrow g=a_i\))

Table 58 Functions for scheduling

Limiting activity suffixes taking absence into account
	\(a\) is the activity
	\(d\) the absence value
cp::ActivityBegin( \(a\), \(d\))	Return begin of activity
cp::ActivityEnd( \(a\), \(d\))	Return end of activity
cp::ActivityLength( \(a\), \(d\))	Return length of activity
cp::ActivitySize( \(a\), \(d\))	Return size of activity
Adjacent Activity
	\(r\) is the resource
	\(s\) is the scheduled activity
	\(e\) is extreme value (when \(s\) is first or last)
	\(a\) is absent value (\(s\) is not scheduled)
cp::BeginOfNext( \(r\), \(s\), \(e\), \(a\))	Beginning of next activity
cp::BeginOfPrevious( \(r\), \(s\), \(e\), \(a\))	Beginning of previous activity
cp::EndOfNext( \(r\), \(s\), \(e\), \(a\))	End of next activity
cp::EndOfPrevious( \(r\), \(s\), \(e\), \(a\))	End of previous activity
cp::GroupOfNext( \(r\), \(s\), \(e\), \(a\))	Group of next activity, see also The GroupDefinition attribute
cp::GroupOfPrevious( \(r\), \(s\), \(e\), \(a\))	Group of previous activity
cp::LengthOfNext( \(r\), \(s\), \(e\), \(a\))	Length of next activity
cp::LengthOfPrevious( \(r\), \(s\), \(e\), \(a\))	Length of previous activity
cp::SizeOfNext( \(r\), \(s\), \(e\), \(a\))	Size of next activity
cp::SizeOfPrevious( \(r\), \(s\), \(e\), \(a\))	Size of previous activity

Global scheduling constraints

In addition to these precedence constraints and the constraints that are defined by resources, AIMMS offers several other global constraints that are helpful in modeling scheduling problems. this table presents the global scheduling constraints and functions available in AIMMS. These constraints are based on activities and can be used to represent hierarchical planning problems (cp::Span), to schedule activities over alternative resources (cp::Alternative), and to synchronize the execution of multiple activities (cp::Synchronize).

Functions on activities

There are several functions available that provide control over the value to be used for the suffixes of activities in the case of absence. In addition, there are functions available for relating adjacent activities on a resource. this table lists the functions available that operate on activities. As an example, consider a model whereby the length of two adjacent jobs is limited:

Set Timeline {
    Index           :  tl;
}
Set Jobs {
    Index           :  j;
}
Parameter JobLen {
    IndexDomain     :  j;
}
Activity doJob {
    IndexDomain     :  j;
    ScheduleDomain  :  Timeline;
    Length          :  Joblen(j);
}
Resource aWorker {
    Usage           :  sequential;
    ScheduleDomain  :  Timeline;
    Activities      :  doJob(j);
}
Constraint LimitLengthTwoAdjacentJobs {
    IndexDomain     :  j;
    Definition      : {
        cp::ActivityLength(doJob(j),0) +
        cp::LengthOfNext(aWorker,doJob(j)) <= 8
    }
}

In the constraint LimitLengthTwoAdjacentJobs we take the length of job via the function cp::ActivityLength and the length of the next job for resource aWorker via the function cp::LengthOfNext. In the above constraint, the use of the function cp::ActivityLength is not essential because activity doJob is not optional. We can use the suffix notation instead and the constraint becomes:

Constraint LimitLengthTwoAdjacentJobs {
    IndexDomain     :  j;
    Definition      : {
        doJob(j).Length +
        cp::LengthOfNext(aWorker,doJob(j)) <= 8
    }
}

Problem Schedule Domain

The problem schedule domain of a mathematical program is a single named set containing all timeslots referenced in the activities, resources and timeslot valued element variables of that mathematical program. For the activities to be scheduled, we are usually interested in when they take place in real time; the mapping to real time is an ingredient of the solution. An exception might be if we are interested in the process of scheduling instead of its results. In that case, a contiguous subset of the Integers suffices. Contiguous subsets of Integers are supported by AIMMS, but not considered in the remainder of this subsection.

Real world representations

The problem schedule domain represents the period of time on which activities are to be scheduled. This portion of time is discretized into timeslots. Consider the following three use cases for a problem schedule domain.

1. The first use case is probably the most common one; the distance in time between two consecutive timeslots is constant. This distance is equal to a single unit of time. As an example, consider an application that constructs a maintenance scheme for playing fields. Two consecutive line painting activities should not be scheduled too close or too far from each other. Similarly for other consecutive activities of the same type such as garbage pickup. In this use case the distance in time between two consecutive timeslots is meaningful. A Calendar is practical for this use case.

2. The second use case is the one in which the distance in time between two consecutive timeslots is not constant. As an example, consider an application that constructs a sequence of practice meetings for teams with a limited number of playing fields available. The set of available dates is based on the team member availability, and the distance in time between two consecutive time slots may vary. An important restriction for this application is that two meetings with the same type of practice should be some number of meetings apart. In addition, we want to avoid, for each team, peaks and big holes in exercise dates by limiting the number of exercise dates skipped between two consecutive exercises.

3. The third use case is a combination of the other two use cases. The problem schedule domain is again one whereby the distance in time between two consecutive timeslots is constant. In addition, there are subsets of this problem schedule domain which apply to selected activities and resources. As an example, consider an application that schedules both maintenance activities and team practice sessions on a set of playing fields.

The above use cases are illustrated in AIMMS below.

Use case 1: constant distance

In the first use case as illustrated by the example below, the problem schedule domain is the calendar yearCal. Two consecutive timeslots in that calendar have the fixed distance of 1 day. The activity FieldMaintenance models that there are various types of maintenance activities to be scheduled for the various fields, and each type of maintenance may occur more than once. The two constraints in this example restrict the minimal and maximal distance between consecutive maintenance activities of the same type on the same field.

Calendar yearCal {
    Index           :  d;
    Unit            :  day;
    BeginDate       :  "2012-01-01";
    EndDate         :  "2012-12-31";
    TimeslotFormat  :  "%c%y-%sm-%sd";
}
Activity FieldMaintenance {
    IndexDomain     :  (pf, mt, occ);
    ScheduleDomain  :  yearCal;
    Property        :  Optional;
    Length          :  1[day];
    Comment         : {
        "Maintenance on
        playing field     pf
        maintenance type  mt
        occurrence       occ"
     }
Constraint maintenanceMinimalDistance {
    IndexDomain     :  (pf, mt, occ) | occ <> first( occurrences );
    Text            :  "at least 7 days apart.";
    Definition      : {
        cp::BeginBeforeBegin( FieldMaintenance(pf, mt, occ-1),
        FieldMaintenance(pf, mt, occ), 7 )
    }
}
Constraint maintenanceMaximalDistance {
    IndexDomain     :  (pf, mt, occ) | occ <> first( occurrences );
    Text            :  "at most 14 days apart.";
    Definition      : {
        cp::BeginBeforeBegin( FieldMaintenance(pf, mt, occ),
        FieldMaintenance(pf, mt, occ-1), -14 )
    }
}

Use case 2: varying distance

For the second use case, the same calendar yearCal is declared as in the first use case, in order to relate to real time. We are interested in only a selection of the dates available, and a subset exerciseCal is created from this calendar. In order to remove the fixed distance from the timeslots, the elements in exerciseCal are copied to exerciseDates.

Calendar yearCal {
    ...
}
Set  exerciseCal {
    SubsetOf        :  yearCal;
    Index           :  yc;
}
Set exerciseDates {
    Index           :  ed;
    Comment         :  "Constructed in ...""}

A simple way of copying the elements with their names from exerciseCal to exerciseDates is in the code fragment below.

Empty exerciseDates ;
for yc do
    exerciseDates += StringToElement(exerciseDates,
                    formatString("%e",yc), create:1 );
endfor ;

Now that we have the set of exercise dates without a time unit associated, we can use it to declare exercise activities for each team and enforce a minimal distance between exercises of the same type as illustrated below. This minimal distance will now be enforced using a sequential resource and counting the number of times a particular exercise type occurred.

Set exerciseTypes {
    Index           :  et;
}
Activity gExerciseTeam {
    IndexDomain     :  (tm,occ);
    ScheduleDomain  :  exerciseDates;
    Length          :  1;
    Comment         : {
        "occ in Occurrencs, defining the number of times
        team tm has to exercise"
     }
Resource teamExercises {
    Usage           :  sequential;
    IndexDomain     :  tm;
    ScheduleDomain  :  exerciseDates;
    Activities      :  gExerciseTeam(tm, occ);
    Precedes        :  (gExerciseTeam(tm, occ1),gExerciseTeam(tm, occ2)):occ1=occ2-1;
    Comment         :  "Purpose: determine when a team may exercise""}
Activity exerciseTeam {
    IndexDomain     :  (tm,et,occ);
    ScheduleDomain  :  exerciseDates;
    Property        :  optional;
    Length          :  1;
}

Constraint oneExerciseType {
    IndexDomain     :  (tm,occ);
    Definition      : {
        cp::Alternative(
        globalActivity  :  gExerciseTeam(tm, occ),
        activityBinding :  et,
        subActivity     :  ExerciseTeam(tm, et, occ))
    }
    Comment         :  "Purpose: select a single type of exercise""}
Constraint doingAnExerciseTypeAtMostOnceOverOccurrences {
    IndexDomain     :  (tm,et,occ) | occ <> first( occurrences );
    Definition      : {
        sum( occ1 | occ1 <= occ and occ1 < occ + 2,
        ExerciseTeam(tm, et, occ).Present ) <= 1
    }
    Comment         : {
        "Purpose: the same type of exercise should be some
        exercises apart"
     }
Constraint avoidSmallHolesBetweenExercises {
    IndexDomain     :  (tm,occ) | occ <> first( occurrences );
    Text            :  "at least minHoleSize exercise dates apart.";
    Definition      : {
        cp::EndBeforeBegin( gExerciseTeam(tm, occ-1),
        gExerciseTeam(tm, occ), minHoleSize )
    }
}
Constraint avoidBigHolesBetweenExercises {
    IndexDomain    :  (tm,occ) | occ <> first( occurrences );
    Text            :  "at most maxHoleSize exercise dates apart.":
    Definition      : {
        cp::BeginBeforeEnd( gExerciseTeam(tm, occ),
        gExerciseTeam(tm, occ-1), -maxHoleSize )
    }
}

Use case 3: combination

There can be only one problem schedule domain per mathematical program; we use the one from the first use case as it encompasses the one from the second use case. Thus we need to adapt the schedule domains of selected activities and resources to the following:

Activity gExerciseTeam {
    IndexDomain     :  (tm,occ);
    ScheduleDomain  :  exerciseCal ! modified;
    Length          :  1[day]      ! modified;
}
Resource OneExercise {
    Usage           :  sequential;
    IndexDomain     :  tm;
    ScheduleDomain  :  exerciseCal ! modified;
    Activities      :  gExerciseTeam(tm, occ);
    Precedes        :  (gExerciseTeam(tm, occ1),gExerciseTeam(tm, occ2)):occ1=occ2-1;
    Comment         :  "Purpose: determine when a team may exercise""}
Activity exerciseTeam {
    IndexDomain    :  (tm,et,occ);
    ScheduleDomain  :  exerciseCal ! modified;
    Property        :  optional;
    Length          :  1[day]      ! modified;
}

The constraints oneExerciseType and doingAnExerciseTypeAtMostOnceOverOccurrences can be left unchanged as they are not dependent on the distance between timeslots. The constraints avoidSmallHolesBetweenExercises and avoidBigHolesBetweenExercises is dependent on the distance between elements of exerciseDates and will now have to be remodeled. By using the fact that the .Size refers to the number of elements in the schedule domain of an activity between its .Begin and .End and that we can define an activity that encompasses a hole by spanning the previous exercise and the current one, the remodeling is done as follows:

Activity encompassHoleBetweenExercises {
    IndexDomain     :  (tm,occ)|occ <> first(occurrences);
    ScheduleDomain  :  exerciseCal;
}
Constraint defineEncompassHoleBetweenExercises {
    IndexDomain     :  (tm,occ)|occ <> first(Occurrences);
    Definition      : {
        cp::Span(
        globalActivity  :  encompassHoleBetweenExercises(tm, occ),
        activityBinding :  occ1 | occ1 = occ or occ1 = occ-1,
        subActivity     :  gExerciseTeam(tm, occ1))
    }
}
Constraint maxSizeEncompassingActivity {
    IndexDomain     :  (tm,occ)|occ <> first(Occurrences);
    Definition      : {
        encompassHoleBetweenExercises(tm,occ).size <=
        (maxHoleSize + 2)[day]
    }
}
Constraint minSizeEncompassingActivity {
    IndexDomain    :  (tm,occ)|occ <> first(Occurrences);
    Definition     : {
        encompassHoleBetweenExercises(tm,occ).size >=
        (minHoleSize + 2)[day]
    }
}

comparing use cases 2 and 3

Only when the distance in real time is not relevant to an application, the representation chosen for use case 2 has the following advantages over the representation chosen for use case 3:

• The limiting of the size of a hole is formulated more directly using the cp::EndBeforeBegin and cp::BeginBeforeEnd than one using an additional activity leading to a formulation that is easier to understand.

• We not only lose the power of propagation provided by the global constraints cp::EndBeforeBegin and cp::BeginBeforeEnd in use case 3, but we also introduce another activity, and thus additional variables, which increases the search space thereby decreasing the perfomance further.

• The set exerciseDates is smaller than the set yearCal. It is generally a good idea to keep the sets used as ranges for element variables small including the schedule domain to be considered.

This concludes the discussion on multiple use cases for problem schedule domains.

The attribute ScheduleDomain of a mathematical program

When an application contains activities, the attribute ScheduleDomain becomes available to a mathematical program declared in that application. Unlike the attribute with the same name for activities and resources, only a single named one-dimensional set can be filled in here. If this attribute is filled in, with, say Timeline, then AIMMS will ensure that each activity and resource has a schedule domain that is a subset of Timeline. In addition, for each element variable with a range say, selectedMoments, where Timeline and selectedMoments have the same root set, AIMMS will verify that selectedMoments is a subset of Timeline. In addition, the problem schedule domain, say Timeline, has to meet one of the following three requirements:

• Timeline is a true subset of the set Integers. In order to make references forward and backward in time unambiguous, it is required that Timeline is contiguous.

• Timeline is a subset of a calendar. Again, in order to make references forward and backward in time unambiguous, it is required that Timeline is contiguous.

• Timeline is not a subset of Integers nor a subset of a calendar. No additional requirements are placed on Timeline.

This attribute is not mandatory.

Deriving the problem schedule domain

If this attribute is not filled in, then AIMMS will derive the problem schedule domain by finding the smallest common superset of the schedule domains of the activities and resources of the mathematical program. If this set is not a calendar, but a subset thereof, AIMMS chooses to use the calendar instead. This is motivated by the assumption that the length between timeslots is usually relevant in scheduling applications. In scheduling applications in which the subset is more appropriate, copying the elements of a calendar provides an alternative, as illustrated above.