/usr/share/mozart/doc/fdt/node48.html is in mozart-doc 1.4.0-8ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>11.2 Constructing a Bridge</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node47.html#section.scheduling.house"><< Prev</A></TD><TD><A href="node46.html">- Up -</A></TD><TD><A href="node49.html#section.scheduling.edgefinding">Next >></A></TD></TR></TABLE><DIV id="section.scheduling.bridge"><H2><A name="section.scheduling.bridge">11.2 Constructing a Bridge</A></H2><P>The following problem is taken from <A href="bib.html#bartusch.83">[Bar83]</A> and is used as a benchmark in the constraint programming community. The problem is to schedule the construction of the bridge shown in <A href="node48.html#fig.bridgeproblem">Figure 11.10</A>. </P><DIV id="fig.bridgeproblem"><HR><P><A name="fig.bridgeproblem"></A></P><DIV align="center"><IMG alt="" src="bridge.gif"></DIV><P class="caption"><STRONG>Figure 11.10:</STRONG> The Bridge Problem.</P><HR></DIV><P> </P><DIV class="unnumbered"><H3><A name="label147">Problem Specification</A></H3><P>The problem is specified as shown in <A href="node48.html#fig.bridgetable">Figure 11.11</A>. From this table we derive precedence and capacity constraints as in the sections before. We also assume that a resource cannot handle more than one activity at a time. Such a kind of resource is also known as a <EM>unary resource</EM>. </P><DIV id="fig.bridgetable"><HR><P><A name="fig.bridgetable"></A></P><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TH><P>No </P></TH><TH><P>Na. </P></TH><TH><P>Description </P></TH><TH><P>Dur </P></TH><TH><P>Preds </P></TH><TH><P>Res</P></TH></TR><TR valign="top"><TD><P>1 </P></TD><TD><P>pa </P></TD><TD><P>beginning of project</P></TD><TD><P>0 </P></TD><TD><P>- </P></TD><TD><P>noResource </P></TD></TR><TR valign="top"><TD><P>2 </P></TD><TD><P>a1 </P></TD><TD><P>excavation (abutment 1) </P></TD><TD><P>4 </P></TD><TD><P>pa </P></TD><TD><P>excavator</P></TD></TR><TR valign="top"><TD><P>3</P></TD><TD><P>a2 </P></TD><TD><P>excavation (pillar 1) </P></TD><TD><P>2 </P></TD><TD><P>pa </P></TD><TD><P>excavator</P></TD></TR><TR valign="top"><TD><P>4</P></TD><TD><P>a3 </P></TD><TD><P>excavation (pillar 2) </P></TD><TD><P>2 </P></TD><TD><P>pa </P></TD><TD><P>excavator</P></TD></TR><TR valign="top"><TD><P>5</P></TD><TD><P>a4 </P></TD><TD><P>excavation (pillar 3) </P></TD><TD><P>2 </P></TD><TD><P>pa </P></TD><TD><P>excavator</P></TD></TR><TR valign="top"><TD><P>6</P></TD><TD><P>a5 </P></TD><TD><P>excavation (pillar 4) </P></TD><TD><P>2 </P></TD><TD><P>pa </P></TD><TD><P>excavator</P></TD></TR><TR valign="top"><TD><P>7</P></TD><TD><P>a6 </P></TD><TD><P>excavation (abutment 2) </P></TD><TD><P>5 </P></TD><TD><P>pa </P></TD><TD><P>excavator</P></TD></TR><TR valign="top"><TD><P>8</P></TD><TD><P>p1 </P></TD><TD><P>foundation piles 2 </P></TD><TD><P>20 </P></TD><TD><P>a3 </P></TD><TD><P>pile driver</P></TD></TR><TR valign="top"><TD><P>9</P></TD><TD><P>p2 </P></TD><TD><P>foundation piles 3 </P></TD><TD><P>13 </P></TD><TD><P>a4 </P></TD><TD><P>pile driver</P></TD></TR><TR valign="top"><TD><P>10</P></TD><TD><P>ue </P></TD><TD><P>erection of temporary housing </P></TD><TD><P>10 </P></TD><TD><P>pa </P></TD><TD><P>noResource</P></TD></TR><TR valign="top"><TD><P>11</P></TD><TD><P>s1 </P></TD><TD><P>formwork (abutment 1) </P></TD><TD><P>8 </P></TD><TD><P>a1 </P></TD><TD><P>carpentry</P></TD></TR><TR valign="top"><TD><P>12</P></TD><TD><P>s2 </P></TD><TD><P>formwork (pillar 1) </P></TD><TD><P>4 </P></TD><TD><P>a2 </P></TD><TD><P>carpentry</P></TD></TR><TR valign="top"><TD><P>13</P></TD><TD><P>s3 </P></TD><TD><P>formwork (pillar 2) </P></TD><TD><P>4 </P></TD><TD><P>p1 </P></TD><TD><P>carpentry</P></TD></TR><TR valign="top"><TD><P>14</P></TD><TD><P>s4 </P></TD><TD><P>formwork (pillar 3) </P></TD><TD><P>4 </P></TD><TD><P>p2 </P></TD><TD><P>carpentry</P></TD></TR><TR valign="top"><TD><P>15</P></TD><TD><P>s5 </P></TD><TD><P>formwork (pillar 4) </P></TD><TD><P>4 </P></TD><TD><P>a5 </P></TD><TD><P>carpentry</P></TD></TR><TR valign="top"><TD><P>16</P></TD><TD><P>s6 </P></TD><TD><P>formwork (abutment 2) </P></TD><TD><P>10 </P></TD><TD><P>a6 </P></TD><TD><P>carpentry</P></TD></TR><TR valign="top"><TD><P>17</P></TD><TD><P>b1 </P></TD><TD><P>concrete foundation (abutment 1) </P></TD><TD><P>1 </P></TD><TD><P>s1 </P></TD><TD><P>concrete mixer</P></TD></TR><TR valign="top"><TD><P>18</P></TD><TD><P>b2 </P></TD><TD><P>concrete foundation (pillar 1) </P></TD><TD><P>1 </P></TD><TD><P>s2 </P></TD><TD><P>concrete mixer</P></TD></TR><TR valign="top"><TD><P>19</P></TD><TD><P>b3 </P></TD><TD><P>concrete foundation (pillar 2) </P></TD><TD><P>1 </P></TD><TD><P>s3 </P></TD><TD><P>concrete mixer</P></TD></TR><TR valign="top"><TD><P>20</P></TD><TD><P>b4 </P></TD><TD><P>concrete foundation (pillar 3) </P></TD><TD><P>1 </P></TD><TD><P>s4 </P></TD><TD><P>concrete mixer</P></TD></TR><TR valign="top"><TD><P>21</P></TD><TD><P>b5 </P></TD><TD><P>concrete foundation (pillar 4) </P></TD><TD><P>1 </P></TD><TD><P>s5 </P></TD><TD><P>concrete mixer</P></TD></TR><TR valign="top"><TD><P>22</P></TD><TD><P>b6 </P></TD><TD><P>concrete foundation (abutment 2) </P></TD><TD><P>1 </P></TD><TD><P>s6 </P></TD><TD><P>concrete mixer</P></TD></TR><TR valign="top"><TD><P>23</P></TD><TD><P>ab1 </P></TD><TD><P>concrete setting time (abutment 1) </P></TD><TD><P>1 </P></TD><TD><P>b1 </P></TD><TD><P>noResource</P></TD></TR><TR valign="top"><TD><P>24</P></TD><TD><P>ab2 </P></TD><TD><P>concrete setting time (pillar 1) </P></TD><TD><P>1 </P></TD><TD><P>b2 </P></TD><TD><P>noResource</P></TD></TR><TR valign="top"><TD><P>25</P></TD><TD><P>ab3 </P></TD><TD><P>concrete setting time (pillar 2) </P></TD><TD><P>1 </P></TD><TD><P>b3 </P></TD><TD><P>noResource</P></TD></TR><TR valign="top"><TD><P>26</P></TD><TD><P>ab4 </P></TD><TD><P>concrete setting time (pillar 3) </P></TD><TD><P>1 </P></TD><TD><P>b4 </P></TD><TD><P>noResource</P></TD></TR><TR valign="top"><TD><P>27</P></TD><TD><P>ab5 </P></TD><TD><P>concrete setting time (pillar 4) </P></TD><TD><P>1 </P></TD><TD><P>b5 </P></TD><TD><P>noResource</P></TD></TR><TR valign="top"><TD><P>28</P></TD><TD><P>ab6 </P></TD><TD><P>concrete setting time (abutment 2) </P></TD><TD><P>1 </P></TD><TD><P>b6 </P></TD><TD><P>noResource</P></TD></TR><TR valign="top"><TD><P>29</P></TD><TD><P>m1 </P></TD><TD><P>masonry work (abutment 1) </P></TD><TD><P>16 </P></TD><TD><P>ab1</P></TD><TD><P>bricklaying</P></TD></TR><TR valign="top"><TD><P>30</P></TD><TD><P>m2 </P></TD><TD><P>masonry work (pillar 1) </P></TD><TD><P>8 </P></TD><TD><P>ab2 </P></TD><TD><P>bricklaying</P></TD></TR><TR valign="top"><TD><P>31</P></TD><TD><P>m3 </P></TD><TD><P>masonry work (pillar 2) </P></TD><TD><P>8 </P></TD><TD><P>ab3 </P></TD><TD><P>bricklaying</P></TD></TR><TR valign="top"><TD><P>32</P></TD><TD><P>m4 </P></TD><TD><P>masonry work (pillar 3) </P></TD><TD><P>8 </P></TD><TD><P>ab4 </P></TD><TD><P>bricklaying</P></TD></TR><TR valign="top"><TD><P>33</P></TD><TD><P>m5 </P></TD><TD><P>masonry work (pillar 4) </P></TD><TD><P>8 </P></TD><TD><P>ab5 </P></TD><TD><P>bricklaying</P></TD></TR><TR valign="top"><TD><P>34</P></TD><TD><P>m6 </P></TD><TD><P>masonry work (abutment 2) </P></TD><TD><P>20 </P></TD><TD><P>ab6</P></TD><TD><P>bricklaying</P></TD></TR><TR valign="top"><TD><P>35</P></TD><TD><P>l </P></TD><TD><P>delivery of the preformed bearers </P></TD><TD><P>2 </P></TD><TD><P>- </P></TD><TD><P>crane</P></TD></TR><TR valign="top"><TD><P>36</P></TD><TD><P>t1 </P></TD><TD><P>positioning (preformed bearer 1) </P></TD><TD><P>12 </P></TD><TD><P>m1, m2, l </P></TD><TD><P>crane</P></TD></TR><TR valign="top"><TD><P>37</P></TD><TD><P>t2 </P></TD><TD><P>positioning (preformed bearer 2) </P></TD><TD><P>12 </P></TD><TD><P>m2, m3, l </P></TD><TD><P>crane</P></TD></TR><TR valign="top"><TD><P>38</P></TD><TD><P>t3 </P></TD><TD><P>positioning (preformed bearer 3) </P></TD><TD><P>12 </P></TD><TD><P>m3, m4, l </P></TD><TD><P>crane</P></TD></TR><TR valign="top"><TD><P>39</P></TD><TD><P>t4 </P></TD><TD><P>positioning (preformed bearer 4) </P></TD><TD><P>12 </P></TD><TD><P>m4, m5, l </P></TD><TD><P>crane</P></TD></TR><TR valign="top"><TD><P>40</P></TD><TD><P>t5 </P></TD><TD><P>positioning (preformed bearer 5) </P></TD><TD><P>12 </P></TD><TD><P>m5, m6, l </P></TD><TD><P>crane</P></TD></TR><TR valign="top"><TD><P>41</P></TD><TD><P>ua </P></TD><TD><P>removal of the temporary housing </P></TD><TD><P>10 </P></TD><TD><P>- </P></TD><TD><P>noResource</P></TD></TR><TR valign="top"><TD><P>42</P></TD><TD><P>v1 </P></TD><TD><P>filling 1 </P></TD><TD><P>15 </P></TD><TD><P>t1 </P></TD><TD><P>caterpillar</P></TD></TR><TR valign="top"><TD><P>43</P></TD><TD><P>v2 </P></TD><TD><P>filling 2 </P></TD><TD><P>10 </P></TD><TD><P>t5 </P></TD><TD><P>caterpillar</P></TD></TR><TR valign="top"><TD><P>44</P></TD><TD><P>pe </P></TD><TD><P>end of project </P></TD><TD><P>0 </P></TD><TD><P>t2, t3, t4, v1, v2, ua</P></TD><TD><P>noResource</P></TD></TR></TABLE><P class="caption"><STRONG>Figure 11.11:</STRONG> Data for bridge construction.</P><HR></DIV><P> </P><DIV class="apropos"><P class="margin">unary resources</P><P> Due to some peculiarities of the problem, we have the following additional constraints. </P><OL type="1"><LI><P>The time between the completion of the formwork and the completion of the corresponding concrete foundation is at most 4 days.</P></LI><LI><P>Between the end of a particular foundation and the beginning of the corresponding formwork can at most 3 days elapse.</P></LI><LI><P>The erection of the temporary housing must begin at least six days before each formwork. </P></LI><LI><P>The removal of the temporary housing can start at most two days before the end of the last masonry. </P></LI><LI><P>The delivery of the preformed bearers occurs exactly 30 days after the beginning of the project. </P></LI></OL><P> </P></DIV><P>To deal with the additional constraints we refine the record containing the specification of the problem. We add a field under the feature <CODE>constraints</CODE> that contains a procedure parameterized by the records containing the start times and the durations of tasks (see <A href="node48.html#fig.bridgespec">Figure 11.12</A>). This procedure will be applied by the scheduling script. </P><DIV id="fig.bridgespec"><HR><P><A name="fig.bridgespec"></A></P><DL class="anonymous"><DD class="code"><CODE>bridge(tasks:<BR> </CODE><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A href="node54.html#label178">Bridge task specification</A><SPAN class="chunkborder">></SPAN></SPAN><CODE> <BR> constraints:<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Start Dur}<BR> {ForAll [s1<SPAN class="keyword">#</SPAN>b1 s2<SPAN class="keyword">#</SPAN>b2 s3<SPAN class="keyword">#</SPAN>b3 s4<SPAN class="keyword">#</SPAN>b4 s5<SPAN class="keyword">#</SPAN>b5 s6<SPAN class="keyword">#</SPAN>b6]<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> A<SPAN class="keyword">#</SPAN>B}<BR> (Start<SPAN class="keyword">.</SPAN>B <SPAN class="keyword">+</SPAN> Dur<SPAN class="keyword">.</SPAN>B) <SPAN class="keyword">-</SPAN> (Start<SPAN class="keyword">.</SPAN>A <SPAN class="keyword">+</SPAN> Dur<SPAN class="keyword">.</SPAN>A) <SPAN class="keyword">=<:</SPAN> 4 <BR> <SPAN class="keyword">end</SPAN>}<BR> {ForAll [a1<SPAN class="keyword">#</SPAN>s1 a2<SPAN class="keyword">#</SPAN>s2 a5<SPAN class="keyword">#</SPAN>s5 a6<SPAN class="keyword">#</SPAN>s6 p1<SPAN class="keyword">#</SPAN>s3 p2<SPAN class="keyword">#</SPAN>s4]<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> A<SPAN class="keyword">#</SPAN>B}<BR> Start<SPAN class="keyword">.</SPAN>B <SPAN class="keyword">-</SPAN> (Start<SPAN class="keyword">.</SPAN>A <SPAN class="keyword">+</SPAN> Dur<SPAN class="keyword">.</SPAN>A) <SPAN class="keyword">=<:</SPAN> 3<BR> <SPAN class="keyword">end</SPAN>}<BR> {ForAll [s1 s2 s3 s4 s5 s6]<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> A}<BR> Start<SPAN class="keyword">.</SPAN> A <SPAN class="keyword">>=:</SPAN> Start<SPAN class="keyword">.</SPAN>ue <SPAN class="keyword">+</SPAN> 6<BR> <SPAN class="keyword">end</SPAN>}<BR> {ForAll [m1 m2 m3 m4 m5 m6]<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> A}<BR> (Start<SPAN class="keyword">.</SPAN>A <SPAN class="keyword">+</SPAN> Dur<SPAN class="keyword">.</SPAN>A) <SPAN class="keyword">-</SPAN> 2 <SPAN class="keyword">=<:</SPAN> Start<SPAN class="keyword">.</SPAN>ua<BR> <SPAN class="keyword">end</SPAN>}<BR> Start<SPAN class="keyword">.</SPAN>l <SPAN class="keyword">=:</SPAN> Start<SPAN class="keyword">.</SPAN>pa <SPAN class="keyword">+</SPAN> 30<BR> Start<SPAN class="keyword">.</SPAN>pa = 0<BR> <SPAN class="keyword">end</SPAN>)</CODE></DD></DL><P class="caption"><STRONG>Figure 11.12:</STRONG> Specification for bridge construction.</P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label148">Model</A></H3><P>A trivial upper bound of the makespan is the sum of all durations of the tasks. For the bridge construction problem we have 271 as the upper bound. We adopt the model of the house problem including capacity constraints. The additional constraints can be modeled with propagators for the following constraints over the problem variables (<IMG alt="\Dur{T}" src="latex285.png"> denotes the duration of a task <IMG alt="T" src="latex101.png">). </P><OL type="1"><LI><P></P><BLOCKQUOTE><P><IMG alt="(Bi + \Dur{Bi}) - (Si+\Dur{Si}) \leq 4, \quad 1 \leq i \leq 6" src="latex286.png"></P></BLOCKQUOTE><P></P></LI><LI><P></P><BLOCKQUOTE><P><IMG alt="Si - (Ai+\Dur{Ai}) \leq 3, \quad i \in \{1,2,5,6\}" src="latex287.png"></P></BLOCKQUOTE><P></P><P></P><BLOCKQUOTE><P><IMG alt="S3-(P1+\Dur{P1}) \leq 3" src="latex288.png"></P></BLOCKQUOTE><P></P><P></P><BLOCKQUOTE><P><IMG alt="S4-(P2+\Dur{P2}) \leq 3" src="latex289.png"></P></BLOCKQUOTE><P></P></LI><LI><P></P><BLOCKQUOTE><P><IMG alt="\mbox{UE} + 6 \leq Si, \quad 1 \leq i \leq 6" src="latex290.png"></P></BLOCKQUOTE><P></P></LI><LI><P></P><BLOCKQUOTE><P><IMG alt="(Mi+\Dur{Mi}) - 2 \leq \mbox{UA}, \quad 1 \leq i \leq 6" src="latex291.png"></P></BLOCKQUOTE><P></P></LI><LI><P></P><BLOCKQUOTE><P><IMG alt="L = \mbox{PA} + 30" src="latex292.png"></P></BLOCKQUOTE><P></P></LI></OL><P> </P></DIV><DIV class="unnumbered"><H3><A name="label149">Distribution Strategy</A></H3><P>We first try the distribution strategy of <A href="node47.html#sec.bahcc">Section 11.1.2</A>, i. e. the first-fail strategy. The first solution of the problem is found with 97949 choice nodes and has a makespan of 133. After 500000 choice nodes no better solution is found. This is very unsatisfactory if we know that the optimal makespan is 104. </P><P>Thus, we try the distributor described in <A href="node47.html#sec.serializers">Section 11.1.3</A>, i. e. the naive serializer. Now we find the first solution with makespan 120 with only 77 choice nodes. With 95 choice nodes we find a solution with makespan 112. After 500000 choice nodes no better solution is found. </P><P>In order to solve the problem we combine the ideas of first-fail and of serializers. The idea behind first-fail is to distribute first with a variable which has the smallest domain. This variable should occur in many constraints and should lead to much constraint propagation. The variable with the smallest domain acts as a bottleneck for the problem. This idea can be transferred to scheduling problems. A simple criterion for a resource to be a bottleneck is the sum of the durations of tasks to be scheduled on that resource. Hence, we will serialize first the tasks on a resource where the sum of durations is maximal. </P></DIV><DIV class="unnumbered"><H3><A name="label150">Script</A></H3><P></P><DIV id="fig.bridgecompiler"><HR><P><A name="fig.bridgecompiler"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Compile</SPAN> Spec Capacity Serializer}<BR> TaskSpec = Spec<SPAN class="keyword">.</SPAN>tasks<BR> Constraints = </CODE><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A href="node48.html#label151">Extract additional constraints</A><SPAN class="chunkborder">></SPAN></SPAN><CODE> <BR> Dur = {GetDur TaskSpec}<BR> TasksOnRes = {GetTasksOnResource TaskSpec}<BR><SPAN class="keyword">in</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Start}<BR> Start = {GetStart TaskSpec}<BR> </CODE><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A href="node47.html#label134">Post precedence constraints</A><SPAN class="chunkborder">></SPAN></SPAN><CODE> <BR> {Constraints Start Dur}<BR> {Capacity TasksOnRes Start Dur}<BR> {Serializer TasksOnRes Start Dur}<BR> </CODE><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A href="node47.html#label135">Assign start times</A><SPAN class="chunkborder">></SPAN></SPAN><CODE> <BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> </CODE></DD></DL><P class="caption"><STRONG>Figure 11.13:</STRONG> A scheduling compiler for the bridge problem.</P><HR></DIV><P> </P><P><A href="node48.html#fig.bridgecompiler">Figure 11.13</A> shows the scheduling we will employ for the remaining problems. The variable <CODE>Constraints</CODE> refers to a binary procedure possibly containing additional constraints for a scheduling problem, it is computed as follows: </P><DL><DT><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A name="label151">Extract additional constraints</A><SPAN class="chunkborder">>=</SPAN></SPAN></DT><DD class="code"><CODE><SPAN class="keyword">if</SPAN> {HasFeature Spec constraints} <SPAN class="keyword">then</SPAN> <BR> Spec<SPAN class="keyword">.</SPAN>constraints<BR><SPAN class="keyword">else</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> _ _} <BR> <SPAN class="keyword">skip</SPAN> <BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P> </P><P>Note that we have parameterized the scheduling compiler with procedures to post the capacity constraints and the serializer. This makes it straightforward to solve the bridge problem with stronger techniques. </P><P>The procedure <CODE>DistributedSorted</CODE> orders the tasks on resources according to our bottleneck criterion (see <A href="node48.html#figure.scheduling.sortdist">Figure 11.14</A>). </P><P></P><DIV id="figure.scheduling.sortdist"><HR><P><A name="figure.scheduling.sortdist"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">DistributeSorted</SPAN> TasksOnRes Start Dur}<BR> <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">DurOnRes</SPAN> Ts}<BR> {FoldL Ts <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> D T} <BR> D<SPAN class="keyword">+</SPAN>Dur<SPAN class="keyword">.</SPAN>T <BR> <SPAN class="keyword">end</SPAN> 0}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">in</SPAN> <BR> {ForAll {Sort {Record<SPAN class="keyword">.</SPAN>toList TasksOnRes}<BR> <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Ts1 Ts2}<BR> {DurOnRes Ts1} <SPAN class="keyword">></SPAN> {DurOnRes Ts2}<BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Ts}<BR> {ForAllTail Ts<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> T1<SPAN class="keyword">|</SPAN>Tr}<BR> {ForAll Tr<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> T2}<BR> <SPAN class="keyword">choice</SPAN> Start<SPAN class="keyword">.</SPAN>T1 <SPAN class="keyword">+</SPAN> Dur<SPAN class="keyword">.</SPAN>T1 <SPAN class="keyword">=<:</SPAN> Start<SPAN class="keyword">.</SPAN>T2<BR> <SPAN class="keyword">[]</SPAN> Start<SPAN class="keyword">.</SPAN>T2 <SPAN class="keyword">+</SPAN> Dur<SPAN class="keyword">.</SPAN>T2 <SPAN class="keyword">=<:</SPAN> Start<SPAN class="keyword">.</SPAN>T1<BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN>}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 11.14:</STRONG> Serializer that orders tasks by bottleneck criterion.</P><HR></DIV><P> </P><P>The optimal solution can be found by </P><DL class="anonymous"><DD class="code"><CODE>{ExploreBest {Compile Bridge<BR> Schedule<SPAN class="keyword">.</SPAN>serializedDisj<BR> DistributeSorted} <BR> Earlier}</CODE></DD></DL><P> The full search tree consists of 1268 choice nodes and 8 solution nodes (see <A href="node48.html#fig.scheduling.bridge">Figure 11.15</A>). </P><P></P><DIV id="fig.scheduling.bridge"><HR><P><A name="fig.scheduling.bridge"></A></P><DIV align="center"><IMG alt="" src="bridge-tree-1.png" id="pic.bridge-tree-1"></DIV><P class="caption"><STRONG>Figure 11.15:</STRONG> A search tree for the bridge problem.</P><HR></DIV><P> </P><P>The optimal solution can be visualized by a kind of Gantt-chart (see <A href="node48.html#fig.gantt">Figure 11.16</A>). The makespan of the schedule (104 in this case) is indicated by a dashed line. Rectangles denote tasks. The left border of the rectangle indicates the start time of the task and the width of the rectangle indicates the duration of the task. Tasks scheduled on the same resource have the same texture. </P><P></P><DIV id="fig.gantt"><HR><P><A name="fig.gantt"></A></P><DIV align="center"><IMG alt="" src="gantt.gif"></DIV><P class="caption"><STRONG>Figure 11.16:</STRONG> The Gantt-chart for the bridge problem.</P><HR></DIV><P> </P><P>The way we can solve scheduling problems by now seems to be satisfactory. But the current approach has two major flaws. First, the propagation of capacity constraint is rather weak. If we want to solve more demanding scheduling problems (like some benchmark problems from Operations Research) we need stronger propagation. Second, the bottleneck criterion of the serializer is rather coarse. We need more subtle techniques to solve more demanding problems. Furthermore, we need <IMG alt="(n \cdot (n-1))/2" src="latex293.png"> ordering decisions for <IMG alt="n" src="latex43.png"> tasks on the same resource which may result in deep search trees. This is not feasible for larger problems. Both problems will be solved in forthcoming sections. </P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node47.html#section.scheduling.house"><< Prev</A></TD><TD><A href="node46.html">- Up -</A></TD><TD><A href="node49.html#section.scheduling.edgefinding">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~schulte/">Christian Schulte</A> and <A href="http://www.ps.uni-sb.de/~smolka/">Gert Smolka</A><BR><SPAN class="version">Version 1.4.0 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|