18 #include "absl/strings/numbers.h"
19 #include "absl/strings/str_cat.h"
20 #include "absl/strings/str_split.h"
21 #include "google/protobuf/wrappers.pb.h"
26 #include "ortools/data/jobshop_scheduling.pb.h"
29 "Scaling factor for floating point penalties.");
35 void JsspParser::SetJobs(
int job_count) {
37 declared_job_count_ = job_count;
38 problem_.clear_jobs();
39 for (
int i = 0; i < job_count; ++i) {
40 problem_.add_jobs()->set_name(absl::StrCat(
"J", i));
44 void JsspParser::SetMachines(
int machine_count) {
46 declared_machine_count_ = machine_count;
47 problem_.clear_machines();
48 for (
int i = 0; i < machine_count; ++i) {
49 problem_.add_machines()->set_name(absl::StrCat(
"M", i));
58 if (absl::EndsWith(filename,
"fjs")) {
60 }
else if (absl::EndsWith(filename,
".txt")) {
65 for (
const std::string& line :
FileLines(filename)) {
69 switch (problem_type_) {
71 ProcessJsspLine(line);
75 ProcessTaillardLine(line);
79 ProcessFlexibleLine(line);
83 ProcessSdstLine(line);
87 ProcessTardinessLine(line);
95 ProcessEarlyTardyLine(line);
107 void JsspParser::ProcessJsspLine(
const std::string& line) {
108 const std::vector<std::string> words =
109 absl::StrSplit(line,
' ', absl::SkipEmpty());
110 switch (parser_state_) {
112 if (words.size() == 2 && words[0] ==
"instance") {
113 problem_.set_name(words[1]);
115 current_job_index_ = 0;
116 }
else if (words.size() == 1 && words[0] ==
"1") {
118 }
else if (words.size() == 2) {
119 SetJobs(strtoint32(words[0]));
120 SetMachines(strtoint32(words[1]));
127 if (words.size() == 2) {
128 SetJobs(strtoint32(words[0]));
129 SetMachines(strtoint32(words[1]));
130 problem_.set_makespan_cost_per_time_unit(1L);
136 CHECK_GE(words.size(), declared_machine_count_ * 2);
137 Job*
const job = problem_.mutable_jobs(current_job_index_);
138 for (
int i = 0; i < declared_machine_count_; ++i) {
139 const int machine_id = strtoint32(words[2 * i]);
140 const int64 duration = strtoint64(words[2 * i + 1]);
141 Task*
const task = job->add_tasks();
142 task->add_machine(machine_id);
143 task->add_duration(duration);
145 if (words.size() == declared_machine_count_ * 2 + 3) {
147 const int due_date = strtoint32(words[declared_machine_count_ * 2]);
148 const int early_cost =
149 strtoint32(words[declared_machine_count_ * 2 + 1]);
150 const int late_cost =
151 strtoint32(words[declared_machine_count_ * 2 + 2]);
152 job->set_early_due_date(due_date);
153 job->set_late_due_date(due_date);
154 job->set_earliness_cost_per_time_unit(early_cost);
155 job->set_lateness_cost_per_time_unit(late_cost);
157 current_job_index_++;
158 if (current_job_index_ == declared_job_count_) {
159 parser_state_ =
DONE;
164 LOG(
FATAL) <<
"Should not be here with state " << parser_state_;
169 void JsspParser::ProcessTaillardLine(
const std::string& line) {
170 const std::vector<std::string> words =
171 absl::StrSplit(line,
' ', absl::SkipEmpty());
173 switch (parser_state_) {
175 if (words.size() == 2) {
176 problem_type_ =
SDST;
177 ProcessSdstLine(line);
179 }
else if (words.size() == 3) {
181 ProcessTardinessLine(line);
184 if (words.size() == 1 && strtoint32(words[0]) > 0) {
186 SetJobs(strtoint32(words[0]));
192 SetMachines(strtoint32(words[0]));
193 problem_.set_makespan_cost_per_time_unit(1L);
199 const int seed = strtoint32(words[0]);
200 problem_.set_seed(seed);
205 ABSL_FALLTHROUGH_INTENDED;
208 current_job_index_ = strtoint32(words[0]);
218 CHECK_EQ(declared_machine_count_, words.size());
219 Job*
const job = problem_.mutable_jobs(current_job_index_);
220 for (
int i = 0; i < declared_machine_count_; ++i) {
221 const int64 duration = strtoint64(words[i]);
222 Task*
const task = job->add_tasks();
223 task->add_machine(i);
224 task->add_duration(duration);
227 current_job_index_ == declared_job_count_ - 1 ?
DONE :
JOB_READ;
231 LOG(
FATAL) <<
"Should not be here with state " << parser_state_;
235 void JsspParser::ProcessFlexibleLine(
const std::string& line) {
236 const std::vector<std::string> words =
237 absl::StrSplit(line,
' ', absl::SkipEmpty());
238 switch (parser_state_) {
241 SetJobs(strtoint32(words[0]));
242 SetMachines(strtoint32(words[1]));
243 problem_.set_makespan_cost_per_time_unit(1L);
248 const int operations_count = strtoint32(words[0]);
250 Job*
const job = problem_.mutable_jobs(current_job_index_);
251 for (
int operation = 0; operation < operations_count; ++operation) {
252 const int alternatives_count = strtoint32(words[
index++]);
253 Task*
const task = job->add_tasks();
254 for (
int alt = 0; alt < alternatives_count; alt++) {
256 const int machine_id = strtoint32(words[
index++]) - 1;
257 const int64 duration = strtoint64(words[
index++]);
258 task->add_machine(machine_id);
259 task->add_duration(duration);
263 current_job_index_++;
264 if (current_job_index_ == declared_job_count_) {
265 parser_state_ =
DONE;
270 LOG(
FATAL) <<
"Should not be here with state " << parser_state_;
274 void JsspParser::ProcessSdstLine(
const std::string& line) {
275 const std::vector<std::string> words =
276 absl::StrSplit(line,
' ', absl::SkipEmpty());
277 switch (parser_state_) {
279 if (words.size() == 2) {
280 SetJobs(strtoint32(words[0]));
281 SetMachines(strtoint32(words[1]));
282 problem_.set_makespan_cost_per_time_unit(1L);
284 current_machine_index_ = 0;
289 CHECK_EQ(words.size(), declared_machine_count_ * 2);
290 Job*
const job = problem_.mutable_jobs(current_job_index_);
291 for (
int i = 0; i < declared_machine_count_; ++i) {
292 const int machine_id = strtoint32(words[2 * i]);
293 const int64 duration = strtoint64(words[2 * i + 1]);
294 Task*
const task = job->add_tasks();
295 task->add_machine(machine_id);
296 task->add_duration(duration);
298 current_job_index_++;
299 if (current_job_index_ == declared_job_count_) {
312 CHECK_EQ(words[0], absl::StrCat(
"M", current_machine_index_)) << line;
313 current_job_index_ = 0;
318 CHECK_EQ(declared_job_count_, words.size());
319 Machine*
const machine =
320 problem_.mutable_machines(current_machine_index_);
321 for (
const std::string& w : words) {
322 const int64 t = strtoint64(w);
323 machine->mutable_transition_time_matrix()->add_transition_time(t);
325 if (++current_job_index_ == declared_job_count_) {
326 parser_state_ = ++current_machine_index_ == declared_machine_count_
333 LOG(
FATAL) <<
"Should not be here with state " << parser_state_
334 <<
"with line " << line;
339 void JsspParser::ProcessTardinessLine(
const std::string& line) {
340 const std::vector<std::string> words =
341 absl::StrSplit(line,
' ', absl::SkipEmpty());
342 switch (parser_state_) {
345 SetJobs(strtoint32(words[0]));
346 SetMachines(strtoint32(words[1]));
348 current_job_index_ = 0;
353 Job*
const job = problem_.mutable_jobs(current_job_index_);
354 const int64 est = strtoint64(words[0]);
356 job->mutable_earliest_start()->set_value(est);
358 job->set_late_due_date(strtoint64(words[1]));
359 const double weight = std::stod(words[2]);
361 round(
weight * absl::GetFlag(FLAGS_jssp_scaling_up_factor)));
362 job->set_lateness_cost_per_time_unit(tardiness);
363 const int num_operations = strtoint32(words[3]);
364 for (
int i = 0; i < num_operations; ++i) {
365 const int machine_id = strtoint32(words[4 + 2 * i]) - 1;
366 const int64 duration = strtoint64(words[5 + 2 * i]);
367 Task*
const task = job->add_tasks();
368 task->add_machine(machine_id);
369 task->add_duration(duration);
371 current_job_index_++;
372 if (current_job_index_ == declared_job_count_) {
374 bool all_integral =
true;
375 for (
const Job& job : problem_.jobs()) {
376 if (job.lateness_cost_per_time_unit() %
377 absl::GetFlag(FLAGS_jssp_scaling_up_factor) !=
379 all_integral =
false;
384 for (Job& job : *problem_.mutable_jobs()) {
385 job.set_lateness_cost_per_time_unit(
386 job.lateness_cost_per_time_unit() /
387 absl::GetFlag(FLAGS_jssp_scaling_up_factor));
390 problem_.mutable_scaling_factor()->set_value(
391 1.0L / absl::GetFlag(FLAGS_jssp_scaling_up_factor));
393 parser_state_ =
DONE;
398 LOG(
FATAL) <<
"Should not be here with state " << parser_state_
399 <<
"with line " << line;
404 void JsspParser::ProcessPssLine(
const std::string& line) {
405 const std::vector<std::string> words =
406 absl::StrSplit(line,
' ', absl::SkipEmpty());
407 switch (parser_state_) {
409 problem_.set_makespan_cost_per_time_unit(1L);
411 SetJobs(strtoint32(words[0]));
417 SetMachines(strtoint32(words[0]));
419 current_job_index_ = 0;
424 CHECK_EQ(declared_machine_count_, strtoint32(words[0]));
425 if (++current_job_index_ == declared_job_count_) {
427 current_job_index_ = 0;
428 current_machine_index_ = 0;
436 const int machine_id = strtoint32(words[0]) - 1;
437 const int duration = strtoint32(words[1]);
438 Job*
const job = problem_.mutable_jobs(current_job_index_);
439 Task*
const task = job->add_tasks();
440 task->add_machine(machine_id);
441 task->add_duration(duration);
442 if (++current_machine_index_ == declared_machine_count_) {
443 current_machine_index_ = 0;
444 if (++current_job_index_ == declared_job_count_) {
445 current_job_index_ = -1;
446 current_machine_index_ = 0;
448 transition_index_ = 0;
449 for (
int m = 0; m < declared_machine_count_; ++m) {
450 Machine*
const machine = problem_.mutable_machines(m);
451 for (
int i = 0; i < declared_job_count_ * declared_job_count_;
453 machine->mutable_transition_time_matrix()->add_transition_time(0);
462 const int index = transition_index_++;
463 const int size = declared_job_count_ * declared_machine_count_ + 1;
464 const int t1 =
index / size;
465 const int t2 =
index % size;
466 if (t1 == 0 || t2 == 0) {
469 const int item1 = t1 - 1;
470 const int item2 = t2 - 1;
471 const int job1 = item1 / declared_machine_count_;
472 const int task1 = item1 % declared_machine_count_;
473 const int m1 = problem_.jobs(job1).tasks(task1).machine(0);
474 const int job2 = item2 / declared_machine_count_;
475 const int task2 = item2 % declared_machine_count_;
476 const int m2 = problem_.jobs(job2).tasks(task2).machine(0);
480 const int transition = strtoint32(words[0]);
481 Machine*
const machine = problem_.mutable_machines(m1);
482 machine->mutable_transition_time_matrix()->set_transition_time(
483 job1 * declared_job_count_ + job2, transition);
484 if (transition_index_ == size * size) {
485 parser_state_ =
DONE;
490 LOG(
FATAL) <<
"Should not be here with state " << parser_state_
491 <<
"with line " << line;
496 void JsspParser::ProcessEarlyTardyLine(
const std::string& line) {
497 const std::vector<std::string> words =
498 absl::StrSplit(line,
' ', absl::SkipEmpty());
499 switch (parser_state_) {
501 CHECK_EQ(words.size(), declared_machine_count_ * 2 + 3);
502 Job*
const job = problem_.mutable_jobs(current_job_index_);
503 for (
int i = 0; i < declared_machine_count_; ++i) {
504 const int machine_id = strtoint32(words[2 * i]);
505 const int64 duration = strtoint64(words[2 * i + 1]);
506 Task*
const task = job->add_tasks();
507 task->add_machine(machine_id);
508 task->add_duration(duration);
511 const int due_date = strtoint32(words[declared_machine_count_ * 2]);
512 const int early_cost = strtoint32(words[declared_machine_count_ * 2 + 1]);
513 const int late_cost = strtoint32(words[declared_machine_count_ * 2 + 2]);
514 job->set_early_due_date(due_date);
515 job->set_late_due_date(due_date);
516 job->set_earliness_cost_per_time_unit(early_cost);
517 job->set_lateness_cost_per_time_unit(late_cost);
518 current_job_index_++;
519 if (current_job_index_ == declared_job_count_) {
520 parser_state_ =
DONE;
525 LOG(
FATAL) <<
"Should not be here with state " << parser_state_;
530 int JsspParser::strtoint32(
const std::string& word) {
532 CHECK(absl::SimpleAtoi(word, &result));
536 int64 JsspParser::strtoint64(
const std::string& word) {
538 CHECK(absl::SimpleAtoi(word, &result));
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define CHECK_GT(val1, val2)
#define CHECK_LE(val1, val2)
bool ParseFile(const std::string &filename)
ABSL_FLAG(int64, jssp_scaling_up_factor, 100000L, "Scaling factor for floating point penalties.")
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...