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

Preemptive Resource Constrained Project Scheduling Problem

Principles learned

  • Set precedence constraints

  • Relax preemption constraints

  • Use interval decision variables

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

Problem

../_images/prcpsp.svg

In the preemptive 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 can 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.

Download the example


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:

    • Duration of the task

    • Resource requirements (weights) for each resource

    • Number of successors

    • Task ID for each successor

Program

We consider a pseudo-preemptive mode of the Resource-Constrained Project Scheduling Problem (RCPSP), in which each task can be split into at most N subtasks, with N a constant number. For each task, we use N interval decision variables to model the time range of each of its subtasks.

For each task, the sum of the lengths of its subtasks’ intervals is constrained to be equal to the task’s total duration.

The N preemption intervals of each task are ordered.

The precedence constraints are easily written: the last subtask of each task must be placed before the first subtask of 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 prcpsp.lsp inFileName=instances/Pat1.rcp [outFileName=] [lsTimeLimit=]
use io;

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

    inFile = io.openRead(inFileName);
    nbTasks = inFile.readInt();
    nbResources = inFile.readInt();

    // Maximum capacity of each resource
    for [r in 0...nbResources] {
        capacity[r] = inFile.readInt();
    }

    for [i in 0...nbTasks] {
        // Duration of each task
        duration[i] = inFile.readInt();
        for[r in 0...nbResources] {
            // Resource weight of resource r required for task i
            weight[i][r] = inFile.readInt();
        }
        nbSuccessors[i] = inFile.readInt();
        // Successors of each task i
        for [s in 0...nbSuccessors[i]] {
            successors[i][s] = inFile.readInt() - 1;
        }
    }

    // Trivial upper bound for the start times of the tasks
    horizon = sum[i in 0...nbTasks](duration[i]);

    // Number of intervals authorized for each task (pseudo preemption)
    maxNbPreemptions = 4;
    
    inFile.close();
}

function model() {
    // Interval decisions: time range of each task
    // Each task can be split into maxNbPreemptions subtasks
    tasks[0...nbTasks][0...maxNbPreemptions] <- interval(0, horizon);
   
    for [i in 0...nbTasks]{
        // Task duration constraints
        constraint sum[t in 0...maxNbPreemptions](length(tasks[i][t])) == duration[i];

        // Precedence constraints between each task's subtasks
        for[t in 0...maxNbPreemptions - 1]{
            constraint tasks[i][t] < tasks[i][t+1];
        }
    }
    
    // Precedence constraints between the tasks
    for[i in 0...nbTasks][s in 0...nbSuccessors[i]] {
        constraint tasks[i][maxNbPreemptions-1] < tasks[successors[i][s]][0];
    }

    // Makespan: end of the last task
    makespan <- max[i in 0...nbTasks] (end(tasks[i][maxNbPreemptions-1]));

    // Cumulative resource constraints
    for [r in 0...nbResources] {
        constraint and(0...makespan,
                  t => sum[i in 0...nbTasks][k in 0...maxNbPreemptions]
                  (weight[i][r] * contains(tasks[i][k], t)) <= capacity[r]);
    }

    // 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 of each subtask */
function output() {
    if (outFileName != nil) {
        outFile = io.openWrite(outFileName);
        println("Solution written in file ", outFileName);
        outFile.println(makespan.value);
        for [i in 0...nbTasks] {
            outFile.print(i + 1);
            startTime = tasks[i][0].value.start ;
            for [k in 0...maxNbPreemptions]{
                if (tasks[i][k].value.end != startTime){
                    outFile.print(" (", startTime, " ", tasks[i][k].value.end,")");
                }
                if (k < maxNbPreemptions - 1){
                    startTime = tasks[i][k + 1].value.start;
                }
            }
            outFile.println();
        }
    }
}
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python prcpsp.py instances\Pat1.rcp
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_5/bin/python
python prcpsp.py instances/Pat1.rcp
import localsolver
import sys


# The input files follow the "Patterson" format
def read_instance(filename):
    with open(filename) as f:
        lines = f.readlines()

    first_line = lines[0].split()

    # Number of tasks
    nb_tasks = int(first_line[0])

    # Number of resources
    nb_resources = int(first_line[1])

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

    # Duration of each task
    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)]

    for i in range(nb_tasks):
        line = lines[i + 2].split()
        duration[i] = int(line[0])
        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))

    # Number of intervals authorized for each task (pseudo preemption)
    max_nb_preemptions = 4 

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


def main(instance_file, output_file, time_limit):
    nb_tasks, nb_resources, capacity, duration, weight, nb_successors, successors, horizon, max_nb_preemptions = read_instance(
        instance_file)

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

        # Interval decisions: time range of each task
        # Each task can be split into max_nb_preemtptions subtasks
        tasks = [[model.interval(0, horizon) for t in range(max_nb_preemptions)] 
                 for i in range(nb_tasks)]

        for i in range(nb_tasks):
            # Task duration constraints
            model.constraint(
                    model.sum(model.length(tasks[i][t]) for t in range(max_nb_preemptions)) == duration[i])
            
            # Precedence constraints between each task's subtasks
            for t in range(max_nb_preemptions - 1):
                model.constraint(tasks[i][t] < tasks[i][t + 1])
           
        # Precedence constraints between the tasks
        for i in range(nb_tasks):
            for s in range(nb_successors[i]):
                model.constraint(tasks[i][max_nb_preemptions - 1] < tasks[successors[i][s]][0])

        # Makespan: end of the last task
        makespan = model.max([model.end(tasks[i][max_nb_preemptions - 1]) for i in range(nb_tasks)])

        # 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][k], t)
                                    for i in range(nb_tasks) for k in range(max_nb_preemptions))
                <= 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 of each subtask
        #
        if output_file != None:
            with open(output_file, "w") as f:
                print("Solution written in file", output_file)
                f.write(str(makespan.value) + "\n")
                for i in range(nb_tasks):
                    start_time = tasks[i][0].value.start()
                    f.write(str(i + 1))
                    for k in range(max_nb_preemptions):
                        if tasks[i][k].value.end() != start_time :
                            f.write(" (" + str(start_time) + " " + str(tasks[i][k].value.end()) + ")")
                            if k < max_nb_preemptions - 1 :
                                start_time = tasks[i][k + 1].value.start()
                    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[1]
    output_file = sys.argv[2] if len(sys.argv) >= 3 else None
    time_limit = int(sys.argv[3]) if len(sys.argv) >= 4 else 60
    main(instance_file, output_file, time_limit)
Compilation / Execution (Windows)
cl /EHsc prcpsp.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver125.lib
prcpsp instances\Pat1.rcp
Compilation / Execution (Linux)
g++ prcpsp.cpp -I/opt/localsolver_12_5/include -llocalsolver125 -lpthread -o prcpsp
./prcpsp instances/Pat1.rcp
#include "localsolver.h"
#include <algorithm>
#include <fstream>
#include <iostream>
#include <limits>
#include <numeric>
#include <vector>

using namespace localsolver;

class Prcpsp {
private:
    // Number of tasks
    int nbTasks;
    // Number of resources
    int nbResources;
    // Maximum capacity of each resource
    std::vector<int> capacity;
    // Duration of each task
    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;
    // Number of intervals authorized for each task (pseudo preemption)
    int maxNbPreemptions = 4;

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

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

    // The input files follow the "Patterson" format
    void readInstance(const std::string& fileName) {
        std::ifstream infile;
        infile.exceptions(std::ifstream::failbit | std::ifstream::badbit);
        infile.open(fileName.c_str());

        infile >> nbTasks;
        infile >> nbResources;

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

        duration.resize(nbTasks);
        weight.resize(nbTasks);
        nbSuccessors.resize(nbTasks);
        successors.resize(nbTasks);

        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
        // Each task can be split into maxNbPreemptions subtasks
        tasks.resize(nbTasks);
        for (int i = 0; i < nbTasks; ++i) {

            tasks[i].resize(maxNbPreemptions);

            for (int t = 0; t < maxNbPreemptions; t++){
                tasks[i][t] = model.intervalVar(0, horizon);
            }
            
            // Task duration constraints
            LSExpression taskDuration = model.sum();
            for (int t = 0; t < maxNbPreemptions; t++) {
                taskDuration.addOperand(model.length(tasks[i][t]));
            }
            model.constraint(taskDuration == duration[i]);

            // Precedence constraints between each task's subtasks
            for (int t = 0; t < maxNbPreemptions - 1; t++){
                model.constraint(tasks[i][t] < tasks[i][t + 1]);
            }
        }
        
        // Precedence constraints between the tasks
        for (int i = 0; i < nbTasks; ++i) {
            for (int s = 0; s < nbSuccessors[i]; ++s) {
                model.constraint(tasks[i][maxNbPreemptions - 1] < tasks[successors[i][s]][0]);
            }
        }
        
        // Makespan: end of the last task
        makespan = model.max();
        for (int i = 0; i < nbTasks; ++i) {
            makespan.addOperand(model.end(tasks[i][maxNbPreemptions - 1]));
        }
        
        // 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) {
                    for (int k = 0; k < maxNbPreemptions; k++){
                        LSExpression taskWeight = weight[i][r] * model.contains(tasks[i][k], t);
                        totalWeight.addOperand(taskWeight);
                    }
                }
                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 of each subtask */
    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) {
            lsint startTime = (tasks[i][0]).getIntervalValue().getStart();
            outfile << i + 1;
            for (int k = 0; k < maxNbPreemptions; k++){
                if ((tasks[i][k]).getIntervalValue().getEnd() != startTime){
                outfile << " (" << startTime << " "
                                    << (tasks[i][k]).getIntervalValue().getEnd() << ")";
                    if (k < maxNbPreemptions - 1){
                        startTime = (tasks[i][k + 1]).getIntervalValue().getStart();
                    }
                }
            }
            outfile << std::endl;
        }
        outfile.close();
    }
};

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

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

    Prcpsp model(instanceFile);
    try {
        model.readInstance(instanceFile);
        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 Prcpsp.cs /reference:localsolvernet.dll
Prcpsp instances\Pat1.rcp
using System;
using System.IO;
using localsolver;

public class Prcpsp : IDisposable
{
    // Number of tasks
    private int nbTasks;

    // Number of resources
    private int nbResources;

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

    // Duration of each task
    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;

    // Number of intervals authorized for each task (pseudo preemption)
    private int maxNbPreemptions = 4;

    // LocalSolver
    private LocalSolver localsolver;

    // Decision variables: time range of each task
    private LSExpression[,] tasks;

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

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

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

    // The input files follow the "Patterson" format
    private void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] splitted = SplitInput(input);
            if (splitted.Length == 0)
                splitted = SplitInput(input);
            nbTasks = int.Parse(splitted[0]);
            nbResources = int.Parse(splitted[1]);

            // 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]);

            duration = new int[nbTasks];
            weight = new int[nbTasks, nbResources];
            nbSuccessors = new int[nbTasks];
            successors = new int[nbTasks][];

            for (int i = 0; i < nbTasks; ++i)
            {
                splitted = SplitInput(input);
                if (splitted.Length == 0)
                    splitted = SplitInput(input);
                duration[i] = int.Parse(splitted[0]);
                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
        // Each task can be split into maxNbPreemptions subtasks
        tasks = new LSExpression[nbTasks, maxNbPreemptions];
        for (int i = 0; i < nbTasks; ++i)
        {
            for (int t = 0; t < maxNbPreemptions; ++t){
                tasks[i, t] = model.Interval(0, horizon);
            }

            // Task duration constraints
            LSExpression  taskDuration = model.Sum();
            for (int t = 0; t < maxNbPreemptions; ++t){
                taskDuration.AddOperand(model.Length(tasks[i, t]));
            }
            model.Constraint(taskDuration == duration[i]);

            // Precedence constraints between each task's subtasks
            for (int t = 0; t < maxNbPreemptions - 1; ++t){
                model.Constraint(tasks[i, t] < tasks[i, t + 1]);
            }
        }

        // Precedence constraints between the tasks
        for (int i = 0; i < nbTasks; ++i)
        {
            for (int s = 0; s < nbSuccessors[i]; ++s)
            {
                model.Constraint(tasks[i, maxNbPreemptions - 1] < tasks[successors[i][s], 0]);
            }
        }

        // Makespan: end of the last task
        makespan = model.Max();
        for (int i = 0; i < nbTasks; ++i)
            makespan.AddOperand(model.End(tasks[i, maxNbPreemptions - 1]));

        // 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)
                    {
                        for (int k = 0; k < maxNbPreemptions; ++k){
                            totalWeight.AddOperand(weight[i, r] * model.Contains(tasks[i, k], t));
                        }
                    }
                    return 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 of each subtask */
    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)
            {
                long startTime = tasks[i, 0].GetIntervalValue().Start();
                output.Write((i + 1));
                for (int k = 0; k < maxNbPreemptions; ++k){
                    if (tasks[i, k].GetIntervalValue().End() != startTime){
                        output.Write(" (" + startTime + " " + tasks[i, k].GetIntervalValue().End() + ")");
                        if (k < maxNbPreemptions - 1){
                            startTime = tasks[i, k + 1].GetIntervalValue().Start();
                        }
                    }   
                } 
                output.WriteLine();
            }
        }
    }

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

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

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

public class Prcpsp {
    // Number of tasks
    private int nbTasks;
    // Number of resources
    private int nbResources;
    // Maximum capacity of each resource
    private int[] capacity;
    // Duration of each task
    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;
    // Number of intervals authorized for each task (pseudo preemption)
    private int maxNbPreemptions = 4;

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

    public Prcpsp(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))) {
            nbTasks = input.nextInt();
            nbResources = input.nextInt();

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

            duration = new int[nbTasks];
            weight = new int[nbTasks][nbResources];
            nbSuccessors = new int[nbTasks];
            successors = new int[nbTasks][];
            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
        // Each task can be split into maxNbPreemptions subtasks
        tasks = new LSExpression[nbTasks][maxNbPreemptions];
        for (int i = 0; i < nbTasks; ++i){

            for (int t = 0; t < maxNbPreemptions; ++t) {
                tasks[i][t] = model.intervalVar(0, horizon);
            }
            
            // Task duration constraints
            LSExpression taskDuration = model.sum();
            for (int t = 0; t < maxNbPreemptions; ++t) {
                taskDuration.addOperand(model.length(tasks[i][t]));
            }
            model.constraint(model.eq(taskDuration, duration[i]));

            // Precedence constraints between each task's subtasks
            for (int t = 0; t < maxNbPreemptions - 1; ++t){
                model.constraint(model.lt(tasks[i][t], tasks[i][t + 1]));
            }
        }

        // Precedence constraints between the tasks
        for (int i = 0; i < nbTasks; ++i) {
            for (int s = 0; s < nbSuccessors[i]; ++s) {
                model.constraint(model.lt(tasks[i][maxNbPreemptions - 1], tasks[successors[i][s]][0]));
            }
        }

        // Makespan: end of the last task
        makespan = model.max();
        for (int i = 0; i < nbTasks; ++i) {
            makespan.addOperand(model.end(tasks[i][maxNbPreemptions - 1]));
        }

        // 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) {
                    for (int k = 0; k < maxNbPreemptions; ++k){
                        totalWeight.addOperand(model.prod(
                            weight[i][rL],
                            model.contains(tasks[i][k], t)));
                    }
                }
                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 of each subtask
     */
    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) {
                long start_time = tasks[i][0].getIntervalValue().getStart();
                output.print(i + 1);
                for (int k = 0; k < maxNbPreemptions; ++k){
                    if (tasks[i][k].getIntervalValue().getEnd() != start_time){
                        output.print(" (" + start_time + " "
                            + tasks[i][k].getIntervalValue().getEnd() + ")");
                        if (k < maxNbPreemptions - 1){
                            start_time = tasks[i][k + 1].getIntervalValue().getStart();
                        }
                    }
                }
                output.println();
            }
        }
    }

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

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

        try (LocalSolver localsolver = new LocalSolver()) {
            Prcpsp model = new Prcpsp(localsolver, instanceFile);
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}