rcpsp_parser.cc

Go to the documentation of this file.

// Copyright 2010-2024 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/rcpsp_parser.h"
 
#include <cstdint>
#include <string>
#include <vector>
 
#include "absl/strings/match.h"
#include "absl/strings/numbers.h"
#include "absl/strings/str_split.h"
#include "absl/strings/string_view.h"
#include "ortools/base/path.h"
#include "ortools/scheduling/rcpsp.pb.h"
#include "ortools/util/filelineiter.h"
 
namespace operations_research {
namespace scheduling {
namespace rcpsp {
 
RcpspParser::RcpspParser()
    : seed_(-1),
      load_status_(NOT_STARTED),
      num_declared_tasks_(-1),
      current_task_(-1),
      unreads_(0) {
  rcpsp_.set_deadline(-1);
  rcpsp_.set_horizon(-1);
}
 
bool RcpspParser::ParseFile(const std::string& file_name) {
  if (load_status_ != NOT_STARTED) {
    return false;
  }
 
  const bool is_rcpsp_max =
      absl::EndsWith(file_name, ".sch") || absl::EndsWith(file_name, ".SCH");
  const bool is_patterson = absl::EndsWith(file_name, ".rcp");
  load_status_ = HEADER_SECTION;
 
  for (const std::string& line : FileLines(file_name)) {
    if (is_rcpsp_max) {
      ProcessRcpspMaxLine(line);
    } else if (is_patterson) {
      ProcessPattersonLine(line);
    } else {
      ProcessRcpspLine(line);
    }
    if (load_status_ == ERROR_FOUND) {
      LOG(INFO) << rcpsp_;
      return false;
    }
  }
  VLOG(1) << "Read file: " << file_name << ", max = " << is_rcpsp_max
          << ", patterson = " << is_patterson << ", with "
          << rcpsp_.tasks_size() << " tasks, and " << rcpsp_.resources_size()
          << " resources.";
 
  // We use a temporary string as open source protobufs do not accept
  // set_name(string_view).
  std::string problem_name(file::Stem(file_name));
  rcpsp_.set_name(problem_name);
 
  // Count the extra start and end tasks.
  return num_declared_tasks_ + 2 == rcpsp_.tasks_size() &&
         load_status_ == PARSING_FINISHED;
}
 
void RcpspParser::ReportError(const std::string& line) {
  LOG(ERROR) << "Error: status = " << load_status_ << ", line = " << line;
  load_status_ = ERROR_FOUND;
}
 
void RcpspParser::SetNumDeclaredTasks(int t) {
  num_declared_tasks_ = t;
  recipe_sizes_.resize(t + 2, 0);  // The data format adds 2 sentinels.
}
 
void RcpspParser::ProcessRcpspLine(const std::string& line) {
  if (absl::StartsWith(line, "***")) return;
  if (absl::StartsWith(line, "---")) return;
 
  const std::vector<std::string> words =
      absl::StrSplit(line, absl::ByAnyChar(" :\t\r"), absl::SkipEmpty());
 
  if (words.empty()) return;
 
  switch (load_status_) {
    case NOT_STARTED: {
      ReportError(line);
      break;
    }
    case HEADER_SECTION: {
      if (words[0] == "file") {
        rcpsp_.set_basedata(words[3]);
      } else if (words[0] == "initial") {
        rcpsp_.set_seed(strtoint64(words[4]));
        load_status_ = PROJECT_SECTION;
      } else if (words[0] == "jobs") {
        // Workaround for the mmlib files which has less headers.
        SetNumDeclaredTasks(strtoint32(words[4]) - 2);
        load_status_ = PROJECT_SECTION;
      } else {
        ReportError(line);
      }
      break;
    }
    case PROJECT_SECTION: {
      if (words[0] == "projects") {
        // Nothing to do.
      } else if (words[0] == "jobs") {
        // This declaration counts the 2 sentinels.
        SetNumDeclaredTasks(strtoint32(words[4]) - 2);
      } else if (words[0] == "horizon") {
        rcpsp_.set_horizon(strtoint32(words[1]));
      } else if (words[0] == "RESOURCES") {
        // Nothing to do.
      } else if (words.size() > 1 && words[1] == "renewable") {
        for (int i = 0; i < strtoint32(words[2]); ++i) {
          Resource* const res = rcpsp_.add_resources();
          res->set_max_capacity(-1);
          res->set_renewable(true);
          res->set_unit_cost(0);
        }
      } else if (words.size() > 1 && words[1] == "nonrenewable") {
        for (int i = 0; i < strtoint32(words[2]); ++i) {
          Resource* const res = rcpsp_.add_resources();
          res->set_max_capacity(-1);
          res->set_min_capacity(-1);
          res->set_renewable(false);
          res->set_unit_cost(0);
        }
      } else if (words.size() > 1 && words[1] == "doubly") {
        // Nothing to do.
      } else if (words.size() == 2 && words[0] == "PROJECT") {
        load_status_ = INFO_SECTION;
      } else if (words.size() == 2 && words[0] == "PRECEDENCE") {
        // mmlib files have no info section.
        load_status_ = PRECEDENCE_SECTION;
      } else {
        ReportError(line);
      }
      break;
    }
    case INFO_SECTION: {
      if (words[0] == "pronr.") {
        // Nothing to do.
      } else if (words.size() == 6) {
        SetNumDeclaredTasks(strtoint32(words[1]));
        rcpsp_.set_release_date(strtoint32(words[2]));
        rcpsp_.set_due_date(strtoint32(words[3]));
        rcpsp_.set_tardiness_cost(strtoint32(words[4]));
        rcpsp_.set_mpm_time(strtoint32(words[5]));
      } else if (words.size() == 2 && words[0] == "PRECEDENCE") {
        load_status_ = PRECEDENCE_SECTION;
      } else {
        ReportError(line);
      }
      break;
    }
    case PRECEDENCE_SECTION: {
      if (words[0] == "jobnr.") {
        // Nothing to do.
      } else if (words.size() >= 3) {
        const int task_index = strtoint32(words[0]) - 1;
        CHECK_EQ(task_index, rcpsp_.tasks_size());
        recipe_sizes_[task_index] = strtoint32(words[1]);
        const int num_successors = strtoint32(words[2]);
        if (words.size() != 3 + num_successors) {
          ReportError(line);
          break;
        }
        Task* const task = rcpsp_.add_tasks();
        for (int i = 0; i < num_successors; ++i) {
          // The array of tasks is 0-based for us.
          task->add_successors(strtoint32(words[3 + i]) - 1);
        }
      } else if (words[0] == "REQUESTS/DURATIONS") {
        load_status_ = REQUEST_SECTION;
      } else {
        ReportError(line);
      }
      break;
    }
    case REQUEST_SECTION: {
      if (words[0] == "jobnr.") {
        // Nothing to do.
      } else if (words.size() == 3 + rcpsp_.resources_size()) {
        // Start of a new task (index is 0-based for us).
        current_task_ = strtoint32(words[0]) - 1;
        const int current_recipe = strtoint32(words[1]) - 1;
        CHECK_EQ(current_recipe, rcpsp_.tasks(current_task_).recipes_size());
        if (current_recipe != 0) {
          ReportError(line);
          break;
        }
        Recipe* const recipe =
            rcpsp_.mutable_tasks(current_task_)->add_recipes();
        recipe->set_duration(strtoint32(words[2]));
        for (int i = 0; i < rcpsp_.resources_size(); ++i) {
          const int demand = strtoint32(words[3 + i]);
          if (demand != 0) {
            recipe->add_demands(demand);
            recipe->add_resources(i);
          }
        }
      } else if (words.size() == 2 + rcpsp_.resources_size()) {
        // New recipe for a current task.
        const int current_recipe = strtoint32(words[0]) - 1;
        CHECK_EQ(current_recipe, rcpsp_.tasks(current_task_).recipes_size());
        Recipe* const recipe =
            rcpsp_.mutable_tasks(current_task_)->add_recipes();
        recipe->set_duration(strtoint32(words[1]));
        for (int i = 0; i < rcpsp_.resources_size(); ++i) {
          const int demand = strtoint32(words[2 + i]);
          if (demand != 0) {
            recipe->add_demands(demand);
            recipe->add_resources(i);
          }
        }
      } else if (words[0] == "RESOURCEAVAILABILITIES" ||
                 (words[0] == "RESOURCE" && words[1] == "AVAILABILITIES")) {
        load_status_ = RESOURCE_SECTION;
      } else {
        ReportError(line);
      }
      break;
    }
    case RESOURCE_SECTION: {
      if (words.size() == 2 * rcpsp_.resources_size()) {
        // Nothing to do.
      } else if (words.size() == rcpsp_.resources_size()) {
        for (int i = 0; i < words.size(); ++i) {
          rcpsp_.mutable_resources(i)->set_max_capacity(strtoint32(words[i]));
        }
        load_status_ = PARSING_FINISHED;
      } else {
        ReportError(line);
      }
      break;
    }
    case RESOURCE_MIN_SECTION: {
      LOG(FATAL) << "Should not be here";
      break;
    }
    case PARSING_FINISHED: {
      break;
    }
    case ERROR_FOUND: {
      break;
    }
  }
}
 
void RcpspParser::ProcessRcpspMaxLine(const std::string& line) {
  const std::vector<std::string> words =
      absl::StrSplit(line, absl::ByAnyChar(" :\t[]\r"), absl::SkipEmpty());
 
  switch (load_status_) {
    case NOT_STARTED: {
      ReportError(line);
      break;
    }
    case HEADER_SECTION: {
      rcpsp_.set_is_rcpsp_max(true);
      if (words.size() == 2) {
        rcpsp_.set_is_consumer_producer(true);
      } else if (words.size() < 4 || strtoint32(words[3]) != 0) {
        ReportError(line);
        break;
      }
 
      if (words.size() == 5) {
        rcpsp_.set_deadline(strtoint32(words[4]));
        rcpsp_.set_is_resource_investment(true);
      }
 
      SetNumDeclaredTasks(strtoint32(words[0]));
      temp_delays_.resize(num_declared_tasks_ + 2);
 
      // Creates resources.
      if (rcpsp_.is_consumer_producer()) {
        const int num_nonrenewable_resources = strtoint32(words[1]);
        for (int i = 0; i < num_nonrenewable_resources; ++i) {
          Resource* const res = rcpsp_.add_resources();
          res->set_max_capacity(-1);
          res->set_min_capacity(-1);
          res->set_renewable(false);
          res->set_unit_cost(0);
        }
      } else {
        const int num_renewable_resources = strtoint32(words[1]);
        const int num_nonrenewable_resources = strtoint32(words[2]);
        for (int i = 0; i < num_renewable_resources; ++i) {
          Resource* const res = rcpsp_.add_resources();
          res->set_max_capacity(-1);
          res->set_renewable(true);
          res->set_unit_cost(0);
        }
        for (int i = 0; i < num_nonrenewable_resources; ++i) {
          Resource* const res = rcpsp_.add_resources();
          res->set_max_capacity(-1);
          res->set_min_capacity(-1);
          res->set_renewable(false);
          res->set_unit_cost(0);
        }
      }
 
      // Set up for the next section.
      load_status_ = PRECEDENCE_SECTION;
      current_task_ = 0;
      break;
    }
    case PROJECT_SECTION: {
      LOG(FATAL) << "Should not be here";
      break;
    }
    case INFO_SECTION: {
      LOG(FATAL) << "Should not be here";
      break;
    }
    case PRECEDENCE_SECTION: {
      if (words.size() < 3) {
        ReportError(line);
        break;
      }
 
      const int task_id = strtoint32(words[0]);
      if (task_id != current_task_) {
        ReportError(line);
        break;
      } else {
        current_task_++;
      }
 
      const int num_recipes = strtoint32(words[1]);
      recipe_sizes_[task_id] = num_recipes;
      const int num_successors = strtoint32(words[2]);
 
      Task* const task = rcpsp_.add_tasks();
 
      // Read successors.
      for (int i = 0; i < num_successors; ++i) {
        task->add_successors(strtoint32(words[3 + i]));
      }
 
      // Read flattened delays into temp_delays_.
      for (int i = 3 + num_successors; i < words.size(); ++i) {
        temp_delays_[task_id].push_back(strtoint32(words[i]));
      }
 
      if (task_id == num_declared_tasks_ + 1) {
        // Convert the flattened delays into structured delays (1 vector per
        // successor) in the task_size.
        for (int t = 1; t <= num_declared_tasks_; ++t) {
          const int num_recipes = recipe_sizes_[t];
          const int num_successors = rcpsp_.tasks(t).successors_size();
          int count = 0;
          for (int s = 0; s < num_successors; ++s) {
            PerSuccessorDelays* const succ_delays =
                rcpsp_.mutable_tasks(t)->add_successor_delays();
            for (int r1 = 0; r1 < num_recipes; ++r1) {
              PerRecipeDelays* const recipe_delays =
                  succ_delays->add_recipe_delays();
              const int other = rcpsp_.tasks(t).successors(s);
              const int num_other_recipes = recipe_sizes_[other];
              for (int r2 = 0; r2 < num_other_recipes; ++r2) {
                recipe_delays->add_min_delays(temp_delays_[t][count++]);
              }
            }
          }
          CHECK_EQ(count, temp_delays_[t].size());
        }
 
        // Setup for next section.
        current_task_ = 0;
        load_status_ = REQUEST_SECTION;
      }
      break;
    }
    case REQUEST_SECTION: {
      if (words.size() == 3 + rcpsp_.resources_size()) {
        // Start of a new task.
        current_task_ = strtoint32(words[0]);
 
        // 0 based indices for the recipe.
        const int current_recipe = strtoint32(words[1]) - 1;
        CHECK_EQ(current_recipe, rcpsp_.tasks(current_task_).recipes_size());
        if (current_recipe != 0) {
          ReportError(line);
          break;
        }
        Recipe* const recipe =
            rcpsp_.mutable_tasks(current_task_)->add_recipes();
        recipe->set_duration(strtoint32(words[2]));
        for (int i = 0; i < rcpsp_.resources_size(); ++i) {
          const int demand = strtoint32(words[3 + i]);
          if (demand != 0) {
            recipe->add_demands(demand);
            recipe->add_resources(i);
          }
        }
      } else if (words.size() == 2 + rcpsp_.resources_size() &&
                 rcpsp_.is_consumer_producer()) {
        // Start of a new task.
        current_task_ = strtoint32(words[0]);
 
        // 0 based indices for the recipe.
        const int current_recipe = strtoint32(words[1]) - 1;
        CHECK_EQ(current_recipe, rcpsp_.tasks(current_task_).recipes_size());
        if (current_recipe != 0) {
          ReportError(line);
          break;
        }
        Recipe* const recipe =
            rcpsp_.mutable_tasks(current_task_)->add_recipes();
        recipe->set_duration(0);
        for (int i = 0; i < rcpsp_.resources_size(); ++i) {
          const int demand = strtoint32(words[2 + i]);
          if (demand != 0) {
            recipe->add_demands(demand);
            recipe->add_resources(i);
          }
        }
      } else if (words.size() == 2 + rcpsp_.resources_size()) {
        // New recipe for a current task.
        const int current_recipe = strtoint32(words[0]) - 1;
        CHECK_EQ(current_recipe, rcpsp_.tasks(current_task_).recipes_size());
        Recipe* const recipe =
            rcpsp_.mutable_tasks(current_task_)->add_recipes();
        recipe->set_duration(strtoint32(words[1]));
        for (int i = 0; i < rcpsp_.resources_size(); ++i) {
          const int demand = strtoint32(words[2 + i]);
          if (demand != 0) {
            recipe->add_demands(demand);
            recipe->add_resources(i);
          }
        }
      }
      if (current_task_ == num_declared_tasks_ + 1) {
        if (rcpsp_.is_consumer_producer()) {
          load_status_ = RESOURCE_MIN_SECTION;
        } else {
          load_status_ = RESOURCE_SECTION;
        }
      }
      break;
    }
    case RESOURCE_SECTION: {
      if (words.size() == rcpsp_.resources_size()) {
        for (int i = 0; i < words.size(); ++i) {
          if (rcpsp_.is_resource_investment()) {
            rcpsp_.mutable_resources(i)->set_unit_cost(strtoint32(words[i]));
          } else {
            rcpsp_.mutable_resources(i)->set_max_capacity(strtoint32(words[i]));
          }
        }
        load_status_ = PARSING_FINISHED;
      } else {
        ReportError(line);
      }
      break;
    }
    case RESOURCE_MIN_SECTION: {
      if (words.size() == rcpsp_.resources_size()) {
        for (int i = 0; i < words.size(); ++i) {
          rcpsp_.mutable_resources(i)->set_min_capacity(strtoint32(words[i]));
        }
        load_status_ = RESOURCE_SECTION;
      } else {
        ReportError(line);
      }
      break;
    }
    case PARSING_FINISHED: {
      break;
    }
    case ERROR_FOUND: {
      break;
    }
  }
}
 
void RcpspParser::ProcessPattersonLine(const std::string& line) {
  const std::vector<std::string> words =
      absl::StrSplit(line, absl::ByAnyChar(" :\t[]\r"), absl::SkipEmpty());
 
  if (words.empty()) return;
 
  switch (load_status_) {
    case NOT_STARTED: {
      ReportError(line);
      break;
    }
    case HEADER_SECTION: {
      if (words.size() != 2) {
        ReportError(line);
        break;
      }
      SetNumDeclaredTasks(strtoint32(words[0]) - 2);  // Remove the 2 sentinels.
 
      // Creates resources.
      const int num_renewable_resources = strtoint32(words[1]);
      for (int i = 0; i < num_renewable_resources; ++i) {
        Resource* const res = rcpsp_.add_resources();
        res->set_max_capacity(-1);
        res->set_min_capacity(-1);
        res->set_renewable(true);
        res->set_unit_cost(0);
      }
 
      // Set up for the next section.
      load_status_ = RESOURCE_SECTION;
      break;
    }
    case PROJECT_SECTION: {
      LOG(FATAL) << "Should not be here";
      break;
    }
    case INFO_SECTION: {
      LOG(FATAL) << "Should not be here";
      break;
    }
    case PRECEDENCE_SECTION: {
      if (unreads_ > 0) {
        for (int i = 0; i < words.size(); ++i) {
          rcpsp_.mutable_tasks(current_task_)
              ->add_successors(strtoint32(words[i]) - 1);
          unreads_--;
          CHECK_GE(unreads_, 0);
        }
      } else {
        if (words.size() < 2 + rcpsp_.resources_size()) {
          ReportError(line);
          break;
        }
        CHECK_EQ(current_task_, rcpsp_.tasks_size());
        Task* const task = rcpsp_.add_tasks();
        Recipe* const recipe = task->add_recipes();
        recipe->set_duration(strtoint32(words[0]));
 
        const int num_resources = rcpsp_.resources_size();
        for (int i = 1; i <= num_resources; ++i) {
          const int demand = strtoint32(words[i]);
          if (demand != 0) {
            recipe->add_demands(demand);
            recipe->add_resources(i - 1);
          }
        }
 
        unreads_ = strtoint32(words[1 + num_resources]);
        for (int i = 2 + num_resources; i < words.size(); ++i) {
          // Successors are 1 based in the data file.
          task->add_successors(strtoint32(words[i]) - 1);
          unreads_--;
          CHECK_GE(unreads_, 0);
        }
      }
 
      if (unreads_ == 0 && ++current_task_ == num_declared_tasks_ + 2) {
        load_status_ = PARSING_FINISHED;
      }
      break;
    }
    case REQUEST_SECTION: {
      LOG(FATAL) << "Should not be here";
      break;
    }
    case RESOURCE_SECTION: {
      if (words.size() == rcpsp_.resources_size()) {
        for (int i = 0; i < words.size(); ++i) {
          rcpsp_.mutable_resources(i)->set_max_capacity(strtoint32(words[i]));
        }
        load_status_ = PRECEDENCE_SECTION;
        current_task_ = 0;
      } else {
        ReportError(line);
      }
      break;
    }
    case RESOURCE_MIN_SECTION: {
      LOG(FATAL) << "Should not be here";
      break;
    }
    case PARSING_FINISHED: {
      break;
    }
    case ERROR_FOUND: {
      break;
    }
  }
}
 
int RcpspParser::strtoint32(absl::string_view word) {
  int result;
  CHECK(absl::SimpleAtoi(word, &result));
  return result;
}
 
int64_t RcpspParser::strtoint64(absl::string_view word) {
  int64_t result;
  CHECK(absl::SimpleAtoi(word, &result));
  return result;
}
 
}  // namespace rcpsp
}  // namespace scheduling
}  // namespace operations_research