1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  *  Main authors:
4  *     Guido Tack <tack@gecode.org>
5  *     Christian Schulte <schulte@gecode.org>
6  *
7  *  Copyright:
8  *     Guido Tack, 2004
9  *     Christian Schulte, 2004
10  *
11  *  This file is part of Gecode, the generic constraint
12  *  development environment:
13  *     http://www.gecode.org
14  *
15  *  Permission is hereby granted, free of charge, to any person obtaining
16  *  a copy of this software and associated documentation files (the
17  *  "Software"), to deal in the Software without restriction, including
18  *  without limitation the rights to use, copy, modify, merge, publish,
19  *  distribute, sublicense, and/or sell copies of the Software, and to
20  *  permit persons to whom the Software is furnished to do so, subject to
21  *  the following conditions:
22  *
23  *  The above copyright notice and this permission notice shall be
24  *  included in all copies or substantial portions of the Software.
25  *
26  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 
37 #include <gecode/driver.hh>
38 #include <gecode/int.hh>
39 #include <gecode/set.hh>
40 
41 using namespace Gecode;
42 
43 namespace {
44   /// The airline employees
45   typedef enum {
46     Tom, David, Jeremy, Ron,
47     Joe, Bill, Fred,
48     Bob, Mario, Ed,
49     Carol, Janet, Tracy,
50     Marilyn, Carolyn, Cathy,
51     Inez, Jean, Heather, Juliet
52   } Employee;
53   const int noOfEmployees = Juliet+1;
54 
55   /// A flight to schedule
56   struct Flight {
57     int staff;     ///< Overall number of cabin crew needed
58     int stewards;  ///< How many stewards are required
59     int hostesses; ///< How many hostesses are required
60     int french;    ///< How many French speaking employees are required
61     int spanish;   ///< How many Spanish speaking employees are required
62     int german;    ///< How many German speaking employees are required
63   };
64 
65   const char* employeeToName(Employee e);
66   extern const int stewards[];
67   extern const int noOfStewards;
68   extern const int hostesses[];
69   extern const int noOfHostesses;
70   extern const int spanishSpeaking[];
71   extern const int noOfSpanishSpeaking;
72   extern const int frenchSpeaking[];
73   extern const int noOfFrenchSpeaking;
74   extern const int germanSpeaking[];
75   extern const int noOfGermanSpeaking;
76   extern const Flight requiredCrew[];
77   extern const int noOfFlights;
78 }
79 
80 /**
81  * \brief %Example: Airline crew allocation
82  *
83  * Assign 20 flight attendants to 10 flights. Each flight needs a certain
84  * number of cabin crew, and they have to speak certain languages.
85  * Every cabin crew member has two flights off after an attended flight.
86  *
87  * \ingroup Example
88  *
89  */
90 class Crew : public Script {
91 public:
92   /// The crew for each flight
93   SetVarArray flight;
94 
95   /// The actual model
Crew(const Options & opt)96   Crew(const Options& opt)
97     : Script(opt), flight(*this,noOfFlights,IntSet::empty,0,noOfEmployees-1) {
98     IntSet stewardsDS(stewards,noOfStewards);
99     IntSet hostessesDS(hostesses,noOfHostesses);
100     IntSet spanishDS(spanishSpeaking, noOfSpanishSpeaking);
101     IntSet frenchDS(frenchSpeaking, noOfFrenchSpeaking);
102     IntSet germanDS(germanSpeaking, noOfGermanSpeaking);
103 
104     for (int i=0; i<noOfFlights; i++) {
105       // The flight has staff as required by the specification
106       rel(*this, cardinality(flight[i]) == requiredCrew[i].staff);
107 
108       // Enough members of different categories are on board
109       rel(*this, cardinality(flight[i] & stewardsDS) >=
110           requiredCrew[i].stewards);
111       rel(*this, cardinality(flight[i] & hostessesDS) >=
112           requiredCrew[i].hostesses);
113       rel(*this, cardinality(flight[i] & spanishDS) >=
114           requiredCrew[i].spanish);
115       rel(*this, cardinality(flight[i] & frenchDS) >=
116           requiredCrew[i].french);
117       rel(*this, cardinality(flight[i] & germanDS) >=
118           requiredCrew[i].german);
119     }
120 
121     // No crew member of flight i works on flights i+1 and i+2
122     for (int i=0; i<noOfFlights-2; i++) {
123       rel(*this, flight[i] || flight[i+1]);
124       rel(*this, flight[i] || flight[i+2]);
125     }
126     rel(*this, flight[noOfFlights-2] || flight[noOfFlights-1]);
127 
128     branch(*this, flight, SET_VAR_NONE(), SET_VAL_MIN_INC());
129   }
130 
131   /// Print solution
132   virtual void
print(std::ostream & os) const133   print(std::ostream& os) const {
134     for (int i=0; i<noOfFlights; i++) {
135       os << "\tFlight " << i+1 << ":" << std::endl;
136       os << "\t\tCrew\tStew.\tHost.\tFrench\tSpanish\tGerman"
137          << std::endl << "\t";
138       os << "\t" << requiredCrew[i].staff << "\t" << requiredCrew[i].stewards
139          << "\t" << requiredCrew[i].hostesses << "\t"
140          << requiredCrew[i].spanish
141          << "\t" << requiredCrew[i].french << "\t" << requiredCrew[i].german
142          << std::endl;
143 
144       os << "\t\tSchedule:" << std::endl << "\t\t";
145       if (flight[i].assigned()) {
146         for (SetVarGlbValues d(flight[i]);d();++d) {
147           os << employeeToName(static_cast<Employee>(d.val())) << " ";
148         }
149       } else {
150         os << "\tRequired: ";
151         for (SetVarGlbValues d(flight[i]);d();++d) {
152           os << employeeToName(static_cast<Employee>(d.val())) << " ";
153         }
154         os << std::endl << "\t\t\tPossible: ";
155         for (SetVarUnknownValues d(flight[i]);d();++d) {
156           os << employeeToName(static_cast<Employee>(d.val())) << " ";
157         }
158       }
159       os << std::endl << std::endl;
160     }
161   }
162 
163   /// Constructor for cloning \a s
Crew(Crew & s)164   Crew(Crew& s)
165     : Script(s) {
166     flight.update(*this, s.flight);
167   }
168   /// Copy during cloning
169   virtual
copy(void)170   Space *copy(void) {
171     return new Crew(*this);
172   }
173 
174 };
175 
176 /** \brief Main-function
177  *  \relates Crew
178  */
179 int
main(int argc,char * argv[])180 main(int argc, char* argv[]) {
181   Options o("Crew");
182   o.iterations(100);
183   o.parse(argc,argv);
184   Script::run<Crew,DFS,Options>(o);
185   return 0;
186 }
187 
188 namespace {
189 
190   /// Return name of employee \a e as a string
191   const char*
employeeToName(Employee e)192   employeeToName(Employee e) {
193     switch(e) {
194     case Tom : return "Tom";
195     case David : return "David";
196     case Jeremy: return "Jeremy";
197     case Ron: return "Ron";
198     case Joe: return "Joe";
199     case Bill: return "Bill";
200     case Fred: return "Fred";
201     case Bob: return "Bob";
202     case Mario: return "Mario";
203     case Ed: return "Ed";
204     case Carol: return "Carol";
205     case Janet: return "Janet";
206     case Tracy: return "Tracy";
207     case Marilyn: return "Marilyn";
208     case Carolyn: return "Carolyn";
209     case Cathy: return "Cathy";
210     case Inez: return "Inez";
211     case Jean: return "Jean";
212     case Heather: return "Heather";
213     case Juliet: return "Juliet";
214     default: GECODE_NEVER; return "";
215     }
216   }
217 
218   // these have to be sorted!
219   /// The stewards
220   const int stewards[] =
221     {Tom, David, Jeremy, Ron, Joe, Bill, Fred, Bob, Mario, Ed};
222   /// The number of stewards
223   const int noOfStewards = sizeof(stewards) / sizeof(int);
224   /// The hostesses
225   const int hostesses[] =
226     { Carol, Janet, Tracy, Marilyn, Carolyn, Cathy, Inez,
227       Jean, Heather, Juliet };
228   /// The number of hostesses
229   const int noOfHostesses = sizeof(hostesses) / sizeof(int);
230   /// The French speaking employees
231   const int frenchSpeaking[] =
232     { Bill, Inez, Jean, Juliet };
233   /// The number of French speaking employees
234   const int noOfFrenchSpeaking = sizeof(frenchSpeaking) / sizeof(int);
235   /// The German speaking employees
236   const int germanSpeaking[] =
237     { Tom, Jeremy, Mario, Cathy, Juliet };
238   /// The number of German speaking employees
239   const int noOfGermanSpeaking = sizeof(germanSpeaking) / sizeof(int);
240   /// The Spanish speaking employees
241   const int spanishSpeaking[] =
242     { Joe, Bill, Fred, Mario, Marilyn, Inez, Heather };
243   /// The number of Spanish speaking employees
244   const int noOfSpanishSpeaking = sizeof(spanishSpeaking) / sizeof(int);
245 
246   /// The flights to schedule
247   const Flight requiredCrew[] =
248     { {4,1,1,1,1,1},
249       {5,1,1,1,1,1},
250       {5,1,1,1,1,1},
251       {6,2,2,1,1,1},
252       {7,3,3,1,1,1},
253       {4,1,1,1,1,1},
254       {5,1,1,1,1,1},
255       {6,1,1,1,1,1},
256       {6,2,2,1,1,1},
257       {7,3,3,1,1,1} };
258 
259   /// The number of flights to schedule
260   const int noOfFlights = sizeof(requiredCrew) / sizeof(Flight);
261 }
262 
263 // STATISTICS: example-any
264 
265