Tasks and resources

Scheduling and planning problems are concerned with determining a plan for the execution of a given set of tasks. The objective may be to generate a feasible schedule that satisfies the given constraints (such as sequence of tasks or limited resource availability) or to optimize a given criterion such as the makespan of the schedule.

Xpress Kalis defines several aggregate modeling objects to simplify the formulation of standard scheduling problems: tasks (processing operations, activities) are represented by the type cptask and resources (machines, raw material etc.) by the type cpresource. When working with these scheduling objects it is often sufficient to state the objects and their properties, such as task duration or resource use; the necessary constraint relations are set up automatically by Xpress Kalis (referred to as implicit constraints). In the following sections we show a number of examples using this mechanism:

• The simplest case of a scheduling problem involves only tasks and precedence constraints between tasks (project scheduling problem in Section Precedences).
• Tasks may be mutually exclusive, e.g. because they use the same unitary resource (disjunctive scheduling / sequencing problem in Section Disjunctive scheduling: unary resources).
• Resources may be usable by several tasks at a time, up to a given capacity limit (cumulative resources, see Section Cumulative scheduling: discrete resources).
• A different classification of resources is the distinction between renewable and non-renewable resources (see Section Renewable and non-renewable resources).
• Many extensions of the standard problems are possible, such as sequence-dependent setup time (see Section Setup times), choice of resources (Section Alternative resources), tasks with non-constant resource profiles (Section Resource profiles), or given idle times for resources (Section Resource idle times and preemption of tasks).

If the enumeration is started with the function cp_schedule the solver will employ specialized search strategies suitable for the corresponding (scheduling) problem type. It is possible to parameterize these strategies or to define user search strategies for scheduling objects (see Section Enumeration). Alternatively, the standard optimization functions cp_minimize / cp_maximize may be used. In this case the enumeration does not exploit the structural information provided by the scheduling objects and works simply with decision variables.

The properties of scheduling objects (such as start time or duration of tasks) can be accessed and employed, for instance, in the definition of constraints, thus giving the user the possibility to extend the predefined standard problems with other types of constraints. For even greater flexibility Xpress Kalis also enables the user to formulate his scheduling problems without the aggregate modeling objects, using dedicated global constraints on decision variables of type cpvar. Most examples in this chapter are therefore given with two different implementations, one using the scheduling objects and another without these objects.