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"
26#include "ortools/data/jobshop_scheduling.pb.h"
27
28ABSL_FLAG(int64, jssp_scaling_up_factor, 100000L,
29 "Scaling factor for floating point penalties.");
30
31namespace operations_research {
32namespace data {
33namespace jssp {
34
35void 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
44void 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
53bool 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
107void 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
169void 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}
235void 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}
274void 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
339void 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
404void 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
496void 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
530int JsspParser::strtoint32(const std::string& word) {
531 int result;
532 CHECK(absl::SimpleAtoi(word, &result));
533 return result;
534}
535
536int64 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