• Docs »
• Example tour »
• Flexible Resource Constrained Project Scheduling Problem

# Flexible Resource Constrained Project Scheduling Problem¶

## Principles learned¶

• Add multiple set decision variables

• Use the find, contains and partition operators

• Use of interval decision variables

• Set precedence constraints

• Use of a nesting of two lambda expressions to write a constraint

## Problem¶

In the flexible cumulative problem, a project consists of a set of tasks that have to be scheduled. We have a finite number of renewable resources. Each task has to be done by one and only one resource and there can be several resources that can carry out this activity. Each task has a given duration and weight (both possibly equal to zero) on each resource and cannot be interrupted. The weight represents the amount of the resource it consumes while the task is being processed. If both the duration and the weight of the task for a given resource are zero, then the corresponding task cannot be performed by this resource. There are precedence constraints between the tasks: each task must end before any of its successors can start. 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 format of the data files is as follows:

• First line:

• Number of renewable resources

• Second line: Maximum capacity for each resource

• From the third line, for each task * for each resource

• Resource requirements (weights)

• From the next line, for each task:

• Number of successors

• Task ID for each successor

## Program¶

We use set variables to model the set of tasks done by the resource.

Each task must be processed, hence the `partition` operator on the sets, which ensures that each task will belong to one and only one resource. Resources that are not compatible for an operation are filtered out using a contains operator.

The `find` operator takes as argument an array of sets and an integer value, and returns the position of the set containing the value in the array, if it exists. Here, we use this operator to retrieve the id of the resource used for each task. It then allows to deduce the duration of the operation, since it depends on the selected resource.

We use interval variables to model the start and end times of the tasks which have to respect the duration of the task according to the resource that process it.

The precedence constraints are easily written: each task must end before any of its successors can start.

The cumulative resource constraints can be formulated as follows: for each resource r, 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 r, the weights of all the tasks it processes at time slot t.

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

Execution:
localsolver flexible_cumulative.lsp inFileName=instances/pat1.fc [outFileName=] [lsTimeLimit=]
```use io;

function input() {
local usage = "Usage: localsolver flexible_cumulative.lsp inFileName=instanceFile "
+ "[outFileName=outputFile] [lsTimeLimit=timeLimit]";
if (inFileName == nil) throw usage;

// Number of resources

// Maximum capacity of each resource
for [i in 0...nbTasks][r in 0...nbResources] {
// Duration of task i if task i is done by resource r
// Resource weight of resource r required for task i
}

// The number of successors of 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() {
// Set of tasks done by each resource

// Only compatible resources can be selected for a task
for [i in 0...nbTasks][r in 0...nbResources] {
if (taskProcessingTime[i][r] == 0 && weight[r][i] == 0)
}

// All tasks are scheduled on the resources

// For each task, the selected resource

// 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, t =>
}

// 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 selected resource, 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 flexible_cumulative.py instances\pat1.fc
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_0/bin/python
python flexible_cumulative.py instances/pat1.fc
```import localsolver
import sys

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 of task i if task i is done by resource r

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

# 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_d_w = lines[i + 2].split()
for r in range(nb_resources):
weight[r].append(int(line_d_w[2 * r + 1]))

line_succ = lines[i + 2 + nb_tasks].split()
nb_successors[i] = int(line_succ)
successors[i] = [int(elm) for elm in line_succ[1::]]

# Trivial upper bound for the start times of the tasks

def main(instance_file, output_file, time_limit):

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

# Set of tasks done by each resource

# Only compatible resources can be selected for a task
for r in range(nb_resources):
if task_processing_time_data[i][r] == 0 and weight[r][i] == 0:

# For each task, the selected resource

# All tasks are scheduled on the resources
model.constraint(model.partition(resources))

# Interval decisions: time range of each task

# Create LocalSolver arrays to be able to access them with an "at" operator
weight_array = model.array(weight)

# 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 i: model.at(weight_array, r, i) * model.contains(tasks_array[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 selected resource, 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) + " " + str(task_resource[i].value) + " " + str(tasks[i].value.start()) + " " +
f.write("\n")

if __name__ == '__main__':
if len(sys.argv) < 2:
print("Usage: python flexible_cumulative.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 flexible_cumulative.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver120.lib
flexible_cumulative instances\pat1.fc
Compilation / Execution (Linux)
g++ flexible_cumulative.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -lpthread -o flexible_cumulative
./flexible_cumulative instances/pat1.fc
```#include "localsolver.h"
#include <algorithm>
#include <fstream>
#include <iostream>
#include <limits>
#include <numeric>
#include <vector>

using namespace localsolver;

class FlexibleCumulative {
private:
// Number of resources
int nbResources;
// Maximum capacity of each resource
std::vector<int> capacity;
// Duration of task i if task i is done by resource r
// Resource weight of resource r required for task i
std::vector<std::vector<int>> weightData;
// 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: set of tasks done by each resource
// Decision variables: time range of each task
// For each task, the selected resource
// Objective = minimize the makespan: end of the last task
LSExpression makespan;

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

std::ifstream infile;
infile.open(fileName.c_str());

infile >> nbResources;

capacity.resize(nbResources);
for (int r = 0; r < nbResources; ++r) {
infile >> capacity[r];
}

weightData.resize(nbResources);

for (int i = 0; i < nbTasks; ++i) {
}

for (int r = 0; r < nbResources; ++r) {
}

for (int i = 0; i < nbTasks; ++i) {
for (int r = 0; r < nbResources; ++r) {
std::cout << i << " " << r << " " << taskProcessingTimeData[i][r] << std::endl;
infile >> weightData[r][i];
}
}

for (int i = 0; i < nbTasks; ++i) {
infile >> nbSuccessors[i];
successors[i].resize(nbSuccessors[i]);
for (int s = 0; s < nbSuccessors[i]; ++s) {
infile >> successors[i][s];
}
}

infile.close();
}

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

LSExpression resources = model.array();
for (int r = 0; r < nbResources; ++r) {
}

// Create LocalSolver arrays to be able to access them with "at" operators
LSExpression weight = model.array();
for (int r = 0; r < nbResources; ++r) {
}
for (int i = 0; i < nbTasks; ++i) {
}

// Only compatible resources can be selected for a task
for (int i = 0; i < nbTasks; ++i) {
for (int r = 0; r < nbResources; ++r) {
if (taskProcessingTimeData[i][r] == 0 && weightData[r][i] == 0) {
}
}
}

// All tasks are scheduled on the resources
model.constraint(model.partition(resources));

for (int i = 0; i < nbTasks; ++i) {
// For each task, the selected resource
}

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

}

// 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) {
}

// Create a LocalSolver array to be able to access it with "at" operator
for (int i = 0; i < nbTasks; ++i) {
}

// Cumulative resource constraints
for (int r = 0; r < nbResources; ++r) {
LSExpression capacityRespected = model.createLambdaFunction([&](LSExpression t) {
LSExpression taskWeight = model.createLambdaFunction([&](LSExpression i) {
return model.at(weight, r, i) * model.contains(tasksArray[i], t);
});
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 selected resource, 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 << " " << taskResource[i].getValue() << " " << tasks[i].getIntervalValue().getStart() << " "
}
outfile.close();
}
};

int main(int argc, char** argv) {
if (argc < 2) {
std::cout << "Usage: flexible_cumulative 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";

FlexibleCumulative 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 FlexibleCumulative.cs /reference:localsolvernet.dll
FlexibleCumulative instances\pat1.fc
```using System;
using System.IO;
using System.Linq;
using localsolver;

public class FlexibleCumulative : IDisposable
{

// Number of resources
private int nbResources;

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

// Duration of task i if task i is done by resource r

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

// 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: set of tasks done by each resource

// Decision variables: time range of each task

// For each task, the selected resource

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

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

return input.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
}

{
{
if (splitted.Length == 0)
nbResources = int.Parse(splitted);

capacity = new int[nbResources];
for (int r = 0; r < nbResources; ++r)
capacity[r] = int.Parse(splitted[r]);

for (int i = 0; i < nbTasks; i++)

weightData = new int[nbResources][];
for (int r = 0; r < nbResources; r++)

for (int i = 0; i < nbTasks; ++i)
{
if (splitted.Length == 0)
for (int r = 0; r < nbResources; ++r)
{
weightData[r][i] = int.Parse(splitted[2 * r + 1]);
}
}

for (int i = 0; i < nbTasks; ++i)
{
if (splitted.Length == 0)
nbSuccessors[i] = int.Parse(splitted);
successors[i] = new int[nbSuccessors[i]];
for (int s = 0; s < nbSuccessors[i]; ++s)
successors[i][s] = int.Parse(splitted[s + 1]);
}
}
}

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

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

for (int r = 0; r < nbResources; ++r)

// Create LocalSolver arrays to be able to access them with "at" operators
LSExpression weight = model.Array(weightData);

// Only compatible resources can be selected for a task
for (int i = 0; i < nbTasks; ++i)
{
for (int r = 0; r < nbResources; ++r)
{
if (taskProcessingTimeData[i][r] == 0 && weightData[r][i] == 0)
{
}
}
}

// All tasks are scheduled on the resources
model.Constraint(model.Partition(resources));

for (int i = 0; i < nbTasks; ++i)
{
// For each task, the selected resource
}

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

LSExpression iExpr = model.CreateConstant(i);
}

// Create a LocalSolver array to be able to access it with "at" operator
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 rExpr = model.CreateConstant(r);
return model.At(weight, rExpr, i) * model.Contains(tasksArray[i], t);
});
});
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 selected resource, 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 + " " + taskResource[i].GetValue() + " " + tasks[i].GetIntervalValue().Start() + " "
output.WriteLine();
}
}
}

public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: FlexibleCumulative 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 (FlexibleCumulative model = new FlexibleCumulative(instanceFile))
{
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}
```
Compilation / Execution (Windows)
javac FlexibleCumulative.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. FlexibleCumulative instances\pat1.fc
Compilation / Execution (Linux)
javac FlexibleCumulative.java -cp /opt/localsolver_12_0/bin/localsolver.jar
java -cp /opt/localsolver_12_0/bin/localsolver.jar:. FlexibleCumulative instances/pat1.fc
```import java.util.*;
import java.io.*;
import localsolver.*;

public class FlexibleCumulative {
// Number of resources
private int nbResources;
// Maximum capacity of each resource
private int[] capacity;
// Duration of task i if task i is done by resource r
// Resource weight of resource r required for task i
private int[][] weightData;
// 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: set of tasks done by each resource
// Decision variables: time range of each task
// For each task, the selected resource
// Objective = minimize the makespan: end of the last task
private LSExpression makespan;

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

private void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
nbResources = input.nextInt();

capacity = new int[nbResources];
for (int r = 0; r < nbResources; ++r) {
capacity[r] = input.nextInt();
}

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

for (int r = 0; r < nbResources; ++r) {
}
}
}
}
}

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

for (int r = 0; r < nbResources; ++r) {
}
// Create LocalSolver arrays to be able to access them with "at" operators
LSExpression weight = model.array(weightData);

// Only compatible resources can be selected for a task
for (int i = 0; i < nbTasks; ++i) {
for (int r = 0; r < nbResources; ++r) {
if (taskProcessingTimeData[i][r] == 0 && weightData[r][i] == 0) {
}
}
}

// All tasks are scheduled on the resources
model.constraint(model.partition(resources));

for (int i = 0; i < nbTasks; ++i) {
// For each task, the selected resource
}

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

LSExpression iExpr = model.createConstant(i);
}

// Create a LocalSolver array to be able to access it with "at" operator
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 taskWeight = model.lambdaFunction(i -> {
LSExpression rExpr = model.createConstant(rL);
return model.prod(
model.at(weight, rExpr, i),
});
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 selected resource, 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 + " " + taskResource[i].getValue() + " " + tasks[i].getIntervalValue().getStart() + " "
}
}
}

public static void main(String[] args) {
if (args.length < 1) {
System.out.println("Usage: java FlexibleCumulative 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()) {
FlexibleCumulative model = new FlexibleCumulative(localsolver, instanceFile);