/usr/share/mozart/doc/fst/node5.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>5 A Crew Allocation Problem</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="node4.html#fset.examples.binpacking"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node6.html#fset.examples.golf">Next >></A></TD></TR></TABLE><DIV id="fset.examples.crew"><H1><A name="fset.examples.crew">5 A Crew Allocation Problem</A></H1><P class="margin">Problem Specification</P><P> A small air-line has to assign their 20 flight attendants to 10 flights. Each flight has to be accompanied by a certain number of cabin crew (see <A href="node5.html#table.crew_per_flight">Table 5.1</A>) that has to meet a couple of constraints. First, to serve the needs of international clients the cabin crew has to be able to speak German, Spanish, and French (see <A href="node5.html#table.foreign_lang_per_flight">Table 5.2</A>). Further, a minimal number of stewardesses resp. stewards have to attend a flight (see <A href="node5.html#table.sex_per_flight">Table 5.3</A>). Finally, every cabin crew member has two flights off after an attended flight. </P><DIV class="table" id="table.crew_per_flight"><HR><P><A name="table.crew_per_flight"></A></P></DIV><TABLE align="center" class="dyptic"><TR valign="top"><TD><P></P><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TH><P>flight #</P></TH><TH><P># of cabin staff</P></TH></TR><TR valign="top"><TD><P>1</P></TD><TD><P>4</P></TD></TR><TR valign="top"><TD><P>2</P></TD><TD><P>4</P></TD></TR><TR valign="top"><TD><P>3</P></TD><TD><P>5</P></TD></TR><TR valign="top"><TD><P>4</P></TD><TD><P>5</P></TD></TR><TR valign="top"><TD><P>5</P></TD><TD><P>6</P></TD></TR></TABLE><P></P></TD><TD><P></P><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TH><P>flight #</P></TH><TH><P># of cabin staff</P></TH></TR><TR valign="top"><TD><P>6</P></TD><TD><P>4</P></TD></TR><TR valign="top"><TD><P>7</P></TD><TD><P>4</P></TD></TR><TR valign="top"><TD><P>8</P></TD><TD><P>5</P></TD></TR><TR valign="top"><TD><P>9</P></TD><TD><P>5</P></TD></TR><TR valign="top"><TD><P>10</P></TD><TD><P>6</P></TD></TR></TABLE><P></P></TD></TR></TABLE><DIV class="table"><P class="caption"><STRONG>Table 5.1:</STRONG> Cabin crew per flight.</P><HR></DIV><P> </P><DIV class="table" id="table.foreign_lang_per_flight"><HR><P><A name="table.foreign_lang_per_flight"></A></P></DIV><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TD><P></P><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TH><P>flight #</P></TH><TH><P>French</P></TH><TH><P>Spanish</P></TH><TH><P>German</P></TH></TR><TR valign="top"><TD><P>1</P></TD><TD><P>1</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>2</P></TD><TD><P>1</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>3</P></TD><TD><P>1</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>4</P></TD><TD><P>2</P></TD><TD><P>2</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>5</P></TD><TD><P>2</P></TD><TD><P>2</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>6</P></TD><TD><P>1</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>7</P></TD><TD><P>1</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>8</P></TD><TD><P>1</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>9</P></TD><TD><P>1</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>10</P></TD><TD><P>1</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR></TABLE><P></P></TD></TR></TABLE><DIV class="table"><P class="caption"><STRONG>Table 5.2:</STRONG> Cabin crew speaking foreign language per flight.</P><HR></DIV><P> </P><DIV class="table" id="table.sex_per_flight"><HR><P><A name="table.sex_per_flight"></A></P></DIV><TABLE align="center" class="dyptic"><TR valign="top"><TD><P></P><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TH><P>flight #</P></TH><TH><P>male</P></TH><TH><P>female</P></TH></TR><TR valign="top"><TD><P>1</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>2</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>3</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>4</P></TD><TD><P>2</P></TD><TD><P>2</P></TD></TR><TR valign="top"><TD><P>5</P></TD><TD><P>3</P></TD><TD><P>2</P></TD></TR></TABLE><P></P></TD><TD><P></P><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TH><P>flight #</P></TH><TH><P>male</P></TH><TH><P>female</P></TH></TR><TR valign="top"><TD><P>6</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>7</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>8</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>9</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR><TR valign="top"><TD><P>10</P></TD><TD><P>1</P></TD><TD><P>1</P></TD></TR></TABLE><P></P></TD></TR></TABLE><DIV class="table"><P class="caption"><STRONG>Table 5.3:</STRONG> Male resp. female cabin crew per flight.</P><HR></DIV><P> </P><P class="margin">Model</P><P> The cabin crew for every flight is represented as a set. The constraints on cabin crews of individual flights are modeled in terms of constraints on the cardinality of the intersection of the cabin crew set of that flight with the sets associated with particular restrictions. Therefore the following subsets of the cabin crew are introduced: male, female, Spanish-speaking, French-speaking, and German-speaking cabin crew. The constraint that a crew member has two flights off after an attended flight is expressed by the disjointness of the appropriate sets representing a crew per flight. </P><P class="margin">Solver</P><P> The function <CODE>AssignCrew</CODE> returns a solver configured according to its arguments <CODE>FlightData</CODE> and <CODE>Crew</CODE>. As previously mentioned, the constraints on the cabin crew of a flight are expressed in terms of sets of crew members meeting these constraints. For that reason the following variables are defined: </P><UL><LI><P><CODE>Stewards</CODE> (male cabin crew members), </P></LI><LI><P><CODE>Stewardesses</CODE> (female cabin crew members), </P></LI><LI><P><CODE>FrenchSpeaking</CODE>, <CODE>GermanSpeaking</CODE>, and <CODE>SpanishSpeaking</CODE> (French-, German-, resp. Spanish-speaking cabin crew members). </P></LI></UL><P> Procedure <CODE>TeamConstraint</CODE> imposes the abovementioned constraints on the individual flight cabin crew sets intersecting them with appropriate sets (<CODE>FS<SPAN class="keyword">.</SPAN>intersection</CODE>), and constrains the intersection's cardinality according to <A href="node5.html#table.crew_per_flight">Table 5.1</A>, <A href="node5.html#table.foreign_lang_per_flight">Table 5.2</A>, and <A href="node5.html#table.sex_per_flight">Table 5.3</A> (using <CODE>FS<SPAN class="keyword">.</SPAN>card</CODE> and <CODE><SPAN class="keyword">>=:</SPAN></CODE>). </P><P> The procedure <CODE>SequenceDisjoint</CODE> is responsible to ensure that every crew member may enjoy a two-flight break between two flights. It is a recursive procedure imposing <CODE>FS<SPAN class="keyword">.</SPAN>disjoint</CODE> upon every 3 subsequent sets. </P><P> The actual solver declares the local variable <CODE>Flights</CODE> that contains the list of sets representing the individual crew assignments. Then, the constraints of the procedure <CODE>TeamConstraint</CODE> are imposed on <CODE>Flights</CODE> by the <CODE>Map</CODE> loop, by mapping the data provided by <CODE>FlightData</CODE> to <CODE>Flights</CODE>. The distribution is straightforward and has no particularities. </P><P class="margin">Dealing with sets of literals</P><P> Often real-life applications deal with sets of names, descriptions and the like rather than integers, which can be represented by Oz literals. The functions <CODE>SetOfLiterals</CODE>, <CODE>Lits2Ints</CODE>, and <CODE>Ints2Lits</CODE> allow to model sets of literals. The function <CODE>SetOfLiterals</CODE> returns an abstract data structure that enables <CODE>Lits2Ints</CODE> and <CODE>Ints2Lits</CODE> to map literals to integers and vice versa. The last line of the solver procedure converts the internal solution to a representation corresponding to the format of <CODE>AssignCrew</CODE>'s argument <CODE>Crew</CODE> (see below). </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">declare</SPAN> <BR> <BR><SPAN class="keyword">local</SPAN> <BR> Lit2Int = {NewName}<BR> Int2Lit = {NewName}<BR><SPAN class="keyword">in</SPAN> <BR> <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">SetOfLiterals</SPAN> Lits}<BR> sol(Lit2Int:<BR> {NewChunk<BR> {List<SPAN class="keyword">.</SPAN>toRecord l2i<BR> {List<SPAN class="keyword">.</SPAN>mapInd Lits <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> I L}<BR> L<SPAN class="keyword">#</SPAN>I<BR> <SPAN class="keyword">end</SPAN>}}}<BR> Int2Lit:<BR> {NewChunk<BR> {List<SPAN class="keyword">.</SPAN>toRecord i2l<BR> {List<SPAN class="keyword">.</SPAN>mapInd Lits <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> I L}<BR> I<SPAN class="keyword">#</SPAN>L<BR> <SPAN class="keyword">end</SPAN>}}})<BR> <SPAN class="keyword">end</SPAN> <BR> <BR> <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Lits2Ints</SPAN> SetOfLiterals Literals}<BR> {Map Literals <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Lit}<BR> SetOfLiterals<SPAN class="keyword">.</SPAN>Lit2Int<SPAN class="keyword">.</SPAN>Lit<BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN> <BR> <BR> <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Ints2Lits</SPAN> SetOfLiterals Ints}<BR> {Map Ints <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Int}<BR> SetOfLiterals<SPAN class="keyword">.</SPAN>Int2Lit<SPAN class="keyword">.</SPAN>Int<BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> <BR> <BR><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">CrewProb</SPAN> FlightData Crew}<BR> CabinStaff = {Append Crew<SPAN class="keyword">.</SPAN>stewards Crew<SPAN class="keyword">.</SPAN>stewardesses}<BR> CrewSet = {SetOfLiterals CabinStaff}<BR> Stewards = {FS<SPAN class="keyword">.</SPAN>value<SPAN class="keyword">.</SPAN>make<BR> {Lits2Ints CrewSet Crew<SPAN class="keyword">.</SPAN>stewards}}<BR> Stewardesses = {FS<SPAN class="keyword">.</SPAN>value<SPAN class="keyword">.</SPAN>make<BR> {Lits2Ints CrewSet Crew<SPAN class="keyword">.</SPAN>stewardesses}}<BR> FrenchSpeaking = {FS<SPAN class="keyword">.</SPAN>value<SPAN class="keyword">.</SPAN>make<BR> {Lits2Ints CrewSet Crew<SPAN class="keyword">.</SPAN>frenchspeaking}}<BR> GermanSpeaking = {FS<SPAN class="keyword">.</SPAN>value<SPAN class="keyword">.</SPAN>make<BR> {Lits2Ints CrewSet Crew<SPAN class="keyword">.</SPAN>germanspeaking}}<BR> SpanishSpeaking = {FS<SPAN class="keyword">.</SPAN>value<SPAN class="keyword">.</SPAN>make<BR> {Lits2Ints CrewSet Crew<SPAN class="keyword">.</SPAN>spanishspeaking}}<BR> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">TeamConstraint</SPAN> Team Flight}<BR> flight(no:_ crew:N stewards:NStew stewardesses:NHost<BR> frenchspeaking:NFrench germanspeaking:NGerman<BR> spanishspeaking:NSpanish) = Flight<BR> <SPAN class="keyword">in</SPAN> <BR> {FS<SPAN class="keyword">.</SPAN>card Team N}<BR> {FS<SPAN class="keyword">.</SPAN>card<BR> {FS<SPAN class="keyword">.</SPAN>intersect Team Stewards}} <SPAN class="keyword">>=:</SPAN> NStew<BR> {FS<SPAN class="keyword">.</SPAN>card<BR> {FS<SPAN class="keyword">.</SPAN>intersect Team Stewardesses}} <SPAN class="keyword">>=:</SPAN> NHost<BR> {FS<SPAN class="keyword">.</SPAN>card<BR> {FS<SPAN class="keyword">.</SPAN>intersect Team FrenchSpeaking}} <SPAN class="keyword">>=:</SPAN> NFrench<BR> {FS<SPAN class="keyword">.</SPAN>card<BR> {FS<SPAN class="keyword">.</SPAN>intersect Team GermanSpeaking}} <SPAN class="keyword">>=:</SPAN> NGerman<BR> {FS<SPAN class="keyword">.</SPAN>card<BR> {FS<SPAN class="keyword">.</SPAN>intersect Team SpanishSpeaking}} <SPAN class="keyword">>=:</SPAN> NSpanish<BR> <SPAN class="keyword">end</SPAN> <BR> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">SequencedDisjoint</SPAN> L}<BR> <SPAN class="keyword">case</SPAN> L <SPAN class="keyword">of</SPAN> A<SPAN class="keyword">|</SPAN>B<SPAN class="keyword">|</SPAN>C<SPAN class="keyword">|</SPAN>T <SPAN class="keyword">then</SPAN> <BR> {FS<SPAN class="keyword">.</SPAN>disjoint A B}<BR> {FS<SPAN class="keyword">.</SPAN>disjoint A C}<BR> {SequencedDisjoint B<SPAN class="keyword">|</SPAN>C<SPAN class="keyword">|</SPAN>T}<BR> <SPAN class="keyword">elseof</SPAN> A<SPAN class="keyword">|</SPAN>B<SPAN class="keyword">|</SPAN>nil <SPAN class="keyword">then</SPAN> <BR> {FS<SPAN class="keyword">.</SPAN>disjoint A B}<BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">in</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Sol}<BR> Flights = {FS<SPAN class="keyword">.</SPAN>var<SPAN class="keyword">.</SPAN>list<SPAN class="keyword">.</SPAN>upperBound<BR> {Length FlightData}<BR> {Lits2Ints CrewSet CabinStaff}}<BR> <SPAN class="keyword">in</SPAN> <BR> {Map FlightData <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> D F}<BR> {TeamConstraint F D}<BR> <SPAN class="keyword">end</SPAN> Flights}<BR> <BR> {SequencedDisjoint Flights}<BR> <BR> {FS<SPAN class="keyword">.</SPAN>distribute naive Flights}<BR> <BR> Sol = {Map Flights<BR> <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> F}<BR> {Ints2Lits CrewSet {FS<SPAN class="keyword">.</SPAN>monitorIn F}}<BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> <BR></PRE></BLOCKQUOTE><P> </P><P> The following sample data can be used to test the solver: </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">declare</SPAN> <BR>Flights =<BR>[flight(no: 1 crew:4 stewards:1 stewardesses:1<BR> frenchspeaking:1 spanishspeaking:1<BR> germanspeaking:1)<BR> flight(no: 2 crew:5 stewards:1 stewardesses:1<BR> frenchspeaking:1 spanishspeaking:1<BR> germanspeaking:1)<BR> flight(no: 3 crew:5 stewards:1 stewardesses:1<BR> frenchspeaking:1 spanishspeaking:1<BR> germanspeaking:1)<BR> flight(no: 4 crew:6 stewards:2 stewardesses:2<BR> frenchspeaking:1 spanishspeaking:1<BR> germanspeaking:1)<BR> flight(no: 5 crew:7 stewards:3 stewardesses:3<BR> frenchspeaking:1 spanishspeaking:1<BR> germanspeaking:1)<BR> flight(no: 6 crew:4 stewards:1 stewardesses:1<BR> frenchspeaking:1 spanishspeaking:1<BR> germanspeaking:1)<BR> flight(no: 7 crew:5 stewards:1 stewardesses:1<BR> frenchspeaking:1 spanishspeaking:1<BR> germanspeaking:1)<BR> flight(no: 8 crew:6 stewards:1 stewardesses:1<BR> frenchspeaking:1 spanishspeaking:1<BR> germanspeaking:1)<BR> flight(no: 9 crew:6 stewards:2 stewardesses:2<BR> frenchspeaking:1 spanishspeaking:1<BR> germanspeaking:1)<BR> flight(no:10 crew:7 stewards:3 stewardesses:3<BR> frenchspeaking:1 spanishspeaking:1<BR> germanspeaking:1)]<BR> <BR>Crew =<BR>crew(stewards:<BR> [tom david jeremy ron joe bill fred bob mario ed]<BR> stewardesses:<BR> [carol janet tracy marilyn carolyn cathy inez<BR> jean heather juliet]<BR> frenchspeaking:<BR> [inez bill jean juliet]<BR> germanspeaking:<BR> [tom jeremy mario cathy juliet]<BR> spanishspeaking:<BR> [bill fred joe mario marilyn inez heather])<BR></PRE></BLOCKQUOTE><P> Running the solver by <CODE>{ExploreOne {AssignCrew Flights Crew}}</CODE>. and invoking the Oz Browser on the solution node results in: </P><P></P><DIV align="center"><IMG alt="" src="crew_browser.gif" id="pic.crew_browser"></DIV><P> </P><P> The flights are to be attended in the order they appear in the solution list. Each sublist denotes the assignment for an individual flight. </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node4.html#fset.examples.binpacking"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node6.html#fset.examples.golf">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~tmueller/">Tobias Müller</A><BR><SPAN class="version">Version 1.4.0 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|