## 6.1 Serialization for Unary Resources

Serializing a unary resource which can execute at most one task simultaneously means that the tasks must be scheduled non-overlapping in time.

The following conventions hold. The argument StartR is a record of finite domain integers denoting start times of tasks. The argument DurR is a record of integers denoting durations of tasks. The arities of StartR and DurR must be equal.

The integers and literals occurring in TasksLIvv denote the tasks to be scheduled. Each element of TasksLIvv must occur in the arity of StartR. The tasks occurring in the vectors TasksLIv are scheduled on the same resource.

`serializedDisj`

`{Schedule.serializedDisj ``+TasksLIvv`` ``+StartR`` ``+DurR``}`

creates a propagator, which states that all tasks TasksLIv scheduled on the same resource must not overlap in time.

The propagator does the same propagation as the conjunction of all reified constraints modelling that two tasks must not overlap in time, i. e.

`(`StartR`.`T1` + `DurR`.`T1` =<: `StartR`.`T2`) + (`StartR`.`T2` + `DurR`.`T2` =<: `StartR`.`T1`) =: 1`

Assume the following tasks and durations:

Resource

Duration

`a`

`r`

`4`

`b`

`r`

`6`

`c`

`r`

`7`

`d`

`s`

`7`

`e`

`s`

`4`

In addition let us assume that no further restriction on the start times is given.

Then

`Dur   = dur(a:4 b:6 c:7 d:7 e:4)Start = {FD.record start [a b c d e] 0#FD.sup}Tasks = (a#b#c)#(d#e){Schedule.serializedDisj Tasks Start Dur}`

serializes the tasks for the resources `r` and `s` (for `FD.record` see *). Note that the resources are kept anonymous, they are just reflected by the vector elements in `Tasks`. If we would like to make the resources more explicit we could use for `Tasks` the following:

`Tasks = tasks(r:[a b c] s:[d e])`

It also possible to use integers or names rather than atoms for the tasks.

`serialized`

`{Schedule.serialized ``+TasksLIvv`` ``+StartR`` ``+DurR``}`

creates a propagator, which states that all tasks TasksLIv scheduled on the same resource must not overlap in time.

The propagator does stronger propagation than `Schedule.serializedDisj` by using so-called edge-finding. This type of edge-finding is a generalization of a technique described in [MS96].

`taskIntervals`

`{Schedule.taskIntervals ``+TasksLIvv`` ``+StartR`` ``+DurR``}`

creates a propagator, which states that all tasks TasksLIv scheduled on the same resource must not overlap in time.

The propagator does even stronger propagation than `Schedule.serialized` by using so-called task-intervals [CL95]. The propagation of this propagator is slightly weaker than the propagation described in [CL95].

Denys Duchier, Leif Kornstaedt, Martin Homik, Tobias Müller, Christian Schulte and Peter Van Roy
Version 1.4.0 (20080702)