559 lines
18 KiB
C++
559 lines
18 KiB
C++
// Copyright 2010-2025 Google LLC
|
|
// Licensed under the Apache License, Version 2.0 (the "License");
|
|
// you may not use this file except in compliance with the License.
|
|
// You may obtain a copy of the License at
|
|
//
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
//
|
|
// Unless required by applicable law or agreed to in writing, software
|
|
// distributed under the License is distributed on an "AS IS" BASIS,
|
|
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
// See the License for the specific language governing permissions and
|
|
// limitations under the License.
|
|
|
|
#include "ortools/scheduling/jobshop_scheduling_parser.h"
|
|
|
|
#include <cmath>
|
|
#include <cstdint>
|
|
#include <string>
|
|
#include <vector>
|
|
|
|
#include "absl/base/attributes.h"
|
|
#include "absl/flags/flag.h"
|
|
#include "absl/log/check.h"
|
|
#include "absl/strings/match.h"
|
|
#include "absl/strings/numbers.h"
|
|
#include "absl/strings/str_cat.h"
|
|
#include "absl/strings/str_split.h"
|
|
#include "absl/strings/string_view.h"
|
|
#include "google/protobuf/wrappers.pb.h"
|
|
#include "ortools/base/logging.h"
|
|
#include "ortools/base/path.h"
|
|
#include "ortools/scheduling/jobshop_scheduling.pb.h"
|
|
#include "ortools/util/filelineiter.h"
|
|
|
|
ABSL_FLAG(int64_t, jssp_scaling_up_factor, 100000L,
|
|
"Scaling factor for floating point penalties.");
|
|
|
|
namespace operations_research {
|
|
namespace scheduling {
|
|
namespace jssp {
|
|
|
|
void JsspParser::SetJobs(int job_count) {
|
|
CHECK_GT(job_count, 0);
|
|
declared_job_count_ = job_count;
|
|
problem_.clear_jobs();
|
|
for (int i = 0; i < job_count; ++i) {
|
|
problem_.add_jobs()->set_name(absl::StrCat("J", i));
|
|
}
|
|
}
|
|
|
|
void JsspParser::SetMachines(int machine_count) {
|
|
CHECK_GT(machine_count, 0);
|
|
declared_machine_count_ = machine_count;
|
|
problem_.clear_machines();
|
|
for (int i = 0; i < machine_count; ++i) {
|
|
problem_.add_machines()->set_name(absl::StrCat("M", i));
|
|
}
|
|
}
|
|
|
|
bool JsspParser::ParseFile(absl::string_view filename) {
|
|
problem_.Clear();
|
|
// Try to detect the type of the data file.
|
|
// - fjs suffix -> Flexible Jobshop
|
|
// - txt suffix -> Taillard or time dependent scheduling.
|
|
|
|
if (absl::EndsWith(filename, "fjs")) {
|
|
problem_type_ = FLEXIBLE;
|
|
} else if (absl::EndsWith(filename, ".txt")) {
|
|
problem_type_ = TAILLARD;
|
|
} else {
|
|
problem_type_ = JSSP;
|
|
}
|
|
|
|
// We use a temporary string as open source protobufs do not accept
|
|
// set(string_view).
|
|
const std::string problem_name(file::Stem(filename));
|
|
problem_.set_name(problem_name);
|
|
|
|
for (const std::string& line : FileLines(filename)) {
|
|
if (line.empty()) {
|
|
continue;
|
|
}
|
|
switch (problem_type_) {
|
|
case JSSP: {
|
|
ProcessJsspLine(line);
|
|
break;
|
|
}
|
|
case TAILLARD: {
|
|
ProcessTaillardLine(line);
|
|
break;
|
|
}
|
|
case FLEXIBLE: {
|
|
ProcessFlexibleLine(line);
|
|
break;
|
|
}
|
|
case SDST: {
|
|
ProcessSdstLine(line);
|
|
break;
|
|
}
|
|
case TARDINESS: {
|
|
ProcessTardinessLine(line);
|
|
break;
|
|
}
|
|
case PSS: {
|
|
ProcessPssLine(line);
|
|
break;
|
|
}
|
|
case EARLY_TARDY: {
|
|
ProcessEarlyTardyLine(line);
|
|
break;
|
|
}
|
|
default: {
|
|
LOG(FATAL) << "Should not be here.";
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
return parser_state_ != PARSING_ERROR;
|
|
}
|
|
|
|
void JsspParser::ProcessJsspLine(const std::string& line) {
|
|
const std::vector<std::string> words =
|
|
absl::StrSplit(line, ' ', absl::SkipEmpty());
|
|
switch (parser_state_) {
|
|
case START: {
|
|
if (words.size() == 2 && words[0] == "instance") {
|
|
problem_.set_name(words[1]);
|
|
parser_state_ = NAME_READ;
|
|
current_job_index_ = 0;
|
|
} else if (words.size() == 1 && words[0] == "1") {
|
|
problem_type_ = PSS;
|
|
} else if (words.size() == 2) {
|
|
SetJobs(strtoint32(words[0]));
|
|
SetMachines(strtoint32(words[1]));
|
|
problem_type_ = EARLY_TARDY;
|
|
parser_state_ = JOB_COUNT_READ;
|
|
}
|
|
break;
|
|
}
|
|
case NAME_READ: {
|
|
if (words.size() == 2) {
|
|
SetJobs(strtoint32(words[0]));
|
|
SetMachines(strtoint32(words[1]));
|
|
problem_.set_makespan_cost_per_time_unit(1L);
|
|
parser_state_ = JOB_COUNT_READ;
|
|
}
|
|
break;
|
|
}
|
|
case JOB_COUNT_READ: {
|
|
CHECK_GE(words.size(), declared_machine_count_ * 2);
|
|
Job* const job = problem_.mutable_jobs(current_job_index_);
|
|
for (int i = 0; i < declared_machine_count_; ++i) {
|
|
const int machine_id = strtoint32(words[2 * i]);
|
|
const int64_t duration = strtoint64(words[2 * i + 1]);
|
|
Task* const task = job->add_tasks();
|
|
task->add_machine(machine_id);
|
|
task->add_duration(duration);
|
|
}
|
|
if (words.size() == declared_machine_count_ * 2 + 3) {
|
|
// Early Tardy problem in JET format.
|
|
const int due_date = strtoint32(words[declared_machine_count_ * 2]);
|
|
const int early_cost =
|
|
strtoint32(words[declared_machine_count_ * 2 + 1]);
|
|
const int late_cost =
|
|
strtoint32(words[declared_machine_count_ * 2 + 2]);
|
|
job->set_early_due_date(due_date);
|
|
job->set_late_due_date(due_date);
|
|
job->set_earliness_cost_per_time_unit(early_cost);
|
|
job->set_lateness_cost_per_time_unit(late_cost);
|
|
}
|
|
current_job_index_++;
|
|
if (current_job_index_ == declared_job_count_) {
|
|
parser_state_ = DONE;
|
|
}
|
|
break;
|
|
}
|
|
default: {
|
|
LOG(FATAL) << "Should not be here with state " << parser_state_;
|
|
}
|
|
}
|
|
}
|
|
|
|
void JsspParser::ProcessTaillardLine(const std::string& line) {
|
|
const std::vector<std::string> words =
|
|
absl::StrSplit(line, ' ', absl::SkipEmpty());
|
|
|
|
switch (parser_state_) {
|
|
case START: {
|
|
if (words.size() == 2) { // Switch to SDST parser.
|
|
problem_type_ = SDST;
|
|
ProcessSdstLine(line);
|
|
return;
|
|
} else if (words.size() == 3) { // Switch to TARDINESS parser.
|
|
problem_type_ = TARDINESS;
|
|
ProcessTardinessLine(line);
|
|
return;
|
|
}
|
|
if (words.size() == 1 && strtoint32(words[0]) > 0) {
|
|
parser_state_ = JOB_COUNT_READ;
|
|
SetJobs(strtoint32(words[0]));
|
|
}
|
|
break;
|
|
}
|
|
case JOB_COUNT_READ: {
|
|
CHECK_EQ(1, words.size());
|
|
SetMachines(strtoint32(words[0]));
|
|
problem_.set_makespan_cost_per_time_unit(1L);
|
|
parser_state_ = MACHINE_COUNT_READ;
|
|
break;
|
|
}
|
|
case MACHINE_COUNT_READ: {
|
|
CHECK_EQ(1, words.size());
|
|
const int seed = strtoint32(words[0]);
|
|
problem_.set_seed(seed);
|
|
parser_state_ = SEED_READ;
|
|
break;
|
|
}
|
|
case SEED_READ:
|
|
ABSL_FALLTHROUGH_INTENDED;
|
|
case JOB_READ: {
|
|
CHECK_EQ(1, words.size());
|
|
current_job_index_ = strtoint32(words[0]);
|
|
parser_state_ = JOB_ID_READ;
|
|
break;
|
|
}
|
|
case JOB_ID_READ: {
|
|
CHECK_EQ(1, words.size());
|
|
parser_state_ = JOB_LENGTH_READ;
|
|
break;
|
|
}
|
|
case JOB_LENGTH_READ: {
|
|
CHECK_EQ(declared_machine_count_, words.size());
|
|
Job* const job = problem_.mutable_jobs(current_job_index_);
|
|
for (int i = 0; i < declared_machine_count_; ++i) {
|
|
const int64_t duration = strtoint64(words[i]);
|
|
Task* const task = job->add_tasks();
|
|
task->add_machine(i);
|
|
task->add_duration(duration);
|
|
}
|
|
parser_state_ =
|
|
current_job_index_ == declared_job_count_ - 1 ? DONE : JOB_READ;
|
|
break;
|
|
}
|
|
default: {
|
|
LOG(FATAL) << "Should not be here with state " << parser_state_;
|
|
}
|
|
}
|
|
}
|
|
void JsspParser::ProcessFlexibleLine(const std::string& line) {
|
|
const std::vector<std::string> words =
|
|
absl::StrSplit(line, ' ', absl::SkipEmpty());
|
|
switch (parser_state_) {
|
|
case START: {
|
|
CHECK_GE(words.size(), 2);
|
|
SetJobs(strtoint32(words[0]));
|
|
SetMachines(strtoint32(words[1]));
|
|
problem_.set_makespan_cost_per_time_unit(1L);
|
|
parser_state_ = JOB_COUNT_READ;
|
|
break;
|
|
}
|
|
case JOB_COUNT_READ: {
|
|
const int operations_count = strtoint32(words[0]);
|
|
int index = 1;
|
|
Job* const job = problem_.mutable_jobs(current_job_index_);
|
|
for (int operation = 0; operation < operations_count; ++operation) {
|
|
const int alternatives_count = strtoint32(words[index++]);
|
|
Task* const task = job->add_tasks();
|
|
for (int alt = 0; alt < alternatives_count; alt++) {
|
|
// Machine id are 1 based.
|
|
const int machine_id = strtoint32(words[index++]) - 1;
|
|
const int64_t duration = strtoint64(words[index++]);
|
|
task->add_machine(machine_id);
|
|
task->add_duration(duration);
|
|
}
|
|
}
|
|
CHECK_LE(index, words.size()); // Ignore CR at the end of the line.
|
|
current_job_index_++;
|
|
if (current_job_index_ == declared_job_count_) {
|
|
parser_state_ = DONE;
|
|
}
|
|
break;
|
|
}
|
|
default: {
|
|
LOG(FATAL) << "Should not be here with state " << parser_state_;
|
|
}
|
|
}
|
|
}
|
|
void JsspParser::ProcessSdstLine(const std::string& line) {
|
|
const std::vector<std::string> words =
|
|
absl::StrSplit(line, ' ', absl::SkipEmpty());
|
|
switch (parser_state_) {
|
|
case START: {
|
|
if (words.size() == 2) {
|
|
SetJobs(strtoint32(words[0]));
|
|
SetMachines(strtoint32(words[1]));
|
|
problem_.set_makespan_cost_per_time_unit(1L);
|
|
parser_state_ = JOB_COUNT_READ;
|
|
current_machine_index_ = 0;
|
|
}
|
|
break;
|
|
}
|
|
case JOB_COUNT_READ: {
|
|
CHECK_EQ(words.size(), declared_machine_count_ * 2);
|
|
Job* const job = problem_.mutable_jobs(current_job_index_);
|
|
for (int i = 0; i < declared_machine_count_; ++i) {
|
|
const int machine_id = strtoint32(words[2 * i]);
|
|
const int64_t duration = strtoint64(words[2 * i + 1]);
|
|
Task* const task = job->add_tasks();
|
|
task->add_machine(machine_id);
|
|
task->add_duration(duration);
|
|
}
|
|
current_job_index_++;
|
|
if (current_job_index_ == declared_job_count_) {
|
|
parser_state_ = JOBS_READ;
|
|
}
|
|
break;
|
|
}
|
|
case JOBS_READ: {
|
|
CHECK_EQ(1, words.size());
|
|
CHECK_EQ("SSD", words[0]);
|
|
parser_state_ = SSD_READ;
|
|
break;
|
|
}
|
|
case SSD_READ: {
|
|
CHECK_EQ(1, words.size());
|
|
CHECK_EQ(words[0], absl::StrCat("M", current_machine_index_)) << line;
|
|
current_job_index_ = 0;
|
|
parser_state_ = MACHINE_READ;
|
|
break;
|
|
}
|
|
case MACHINE_READ: {
|
|
CHECK_EQ(declared_job_count_, words.size());
|
|
Machine* const machine =
|
|
problem_.mutable_machines(current_machine_index_);
|
|
for (const std::string& w : words) {
|
|
const int64_t t = strtoint64(w);
|
|
machine->mutable_transition_time_matrix()->add_transition_time(t);
|
|
}
|
|
if (++current_job_index_ == declared_job_count_) {
|
|
parser_state_ = ++current_machine_index_ == declared_machine_count_
|
|
? DONE
|
|
: SSD_READ;
|
|
}
|
|
break;
|
|
}
|
|
default: {
|
|
LOG(FATAL) << "Should not be here with state " << parser_state_
|
|
<< "with line " << line;
|
|
}
|
|
}
|
|
}
|
|
|
|
void JsspParser::ProcessTardinessLine(const std::string& line) {
|
|
const std::vector<std::string> words =
|
|
absl::StrSplit(line, ' ', absl::SkipEmpty());
|
|
switch (parser_state_) {
|
|
case START: {
|
|
CHECK_EQ(3, words.size());
|
|
SetJobs(strtoint32(words[0]));
|
|
SetMachines(strtoint32(words[1]));
|
|
parser_state_ = JOB_COUNT_READ;
|
|
current_job_index_ = 0;
|
|
break;
|
|
}
|
|
case JOB_COUNT_READ: {
|
|
CHECK_GE(words.size(), 6);
|
|
Job* const job = problem_.mutable_jobs(current_job_index_);
|
|
const int64_t est = strtoint64(words[0]);
|
|
if (est != 0L) {
|
|
job->mutable_earliest_start()->set_value(est);
|
|
}
|
|
job->set_late_due_date(strtoint64(words[1]));
|
|
const double weight = std::stod(words[2]);
|
|
const int64_t tardiness = static_cast<int64_t>(
|
|
round(weight * absl::GetFlag(FLAGS_jssp_scaling_up_factor)));
|
|
job->set_lateness_cost_per_time_unit(tardiness);
|
|
const int num_operations = strtoint32(words[3]);
|
|
for (int i = 0; i < num_operations; ++i) {
|
|
const int machine_id = strtoint32(words[4 + 2 * i]) - 1; // 1 based.
|
|
const int64_t duration = strtoint64(words[5 + 2 * i]);
|
|
Task* const task = job->add_tasks();
|
|
task->add_machine(machine_id);
|
|
task->add_duration(duration);
|
|
}
|
|
current_job_index_++;
|
|
if (current_job_index_ == declared_job_count_) {
|
|
// Fix tardiness weights if all integer from start.
|
|
bool all_integral = true;
|
|
for (const Job& job : problem_.jobs()) {
|
|
if (job.lateness_cost_per_time_unit() %
|
|
absl::GetFlag(FLAGS_jssp_scaling_up_factor) !=
|
|
0) {
|
|
all_integral = false;
|
|
break;
|
|
}
|
|
}
|
|
if (all_integral) {
|
|
for (Job& job : *problem_.mutable_jobs()) {
|
|
job.set_lateness_cost_per_time_unit(
|
|
job.lateness_cost_per_time_unit() /
|
|
absl::GetFlag(FLAGS_jssp_scaling_up_factor));
|
|
}
|
|
} else {
|
|
problem_.mutable_scaling_factor()->set_value(
|
|
1.0L / absl::GetFlag(FLAGS_jssp_scaling_up_factor));
|
|
}
|
|
parser_state_ = DONE;
|
|
}
|
|
break;
|
|
}
|
|
default: {
|
|
LOG(FATAL) << "Should not be here with state " << parser_state_
|
|
<< "with line " << line;
|
|
}
|
|
}
|
|
}
|
|
|
|
void JsspParser::ProcessPssLine(const std::string& line) {
|
|
const std::vector<std::string> words =
|
|
absl::StrSplit(line, ' ', absl::SkipEmpty());
|
|
switch (parser_state_) {
|
|
case START: {
|
|
problem_.set_makespan_cost_per_time_unit(1L);
|
|
CHECK_EQ(1, words.size());
|
|
SetJobs(strtoint32(words[0]));
|
|
parser_state_ = JOB_COUNT_READ;
|
|
break;
|
|
}
|
|
case JOB_COUNT_READ: {
|
|
CHECK_EQ(1, words.size());
|
|
SetMachines(strtoint32(words[0]));
|
|
parser_state_ = MACHINE_COUNT_READ;
|
|
current_job_index_ = 0;
|
|
break;
|
|
}
|
|
case MACHINE_COUNT_READ: {
|
|
CHECK_EQ(1, words.size());
|
|
CHECK_EQ(declared_machine_count_, strtoint32(words[0]));
|
|
if (++current_job_index_ == declared_job_count_) {
|
|
parser_state_ = JOB_LENGTH_READ;
|
|
current_job_index_ = 0;
|
|
current_machine_index_ = 0;
|
|
}
|
|
break;
|
|
}
|
|
case JOB_LENGTH_READ: {
|
|
CHECK_EQ(4, words.size());
|
|
CHECK_EQ(0, strtoint32(words[2]));
|
|
CHECK_EQ(0, strtoint32(words[3]));
|
|
const int machine_id = strtoint32(words[0]) - 1;
|
|
const int duration = strtoint32(words[1]);
|
|
Job* const job = problem_.mutable_jobs(current_job_index_);
|
|
Task* const task = job->add_tasks();
|
|
task->add_machine(machine_id);
|
|
task->add_duration(duration);
|
|
if (++current_machine_index_ == declared_machine_count_) {
|
|
current_machine_index_ = 0;
|
|
if (++current_job_index_ == declared_job_count_) {
|
|
current_job_index_ = -1;
|
|
current_machine_index_ = 0;
|
|
parser_state_ = JOBS_READ;
|
|
transition_index_ = 0;
|
|
for (int m = 0; m < declared_machine_count_; ++m) {
|
|
Machine* const machine = problem_.mutable_machines(m);
|
|
for (int i = 0; i < declared_job_count_ * declared_job_count_;
|
|
++i) {
|
|
machine->mutable_transition_time_matrix()->add_transition_time(0);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
break;
|
|
}
|
|
case JOBS_READ: {
|
|
CHECK_EQ(1, words.size());
|
|
const int index = transition_index_++;
|
|
const int size = declared_job_count_ * declared_machine_count_ + 1;
|
|
const int t1 = index / size;
|
|
const int t2 = index % size;
|
|
if (t1 == 0 || t2 == 0) { // Dummy task.
|
|
break;
|
|
}
|
|
const int item1 = t1 - 1;
|
|
const int item2 = t2 - 1;
|
|
const int job1 = item1 / declared_machine_count_;
|
|
const int task1 = item1 % declared_machine_count_;
|
|
const int m1 = problem_.jobs(job1).tasks(task1).machine(0);
|
|
const int job2 = item2 / declared_machine_count_;
|
|
const int task2 = item2 % declared_machine_count_;
|
|
const int m2 = problem_.jobs(job2).tasks(task2).machine(0);
|
|
if (m1 != m2) { // We are only interested in same machine transitions.
|
|
break;
|
|
}
|
|
const int transition = strtoint32(words[0]);
|
|
Machine* const machine = problem_.mutable_machines(m1);
|
|
machine->mutable_transition_time_matrix()->set_transition_time(
|
|
job1 * declared_job_count_ + job2, transition);
|
|
if (transition_index_ == size * size) {
|
|
parser_state_ = DONE;
|
|
}
|
|
break;
|
|
}
|
|
default: {
|
|
LOG(FATAL) << "Should not be here with state " << parser_state_
|
|
<< "with line " << line;
|
|
}
|
|
}
|
|
}
|
|
|
|
void JsspParser::ProcessEarlyTardyLine(const std::string& line) {
|
|
const std::vector<std::string> words =
|
|
absl::StrSplit(line, ' ', absl::SkipEmpty());
|
|
switch (parser_state_) {
|
|
case JOB_COUNT_READ: {
|
|
CHECK_EQ(words.size(), declared_machine_count_ * 2 + 3);
|
|
Job* const job = problem_.mutable_jobs(current_job_index_);
|
|
for (int i = 0; i < declared_machine_count_; ++i) {
|
|
const int machine_id = strtoint32(words[2 * i]);
|
|
const int64_t duration = strtoint64(words[2 * i + 1]);
|
|
Task* const task = job->add_tasks();
|
|
task->add_machine(machine_id);
|
|
task->add_duration(duration);
|
|
}
|
|
// Early Tardy problem in JET format.
|
|
const int due_date = strtoint32(words[declared_machine_count_ * 2]);
|
|
const int early_cost = strtoint32(words[declared_machine_count_ * 2 + 1]);
|
|
const int late_cost = strtoint32(words[declared_machine_count_ * 2 + 2]);
|
|
job->set_early_due_date(due_date);
|
|
job->set_late_due_date(due_date);
|
|
job->set_earliness_cost_per_time_unit(early_cost);
|
|
job->set_lateness_cost_per_time_unit(late_cost);
|
|
current_job_index_++;
|
|
if (current_job_index_ == declared_job_count_) {
|
|
parser_state_ = DONE;
|
|
}
|
|
break;
|
|
}
|
|
default: {
|
|
LOG(FATAL) << "Should not be here with state " << parser_state_;
|
|
}
|
|
}
|
|
}
|
|
|
|
int JsspParser::strtoint32(absl::string_view word) {
|
|
int result;
|
|
CHECK(absl::SimpleAtoi(word, &result));
|
|
return result;
|
|
}
|
|
|
|
int64_t JsspParser::strtoint64(absl::string_view word) {
|
|
int64_t result;
|
|
CHECK(absl::SimpleAtoi(word, &result));
|
|
return result;
|
|
}
|
|
|
|
} // namespace jssp
|
|
} // namespace scheduling
|
|
} // namespace operations_research
|