<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>11.1 Building a House</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="node46.html">- Up -</A></TD><TD><A href="node48.html#section.scheduling.bridge">Next >></A></TD></TR></TABLE><DIV id="section.scheduling.house"><H2><A name="section.scheduling.house">11.1 Building a House</A></H2><P>We first consider the problem to build a house (in a simplified way). We will successively refine the problem specification, the model and the distribution strategy in order to solve more and more demanding problems. </P><DIV class="unnumbered"><H3><A name="label127">Problem Specification</A></H3><P>The task names, their description, duration (in days) and the company in charge are given in <A href="node47.html#table.hausbau">Figure 11.1</A>. For example, <CODE>b</CODE> denotes the task involved with the carpentry for the roof. This task lasts for 3 days. Task <CODE>a</CODE> must be finished before the work for task <CODE>b</CODE> is started (indicated by the column <EM>Predecessor</EM>). The company in charge for task <CODE>b</CODE> is <EM>House Inc</EM>. The overall goal is to build the house as quickly as possible. </P><P></P><DIV id="table.hausbau"><HR><P><A name="table.hausbau"></A></P><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TH><P>Task</P></TH><TH><P>Description</P></TH><TH><P>Duration</P></TH><TH><P>Predecessor</P></TH><TH><P>Company</P></TH></TR><TR valign="top"><TD><P><CODE>a</CODE></P></TD><TD><P>Erecting Walls</P></TD><TD><P>7</P></TD><TD><P>none</P></TD><TD><P>Construction Inc.</P></TD></TR><TR valign="top"><TD><P><CODE>b</CODE></P></TD><TD><P>Carpentry for Roof</P></TD><TD><P>3</P></TD><TD><P><CODE>a</CODE></P></TD><TD><P>House Inc.</P></TD></TR><TR valign="top"><TD><P><CODE>c</CODE></P></TD><TD><P>Roof</P></TD><TD><P>1</P></TD><TD><P><CODE>b</CODE></P></TD><TD><P>House Inc.</P></TD></TR><TR valign="top"><TD><P><CODE>d</CODE></P></TD><TD><P>Installations</P></TD><TD><P>8</P></TD><TD><P><CODE>a</CODE></P></TD><TD><P>Construction Inc.</P></TD></TR><TR valign="top"><TD><P><CODE>e</CODE></P></TD><TD><P>Facade Painting</P></TD><TD><P>2</P></TD><TD><P><CODE>c</CODE>, <CODE>d</CODE></P></TD><TD><P>Construction Inc.</P></TD></TR><TR valign="top"><TD><P><CODE>f</CODE></P></TD><TD><P>Windows</P></TD><TD><P>1</P></TD><TD><P><CODE>c</CODE>, <CODE>d</CODE></P></TD><TD><P>House Inc.</P></TD></TR><TR valign="top"><TD><P><CODE>g</CODE></P></TD><TD><P>Garden</P></TD><TD><P>1</P></TD><TD><P><CODE>c</CODE>, <CODE>d</CODE></P></TD><TD><P>House Inc.</P></TD></TR><TR valign="top"><TD><P><CODE>h</CODE></P></TD><TD><P>Ceilings</P></TD><TD><P>3</P></TD><TD><P><CODE>a</CODE></P></TD><TD><P>Construction Inc.</P></TD></TR><TR valign="top"><TD><P><CODE>i</CODE></P></TD><TD><P>Painting</P></TD><TD><P>2</P></TD><TD><P><CODE>f</CODE>, <CODE>h</CODE></P></TD><TD><P>Builder Corp.</P></TD></TR><TR valign="top"><TD><P><CODE>j</CODE></P></TD><TD><P>Moving in</P></TD><TD><P>1</P></TD><TD><P><CODE>i</CODE></P></TD><TD><P>Builder Corp.</P></TD></TR></TABLE><P class="caption"><STRONG>Figure 11.1:</STRONG> Building a house.</P><HR></DIV><P> </P></DIV><DIV id="sec.precedence"><H3><A name="sec.precedence">11.1.1 Building a House: Precedence Constraints</A></H3><P>For the first model we do not consider the companies in charge for the tasks. </P><DIV class="unnumbered"><H4><A name="label128">Model</A></H4><P> The model introduces for each task a variable which stands for the start time of the task. In the sequel we will identify a task and its corresponding variable. The end time of each task is its start time plus its duration. For the time origin we assume 0. A trivial upper bound for the time to build the house can be obtained by summing up all durations of tasks. Here, we obtain 29. </P><DIV class="apropos"><P class="margin">precedence constraints</P><P> From the predecessor relation we can derive a set of so-called <A name="label129"></A><EM>precedence constraints</EM>: </P><BLOCKQUOTE><P><IMG alt="\begin{array}{c}
A+7 \leq B, \qquad B+3 \leq C, \qquad A+7 \leq D, \qquad C+1 \leq E,\\
D+8 \leq E, \qquad C+1\leq F, \qquad D+8\leq F, \qquad C+1\leq G,\\
D+8\leq G, \qquad A+7 \leq H, \qquad F+1\leq I, \qquad H+3 \leq I,\\
I+2 \leq J.
\end{array}" src="latex267.png"></P></BLOCKQUOTE><P> </P></DIV><DIV class="apropos"><P class="margin">makespan</P><P> For example, the constraint <IMG alt="A+7\leq B" src="latex268.png"> means that the earliest start time of <CODE>b</CODE> is 7 days after <CODE>a</CODE> has been started. We assume an additional task <CODE>pe</CODE> modeling the project end for the problem. All other tasks precede <CODE>pe</CODE>. The start time of <CODE>pe</CODE> is called the <A name="label130"></A><EM>makespan</EM> of the schedule. </P></DIV></DIV><DIV class="unnumbered"><H4><A name="label131">Distribution Strategy</A></H4><P>If all propagators have become stable, it is sufficient to determine each variable to the current minimal value in its domain to obtain a solution. This is due to the fact that we only use constraints of the form <IMG alt="x + c \leq y" src="latex269.png"> where <IMG alt="c" src="latex270.png"> is an integer. Hence, we do not need a distributor at all. Note that this fact remains true if we also consider constraints of the form <IMG alt="x+c=y" src="latex271.png"> (this will be needed later). </P></DIV><DIV class="unnumbered"><H4><A name="label132">Script</A></H4><P>The problem specification which is a direct implementation of <A href="node47.html#table.hausbau">Figure 11.1</A> is given in <A href="node47.html#fig.data.hausbau">Figure 11.2</A>. The field under the feature <CODE>tasks</CODE> contains the specification as a list of records. The label of each record gives the task name, the field at feature <CODE>dur</CODE> the duration, the field at feature <CODE>pre</CODE> the list of preceding tasks, and the field at feature <CODE>res</CODE> the resource name. The features <CODE>pre</CODE> and <CODE>res</CODE> are optional, if they are missing no preceding tasks and no resource are required. The task with name <CODE>pe</CODE> denotes the additional task representing the project end. </P><DIV id="fig.data.hausbau"><HR><P><A name="fig.data.hausbau"></A></P><DL class="anonymous"><DD class="code"><CODE>House = house(tasks: [a(dur:7 res:constructionInc) <BR> b(dur:3 pre:[a] res:houseInc) <BR> c(dur:1 pre:[b] res:houseInc) <BR> d(dur:8 pre:[a] res:constructionInc) <BR> e(dur:2 pre:[c d] res:constructionInc) <BR> f(dur:1 pre:[c d] res:houseInc) <BR> g(dur:1 pre:[c d] res:houseInc) <BR> h(dur:3 pre:[a] res:constructionInc) <BR> i(dur:2 pre:[f h] res:builderCorp) <BR> j(dur:1 pre:[i] res:builderCorp) <BR> pe(dur:0 pre:[j])])</CODE></DD></DL><P class="caption"><STRONG>Figure 11.2:</STRONG> The specification to build a house.</P><HR></DIV><P> </P><DIV class="apropos"><P class="margin">scheduling compiler</P><P> <A href="node47.html#fig.script1.hausbau">Figure 11.3</A> shows a procedure that returns a script according to our scheduling specification. The used procedures <CODE>GetDur</CODE> and <CODE>GetStart</CODE> are shown in <A href="node47.html#figure.scheduling.help">Figure 11.4</A>. Such a procedure is called a <A name="label133"></A><EM>scheduling compiler</EM> because it processes the problem specification and returns a script. Hence, the scheduling compiler <EM>compiles</EM> the problem specification into an <EM>executable script</EM>. </P><DIV id="fig.script1.hausbau"><HR><P><A name="fig.script1.hausbau"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Compile</SPAN> Spec}<BR> TaskSpec = Spec<SPAN class="keyword">.</SPAN>tasks<BR> Dur = {GetDur 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> </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.3:</STRONG> Scheduling compiler.</P><HR></DIV><P> </P></DIV><P></P><DIV id="figure.scheduling.help"><HR><P><A name="figure.scheduling.help"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">GetDur</SPAN> TaskSpec}<BR> {List<SPAN class="keyword">.</SPAN>toRecord dur {Map TaskSpec <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> T}<BR> {Label T}<SPAN class="keyword">#</SPAN>T<SPAN class="keyword">.</SPAN>dur<BR> <SPAN class="keyword">end</SPAN>}}<BR><SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">GetStart</SPAN> TaskSpec}<BR> MaxTime = {FoldL TaskSpec <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Time T} <BR> Time<SPAN class="keyword">+</SPAN>T<SPAN class="keyword">.</SPAN>dur<BR> <SPAN class="keyword">end</SPAN> 0}<BR> Tasks = {Map TaskSpec Label}<BR><SPAN class="keyword">in</SPAN> <BR> {FD<SPAN class="keyword">.</SPAN>record start Tasks 0<SPAN class="keyword">#</SPAN>MaxTime}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 11.4:</STRONG> Procedures to compute duration and start records.</P><HR></DIV><P> </P><P>The durations and start times of tasks are stored in the records <CODE>Dur</CODE> and <CODE>Start</CODE>, respectively. The record <CODE>Start</CODE> is the root variable of the script returned by the function <CODE>Compile</CODE>. First, the propagators for the precedence constraints are created, which is shown in <A href="node47.html#figure.scheduling.precedence">Figure 11.5</A>. After the space executing the scheduling script has become stable, the start times are determined. This is shown in <A href="node47.html#figure.scheduling.starttimes">Figure 11.6</A>. </P><DIV id="figure.scheduling.precedence"><HR><P><A name="figure.scheduling.precedence"></A></P><DL><DT><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A name="label134">Post precedence constraints</A><SPAN class="chunkborder">>=</SPAN></SPAN></DT><DD class="code"><CODE>{ForAll TaskSpec<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> T}<BR> {ForAll {CondSelect T pre nil}<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> P}<BR> Start<SPAN class="keyword">.</SPAN>P <SPAN class="keyword">+</SPAN> Dur<SPAN class="keyword">.</SPAN>P <SPAN class="keyword">=<:</SPAN> Start<SPAN class="keyword">.</SPAN>{Label T}<BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN>}</CODE></DD></DL><P class="caption"><STRONG>Figure 11.5:</STRONG> Posting precedence constraints.</P><HR></DIV><P> </P><DIV id="figure.scheduling.starttimes"><HR><P><A name="figure.scheduling.starttimes"></A></P><DL><DT><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A name="label135">Assign start times</A><SPAN class="chunkborder">>=</SPAN></SPAN></DT><DD class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>assign min Start}</CODE></DD></DL><P class="caption"><STRONG>Figure 11.6:</STRONG> Assigning start times.</P><HR></DIV><P> </P><P>The statement </P><DL class="anonymous"><DD class="code"><CODE>{ExploreOne {Compile House}}</CODE></DD></DL><P> runs the script. The makespan of the schedule is 19. By construction this solution is the one with the smallest makespan. </P></DIV></DIV><DIV id="sec.bahcc"><H3><A name="sec.bahcc">11.1.2 Building a House: Capacity Constraints</A></H3><P>In this section we take the companies into account which are in charge for the tasks. We assume that each company cannot handle two tasks simultaneously. That is, the execution of two tasks handled by the same company must not overlap in time. </P><DIV class="unnumbered"><H4><A name="label136">Model</A></H4><P> For each company (which we also call a <A name="label137"></A><EM>resource</EM> because the companies are consumed by a task) we must find a <A name="label138"></A><EM>serialization</EM> of the handled tasks, i. e. for each task pair <IMG alt="A" src="latex98.png">,<IMG alt="B" src="latex39.png"> we must decide whether <IMG alt="A" src="latex98.png"> is finished before <IMG alt="B" src="latex39.png"> starts or vice versa. Assume two tasks with start times <IMG alt="S_1" src="latex272.png"> and <IMG alt="S_2" src="latex273.png"> and the durations <IMG alt="D_1" src="latex274.png"> and <IMG alt="D_2" src="latex275.png">, respectively. </P><DIV class="apropos"><P class="margin">capacity constraints</P><P> Then the constraint </P><BLOCKQUOTE><P><IMG alt="S_1 + D_1 \leq S_2 \quad \vee \quad S_2 + D_2 \leq S_1 " src="latex276.png"></P></BLOCKQUOTE><P> states that the corresponding tasks do not overlap in time. Such a constraint is also known as a <A name="label139"></A><EM>capacity constraint</EM>, because the capacity of the resource must not be exceeded. The capacity constraints can be modeled by reified constraints for each pair of tasks handled by the same resource (company). But this leads to a number of propagators which increases quadratically in the number of tasks on a resource. This is not a feasible approach for problems with many tasks. Thus, we will use a single propagator in the script providing the same propagation as the quadratic number of reified constraints. </P></DIV></DIV><DIV class="unnumbered"><H4><A name="label140">Distribution Strategy</A></H4><P> Because of the capacity constraints we have to provide a distribution strategy. We use the standard first-fail strategy. </P></DIV><DIV class="unnumbered" id="page.tasksonres"><H4><A name="page.tasksonres">Script</A></H4><P> We extend the scheduling compiler in <A href="node47.html#fig.script1.hausbau">Figure 11.3</A> to extract the tasks handled by a common resource. The procedure <CODE>GetTasksOnResource</CODE> takes a task specification and returns a record that maps resource names to tasks. Its implementation is shown in <A href="node47.html#figure.scheduling.tor">Figure 11.7</A>. </P><P></P><DIV id="figure.scheduling.tor"><HR><P><A name="figure.scheduling.tor"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">GetTasksOnResource</SPAN> TaskSpec}<BR> D={Dictionary<SPAN class="keyword">.</SPAN>new}<BR><SPAN class="keyword">in</SPAN> <BR> {ForAll TaskSpec <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> T}<BR> <SPAN class="keyword">if</SPAN> {HasFeature T res} <SPAN class="keyword">then</SPAN> R=T<SPAN class="keyword">.</SPAN>res <SPAN class="keyword">in</SPAN> <BR> {Dictionary<SPAN class="keyword">.</SPAN>put D R {Label T}<SPAN class="keyword">|</SPAN>{Dictionary<SPAN class="keyword">.</SPAN>condGet D R nil}}<BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN>}<BR> {Dictionary<SPAN class="keyword">.</SPAN>toRecord tor D}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 11.7:</STRONG> Extracting tasks on the same resource.</P><HR></DIV><P> </P><P>The modified scheduling compiler is shown in <A href="node47.html#figure.scheduling.compiler2">Figure 11.8</A>. The returned script uses </P><BLOCKQUOTE class="code"><CODE>{Schedule<SPAN class="keyword">.</SPAN>serializedDisj TasksOnRes Start Dur}</CODE></BLOCKQUOTE><P> to create for each resource a single propagator for the capacity constraints as described in the model above. </P><P></P><DIV id="figure.scheduling.compiler2"><HR><P><A name="figure.scheduling.compiler2"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Compile</SPAN> Spec}<BR> TaskSpec = Spec<SPAN class="keyword">.</SPAN>tasks<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> {Schedule<SPAN class="keyword">.</SPAN>serializedDisj TasksOnRes Start Dur}<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> {FD<SPAN class="keyword">.</SPAN>distribute ff Start}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> </CODE></DD></DL><P class="caption"><STRONG>Figure 11.8:</STRONG> A scheduling compiler with resource constraints.</P><HR></DIV><P> </P><DIV class="exercise" id="scheduling.ex.a"><P><B>Exercise 11.1</B> (<A href="answers.html#label183">See solution</A>)</P><BLOCKQUOTE><P>Write a procedure which implements the capacity constraints of the problem by reified constraints. </P></BLOCKQUOTE></DIV><P>But we are not only interested in the first solution but in the best solution. For our problem we are interested in the solution with the smallest makespan. </P><P>For our example we define the order relation </P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Earlier</SPAN> Old New}<BR> Old<SPAN class="keyword">.</SPAN>pe <SPAN class="keyword">>:</SPAN> New<SPAN class="keyword">.</SPAN>pe<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P> stating that the makespan of the new alternative solution must be strictly smaller than the makespan of the already found solution. We assume that the refined scheduling compiler is the procedure <CODE>CompileHouse2</CODE>. Thus, the best solution for our problem can be found by the following statement. </P><DL class="anonymous"><DD class="code"><CODE>{ExploreBest {Compile House} Earlier}</CODE></DD></DL><P> The first solution which is also the optimal one has a makespan of 21. </P></DIV></DIV><DIV id="sec.serializers"><H3><A name="sec.serializers">11.1.3 Building a House: Serializers</A></H3><P>So far we have used only distribution strategies where a variable is selected first and then the domain is further restricted by a basic constraint. Scheduling applications lead to distribution strategies where we distribute not only with basic constraints but with propagators. </P><DIV class="apropos"><P class="margin">serializers</P><P> In the previous section we have seen that it is necessary to <A name="label141"></A><EM>serialize</EM> all tasks on a common resource to satisfy all capacity constraints. This leads to the idea to use a distributor to serialize the tasks. Such a distributor is called a <A name="label142"></A><EM>serializer</EM>. Thus, we refine the scheduling compiler of the previous section by formulating a new distribution strategy. </P></DIV><P>Note that we have to refine the notion of distribution here. In <A href="node8.html#section.constraints.dast">Section 2.6</A> we have distributed a finite domain problem <IMG alt="P" src="latex20.png"> only with constraints <IMG alt="C" src="latex31.png"> and <IMG alt="\neg C" src="latex63.png">. But we can refine the concept of distribution by distributing with constraints <IMG alt="C_1" src="latex277.png"> and <IMG alt="C_2" src="latex278.png"> whenever <IMG alt="P \models C_1 \vee C_2" src="latex279.png"> holds. </P><P>By this condition we are sure that no solution is lost. For a serializer we distribute with constraints <IMG alt="S_1 + D_1 \leq S_2" src="latex280.png"> and <IMG alt="S_2 + D_2 \leq S_1" src="latex281.png"> where we assume two tasks with start times <IMG alt="S_1" src="latex272.png"> and <IMG alt="S_2" src="latex273.png"> and the durations <IMG alt="D_1" src="latex274.png"> and <IMG alt="D_2" src="latex275.png">, respectively. In the presence of capacity constraints the required condition holds by construction, i. e. <IMG alt="P \models S_1 + D_1 \leq S_2
\vee S_2 + D_2 \leq S_1" src="latex282.png">. </P><DIV class="unnumbered"><H4><A name="label143">Ordering Tasks by Distribution</A></H4><P>We replace the first-fail distribution strategy by a strategy consisting of two phases. In the first phase we serialize all tasks on common resources and in the second phase we determine the start times of the variables. The serialization is achieved by distributing for each pair of tasks <IMG alt="T_1" src="latex283.png"> and <IMG alt="T_2" src="latex284.png"> either with the constraint that task <IMG alt="T_1" src="latex283.png"> is finished before <IMG alt="T_2" src="latex284.png"> starts or that task <IMG alt="T_2" src="latex284.png"> is finished before task <IMG alt="T_1" src="latex283.png"> starts. </P><DIV class="apropos"><P class="margin">ordering of tasks</P><P> If such a distribution step takes place we say that the two concerned tasks are <A name="label144"></A><EM>ordered</EM>. After the serialization we have only constraints of the form <IMG alt="x + c \leq y" src="latex269.png">. Thus, it is sufficient for the second phase to determine each variable to the smallest value in its domain. </P></DIV></DIV><DIV class="unnumbered"><H4><A name="label145">Script</A></H4><P> The script for the third version of our problem refines the one in the previous section by replacing the first fail distributor by a distributor that orders task and assigning minimal start times. The distributor that orders tasks on resources is defined as follows: </P><DL><DT><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A name="label146">Order tasks</A><SPAN class="chunkborder">>=</SPAN></SPAN></DT><DD class="code"><CODE>{Record<SPAN class="keyword">.</SPAN>forAll TasksOnRes <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>}</CODE></DD></DL><P> </P><P></P><DIV id="figure.scheduling.compiler3"><HR><P><A name="figure.scheduling.compiler3"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Compile</SPAN> Spec}<BR> TaskSpec = Spec<SPAN class="keyword">.</SPAN>tasks<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> {Schedule<SPAN class="keyword">.</SPAN>serializedDisj TasksOnRes Start Dur}<BR> </CODE><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A href="node47.html#label146">Order tasks</A><SPAN class="chunkborder">></SPAN></SPAN><CODE> <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.9:</STRONG> A scheduling compiler with task ordering.</P><HR></DIV><P> </P><P>The complete scheduling compiler can be found in <A href="node47.html#figure.scheduling.compiler3">Figure 11.9</A>. The optimal solution can be found by </P><DL class="anonymous"><DD class="code"><CODE>{ExploreBest {Compile House} Earlier}</CODE></DD></DL><P> with 28 choice nodes and 3 solution nodes. Thus, for this problem the use of a serializer results in a larger search tree than the first-fail distributor. In the following section we will tackle a harder problem and we will show that the first-fail strategy as well as the naive serializer of this section completely fail to compute the optimal solution of this more difficult problem. </P></DIV></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node46.html">- Up -</A></TD><TD><A href="node48.html#section.scheduling.bridge">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 (20090610)</SPAN></ADDRESS></BODY></HTML>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bd5c3d824c3db63ffd9226c15941e6ad
>
files
>
1222
