OR-Tools  8.2
jobshop_scheduling_parser.cc
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
15 
16 #include <cmath>
17 
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"
25 #include "ortools/base/logging.h"
26 #include "ortools/data/jobshop_scheduling.pb.h"
27 
28 ABSL_FLAG(int64, jssp_scaling_up_factor, 100000L,
29  "Scaling factor for floating point penalties.");
30 
31 namespace operations_research {
32 namespace data {
33 namespace jssp {
34 
35 void JsspParser::SetJobs(int job_count) {
36  CHECK_GT(job_count, 0);
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));
41  }
42 }
43 
44 void JsspParser::SetMachines(int machine_count) {
45  CHECK_GT(machine_count, 0);
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));
50  }
51 }
52 
53 bool JsspParser::ParseFile(const std::string& filename) {
54  problem_.Clear();
55  // Try to detect the type of the data file.
56  // - fjs suffix -> Flexible Jobshop
57  // - txt suffix -> Taillard or time dependent scheduling.
58  if (absl::EndsWith(filename, "fjs")) {
59  problem_type_ = FLEXIBLE;
60  } else if (absl::EndsWith(filename, ".txt")) {
61  problem_type_ = TAILLARD;
62  } else {
63  problem_type_ = JSSP;
64  }
65  for (const std::string& line : FileLines(filename)) {
66  if (line.empty()) {
67  continue;
68  }
69  switch (problem_type_) {
70  case JSSP: {
71  ProcessJsspLine(line);
72  break;
73  }
74  case TAILLARD: {
75  ProcessTaillardLine(line);
76  break;
77  }
78  case FLEXIBLE: {
79  ProcessFlexibleLine(line);
80  break;
81  }
82  case SDST: {
83  ProcessSdstLine(line);
84  break;
85  }
86  case TARDINESS: {
87  ProcessTardinessLine(line);
88  break;
89  }
90  case PSS: {
91  ProcessPssLine(line);
92  break;
93  }
94  case EARLY_TARDY: {
95  ProcessEarlyTardyLine(line);
96  break;
97  }
98  default: {
99  LOG(FATAL) << "Should not be here.";
100  break;
101  }
102  }
103  }
104  return parser_state_ != PARSING_ERROR;
105 }
106 
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_) {
111  case START: {
112  if (words.size() == 2 && words[0] == "instance") {
113  problem_.set_name(words[1]);
114  parser_state_ = NAME_READ;
115  current_job_index_ = 0;
116  } else if (words.size() == 1 && words[0] == "1") {
117  problem_type_ = PSS;
118  } else if (words.size() == 2) {
119  SetJobs(strtoint32(words[0]));
120  SetMachines(strtoint32(words[1]));
121  problem_type_ = EARLY_TARDY;
122  parser_state_ = JOB_COUNT_READ;
123  }
124  break;
125  }
126  case NAME_READ: {
127  if (words.size() == 2) {
128  SetJobs(strtoint32(words[0]));
129  SetMachines(strtoint32(words[1]));
130  problem_.set_makespan_cost_per_time_unit(1L);
131  parser_state_ = JOB_COUNT_READ;
132  }
133  break;
134  }
135  case JOB_COUNT_READ: {
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);
144  }
145  if (words.size() == declared_machine_count_ * 2 + 3) {
146  // Early Tardy problem in JET format.
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);
156  }
157  current_job_index_++;
158  if (current_job_index_ == declared_job_count_) {
159  parser_state_ = DONE;
160  }
161  break;
162  }
163  default: {
164  LOG(FATAL) << "Should not be here with state " << parser_state_;
165  }
166  }
167 }
168 
169 void JsspParser::ProcessTaillardLine(const std::string& line) {
170  const std::vector<std::string> words =
171  absl::StrSplit(line, ' ', absl::SkipEmpty());
172 
173  switch (parser_state_) {
174  case START: {
175  if (words.size() == 2) { // Switch to SDST parser.
176  problem_type_ = SDST;
177  ProcessSdstLine(line);
178  return;
179  } else if (words.size() == 3) { // Switch to TARDINESS parser.
180  problem_type_ = TARDINESS;
181  ProcessTardinessLine(line);
182  return;
183  }
184  if (words.size() == 1 && strtoint32(words[0]) > 0) {
185  parser_state_ = JOB_COUNT_READ;
186  SetJobs(strtoint32(words[0]));
187  }
188  break;
189  }
190  case JOB_COUNT_READ: {
191  CHECK_EQ(1, words.size());
192  SetMachines(strtoint32(words[0]));
193  problem_.set_makespan_cost_per_time_unit(1L);
194  parser_state_ = MACHINE_COUNT_READ;
195  break;
196  }
197  case MACHINE_COUNT_READ: {
198  CHECK_EQ(1, words.size());
199  const int seed = strtoint32(words[0]);
200  problem_.set_seed(seed);
201  parser_state_ = SEED_READ;
202  break;
203  }
204  case SEED_READ:
205  ABSL_FALLTHROUGH_INTENDED;
206  case JOB_READ: {
207  CHECK_EQ(1, words.size());
208  current_job_index_ = strtoint32(words[0]);
209  parser_state_ = JOB_ID_READ;
210  break;
211  }
212  case JOB_ID_READ: {
213  CHECK_EQ(1, words.size());
214  parser_state_ = JOB_LENGTH_READ;
215  break;
216  }
217  case JOB_LENGTH_READ: {
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);
225  }
226  parser_state_ =
227  current_job_index_ == declared_job_count_ - 1 ? DONE : JOB_READ;
228  break;
229  }
230  default: {
231  LOG(FATAL) << "Should not be here with state " << parser_state_;
232  }
233  }
234 }
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_) {
239  case START: {
240  CHECK_GE(words.size(), 2);
241  SetJobs(strtoint32(words[0]));
242  SetMachines(strtoint32(words[1]));
243  problem_.set_makespan_cost_per_time_unit(1L);
244  parser_state_ = JOB_COUNT_READ;
245  break;
246  }
247  case JOB_COUNT_READ: {
248  const int operations_count = strtoint32(words[0]);
249  int index = 1;
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++) {
255  // Machine id are 1 based.
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);
260  }
261  }
262  CHECK_LE(index, words.size()); // Ignore CR at the end of the line.
263  current_job_index_++;
264  if (current_job_index_ == declared_job_count_) {
265  parser_state_ = DONE;
266  }
267  break;
268  }
269  default: {
270  LOG(FATAL) << "Should not be here with state " << parser_state_;
271  }
272  }
273 }
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_) {
278  case START: {
279  if (words.size() == 2) {
280  SetJobs(strtoint32(words[0]));
281  SetMachines(strtoint32(words[1]));
282  problem_.set_makespan_cost_per_time_unit(1L);
283  parser_state_ = JOB_COUNT_READ;
284  current_machine_index_ = 0;
285  }
286  break;
287  }
288  case JOB_COUNT_READ: {
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);
297  }
298  current_job_index_++;
299  if (current_job_index_ == declared_job_count_) {
300  parser_state_ = JOBS_READ;
301  }
302  break;
303  }
304  case JOBS_READ: {
305  CHECK_EQ(1, words.size());
306  CHECK_EQ("SSD", words[0]);
307  parser_state_ = SSD_READ;
308  break;
309  }
310  case SSD_READ: {
311  CHECK_EQ(1, words.size());
312  CHECK_EQ(words[0], absl::StrCat("M", current_machine_index_)) << line;
313  current_job_index_ = 0;
314  parser_state_ = MACHINE_READ;
315  break;
316  }
317  case MACHINE_READ: {
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);
324  }
325  if (++current_job_index_ == declared_job_count_) {
326  parser_state_ = ++current_machine_index_ == declared_machine_count_
327  ? DONE
328  : SSD_READ;
329  }
330  break;
331  }
332  default: {
333  LOG(FATAL) << "Should not be here with state " << parser_state_
334  << "with line " << line;
335  }
336  }
337 }
338 
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_) {
343  case START: {
344  CHECK_EQ(3, words.size());
345  SetJobs(strtoint32(words[0]));
346  SetMachines(strtoint32(words[1]));
347  parser_state_ = JOB_COUNT_READ;
348  current_job_index_ = 0;
349  break;
350  }
351  case JOB_COUNT_READ: {
352  CHECK_GE(words.size(), 6);
353  Job* const job = problem_.mutable_jobs(current_job_index_);
354  const int64 est = strtoint64(words[0]);
355  if (est != 0L) {
356  job->mutable_earliest_start()->set_value(est);
357  }
358  job->set_late_due_date(strtoint64(words[1]));
359  const double weight = std::stod(words[2]);
360  const int64 tardiness = static_cast<int64>(
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; // 1 based.
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);
370  }
371  current_job_index_++;
372  if (current_job_index_ == declared_job_count_) {
373  // Fix tardiness weights if all integer from start.
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) !=
378  0) {
379  all_integral = false;
380  break;
381  }
382  }
383  if (all_integral) {
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));
388  }
389  } else {
390  problem_.mutable_scaling_factor()->set_value(
391  1.0L / absl::GetFlag(FLAGS_jssp_scaling_up_factor));
392  }
393  parser_state_ = DONE;
394  }
395  break;
396  }
397  default: {
398  LOG(FATAL) << "Should not be here with state " << parser_state_
399  << "with line " << line;
400  }
401  }
402 }
403 
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_) {
408  case START: {
409  problem_.set_makespan_cost_per_time_unit(1L);
410  CHECK_EQ(1, words.size());
411  SetJobs(strtoint32(words[0]));
412  parser_state_ = JOB_COUNT_READ;
413  break;
414  }
415  case JOB_COUNT_READ: {
416  CHECK_EQ(1, words.size());
417  SetMachines(strtoint32(words[0]));
418  parser_state_ = MACHINE_COUNT_READ;
419  current_job_index_ = 0;
420  break;
421  }
422  case MACHINE_COUNT_READ: {
423  CHECK_EQ(1, words.size());
424  CHECK_EQ(declared_machine_count_, strtoint32(words[0]));
425  if (++current_job_index_ == declared_job_count_) {
426  parser_state_ = JOB_LENGTH_READ;
427  current_job_index_ = 0;
428  current_machine_index_ = 0;
429  }
430  break;
431  }
432  case JOB_LENGTH_READ: {
433  CHECK_EQ(4, words.size());
434  CHECK_EQ(0, strtoint32(words[2]));
435  CHECK_EQ(0, strtoint32(words[3]));
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;
447  parser_state_ = JOBS_READ;
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_;
452  ++i) {
453  machine->mutable_transition_time_matrix()->add_transition_time(0);
454  }
455  }
456  }
457  }
458  break;
459  }
460  case JOBS_READ: {
461  CHECK_EQ(1, words.size());
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) { // Dummy task.
467  break;
468  }
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);
477  if (m1 != m2) { // We are only interested in same machine transitions.
478  break;
479  }
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;
486  }
487  break;
488  }
489  default: {
490  LOG(FATAL) << "Should not be here with state " << parser_state_
491  << "with line " << line;
492  }
493  }
494 }
495 
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_) {
500  case JOB_COUNT_READ: {
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);
509  }
510  // Early Tardy problem in JET format.
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;
521  }
522  break;
523  }
524  default: {
525  LOG(FATAL) << "Should not be here with state " << parser_state_;
526  }
527  }
528 }
529 
530 int JsspParser::strtoint32(const std::string& word) {
531  int result;
532  CHECK(absl::SimpleAtoi(word, &result));
533  return result;
534 }
535 
536 int64 JsspParser::strtoint64(const std::string& word) {
537  int64 result;
538  CHECK(absl::SimpleAtoi(word, &result));
539  return result;
540 }
541 
542 } // namespace jssp
543 } // namespace data
544 } // namespace operations_research
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define LOG(severity)
Definition: base/logging.h:420
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
int64_t int64
ABSL_FLAG(int64, jssp_scaling_up_factor, 100000L, "Scaling factor for floating point penalties.")
const int FATAL
Definition: log_severity.h:32
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int index
Definition: pack.cc:508
int64 weight
Definition: pack.cc:509