00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037 #include <gecode/driver.hh>
00038 #include <gecode/int.hh>
00039 #include <gecode/set.hh>
00040
00041 using namespace Gecode;
00042
00043 namespace {
00045 typedef enum {
00046 Tom, David, Jeremy, Ron,
00047 Joe, Bill, Fred,
00048 Bob, Mario, Ed,
00049 Carol, Janet, Tracy,
00050 Marilyn, Carolyn, Cathy,
00051 Inez, Jean, Heather, Juliet
00052 } Employee;
00053 const int noOfEmployees = Juliet+1;
00054
00056 struct Flight {
00057 int staff;
00058 int stewards;
00059 int hostesses;
00060 int french;
00061 int spanish;
00062 int german;
00063 };
00064
00065 const char* employeeToName(Employee e);
00066 extern const int stewards[];
00067 extern const int noOfStewards;
00068 extern const int hostesses[];
00069 extern const int noOfHostesses;
00070 extern const int spanishSpeaking[];
00071 extern const int noOfSpanishSpeaking;
00072 extern const int frenchSpeaking[];
00073 extern const int noOfFrenchSpeaking;
00074 extern const int germanSpeaking[];
00075 extern const int noOfGermanSpeaking;
00076 extern const Flight requiredCrew[];
00077 extern const int noOfFlights;
00078 }
00079
00090 class Crew : public Script {
00091 public:
00093 SetVarArray flight;
00094
00096 Crew(const Options& opt)
00097 : Script(opt), flight(*this,noOfFlights,IntSet::empty,0,noOfEmployees-1) {
00098 IntSet stewardsDS(stewards,noOfStewards);
00099 IntSet hostessesDS(hostesses,noOfHostesses);
00100 IntSet spanishDS(spanishSpeaking, noOfSpanishSpeaking);
00101 IntSet frenchDS(frenchSpeaking, noOfFrenchSpeaking);
00102 IntSet germanDS(germanSpeaking, noOfGermanSpeaking);
00103
00104 for (int i=0; i<noOfFlights; i++) {
00105
00106 rel(*this, cardinality(flight[i]) == requiredCrew[i].staff);
00107
00108
00109 rel(*this, cardinality(flight[i] & stewardsDS) >=
00110 requiredCrew[i].stewards);
00111 rel(*this, cardinality(flight[i] & hostessesDS) >=
00112 requiredCrew[i].hostesses);
00113 rel(*this, cardinality(flight[i] & spanishDS) >=
00114 requiredCrew[i].spanish);
00115 rel(*this, cardinality(flight[i] & frenchDS) >=
00116 requiredCrew[i].french);
00117 rel(*this, cardinality(flight[i] & germanDS) >=
00118 requiredCrew[i].german);
00119 }
00120
00121
00122 for (int i=0; i<noOfFlights-2; i++) {
00123 rel(*this, flight[i] || flight[i+1]);
00124 rel(*this, flight[i] || flight[i+2]);
00125 }
00126 rel(*this, flight[noOfFlights-2] || flight[noOfFlights-1]);
00127
00128 branch(*this, flight, SET_VAR_NONE(), SET_VAL_MIN_INC());
00129 }
00130
00132 virtual void
00133 print(std::ostream& os) const {
00134 for (int i=0; i<noOfFlights; i++) {
00135 os << "\tFlight " << i+1 << ":" << std::endl;
00136 os << "\t\tCrew\tStew.\tHost.\tFrench\tSpanish\tGerman"
00137 << std::endl << "\t";
00138 os << "\t" << requiredCrew[i].staff << "\t" << requiredCrew[i].stewards
00139 << "\t" << requiredCrew[i].hostesses << "\t"
00140 << requiredCrew[i].spanish
00141 << "\t" << requiredCrew[i].french << "\t" << requiredCrew[i].german
00142 << std::endl;
00143
00144 os << "\t\tSchedule:" << std::endl << "\t\t";
00145 if (flight[i].assigned()) {
00146 for (SetVarGlbValues d(flight[i]);d();++d) {
00147 os << employeeToName(static_cast<Employee>(d.val())) << " ";
00148 }
00149 } else {
00150 os << "\tRequired: ";
00151 for (SetVarGlbValues d(flight[i]);d();++d) {
00152 os << employeeToName(static_cast<Employee>(d.val())) << " ";
00153 }
00154 os << std::endl << "\t\t\tPossible: ";
00155 for (SetVarUnknownValues d(flight[i]);d();++d) {
00156 os << employeeToName(static_cast<Employee>(d.val())) << " ";
00157 }
00158 }
00159 os << std::endl << std::endl;
00160 }
00161 }
00162
00164 Crew(Crew& s)
00165 : Script(s) {
00166 flight.update(*this, s.flight);
00167 }
00169 virtual
00170 Space *copy(void) {
00171 return new Crew(*this);
00172 }
00173
00174 };
00175
00179 int
00180 main(int argc, char* argv[]) {
00181 Options o("Crew");
00182 o.iterations(100);
00183 o.parse(argc,argv);
00184 Script::run<Crew,DFS,Options>(o);
00185 return 0;
00186 }
00187
00188 namespace {
00189
00191 const char*
00192 employeeToName(Employee e) {
00193 switch(e) {
00194 case Tom : return "Tom";
00195 case David : return "David";
00196 case Jeremy: return "Jeremy";
00197 case Ron: return "Ron";
00198 case Joe: return "Joe";
00199 case Bill: return "Bill";
00200 case Fred: return "Fred";
00201 case Bob: return "Bob";
00202 case Mario: return "Mario";
00203 case Ed: return "Ed";
00204 case Carol: return "Carol";
00205 case Janet: return "Janet";
00206 case Tracy: return "Tracy";
00207 case Marilyn: return "Marilyn";
00208 case Carolyn: return "Carolyn";
00209 case Cathy: return "Cathy";
00210 case Inez: return "Inez";
00211 case Jean: return "Jean";
00212 case Heather: return "Heather";
00213 case Juliet: return "Juliet";
00214 default: GECODE_NEVER; return "";
00215 }
00216 }
00217
00218
00220 const int stewards[] =
00221 {Tom, David, Jeremy, Ron, Joe, Bill, Fred, Bob, Mario, Ed};
00223 const int noOfStewards = sizeof(stewards) / sizeof(int);
00225 const int hostesses[] =
00226 { Carol, Janet, Tracy, Marilyn, Carolyn, Cathy, Inez,
00227 Jean, Heather, Juliet };
00229 const int noOfHostesses = sizeof(hostesses) / sizeof(int);
00231 const int frenchSpeaking[] =
00232 { Bill, Inez, Jean, Juliet };
00234 const int noOfFrenchSpeaking = sizeof(frenchSpeaking) / sizeof(int);
00236 const int germanSpeaking[] =
00237 { Tom, Jeremy, Mario, Cathy, Juliet };
00239 const int noOfGermanSpeaking = sizeof(germanSpeaking) / sizeof(int);
00241 const int spanishSpeaking[] =
00242 { Joe, Bill, Fred, Mario, Marilyn, Inez, Heather };
00244 const int noOfSpanishSpeaking = sizeof(spanishSpeaking) / sizeof(int);
00245
00247 const Flight requiredCrew[] =
00248 { {4,1,1,1,1,1},
00249 {5,1,1,1,1,1},
00250 {5,1,1,1,1,1},
00251 {6,2,2,1,1,1},
00252 {7,3,3,1,1,1},
00253 {4,1,1,1,1,1},
00254 {5,1,1,1,1,1},
00255 {6,1,1,1,1,1},
00256 {6,2,2,1,1,1},
00257 {7,3,3,1,1,1} };
00258
00260 const int noOfFlights = sizeof(requiredCrew) / sizeof(Flight);
00261 }
00262
00263
00264