<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>6.2 Example: Conference</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="node28.html#section.minimizing.mapcolor"><< Prev</A></TD><TD><A href="node27.html">- Up -</A></TD></TR></TABLE><DIV id="section.minimizing.conference"><H2><A name="section.minimizing.conference">6.2 Example: Conference</A></H2><P>This example will employ the constraint provided by <CODE>FD<SPAN class="keyword">.</SPAN>atMost</CODE>. </P><DIV class="unnumbered"><H3><A name="label83">Problem Specification</A></H3><P>We want to construct the time table of a conference. The conference will consist of 11 sessions of equal length. The time table is to be organized as a sequence of slots, where a slot can take up to 3 parallel sessions. There are the following constraints on the timing of the sessions: </P><OL type="1"><LI><P>Session 4 must take place before Session 11.</P></LI><LI><P>Session 5 must take place before Session 10.</P></LI><LI><P>Session 6 must take place before Session 11.</P></LI><LI><P>Session 1 must not be in parallel with Sessions 2, 3, 5, 7, 8, and 10.</P></LI><LI><P>Session 2 must not be in parallel with Sessions 3, 4, 7, 8, 9, and 11.</P></LI><LI><P>Session 3 must not be in parallel with Sessions 5, 6, and 8.</P></LI><LI><P>Session 4 must not be in parallel with Sessions 6, 8, and 10.</P></LI><LI><P>Session 6 must not be in parallel with Sessions 7 and 10.</P></LI><LI><P>Session 7 must not be in parallel with Sessions 8 and 9.</P></LI><LI><P>Session 8 must not be in parallel with Session 10.</P></LI></OL><P> The time table should minimize the number of slots. </P></DIV><DIV class="unnumbered"><H3><A name="label84">Model</A></H3><P>The model has a variable <IMG alt="{\it NbSlots}" src="latex134.png"> saying how many slots the conference has. For the given data, <IMG alt="{\it NbSlots}" src="latex134.png"> can be constrained to the finite domain <IMG alt="4\#{11}" src="latex135.png">. The model also has a variable <IMG alt="{\it Plan}_i" src="latex136.png"> for every session <IMG alt="i" src="latex115.png">, where <IMG alt="{\it Plan}_i" src="latex136.png"> stands for the number of the slot in which Session <IMG alt="i" src="latex115.png"> will take place. Every variable <IMG alt="{\it Plan}_i" src="latex136.png"> can be constrained to the finite domain <IMG alt="1\#{\it NbSlots}" src="latex137.png">. The remaining constraints are obvious from the problem description. </P></DIV><DIV class="unnumbered"><H3><A name="label85">Distribution Strategy</A></H3><P>We use a two-dimensional distribution strategy. We first distribute on <IMG alt="{\it NbSlots}" src="latex134.png">, trying smaller values first. Once <IMG alt="{\it NbSlots}" src="latex134.png"> is determined, we distribute on the variables <IMG alt="{\it Plan}_1,\ldots,{\it Plan}_{11}" src="latex138.png"> using the standard first-fail strategy. </P><P></P><DIV id="progconference"><HR><P><A name="progconference"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Conference</SPAN> Data}<BR> NbSessions = Data<SPAN class="keyword">.</SPAN>nbSessions<BR> NbParSessions = Data<SPAN class="keyword">.</SPAN>nbParSessions<BR> Constraints = Data<SPAN class="keyword">.</SPAN>constraints<BR> MinNbSlots = NbSessions <SPAN class="keyword">div</SPAN> NbParSessions<BR><SPAN class="keyword">in</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Plan}<BR> NbSlots = {FD<SPAN class="keyword">.</SPAN>int MinNbSlots<SPAN class="keyword">#</SPAN>NbSessions}<BR> <SPAN class="keyword">in</SPAN> <BR> {FD<SPAN class="keyword">.</SPAN>distribute naive [NbSlots]}<BR> %% <SPAN class="comment">Plan: Session --> Slot<BR></SPAN> {FD<SPAN class="keyword">.</SPAN>tuple plan NbSessions 1<SPAN class="keyword">#</SPAN>NbSlots Plan}<BR> %% <SPAN class="comment">at most NbParSessions per slot<BR></SPAN> {For 1 NbSlots 1 <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Slot} {FD<SPAN class="keyword">.</SPAN>atMost NbParSessions Plan Slot} <SPAN class="keyword">end</SPAN>}<BR> %% <SPAN class="comment">impose constraints<BR></SPAN> {ForAll Constraints<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> C}<BR> <SPAN class="keyword">case</SPAN> C<BR> <SPAN class="keyword">of</SPAN> before(X Y) <SPAN class="keyword">then</SPAN> <BR> Plan<SPAN class="keyword">.</SPAN>X <SPAN class="keyword"><:</SPAN> Plan<SPAN class="keyword">.</SPAN>Y<BR> <SPAN class="keyword">[]</SPAN> disjoint(X Ys) <SPAN class="keyword">then</SPAN> <BR> {ForAll Ys <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Y} Plan<SPAN class="keyword">.</SPAN>X <SPAN class="keyword">\=:</SPAN> Plan<SPAN class="keyword">.</SPAN>Y <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN>}<BR> {FD<SPAN class="keyword">.</SPAN>distribute ff Plan}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> <BR> <BR>Data = data(nbSessions:11 nbParSessions:3<BR> constraints: [ before(4 11) before(5 10) before(6 11)<BR> disjoint(1 [2 3 5 7 8 10])<BR> disjoint(2 [3 4 7 8 9 11])<BR> disjoint(3 [5 6 8]) disjoint(4 [6 8 10])<BR> disjoint(6 [7 10]) disjoint(7 [8 9])<BR> disjoint(8 [10]) ] )</CODE></DD></DL><P class="caption"><STRONG>Figure 6.2:</STRONG> A script for conference scheduling together with a data specification.</P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label86">Script</A></H3><P>The script in <A href="node29.html#progconference">Figure 6.2</A> is parameterized with an argument <CODE>Data</CODE> specifying the conference to be organized. The figure also shows the specification of the conference described in the problem specification. </P><P>The script creates a local variable <CODE>NbSlots</CODE> specifying the number of slots used by the conference. It then distributes naively on <CODE>NbSlots</CODE>. After <CODE>NbSlots</CODE> is determined, it constrains its root variable <CODE>Plan</CODE> to a tuple mapping the session numbers <CODE>1</CODE>, ..., <CODE>11</CODE> to integers in <CODE>1<SPAN class="keyword">#</SPAN>NbSlots</CODE>. This implicitly creates variables corresponding to the variables <IMG alt="{\it
Plan}_i" src="latex139.png"> of the model. </P><P>The statement </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>atMost NbParSessions Plan Slot}</CODE></BLOCKQUOTE><P> creates a propagator for a constraint saying that at most <CODE>NbParSessions</CODE> components of <CODE>Plan</CODE> can be equal to <CODE>Slot</CODE>. </P><P>The statement <CODE>{ForAll Constraints <SPAN class="keyword">...</SPAN> }</CODE> imposes the constraints of the conference to be scheduled. </P><P>The last statement distributes on <CODE>Plan</CODE> using the first-fail strategy. </P><P>The statement </P><BLOCKQUOTE class="code"><CODE>{ExploreOne {Conference Data}}</CODE></BLOCKQUOTE><P> will explore the search tree until the first solution is found. The first solution minimizes the number of slots and looks as follows: </P><BLOCKQUOTE class="code"><CODE>plan(1 2 3 1 2 2 3 4 1 3 4)</CODE></BLOCKQUOTE><P> This plan says that the conference requires 4 slots, where the sessions 1, 4 and 9 take place in slot 1, the sessions 2, 5 and 6 take place in slot 2, the sessions 3, 7 and 10 take place in slot 3, and the sessions 8 and 11 take place in slot 4. </P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node28.html#section.minimizing.mapcolor"><< Prev</A></TD><TD><A href="node27.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 (20090610)</SPAN></ADDRESS></BODY></HTML>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bd5c3d824c3db63ffd9226c15941e6ad
>
files
>
1202
