this repo has no description
dekker.one
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
41using namespace Gecode;
42
43namespace {
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 */
90class Crew : public Script {
91public:
92 /// The crew for each flight
93 SetVarArray flight;
94
95 /// The actual model
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
133 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
164 Crew(Crew& s)
165 : Script(s) {
166 flight.update(*this, s.flight);
167 }
168 /// Copy during cloning
169 virtual
170 Space *copy(void) {
171 return new Crew(*this);
172 }
173
174};
175
176/** \brief Main-function
177 * \relates Crew
178 */
179int
180main(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
188namespace {
189
190 /// Return name of employee \a e as a string
191 const char*
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