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 #include <cstdio>
00036 #include <cstdlib>
00037
00038 #include "base/commandlineflags.h"
00039 #include "base/commandlineflags.h"
00040 #include "base/integral_types.h"
00041 #include "base/logging.h"
00042 #include "base/stringprintf.h"
00043 #include "base/bitmap.h"
00044 #include "constraint_solver/constraint_solver.h"
00045 #include "constraint_solver/constraint_solveri.h"
00046 #include "cpp/jobshop.h"
00047
00048 DEFINE_string(
00049 data_file,
00050 "",
00051 "Required: input file description the scheduling problem to solve, "
00052 "in our jssp format:\n"
00053 " - the first line is \"instance <instance name>\"\n"
00054 " - the second line is \"<number of jobs> <number of machines>\"\n"
00055 " - then one line per job, with a single space-separated "
00056 "list of \"<machine index> <duration>\"\n"
00057 "note: jobs with one task are not supported");
00058 DEFINE_int32(time_limit_in_ms, 60000, "Time limit in ms, 0 means no limit.");
00059 DEFINE_int32(shuffle_length, 4, "Length of sub-sequences to shuffle LS.");
00060 DEFINE_int32(sub_sequence_length, 4,
00061 "Length of sub-sequences to relax in LNS.");
00062 DEFINE_int32(lns_seed, 1, "Seed of the LNS random search");
00063 DEFINE_int32(lns_limit, 30,
00064 "Limit the size of the search tree in a LNS fragment");
00065
00066
00067 namespace operations_research {
00068
00069
00070 class SwapIntervals : public SequenceVarLocalSearchOperator {
00071 public:
00072 SwapIntervals(const SequenceVar* const* vars, int size)
00073 : SequenceVarLocalSearchOperator(vars, size),
00074 current_var_(-1),
00075 current_first_(-1),
00076 current_second_(-1) {}
00077
00078 virtual ~SwapIntervals() {}
00079
00080 virtual bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) {
00081 CHECK_NOTNULL(delta);
00082 while (true) {
00083 RevertChanges(true);
00084 if (!Increment()) {
00085 VLOG(1) << "finished neighborhood";
00086 return false;
00087 }
00088
00089 std::vector<int> sequence = Sequence(current_var_);
00090 const int tmp = sequence[current_first_];
00091 sequence[current_first_] = sequence[current_second_];
00092 sequence[current_second_] = tmp;
00093 SetForwardSequence(current_var_, sequence);
00094 if (ApplyChanges(delta, deltadelta)) {
00095 VLOG(1) << "Delta = " << delta->DebugString();
00096 return true;
00097 }
00098 }
00099 return false;
00100 }
00101
00102 protected:
00103 virtual void OnStart() {
00104 VLOG(1) << "start neighborhood";
00105 current_var_ = 0;
00106 current_first_ = 0;
00107 current_second_ = 0;
00108 }
00109
00110 private:
00111 bool Increment() {
00112 const SequenceVar* const var = Var(current_var_);
00113 if (++current_second_ >= var->size()) {
00114 if (++current_first_ >= var->size() - 1) {
00115 current_var_++;
00116 current_first_ = 0;
00117 }
00118 current_second_ = current_first_ + 1;
00119 }
00120 return current_var_ < Size();
00121 }
00122
00123 int current_var_;
00124 int current_first_;
00125 int current_second_;
00126 };
00127
00128
00129
00130 class ShuffleIntervals : public SequenceVarLocalSearchOperator {
00131 public:
00132 ShuffleIntervals(const SequenceVar* const* vars, int size, int max_length)
00133 : SequenceVarLocalSearchOperator(vars, size),
00134 max_length_(max_length),
00135 current_var_(-1),
00136 current_first_(-1),
00137 current_index_(-1),
00138 current_length_(-1) {}
00139
00140 virtual ~ShuffleIntervals() {}
00141
00142 virtual bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) {
00143 CHECK_NOTNULL(delta);
00144 while (true) {
00145 RevertChanges(true);
00146 if (!Increment()) {
00147 VLOG(1) << "finished neighborhood";
00148 return false;
00149 }
00150
00151 std::vector<int> sequence = Sequence(current_var_);
00152 std::vector<int> sequence_backup(current_length_);
00153 for (int i = 0; i < current_length_; ++i) {
00154 sequence_backup[i] = sequence[i + current_first_];
00155 }
00156 for (int i = 0; i < current_length_; ++i) {
00157 sequence[i + current_first_] =
00158 sequence_backup[current_permutation_[i]];
00159 }
00160 SetForwardSequence(current_var_, sequence);
00161 if (ApplyChanges(delta, deltadelta)) {
00162 VLOG(1) << "Delta = " << delta->DebugString();
00163 return true;
00164 }
00165 }
00166 return false;
00167 }
00168
00169 protected:
00170 virtual void OnStart() {
00171 VLOG(1) << "start neighborhood";
00172 current_var_ = 0;
00173 current_first_ = 0;
00174 current_index_ = -1;
00175 current_length_ = std::min(Var(current_var_)->size(), max_length_);
00176 current_permutation_.resize(current_length_);
00177 for (int i = 0; i < current_length_; ++i) {
00178 current_permutation_[i] = i;
00179 }
00180 }
00181
00182 private:
00183 bool Increment() {
00184 if (!std::next_permutation(current_permutation_.begin(),
00185 current_permutation_.end())) {
00186 if (++current_first_ >= Var(current_var_)->size() - current_length_) {
00187 if (++current_var_ >= Size()) {
00188 return false;
00189 }
00190 current_first_ = 0;
00191 current_length_ = std::min(Var(current_var_)->size(), max_length_);
00192 current_permutation_.resize(current_length_);
00193 }
00194 current_index_ = 0;
00195 }
00196 return true;
00197 }
00198
00199 const int max_length_;
00200 int current_var_;
00201 int current_first_;
00202 int current_index_;
00203 int current_length_;
00204 std::vector<int> current_permutation_;
00205 };
00206
00207
00208
00209 class SequenceLns : public SequenceVarLocalSearchOperator {
00210 public:
00211 SequenceLns(const SequenceVar* const* vars,
00212 int size,
00213 int seed,
00214 int max_length)
00215 : SequenceVarLocalSearchOperator(vars, size),
00216 random_(seed),
00217 max_length_(max_length) {}
00218
00219 virtual ~SequenceLns() {}
00220
00221 virtual bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) {
00222 CHECK_NOTNULL(delta);
00223 while (true) {
00224 RevertChanges(true);
00225 if (random_.Uniform(2) == 0) {
00226 FreeTimeWindow();
00227 } else {
00228 FreeTwoResources();
00229 }
00230 if (ApplyChanges(delta, deltadelta)) {
00231 VLOG(1) << "Delta = " << delta->DebugString();
00232 return true;
00233 }
00234 }
00235 return false;
00236 }
00237
00238 private:
00239 void FreeTimeWindow() {
00240 for (int i = 0; i < Size(); ++i) {
00241 std::vector<int> sequence = Sequence(i);
00242 const int current_length =
00243 std::min(static_cast<int>(sequence.size()), max_length_);
00244 const int start_position =
00245 random_.Uniform(sequence.size() - current_length);
00246 std::vector<int> forward;
00247 for (int j = 0; j < start_position; ++j) {
00248 forward.push_back(sequence[j]);
00249 }
00250 std::vector<int> backward;
00251 for (int j = sequence.size() - 1;
00252 j >= start_position + current_length;
00253 --j) {
00254 backward.push_back(sequence[j]);
00255 }
00256 SetForwardSequence(i, forward);
00257 SetBackwardSequence(i, backward);
00258 }
00259 }
00260
00261 void FreeTwoResources() {
00262 std::vector<int> free_sequence;
00263 SetForwardSequence(random_.Uniform(Size()), free_sequence);
00264 SetForwardSequence(random_.Uniform(Size()), free_sequence);
00265 }
00266
00267 ACMRandom random_;
00268 const int max_length_;
00269 };
00270
00271
00272
00273
00274 void JobshopLs(const JobShopData& data) {
00275 Solver solver("jobshop");
00276 const int machine_count = data.machine_count();
00277 const int job_count = data.job_count();
00278 const int horizon = data.horizon();
00279
00280
00281
00282
00283 std::vector<std::vector<IntervalVar*> > jobs_to_tasks(job_count);
00284
00285
00286 std::vector<std::vector<IntervalVar*> > machines_to_tasks(machine_count);
00287
00288
00289 for (int job_id = 0; job_id < job_count; ++job_id) {
00290 const std::vector<JobShopData::Task>& tasks = data.TasksOfJob(job_id);
00291 for (int task_index = 0; task_index < tasks.size(); ++task_index) {
00292 const JobShopData::Task& task = tasks[task_index];
00293 CHECK_EQ(job_id, task.job_id);
00294 const string name = StringPrintf("J%dM%dI%dD%d",
00295 task.job_id,
00296 task.machine_id,
00297 task_index,
00298 task.duration);
00299 IntervalVar* const one_task =
00300 solver.MakeFixedDurationIntervalVar(0,
00301 horizon,
00302 task.duration,
00303 false,
00304 name);
00305 jobs_to_tasks[task.job_id].push_back(one_task);
00306 machines_to_tasks[task.machine_id].push_back(one_task);
00307 }
00308 }
00309
00310
00311
00312
00313 for (int job_id = 0; job_id < job_count; ++job_id) {
00314 const int task_count = jobs_to_tasks[job_id].size();
00315 for (int task_index = 0; task_index < task_count - 1; ++task_index) {
00316 IntervalVar* const t1 = jobs_to_tasks[job_id][task_index];
00317 IntervalVar* const t2 = jobs_to_tasks[job_id][task_index + 1];
00318 Constraint* const prec =
00319 solver.MakeIntervalVarRelation(t2, Solver::STARTS_AFTER_END, t1);
00320 solver.AddConstraint(prec);
00321 }
00322 }
00323
00324
00325 for (int machine_id = 0; machine_id < machine_count; ++machine_id) {
00326 solver.AddConstraint(
00327 solver.MakeDisjunctiveConstraint(machines_to_tasks[machine_id]));
00328 }
00329
00330
00331
00332 std::vector<SequenceVar*> all_sequences;
00333 for (int machine_id = 0; machine_id < machine_count; ++machine_id) {
00334 const string name = StringPrintf("Machine_%d", machine_id);
00335 SequenceVar* const sequence =
00336 solver.MakeSequenceVar(machines_to_tasks[machine_id], name);
00337 all_sequences.push_back(sequence);
00338 }
00339
00340
00341 std::vector<IntVar*> all_ends;
00342 for (int job_id = 0; job_id < job_count; ++job_id) {
00343 const int task_count = jobs_to_tasks[job_id].size();
00344 IntervalVar* const task = jobs_to_tasks[job_id][task_count - 1];
00345 all_ends.push_back(task->EndExpr()->Var());
00346 }
00347
00348
00349
00350 IntVar* const objective_var = solver.MakeMax(all_ends)->Var();
00351
00352
00353
00354
00355 DecisionBuilder* const sequence_phase =
00356 solver.MakePhase(all_sequences, Solver::SEQUENCE_DEFAULT);
00357
00358
00359
00360
00361
00362
00363
00364 DecisionBuilder* const obj_phase =
00365 solver.MakePhase(objective_var,
00366 Solver::CHOOSE_FIRST_UNBOUND,
00367 Solver::ASSIGN_MIN_VALUE);
00368
00369 Assignment* const first_solution = solver.MakeAssignment();
00370 first_solution->Add(all_sequences);
00371 first_solution->AddObjective(objective_var);
00372
00373 DecisionBuilder* const store_db = solver.MakeStoreAssignment(first_solution);
00374
00375
00376
00377 DecisionBuilder* const first_solution_phase =
00378 solver.Compose(sequence_phase, obj_phase, store_db);
00379
00380 LOG(INFO) << "Looking for the first solution";
00381 const bool first_solution_found = solver.Solve(first_solution_phase);
00382 if (first_solution_found) {
00383 LOG(INFO) << "Solution found with makespan = "
00384 << first_solution->ObjectiveValue();
00385 } else {
00386 LOG(INFO) << "No initial solution found!";
00387 return;
00388 }
00389
00390 LOG(INFO) << "Switching to local search";
00391 std::vector<LocalSearchOperator*> operators;
00392 LOG(INFO) << " - use swap operator";
00393 LocalSearchOperator* const swap_operator =
00394 solver.RevAlloc(new SwapIntervals(all_sequences.data(),
00395 all_sequences.size()));
00396 operators.push_back(swap_operator);
00397 LOG(INFO) << " - use shuffle operator with a max length of "
00398 << FLAGS_shuffle_length;
00399 LocalSearchOperator* const shuffle_operator =
00400 solver.RevAlloc(new ShuffleIntervals(all_sequences.data(),
00401 all_sequences.size(),
00402 FLAGS_shuffle_length));
00403 operators.push_back(shuffle_operator);
00404 LOG(INFO) << " - use free sub sequences of length "
00405 << FLAGS_sub_sequence_length << " lns operator";
00406 LocalSearchOperator* const lns_operator =
00407 solver.RevAlloc(new SequenceLns(all_sequences.data(),
00408 all_sequences.size(),
00409 FLAGS_lns_seed,
00410 FLAGS_sub_sequence_length));
00411 operators.push_back(lns_operator);
00412
00413
00414 LocalSearchOperator* const concat =
00415 solver.ConcatenateOperators(operators, true);
00416
00417 SearchLimit* const ls_limit =
00418 solver.MakeLimit(kint64max, FLAGS_lns_limit, kint64max, kint64max);
00419 DecisionBuilder* const random_sequence_phase =
00420 solver.MakePhase(all_sequences, Solver::CHOOSE_RANDOM_RANK_FORWARD);
00421 DecisionBuilder* const ls_db =
00422 solver.MakeSolveOnce(solver.Compose(random_sequence_phase, obj_phase),
00423 ls_limit);
00424
00425 LocalSearchPhaseParameters* const parameters =
00426 solver.MakeLocalSearchPhaseParameters(concat, ls_db);
00427 DecisionBuilder* const final_db =
00428 solver.MakeLocalSearchPhase(first_solution, parameters);
00429
00430 OptimizeVar* const objective_monitor = solver.MakeMinimize(objective_var, 1);
00431
00432
00433 const int kLogFrequency = 1000000;
00434 SearchMonitor* const search_log =
00435 solver.MakeSearchLog(kLogFrequency, objective_monitor);
00436
00437 SearchLimit* const limit = FLAGS_time_limit_in_ms > 0 ?
00438 solver.MakeTimeLimit(FLAGS_time_limit_in_ms) :
00439 NULL;
00440
00441
00442 solver.Solve(final_db, search_log, objective_monitor, limit);
00443 }
00444 }
00445
00446 static const char kUsage[] =
00447 "Usage: see flags.\nThis program runs a simple job shop optimization "
00448 "output besides the debug LOGs of the solver.";
00449
00450 int main(int argc, char **argv) {
00451 google::SetUsageMessage(kUsage);
00452 google::ParseCommandLineFlags(&argc, &argv, true);
00453 if (FLAGS_data_file.empty()) {
00454 LOG(FATAL) << "Please supply a data file with --data_file=";
00455 }
00456 operations_research::JobShopData data;
00457 data.Load(FLAGS_data_file);
00458 operations_research::JobshopLs(data);
00459 return 0;
00460 }