<!--
  - Authors:
  -   Christian Schulte <schulte@ps.uni-sb.de>
  -
  - Copyright:
  -   Christian Schulte, 1998
  -
  - Last change:
  -   $Date: 2001-05-02 11:12:18 +0200 (Wed, 02 May 2001) $ by $Author: schulte $
  -   $Revision: 13765 $
  -
  - This file is part of Mozart, an implementation
  - of Oz 3
  -    http://www.mozart-oz.org
  -
  - See the file "LICENSE" or
  -    http://www.mozart-oz.org/LICENSE.html
  - for information on usage and redistribution
  - of this file, and for a DISCLAIMER OF ALL
  - WARRANTIES.
  -
  -->

<Chapter id="Chapter.Schedule">
  <Title/Scheduling Support: <<Schedule>>/

<p>
This chapters describes propagators and distributors for scheduling
applications.  More information on scheduling in Oz can be found
in&nbsp;<ptr to=wuertz.96b> and&nbsp;<ptr to=wuertz.96c>. A tutorial
account on scheduling can be found in <Ptr.extern to="ozdoc:fdt"
key="chapter.scheduling">.


<section id="section.schedule.unary">
  <title/Serialization for Unary Resources/

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

<p>
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. 

<p>
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.

<p>

<p>
<list>

<entry>
<index class=module/<<Schedule>><and><<serializedDisj>>/
<<serializedDisj>>
<synopsis>
<<<
{Schedule.serializedDisj ?+{TasksLIvv} ?+{StartR} ?+{DurR}}
>>>
<item>
creates a propagator, which states that all tasks <<?{TasksLIv}>>
scheduled on the same resource
must not overlap in time. 

<p>
The propagator does the same propagation as
the conjunction of all reified  constraints modelling that two tasks
must not overlap in time, &ie;
<<<
(?{StartR}.?{T1} + ?{DurR}.?{T1} =&lt;: ?{StartR}.?{T2}) +
(?{StartR}.?{T2} + ?{DurR}.?{T2} =&lt;: ?{StartR}.?{T1}) =: 1
>>>
where <<?{T1}>> and <<?{T2}>> are two tasks out of <<?{TasksLIvv}>>.

<p> Assume the following tasks and durations:
<table>
  <tr/ <th/Task/ <th/Resource/ <th/Duration//
  <tr/ <td/<<a>>/ <td/<<r>>/ <td/<<4>>//
  <tr/ <td/<<b>>/ <td/<<r>>/ <td/<<6>>//
  <tr/ <td/<<c>>/ <td/<<r>>/ <td/<<7>>//
  <tr/ <td/<<d>>/ <td/<<s>>/ <td/<<7>>//
  <tr/ <td/<<e>>/ <td/<<s>>/ <td/<<4>>//
</table>
In addition let us assume that no further restriction on the start
times is given. 

<p>
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 <Ptr to="FD.record">). 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.

<entry>
<index class=module/<<Schedule>><and><<serialized>>/
<<serialized>>
<synopsis>
<<<
{Schedule.serialized ?+{TasksLIvv} ?+{StartR} ?+{DurR}}
>>>
<item>
creates a propagator, which states that all tasks <<?{TasksLIv}>>
scheduled on the same resource
must not overlap in time. 

<p>
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
<ptr to=martin.96>. 

<entry>
<index class=module/<<Schedule>><and><<taskIntervals>>/
<<taskIntervals>>
<synopsis>
<<<
{Schedule.taskIntervals ?+{TasksLIvv} ?+{StartR} ?+{DurR}}
>>>
<item>
creates a propagator, which states that all tasks <<?{TasksLIv}>>
scheduled on the same resource
must not overlap in time. 

<p>
The propagator does even stronger propagation than
 <<Schedule.serialized>> by using so-called
task-intervals&nbsp;<ptr to=caseau.95>. The propagation of this propagator is
slightly weaker than the propagation described in&nbsp;<ptr to=caseau.95>. 
</list>



<section id="section.schedule.distribute">
  <title/Distribution/

<p>
In addition to the conventions used in <Ptr
to="section.schedule.unary"> the record of start times <<?{StartR}>>
must have the feature <<pe>>. This feature denotes the task which is
to be scheduled last, &ie; the makespan of the schedule.

<p>
<list>
<entry>
<index class=module/<<Schedule>><and><<firstsDist>>/
<<firstsDist>>
<synopsis>
<<<
{Schedule.firstsDist ?+{TasksLIvv} ?+{StartR} ?+{DurR}}
>>>
<item>
distributes  the tasks occurring in <<?{TasksLIvv}>>, such that every
resource is serialized. 

<p>
More details can be found
in&nbsp;<ptr to=baptiste.95a>.

<entry>
<index class=module/<<Schedule>><and><<lastsDist>>/
<<lastsDist>>
<synopsis>
<<<
{Schedule.lastsDist ?+{TasksLIvv} ?+{StartR} ?+{DurR}}
>>>
<item>
distributes  the tasks occurring in <<?{TasksLIvv}>>, such that every
resource is serialized. 

<p>
More details can be found
in&nbsp;<ptr to=baptiste.95a>. 

<entry>
<index class=module/<<Schedule>><and><<firstsLastsDist>>/
<<firstsLastsDist>>
<synopsis>
<<<
{Schedule.firstsLastsDist ?+{TasksLIvv} ?+{StartR} ?+{DurR}}
>>>
<item>
distributes  the tasks occurring in <<?{TasksLIvv}>>, such that every
resource is serialized. 

<p>
More details can be found
in&nbsp;<ptr to=baptiste.95a>. 

<entry>
<index class=module/<<Schedule>><and><<taskIntervalsDistP>>/
<<taskIntervalsDistP>>
<synopsis>
<<<
{Schedule.taskIntervalsDistP ?+{TasksLIvv} ?+{StartR} 
                             ?+{DurR}}
>>>
<item>
distributes  the tasks occurring in <<?{TasksLIvv}>>, such that every
resource is serialized. This strategy is well suited for proving
optimality.  

<p>
More details can be found in&nbsp;<ptr to=caseau.95>. The
distribution strategy implemented in Oz differs slightly from the one
described in&nbsp;<ptr to=caseau.95>.

<entry>
<index class=module/<<Schedule>><and><<taskIntervalsDistO>>/
<<taskIntervalsDistO>>
<synopsis>
<<<
{Schedule.taskIntervalsDistO ?+{TasksLIvv} ?+{StartR} 
                             ?+{DurR}}
>>>
<item>
distributes  the tasks occurring in <<?{TasksLIvv}>>, such that every
resource is serialized. This strategy is well suited for finding good
solutions in combination with local search techniques.  

<p>
More details can
be found in&nbsp;<ptr to=caseau.95>. The
distribution strategy implemented in Oz differs slightly from the one
described in&nbsp;<ptr to=caseau.95>.
</list>



<section id="section.schedule.cumulative">
  <Title/Cumulative Scheduling/

<p>
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
argument <<?{UseR}>> is a record of integers denoting the resource
usage of tasks. 
The arities of <<?{StartR}>>, <<?{DurR}>>, and <<?{UseR}>> must be 
equal. 

<p>
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. The vector <<?{CapIv}>> is a vector of integers denoting the
capacity of the resources. The number of elements in the vectors
<<?{TasksLIvv}>> 
and <<?{CapIv}>> must be equal. 

<p>
<list>
<entry>
<index class=module/<<Schedule>><and><<cumulative>>/
<<cumulative>>
<synopsis>
<<<
{Schedule.cumulative ?+{TasksLIvv} ?+{StartR} ?+{DurR} 
                     ?+{UseR} ?+{CapIv}}
>>>
<item>
creates a propagator, which states that for all resources <math/i/ and time
instants <math/x/, the resource usage does not exceed the available capacity:
<math display>
\sum_{\hsmash{\{t \in \mbox{TasksA}_i \mid \mbox{StartR.}t \leq x &lt; \mbox{StartR.}t +
\mbox{DurR.}t\}}} \mbox{UseR.}t \leq \mbox{CapI}_i
</math>

<p>
The propagator does not use edge-finding. 

<p>
Assume that we have the following resources and tasks:
<table>
  <tr/ <th/Resource/ <th/Capacity//
  <tr/ <td/<<r>>/    <td/<<5>>//
  <tr/ <td/<<s>>/    <td/<<2>>//
</table>
<table>
  <tr/ <th/Task/ <th/Resource/ <th/Duration/ <th/Usage//
  <tr/ <td/<<a>>/ <td/<<r>>/ <td/<<5>>/ <th/<<5>>//
  <tr/ <td/<<b>>/ <td/<<r>>/ <td/<<2>>/ <th/<<3>>//
  <tr/ <td/<<c>>/ <td/<<s>>/ <td/<<7>>/ <th/<<2>>//
  <tr/ <td/<<d>>/ <td/<<s>>/ <td/<<4>>/ <th/<<3>>//
  <tr/ <td/<<e>>/ <td/<<s>>/ <td/<<9>>/ <th/<<5>>//
</table>
Provided that no limit on the start times of the tasks are given, the
following
<<<
Tasks = tasks([a b] [c d e])
Start = {FD.record start [a b c d e] 0#FD.sup}
Dur   = dur(a:5 b:2 c:7 d:4 e:9)
Use   = use(a:5 b:3 c:2 d:3 e:5)
Cap   = cap(5 2)
{Schedule.cumulative Tasks Start Dur Use Cap}
>>>
propagates that the resource usage does not exceed the resources'
capacities (for <<FD.record>> see&nbsp;<ptr to="FD.record">).

<entry>
<index class=module/<<Schedule>><and><<cumulativeEF>>/
<<cumulativeEF>>
<synopsis>
<<<
{Schedule.cumulativeEF ?+{TasksLIvv} ?+{StartR} ?+{DurR} 
                       ?+{UseR} ?+{CapIv}}
>>>
<item>
creates a propagator, which states that for all resources <math/i/ and time
instants <math/x/, the resource usage does not exceed the available capacity:
<math display>
\sum_{\hsmash{\{t \in \mbox{TasksA}_i \mid \mbox{StartR.}t \leq x < \mbox{StartR.}t +
\mbox{DurR.}t\}}} \mbox{UseR.}t \leq \mbox{CapI}_i
</math><p>

<p>
This propagator  generalizes the edge-finding propagation in 
<<Schedule.serialized>> to deal with non-unary resources. 

<entry>
<index class=module/<<Schedule>><and><<cumulativeTI>>/
<<cumulativeTI>>
<synopsis>
<<<
{Schedule.cumulativeTI ?+{TasksLIvv} ?+{StartR} ?+{DurR} 
                       ?+{UseR} ?+{CapIv}}
>>>
<item>
creates a propagator, which states that for all resources <math/i/ and time
instants <math/x/, the resource usage does not exceed the available capacity:
<math display>
\sum_{\hsmash{\{t \in \mbox{TasksA}_i \mid \mbox{StartR.}t \leq x < \mbox{StartR.}t +
\mbox{DurR.}t\}}} \mbox{UseR.}t \leq \mbox{CapI}_i
</math>

<p>
This propagator generalizes the edge-finding propagation in 
<<Schedule.taskIntervals>> to deal with non-unary resources. 

<entry>
<index class=module/<<Schedule>><and><<cumulativeUp>>/
<<cumulativeUp>>
<synopsis>
<<<
{Schedule.cumulativeUp ?+{TasksLIvv} ?+{StartR} ?+{DurR} 
                       ?+{UseR} ?+{CapIv}}
>>>
<item>
creates a propagator, which states that for all resources <math/i/ and time
instants <math/x/, the resource is at least as large as the available capacity:
<math display>
\sum_{\hsmash{\{t \in \mbox{TasksA}_i \mid \mbox{StartR.}t \leq x < \mbox{StartR.}t +
\mbox{DurR.}t\}}} \mbox{UseR.}t \geq \mbox{CapI}_i
</math>
</list>


<section id="section.schedule.misc">
  <title/Miscellaneous Propagators/

<p>
<list>
<entry>
<index class=module/<<Schedule>><and><<disjoint>>/
<<disjoint>>
<synopsis>
<<<
{Schedule.disjoint ?*{D1} ?+{I1} ?*{D2} ?+{I2}}
>>>
<item>
creates a propagator for <math/D1+I1\leq D2 \;\vee\;
D2+I2\leq D1/. 
Its operational semantics is defined by
<<<
or ?{D1} + ?{I1} =<: ?{D2}
[] ?{D2} + ?{I2} =<: ?{D1}
end
>>>
</list>

</section>

</Chapter>
