Scheduling

Topics covered in this chapter:

Scheduling plays an important role in manufacturing and engineering where it can have a major impact on the productivity of a process. The goal of scheduling is to optimize the production process by telling which operation to do, when, with which staff, and using which equipment.

Let's take the example of constructing a house. This task can be broken down into a set of smaller tasks:

• Grading and preparation of the site
• Foundations
• Framing
• Installation of windows and doors
• Roofing
• Siding
• Electricity
• Plumbing
• Underlayment
• Painting
• etc...

All these tasks must be carried out in a certain order: for example, laying the foundations cannot be done before the excavation and grading of the site. Moreover, certain tasks require specific resources (you need a plumber to do plumbing, a concrete mixer to do the carpentry etc.).

Tasks and resources are represented in kalis by the special purpose types cpresource and cptask.

Tasks

A cptask is represented by three decision variables of type cpvar:

• start representing the starting time of the task
• end representing the ending time of the task
• duration representing the duration of the task

These three structural variables are linked by Xpress Kalis with the following constraint: start + duration = end.

• The starting time variable represents two specific parameters of the task:
  • the Earliest Start Time (EST, represented by the lower bound of the 'start' variable) and its Latest Start Time (LST, represented by the upper bound of the 'start' variable).
• The end variable represents two specific parameters of the task:
  • the Earliest Completion Time (ECT, represented by the lower bound of the 'end' variable) and its Latest Completion Time (LCT, represented by the upper bound of the 'end' variable).
• The duration variable represents two specific parameters of the task:
  • the minimum task duration (Dmin, represented by the lower bound of the 'duration' variable) and the maximum task duration (Dmax, represented by the upper bound of the 'duration' variable).

The picture below illustrates this:

In the case of tasks using resources, another variable is instantiated : the resource assignment binary variable. It is defined for a couple (task, resource) and takes the value 1 if the task uses the specific resource, otherwise it has value 0.

Task attributes can be assigned or retrieved with the following methods:

• getstart
• getend
• getduration
• setduration
• has_assignment
• getassignment
• get_earliest_start_possible
• getname
• setname
• is_fixed
• addpredecessors
• setpredecessors
• addsuccessors
• setsuccessors
• setsetuptime

Resources

A resource can be of two different types:

• Disjunctive when the resource can process only one task at a time (KALIS_UNARY_RESOURCE).
• Cumulative when the resource can process several tasks at the same time (KALIS_DISCRETE_RESOURCE).

Traditional examples of disjunctive resources are Jobshop scheduling problems. Cumulative resources are used for the Resource-Constrained Project Scheduling Problem (RCPSP)

Note that a disjunctive resource is semantically equivalent to a cumulative resource with maximal capacity one and unit resource usage for each task using this resource but this equivalence does not hold in terms of constraint propagation.

When defining a resource with Xpress Kalis its initial capacity is specified. For a disjunctive resource the capacity value is always equal to one. The structural capacity of a resource does not vary over time but a maximal temporal capacity can be imposed at any point of time with the procedure setcapacity.

The following graphic shows an example with three tasks A, B and C executing on a disjunctive resource and on a cumulative resource with resource usage 3 for task A, 1 for task B, and 1 for task C.

Tasks require, provide, consume and produce resources:

• A task requires a resource if some amount of the resource capacity must be made available for the execution of the activity. The capacity is renewable, this means the required capacity becomes available again after the end of the task.
• A task provides a resource if some amount of the resource capacity is made available through the execution of the task. The capacity is renewable, that is, the provided capacity is available only during the execution of the task.
• A task consumes a resource if some amount of the resource capacity must be made available for the execution of the task and the capacity is non-renewable, that is, the consumed capacity is no longer available at the end of the task.
• A task produces a resource if some amount of the resource capacity is made available through the execution of the task and the capacity is non-renewable, that is, the produced capacity is definitively available after the start of the task.

Task productions, requirements, provisions and productions can be accessed with the following methods:

• consumes
• requires
• provides
• produces
• getconsumption
• getrequirement
• getprovision
• getproduction
• is_consuming
• is_requiring
• is_providing
• is_producing

Resources and tasks are declared by using the standard Mosel syntax. For instance, the following code extract shows how to create a task my_cptask, a static array of resources cpresource_array, and a dynamic array of cptask dyn_cptask_array:

declarations
   my_cptask       : cptask
   cpresource_array: array(1..10) of cpresource
   dyn_cptask_array: array(range) of cptask
end-declarations

Note that entries of dynamic arrays of tasks or resources (arrays declared as dynamic at their creation or arrays for which some or all of the index sets are not known at the declaration like dyn_cptask_array in the example above) must be created explicitly using the Mosel procedure create:

declarations
   dyn_cptask_array: array(range) of cptask
end-declarations
forall(i in 3..30) create (dyn_cptask_array(i))

After its declaration, the second step in the creation of a task or resource consists of defining somes attributes with the procedures set_task_attributes and set_resource_attributes.

Schedule

Tasks and resources form a schedule. The cp_schedule method allows to optimize a schedule with respect to any objective variable and implements advanced scheduling techniques specialized in makespan minimization. The creation of the schedule makespan can be automated by calling the getmakespan method that ensures automatically its computation.

A custom scheduling optimization strategy can be specified by using the task_serialize branching scheme to select the task to be scheduled and value choice heuristics for its start and duration variables.

The task selection method can be any user Mosel method or it may be configured with the predefined strategies of Xpress Kalis:

• KALIS_SMALLEST_ECT
• KALIS_SMALLEST_EST
• KALIS_SMALLEST_LCT
• KALIS_SMALLEST_LST
• KALIS_LARGEST_ECT
• KALIS_LARGEST_EST
• KALIS_LARGEST_LCT
• KALIS_LARGEST_LST

The picture below illustrates the definition of a task-based branching strategy:

kalis defines a set of functions for accessing and modifying cptask and cpresource states: