// Copyright 2010-2018 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. One source task with a set of // successors, and one sink task 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.data.rcpsp"; option java_multiple_files = true; option csharp_namespace = "Google.OrTools.Data.Rcpsp"; package operations_research.data.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; }