| - Up - | Next >> |
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
where T1 and T2 are two tasks out of TasksLIvv.
Assume the following tasks and durations:
Task | Resource | Duration |
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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].
| - Up - | Next >> |