• Docs »
• Example tour »
• Resource Constrained Project Scheduling Problem (RCPSP)

# Resource Constrained Project Scheduling Problem (RCPSP)¶

## Principles learned¶

• Set precedence constraints

• Use interval decision variables

• Use a lambda expression to compute a sum with a variable number of terms

## Problem¶

In the resource constrained project scheduling problem, a project consists of a set of tasks that have to be scheduled. Each task has a given duration and cannot be interrupted. There are precedence constraints between the tasks: each task must end before any of its successors can start. There are a set of renewable resources. Each task has a given resource requirement, or weight, (possibly zero) on each resource, representing the amount of resource it consumes while it is being processed. Each resource has a given maximum capacity: it can process several tasks at once, but the sum of the processed tasks’s weights can never exceed this maximum capacity.

The goal is to find a schedule that minimizes the makespan: the time when all tasks have been processed.

## Data¶

The instances provided follow the Patterson format. The format of the data files is as follows:

• First line:

• Number of tasks (including two additional dummy tasks with duration 0, the source and the sink)

• Number of renewable resources

• Second line: Maximum capacity for each resource

• From the third line, for each task:

• Resource requirements (weights) for each resource

• Number of successors

• Task ID for each successor

## Program¶

We use interval decision variables to model the time ranges of the tasks. The length of the interval is constrained by the duration of each task.

The precedence constraints are easily written: each task must be placed before any of its successors.

The cumulative resource constraints can be formulated as follows: for each resource, and for each time slot t, the amount of resource consumed by the tasks that are being processed must not exceed the resource’s capacity.

To model these constraints, we sum up, for each resource, the weights of all the tasks placed over a given time slot t.

The makespan to minimize is the time when all the tasks have been processed.

Execution:
localsolver rcpsp.lsp inFileName=instances/Pat1.rcp [outFileName=] [lsTimeLimit=]
```use io;

// The input files follow The "Patterson" Format
function input() {
local usage = "Usage: localsolver rcpsp.lsp inFileName=instanceFile "
+ "[outFileName=outputFile] [lsTimeLimit=timeLimit]";
if (inFileName == nil) throw usage;

// Maximum capacity of each resource
for [r in 0...nbResources] {
}

for[r in 0...nbResources] {
// Resource weight of resource r required for task i
}
// Successors of each task i
for [s in 0...nbSuccessors[i]] {
}
}

// Trivial upper bound for the start times of the tasks

inFile.close();
}

function model() {
// Interval decisions: time range of each task

// Precedence constraints between the tasks
for[i in 0...nbTasks][s in 0...nbSuccessors[i]] {
}

// Makespan: end of the last task

// Cumulative resource constraints
for [r in 0...nbResources] {
constraint and(0...makespan,
}

// Minimize the makespan
minimize makespan;
}

// Parameterize the solver
function param() {
if (lsTimeLimit == nil) lsTimeLimit = 60;
}

/* Write the solution in a file with the following format:
*  - total makespan
*  - for each task, the task id, the start and end times */
function output() {
if (outFileName != nil) {
outFile = io.openWrite(outFileName);
println("Solution written in file ", outFileName);
outFile.println(makespan.value);
}
}
}
```
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python rcpsp.py instances\Pat1.rcp
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_0/bin/python
python rcpsp.py instances/Pat1.rcp
```import localsolver
import sys

# The input files follow the "Patterson" format
with open(filename) as f:

first_line = lines.split()

# Number of resources
nb_resources = int(first_line)

# Maximum capacity of each resource
capacity = [int(lines.split()[r]) for r in range(nb_resources)]

duration = [0 for i in range(nb_tasks)]

# Resource weight of resource r required for task i
weight = [[] for i in range(nb_tasks)]

# Number of successors
nb_successors = [0 for i in range(nb_tasks)]

# Successors of each task i
successors = [[] for i in range(nb_tasks)]

line = lines[i + 2].split()
duration[i] = int(line)
weight[i] = [int(line[r + 1]) for r in range(nb_resources)]
nb_successors[i] = int(line[nb_resources + 1])
successors[i] = [int(line[nb_resources + 2 + s]) - 1 for s in range(nb_successors[i])]

# Trivial upper bound for the start times of the tasks
horizon = sum(duration[i] for i in range(nb_tasks))

return (nb_tasks, nb_resources, capacity, duration, weight, nb_successors, successors, horizon)

def main(instance_file, output_file, time_limit):
instance_file)

with localsolver.LocalSolver() as ls:
#
# Declare the optimization model
#
model = ls.model

# Interval decisions: time range of each task

# Precedence constraints between the tasks
for s in range(nb_successors[i]):

# Makespan: end of the last task

# Cumulative resource constraints
for r in range(nb_resources):
capacity_respected = model.lambda_function(
lambda t: model.sum(weight[i][r] * model.contains(tasks[i], t)
<= capacity[r])
model.constraint(model.and_(model.range(makespan), capacity_respected))

# Minimize the makespan
model.minimize(makespan)

model.close()

# Parameterize the solver
ls.param.time_limit = time_limit

ls.solve()

#
# Write the solution in a file with the following format:
# - total makespan
# - for each task, the task id, the start and end times
#
if output_file != None:
with open(output_file, "w") as f:
print("Solution written in file", output_file)
f.write(str(makespan.value) + "\n")
f.write(str(i + 1) + " " + str(tasks[i].value.start()) + " " + str(tasks[i].value.end()))
f.write("\n")

if __name__ == '__main__':
if len(sys.argv) < 2:
print("Usage: python rcpsp.py instance_file [output_file] [time_limit]")
sys.exit(1)

instance_file = sys.argv
output_file = sys.argv if len(sys.argv) >= 3 else None
time_limit = int(sys.argv) if len(sys.argv) >= 4 else 60
main(instance_file, output_file, time_limit)
```
Compilation / Execution (Windows)
cl /EHsc rcpsp.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver120.lib
rcpsp instances\Pat1.rcp
Compilation / Execution (Linux)
g++ rcpsp.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -lpthread -o rcpsp
./rcpsp instances/Pat1.rcp
```#include "localsolver.h"
#include <algorithm>
#include <fstream>
#include <iostream>
#include <limits>
#include <numeric>
#include <vector>

using namespace localsolver;

class Rcpsp {
private:
// Number of resources
int nbResources;
// Maximum capacity of each resource
std::vector<int> capacity;
std::vector<int> duration;
// Resource weight of resource r required for task i
std::vector<std::vector<int>> weight;
// Number of successors
std::vector<int> nbSuccessors;
// Successors for each task i
std::vector<std::vector<int>> successors;
// Trivial upper bound for the start times of the tasks
int horizon = 0;

// Localsolver
LocalSolver localsolver;
// Decision variables: time range of each task
// Objective = minimize the makespan: end of the last task of the last job
LSExpression makespan;

public:
Rcpsp(const std::string& fileName) : localsolver() {}

// The input files follow the "Patterson" format
std::ifstream infile;
infile.open(fileName.c_str());

infile >> nbResources;

// The maximum capacity of each resource
capacity.resize(nbResources);
for (int r = 0; r < nbResources; ++r) {
infile >> capacity[r];
}

for (int i = 0; i < nbTasks; ++i) {
infile >> duration[i];
weight[i].resize(nbResources);
for (int r = 0; r < nbResources; ++r) {
infile >> weight[i][r];
}
infile >> nbSuccessors[i];
successors[i].resize(nbSuccessors[i]);
for (int s = 0; s < nbSuccessors[i]; ++s) {
int x;
infile >> x;
successors[i][s] = x - 1;
}
horizon += duration[i];
}

infile.close();
}

void solve(int TimeLimit) {
// Declare the optimization model
LSModel model = localsolver.getModel();

// Interval decisions: time range of each task
for (int i = 0; i < nbTasks; ++i) {

}

// Precedence constraints between the tasks
for (int i = 0; i < nbTasks; ++i) {
for (int s = 0; s < nbSuccessors[i]; ++s) {
}
}

// Makespan: end of the last task
makespan = model.max();
for (int i = 0; i < nbTasks; ++i) {
}

// Cumulative resource constraints
for (int r = 0; r < nbResources; ++r) {
LSExpression capacityRespected = model.createLambdaFunction([&](LSExpression t) {
LSExpression totalWeight = model.sum();
for (int i = 0; i < nbTasks; ++i) {
}
return model.leq(totalWeight, capacity[r]);
});
model.constraint(model.and_(model.range(0, makespan), capacityRespected));
}

// Minimize the makespan
model.minimize(makespan);

model.close();

// Parameterize the solver
localsolver.getParam().setTimeLimit(TimeLimit);

localsolver.solve();
}

/* Write the solution in a file with the following format:
*  - total makespan
*  - for each task, the task id, the start and end times */
void writeSolution(const std::string& fileName) {
std::ofstream outfile(fileName.c_str());
if (!outfile.is_open()) {
std::cerr << "File " << fileName << " cannot be opened." << std::endl;
exit(1);
}
std::cout << "Solution written in file " << fileName << std::endl;

outfile << makespan.getValue() << std::endl;
for (int i = 0; i < nbTasks; ++i) {
outfile << i + 1 << " " << tasks[i].getIntervalValue().getStart() << " "
}
outfile.close();
}
};

int main(int argc, char** argv) {
if (argc < 2) {
std::cout << "Usage: Rcpsp instanceFile [outputFile] [timeLimit]" << std::endl;
exit(1);
}

const char* instanceFile = argv;
const char* outputFile = argc > 2 ? argv : NULL;
const char* strTimeLimit = argc > 3 ? argv : "60";

Rcpsp model(instanceFile);
try {
const int timeLimit = atoi(strTimeLimit);
model.solve(timeLimit);
if (outputFile != NULL)
model.writeSolution(outputFile);
return 0;
} catch (const std::exception& e) {
std::cerr << "An error occurred: " << e.what() << std::endl;
return 1;
}
}
```
Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc Rcpsp.cs /reference:localsolvernet.dll
Rcpsp instances\Pat1.rcp
```using System;
using System.IO;
using localsolver;

public class Rcpsp : IDisposable
{

// Number of resources
private int nbResources;

// Maximum capacity of each resource
private int[] capacity;

private int[] duration;

// Resource weight of resource r required for task i
private int[,] weight;

// Number of successors
private int[] nbSuccessors;

// Successors for each task i
private int[][] successors;

// Trivial upper bound for the start times of the tasks
private int horizon = 0;

// LocalSolver
private LocalSolver localsolver;

// Decision variables: time range of each task

// Objective = minimize the makespan: end of the last task of the last job
private LSExpression makespan;

public Rcpsp(string fileName)
{
localsolver = new LocalSolver();
}

{
if (line == null)
return new string;
return line.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
}

// The input files follow the "Patterson" format
{
{
string[] splitted = SplitInput(input);
if (splitted.Length == 0)
splitted = SplitInput(input);
nbResources = int.Parse(splitted);

// The maximum capacity of each resource
capacity = new int[nbResources];
splitted = SplitInput(input);
for (int r = 0; r < nbResources; ++r)
capacity[r] = int.Parse(splitted[r]);

for (int i = 0; i < nbTasks; ++i)
{
splitted = SplitInput(input);
if (splitted.Length == 0)
splitted = SplitInput(input);
duration[i] = int.Parse(splitted);
for (int r = 0; r < nbResources; ++r)
weight[i, r] = int.Parse(splitted[r + 1]);
nbSuccessors[i] = int.Parse(splitted[nbResources + 1]);
successors[i] = new int[nbSuccessors[i]];
for (int s = 0; s < nbSuccessors[i]; ++s)
successors[i][s] = int.Parse(splitted[s + nbResources + 2]) - 1;
horizon += duration[i];
}
}
}

public void Dispose()
{
localsolver.Dispose();
}

public void Solve(int timeLimit)
{
// Declare the optimization model
LSModel model = localsolver.GetModel();

// Interval decisions: time range of each task
for (int i = 0; i < nbTasks; ++i)
{

}

// Precedence constraints between the tasks
for (int i = 0; i < nbTasks; ++i)
{
for (int s = 0; s < nbSuccessors[i]; ++s)
{
}
}

// Makespan: end of the last task
makespan = model.Max();
for (int i = 0; i < nbTasks; ++i)

// Cumulative resource constraints
for (int r = 0; r < nbResources; ++r)
{
LSExpression capacityRespected = model.LambdaFunction(t =>
{
LSExpression totalWeight = model.Sum();
for (int i = 0; i < nbTasks; ++i)
{
}
}
);
model.Constraint(model.And(model.Range(0, makespan), capacityRespected));
}

// Minimize the makespan
model.Minimize(makespan);

model.Close();

// Parameterize the solver
localsolver.GetParam().SetTimeLimit(timeLimit);

localsolver.Solve();
}

/* Write the solution in a file with the following format:
*  - total makespan
*  - for each task, the task id, the start and end times */
public void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
Console.WriteLine("Solution written in file " + fileName);
output.WriteLine(makespan.GetValue());
for (int i = 0; i < nbTasks; ++i)
{
output.Write((i + 1) + " " + tasks[i].GetIntervalValue().Start() + " " + tasks[i].GetIntervalValue().End());
output.WriteLine();
}
}
}

public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: Rcpsp instanceFile [outputFile] [timeLimit]");
System.Environment.Exit(1);
}

string instanceFile = args;
string outputFile = args.Length > 1 ? args : null;
string strTimeLimit = args.Length > 2 ? args : "60";

using (Rcpsp model = new Rcpsp(instanceFile))
{
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}
```
Compilation / Execution (Windows)
javac Rcpsp.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. Rcpsp instances\Pat1.rcp
Compilation / Execution (Linux)
javac Rcpsp.java -cp /opt/localsolver_12_0/bin/localsolver.jar
java -cp /opt/localsolver_12_0/bin/localsolver.jar:. Rcpsp instances/Pat1.rcp
```import java.util.*;
import java.io.*;
import localsolver.*;

public class Rcpsp {
// Number of resources
private int nbResources;
// Maximum capacity of each resource
private int[] capacity;
private int[] duration;
// Resource weight of resource r required for task i
private int[][] weight;
// Number of successors
private int[] nbSuccessors;
// Successors for each task i
private int[][] successors;
// Trivial upper bound for the start times of the tasks
private int horizon = 0;

// LocalSolver
final LocalSolver localsolver;
// Decision variables: time range of each task
// Objective = minimize the makespan: end of the last task of the last job
private LSExpression makespan;

public Rcpsp(LocalSolver localsolver, String fileName) throws IOException {
this.localsolver = localsolver;
}

// The input files follow the "Patterson" format
private void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
nbResources = input.nextInt();

// The maximum capacity of each resource
capacity = new int[nbResources];
for (int r = 0; r < nbResources; ++r) {
capacity[r] = input.nextInt();
}

for (int i = 0; i < nbTasks; ++i) {
duration[i] = input.nextInt();
for (int r = 0; r < nbResources; ++r) {
weight[i][r] = input.nextInt();
}
nbSuccessors[i] = input.nextInt();
successors[i] = new int[nbSuccessors[i]];
for (int s = 0; s < nbSuccessors[i]; ++s) {
successors[i][s] = input.nextInt() - 1;
}
horizon += duration[i];
}
}
}

public void solve(int timeLimit) {
// Declare the optimization model
LSModel model = localsolver.getModel();

// Interval decisions: time range of each task
for (int i = 0; i < nbTasks; ++i) {

}

// Precedence constraints between the tasks
for (int i = 0; i < nbTasks; ++i) {
for (int s = 0; s < nbSuccessors[i]; ++s) {
}
}

// Makespan: end of the last task
makespan = model.max();
for (int i = 0; i < nbTasks; ++i) {
}

// Cumulative resource constraints
for (int r = 0; r < nbResources; ++r) {
final int rL = r;
LSExpression capacityRespected = model.lambdaFunction(t -> {
LSExpression totalWeight = model.sum();
for (int i = 0; i < nbTasks; ++i) {
weight[i][rL],
}
return model.leq(totalWeight, capacity[rL]);
});
model.constraint(model.and(model.range(0, makespan), capacityRespected));
}

// Minimize the makespan
model.minimize(makespan);

model.close();

// Parameterize the solver
localsolver.getParam().setTimeLimit(timeLimit);

localsolver.solve();
}

/*
* Write the solution in a file with the following format:
* - total makespan
* - for each task, the task id, the start and end times
*/
public void writeSolution(String fileName) throws IOException {
try (PrintWriter output = new PrintWriter(fileName)) {
System.out.println("Solution written in file " + fileName);

output.println(makespan.getValue());

for (int i = 0; i < nbTasks; ++i) {
output.println((i + 1) + " " + tasks[i].getIntervalValue().getStart() + " "
}
}
}

public static void main(String[] args) {
if (args.length < 1) {
System.out.println("Usage: java Rcpsp instanceFile [outputFile] [timeLimit]");
System.exit(1);
}

String instanceFile = args;
String outputFile = args.length > 1 ? args : null;
String strTimeLimit = args.length > 2 ? args : "60";

try (LocalSolver localsolver = new LocalSolver()) {
Rcpsp model = new Rcpsp(localsolver, instanceFile);