/usr/share/mozart/doc/fdt/node51.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.5 Solving Hard Scheduling Problems</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="node50.html#section.scheduling.strongser"><< Prev</A></TD><TD><A href="node46.html">- Up -</A></TD></TR></TABLE><DIV id="section.scheduling.hard"><H2><A name="section.scheduling.hard">11.5 Solving Hard Scheduling Problems</A></H2><P>In this section we tackle more difficult scheduling problems. To this aim we will also develop a new serializer. </P><P>We consider two problems in this section. Both are used as standard benchmark problems for scheduling. The first one is called ABZ6 and was introduced in <A href="bib.html#adams.88">[ABZ88]</A>. The second one is the famous MT10 and was introduced in <A href="bib.html#muth.63">[MT63]</A>. MT10 was considered as an especially hard problem for several years. It took more than 25 years that the optimality of a found makespan was proven <A href="bib.html#carlier.89">[CP89]</A>. </P><P>These problems belong to the class of so-called job-shop problems (see <A href="bib.html#garey.79">[GJ79]</A> or a good text book on scheduling). We slightly simplify the definition for our purposes. A job-shop problem consists of <IMG alt="n" src="latex43.png"> jobs of tasks. Each job <IMG alt="j" src="latex119.png"> consists of <IMG alt="m" src="latex93.png"> tasks <IMG alt="t^j_1" src="latex348.png"> through <IMG alt="t^j_m" src="latex349.png"> such that each task of the job is scheduled on a different (unary) resource. Thus, we have <IMG alt="m" src="latex93.png"> resources. Furthermore, we have the constraint <IMG alt="t^j_i + \Dur{t^j_i} \leq t^j_{i+1}" src="latex350.png"> for all tasks of job <IMG alt="j" src="latex119.png">, i. e. the tasks in a job are serialized. The latter constraints are already known as precedence constraints (see <A href="node47.html#sec.precedence">Section 11.1.1</A>). </P><H3><A name="label160">11.5.1 The Problem ABZ6</A></H3><P>We will consider problem ABZ6 first. The specification is given in <A href="node54.html#data.abz6">*</A>. The problem consists of 10 jobs and 10 resources. We first search for the optimal solution and prove its optimality: </P><DL class="anonymous"><DD class="code"><CODE>{ExploreBest {Compile ABZ6<BR> Schedule<SPAN class="keyword">.</SPAN>serialized<BR> Schedule<SPAN class="keyword">.</SPAN>firstsLastsDist} <BR> Earlier}</CODE></DD></DL><P> The resulting search tree contains 2424 choice nodes. The optimal makespan is 943. </P><P>We now only want to prove the optimality of the makespan 943. To this aim we declare a modified problem as follows. </P><DL class="anonymous"><DD class="code"><CODE>OptABZ6 = {AdjoinAt ABZ6 constraints<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Start Dur}<BR> Start<SPAN class="keyword">.</SPAN>pe <SPAN class="keyword"><:</SPAN> 943<BR> <SPAN class="keyword">end</SPAN>}</CODE></DD></DL><P> The proof of optimality needs 761 choice nodes. </P><P>Hence, the problem <CODE>ABZ6</CODE> seems to be rather easy to solve and we can try our previous bottleneck serializer <CODE>DistributeSorted</CODE>. To find the optimal solution and to prove its optimality a search tree is computed which contains more than 1.2 million choice nodes. Therefore, the problem <EM>is</EM> difficult for our simpler strategies and the gain by our new serializer is dramatic. </P><P>But we can do still better. To this aim we introduce a new serializer. This serializer will not serialize one resource after the other as the previous serializer. Instead a resource <IMG alt="r" src="latex319.png"> is selected first. Then two tasks are selected which are running on <IMG alt="r" src="latex319.png"> and it is distributed with a certain ordering. For the resource selection a criterion is used which combines the global slack and the local slack of each resource. For the task ordering the sets <IMG alt="F" src="latex341.png"> and <IMG alt="L" src="latex100.png"> are computed as shown in the previous section. From these sets two tasks are selected according to a subtle criterion (see <A href="bib.html#caseau.94a">[CL94]</A>). After an ordering decision is made by distribution the process is repeated until all resources are serialized. In contrast to the strategy in <A href="node50.html#section.scheduling.strongser">Section 11.4</A>, a task pair on a resource may be ordered without that the resource which was previously considered needs to be serialized. </P><DIV class="apropos"><P class="margin">task-oriented</P><P> Thus, we call such a serializer a <A name="label161"></A><EM>task-oriented serializer</EM> The strategy implemented in Oz is very similar to the one suggested in <A href="bib.html#caseau.94a">[CL94]</A>. </P></DIV><P>Since we have to compute local slacks, the serializer has a run time complexity of <IMG alt="O(m \cdot n^3)" src="latex346.png"> in each step. Thus, it is more expensive than the resource-oriented serializer of the previous section. Furthermore, the use of this serializer might result in very deep search trees because we order only two tasks at each choice node. But the presented task-oriented serializer has a very important operational behavior besides the fact that it is used for distribution. While it is computing the local slacks of the resources it additionally employs edge-finding for the task intervals considered during this computation. In this way, the serializer may detect several orderings which must hold by the edge-finding rules presented in <A href="node49.html#section.scheduling.edgefinding">Section 11.3</A>. This information is exploited at each choice node by additionally creating the corresponding propagators. Thus, the serializer orders two tasks by distribution and simultaneously adds orderings which are detected deterministically. By this approach the search tree may be reduced dramatically if edge-finding can be applied. As we have seen before, this is the case when the domains are rather narrow, i. e. for example when we want to prove optimality. </P><P>Oz provides the serializer <CODE>Schedule<SPAN class="keyword">.</SPAN>taskIntervalsDistP</CODE> which has the described behavior. To prove optimality for <CODE>ABZ6</CODE> we now only need 145 choice nodes. </P><P>This serializer is especially designed for proving optimality. Hence, do not use this strategy when you want to find the optimal solution from scratch. If we search for the optimal solution the search tree becomes rather deep (a depth larger than 450) (including the proof of optimality) and the full tree contains more than 47000 choice nodes. </P><P>A variant of this task-oriented serializer is especially designed to find good solutions. To this aim Oz provides <CODE>Schedule<SPAN class="keyword">.</SPAN>taskIntervalsDistO</CODE> (see also <A href="bib.html#caseau.95">[CL95]</A>). To find the optimal solution and to prove its optimality with this strategy we need 2979 choice nodes. But be aware that the use of this strategy may also lead to deep search trees which result in high memory consumption. </P><H3><A name="label162">11.5.2 The MT10 Problem</A></H3><P>In this section we tackle the famous <CODE>MT10</CODE> problem (the data specification is <A href="node54.html#data.mt10">*</A>). From the literature we know that 930 is the optimal makespan and we can define a script (compiled from <CODE>OptMT10</CODE>, see <A href="node54.html#data.optmt10">*</A>) which can be used for proving optimality. The proof of optimality can be done with 1850 choice nodes: </P><DL class="anonymous"><DD class="code"><CODE>{ExploreBest {Compile OptMT10<BR> Schedule<SPAN class="keyword">.</SPAN>serialized<BR> Schedule<SPAN class="keyword">.</SPAN>taskIntervalsDistP}<BR> Earlier}</CODE></DD></DL><P> </P><P>Note that the depth of the search tree is only 39. This emphasizes the fact that many orderings can be determined by edge-finding which is employed by the task-oriented serializer. </P><P>To find the optimal solution we better use the serializer <CODE>Schedule<SPAN class="keyword">.</SPAN>firstsLastsDist</CODE>: </P><DL class="anonymous"><DD class="code"><CODE>{ExploreBest {Compile MT10<BR> Schedule<SPAN class="keyword">.</SPAN>serialized<BR> Schedule<SPAN class="keyword">.</SPAN>firstsLastsDist} <BR> Earlier}</CODE></DD></DL><P> The full search tree to find the optimal solution and to prove its optimality contains 16779 choice nodes and has depth 91. </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node50.html#section.scheduling.strongser"><< Prev</A></TD><TD><A href="node46.html">- Up -</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>
|