rcpsp.proto

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.
 
// RCPSP: Resource-Constrained Project Scheduling Problem.
//
// The problem description is as follows:
//
// You have a set of resources. They all have a maximum capacity, and
// can be renewable or not.
//
// You have a set of tasks. Each task has a list of successors, and a
// list of recipes. Each recipe consists of a duration, and a list of
// demands, one per resource.
// The problem is always built with 2 sentinels. The first task is the source
// with a set of successors. The last task is the sink, with no successors and a
// zero duration.
// All tasks are reachable from the source task. And the sink task is reachable
// from all tasks. Furthermore, the graph has no cycles.
//
// The tasks dependencies form a DAG with a single source and a single end.
// Both source and end tasks have a zero duration, and no resource consumption.
//
// In case the problem is of type RCPSP/Max. The data contains an additional
// 3D array of delays per task. This structure contains the following
// information for task i with recipe ri and successor j with recipe rj, then
// start(i) + delay(i, ri, j, rj) <= start(j). This subsumes the normal
// successor predecence of the non RCPSP/Max variation, i.e.:
//   start(i) + duration(i, mi) <= start(j).
//
// In the normal case, the objective is to minimize the makespan of the problem.
//
// In the resource investment problem, there is no makespan. It is
// replaced by a strict deadline, and each task must finish before
// this deadline.  In that case, resources have a unit cost, and the
// objective is to minimize the sum of resource cost.
//
// In the consumer/producer case, tasks have a zero duration, and demands can be
// negative. The constraint states that at each time point, the sum of demands
// happening before or during this time must be between the min and max
// capacity. Note that in that case, both min and max capacity can be negative.
// Furthermore, if 0 is not in [min_capacity, max_capacity], then a sufficient
// set of events must happen at time 0 such that the sum of their demands must
// fall inside the capacity interval.
//
// The supported file formats are:
//   - standard psplib (.sm and .mm):
//     http://www.om-db.wi.tum.de/psplib/data.html
//   - rcpsp problem in the patterson format (.rcp):
//     http://www.om-db.wi.tum.de/psplib/dataob.html
//   - rcpsp/max (.sch):
//     https://www.wiwi.tu-clausthal.de/de/abteilungen/produktion/forschung/
//           schwerpunkte/project-generator/rcpspmax/
//     https://www.wiwi.tu-clausthal.de/de/abteilungen/produktion/forschung/
//           schwerpunkte/project-generator/mrcpspmax/
//   - resource investment problem with max delay (.sch):
//     https://www.wiwi.tu-clausthal.de/de/abteilungen/produktion/forschung/
//           schwerpunkte/project-generator/ripmax/
 
syntax = "proto3";
 
option java_package = "com.google.ortools.scheduling.rcpsp";
option java_multiple_files = true;
option csharp_namespace = "Google.OrTools.Scheduling.Rcpsp";
 
package operations_research.scheduling.rcpsp;
 
message Resource {
  // The max capacity of the cumulative.
  int32 max_capacity = 1;
 
  // This field is used only in the consumer/producer case. It states the
  // minimum capacity that must be valid at each time point.
  int32 min_capacity = 2;
 
  // Indicates if the resource is renewable, that is if a task demands
  // d from this resource, then the available capacity decreases by d at the
  // start of the task and increases by d at the end of the task.
  bool renewable = 3;
 
  // If non zero, then each unit of capacity will incur a cost of unit_cost.
  int32 unit_cost = 4;
}
 
message Recipe {
  // The duration of the task when this recipe is selected.
  int32 duration = 1;
 
  // In the general case, demand must be >= 0. In the consumer/producer case,
  // it can be < 0. Note that in this case, the tasks always have a duration
  // of zero. Thus the effect of the demand (increase or decrease of the
  // current usage) happens at the start of the task.
  repeated int32 demands = 2;
 
  // This parallel list indicates which resource index (in the main problem)
  // the above demand corresponds to.
  repeated int32 resources = 3;
}
 
message PerRecipeDelays {
  repeated int32 min_delays = 1;
}
 
message PerSuccessorDelays {
  repeated PerRecipeDelays recipe_delays = 1;
}
 
message Task {
  // The indices of the successors tasks in the main problem.
  repeated int32 successors = 1;
 
  // The list of possible ways to execute the task.
  repeated Recipe recipes = 2;
 
  // If the current task has n successors and m recipes then this is
  // an n x m matrix where each entry at line i is a vector with the
  // same length as the number of recipes for the task successor[i]. If
  // recipe m1 is chosen for the current task, and recipe m2 is chosen
  // for its successor i, we have:
  //    start(current_task) + delay[i][m1][m2] <= start(successor_task).
  repeated PerSuccessorDelays successor_delays = 3;
}
 
message RcpspProblem {
  // Problem data.
  repeated Resource resources = 1;
  repeated Task tasks = 2;
  // Problem type.
  bool is_consumer_producer = 3;
  bool is_resource_investment = 4;
  bool is_rcpsp_max = 5;
  // If set, it defines a strict date, and each task must finish before this.
  int32 deadline = 6;
  // Additional info stored in the source file.
  // The horizon is a date where we are sure that all tasks can fit before it.
  int32 horizon = 7;
  // The release date is defined in the rcpsp base format, but is not used.
  int32 release_date = 8;
  // The tardiness cost is defined in the rcpsp base format, but is not used.
  int32 tardiness_cost = 9;
  // The mpm_time is defined in the rcpsp base format, but is not used.
  // It is defined as the minimum makespan in case of interruptible tasks.
  int32 mpm_time = 10;
  // Data used by the problem generator.
  int64 seed = 11;
  string basedata = 12;
  // The due date is defined in the rcpsp base format, but is not used.
  int32 due_date = 13;
  string name = 14;
}
 
message RcpspAssignment {
  repeated int64 start_of_task = 1;
  repeated int32 selected_recipe_of_task = 2;
}