This page is for an old version of Hexaly Optimizer. We recommend that you update your version and read the documentation for the latest stable release.
  • Docs »
  • Example tour »
  • Project Scheduling Problem with Production and Consumption of Resources

Project Scheduling Problem with Production and Consumption of Resources¶

Principles learned¶

  • Set inventory constraints

  • Use interval decision variables

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

Problem¶

../_images/reservoir_rcpsp.svg

In the project scheduling problem with inventory constraint, a project consists in a set of tasks to be scheduled. Each task has a given duration and cannot be interrupted. There are some precedence constraints on the tasks: a task must be finished before any of its successors can start. The problem also involves two sets of resources: renewable resources, that are freed by a task as soon as it ends, and inventory resources, that can be consumed and/or produced by tasks. Each task has requirements, or weights, for each renewable resource, as well as an amount consumed when the task starts and an amount produced when the task ends for each inventory resource. The renewable resources each have a capacity: several tasks can be processed at once but their cummulated weights on each resource must not exceed this resource capacity. The inventory resources each have an initial level and this level is substracted to by starting tasks and added to by ending tasks. No inventory level can become negative at any point of time.

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

Download the example


Data¶

The format of data files is as follows:

  • First line:

  • Number of tasks

  • Number of renewable resources

  • Number of inventory resources

  • Second line:

  • Maximum capacity for each renewable resource

  • Initial level for each inventory resource

  • From the third line, for each task:

  • Duration of the task

  • Renewable resource requirements (weights) for each resource

  • Inventory resource consumption (at the beginning) and production (at the end) for each inventory resource

  • Number of successors

  • Task ID of each successor

Program¶

The program is very similar to the original resource constrained project scheduling problem, to which we add inventory resources constraints. The original decision variables do not change: interval decision variables to model the time ranges of each task.

The precedence and cumulative (renewable) resource constraints are modeled in the same way as for the original problem: each task must end before any of its successors starts, and for each resource and each time slot t, the amount of resource consumed by the tasks currently being processsed must not exceed the capacity of this resource.

The inventory resource requirements are expressed as follows: for each inventory resource and each time slot t, the amount of this resource that has been produced by tasks that already ended, added to the initial level of this resource, must always be greater or equal to the amount of this resource consumed by tasks that already started.

To model these constrains, we use a lambda function with a sum operator.

The makespan to minimize is the time where all tasks have ended.

Execution:
localsolver rcpsp_producer_consumer.lsp inFileName=instances/ConsProd_bl2002.rcp [outFileName=] [lsTimeLimit=]
use io;

/* Read instance data. The input files follow the "Kone" format */
function input() {
    local usage = "Usage: localsolver rcpsp_producer_consumer.lsp inFileName=instanceFile "
            + "[outFileName=outputFile] [lsTimeLimit=timeLimit]";
    if (inFileName == nil) throw usage;

    inFile = io.openRead(inFileName);
    nbTasks = inFile.readInt(); // Number of operations
    nbResources = inFile.readInt(); // Number of renewable resources
    nbInventories = inFile.readInt(); // Number of inventories
    capacity[0...nbResources] = inFile.readInt();
    initLevel[0...nbInventories] = inFile.readInt();

    for [i in 0...nbTasks] {
        duration[i] = inFile.readInt();
        weight[i][0...nbResources] = inFile.readInt();
        for [r in 0...nbInventories] {
            startCons[i][r] = inFile.readInt();
            endProd[i][r] = inFile.readInt(); 
        }
        nbSuccessors[i] = inFile.readInt();
        successors[i][0...nbSuccessors[i]] = inFile.readInt()-1;
    }
    
    inFile.close();
    
    finishLevel[r in 0...nbInventories] = initLevel[r];
    for [r in 0...nbInventories] {
        for [i in 0...nbTasks] {
            finishLevel[r] -= startCons[i][r];
            finishLevel[r] += endProd[i][r];
        }
    }
    
    timeHorizon = sum[i in 0...nbTasks](duration[i]);
}

/* Declare the optimization model */
function model() {
    tasks[i in 0...nbTasks] <- interval(0, timeHorizon);
    
    for [i in 0...nbTasks] {
        constraint length(tasks[i]) == duration[i];
        
        for [s in 0...nbSuccessors[i]] {
            constraint end(tasks[i]) <=  start(tasks[successors[i][s]]);
        }
    }
    
    makespan <- max[i in 0...nbTasks] (end(tasks[i]));
    
    for [r in 0...nbResources] {
        constraint and(0...makespan,
            t => (sum[i in 0...nbTasks](weight[i][r] * (contains(tasks[i],t))) <= capacity[r]));
    }
    
    for [r in 0...nbInventories] {
        constraint and(0...makespan,
            t => (0 <=  initLevel[r] +
                  sum[i in 0...nbTasks]((endProd[i][r] * (end(tasks[i]) <= t)) - 
                                      (startCons[i][r] * (start(tasks[i]) <= t)))));
    }
    
    minimize makespan;
}

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

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.println(i + 1, " ", tasks[i].value.start, " ", tasks[i].value.end);
        }
    }
}
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python rcpsp_producer_consumer.py instances\ConsProd_bl2002.rcp
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_5/bin/python
python rcpsp_producer_consumer.py instances/ConsProd_bl2002.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])

    # Number of inventories
    nb_inventories = int(first_line[2])
    
    second_line = lines[1].split()

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

    # Initial level of each inventory
    init_level = [int(second_line[r + nb_resources]) for r in range(nb_inventories)]

    # 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)]

    # Inventory consumed at beginning of task i
    start_cons = [[] for i in range(nb_tasks)]

    # Inventory produced at end of task i
    end_prod = [[] 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)]
        start_cons[i] = [int(line[2*r + nb_resources + 1]) for r in range(nb_inventories)]
        end_prod[i] = [int(line[2*r + nb_resources + 2]) for r in range(nb_inventories)]
        nb_successors[i] = int(line[2*nb_inventories + nb_resources + 1])
        successors[i] = [int(line[2*nb_inventories + 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, nb_inventories, capacity, init_level, duration, weight, start_cons, end_prod, nb_successors, successors, horizon)


def main(instance_file, output_file, time_limit):
    nb_tasks, nb_resources, nb_inventories, capacity, init_level, duration, weight, start_cons, end_prod, nb_successors, successors, horizon = read_instance(
        instance_file)

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

        # Interval decisions: time range of each task
        tasks = [model.interval(0, horizon) for _ in range(nb_tasks)]

        # Task duration constraints
        for i in range(nb_tasks):
            model.constraint(model.length(tasks[i]) == duration[i])

        # Precedence constraints between the tasks
        for i in range(nb_tasks):
            for s in range(nb_successors[i]):
                model.constraint(tasks[i] < tasks[successors[i][s]])

        # Makespan: end of the last task
        makespan = model.max([model.end(tasks[i]) 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], t)
                                    for i in range(nb_tasks))
                <= capacity[r])
            model.constraint(model.and_(model.range(makespan), capacity_respected))

        # Non-negative inventory constraints
        for r in range(nb_resources):
            inventory_value = model.lambda_function(
                lambda t: model.sum(end_prod[i][r] * (model.end(tasks[i]) <= t)
                                        - start_cons[i][r] * (model.start(tasks[i]) <= t)
                                    for i in range(nb_tasks)) 
                                    + init_level[r]
                >= 0)
            model.constraint(model.and_(model.range(makespan), inventory_value))

        # 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")
                for i in range(nb_tasks):
                    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_producer_consumer.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 rcpsp_producer_consumer.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver125.lib
rcpsp_producer_consumer instances\ConsProd_bl2002.rcp
Compilation / Execution (Linux)
g++ rcpsp_producer_consumer.cpp -I/opt/localsolver_12_5/include -llocalsolver125 -lpthread -o rcpsp_producer_consumer
./rcpsp_producer_consumer instances/ConsProd_bl2002.rcp
#include "localsolver.h"
#include <algorithm>
#include <fstream>
#include <iostream>
#include <limits>
#include <numeric>
#include <vector>

using namespace localsolver;

class RcpspProducerConsumer {
private:
    // Number of tasks
    int nbTasks;
    // Number of resources
    int nbResources;
    // Number of inventories
    int nbInventories;
    // Maximum capacity of each resource
    std::vector<int> capacity;
    // Initial level of each inventory
    std::vector<int> initLevel;
    // Duration of each task
    std::vector<int> duration;
    // Resource weight of resource r required for task i
    std::vector<std::vector<int>> weight;
    // Inventory consumed at beginning of task
    std::vector<std::vector<int>> startCons;
    // Inventory produced at end of task
    std::vector<std::vector<int>> endProd;
    // 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
    std::vector<LSExpression> tasks;
    // Objective = minimize the makespan: end of the last task of the last job
    LSExpression makespan;

public:
    RcpspProducerConsumer(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;
        infile >> nbInventories;

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

        duration.resize(nbTasks);
        weight.resize(nbTasks);
        startCons.resize(nbTasks);
        endProd.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];
            }
            startCons[i].resize(nbInventories);
            endProd[i].resize(nbInventories);
            for (int r = 0; r < nbInventories; ++r) {
                infile >> startCons[i][r];
                infile >> endProd[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
        tasks.resize(nbTasks);
        for (int i = 0; i < nbTasks; ++i) {
            tasks[i] = model.intervalVar(0, horizon);

            // Task duration constraints
            model.constraint(model.length(tasks[i]) == duration[i]);
        }

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

        // Makespan: end of the last task
        makespan = model.max();
        for (int i = 0; i < nbTasks; ++i) {
            makespan.addOperand(model.end(tasks[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) {
                    LSExpression taskWeight = weight[i][r] * model.contains(tasks[i], t);
                    totalWeight.addOperand(taskWeight);
                }
                return model.leq(totalWeight, capacity[r]);
            });
            model.constraint(model.and_(model.range(0, makespan), capacityRespected));
        }

        // Non-negative inventory constraints
        for (int r = 0; r < nbInventories; ++r) {
            LSExpression inventoryValue = model.createLambdaFunction([&](LSExpression t) {
                LSExpression totalValue = model.sum();
                totalValue.addOperand(initLevel[r]);
                for (int i = 0; i < nbTasks; ++i) {
                    LSExpression taskValue = endProd[i][r] * (t >= model.end(tasks[i])) - startCons[i][r] * (t >= model.start(tasks[i]));
                    totalValue.addOperand(taskValue);
                }
                return model.geq(totalValue, 0);
            });
            model.constraint(model.and_(model.range(0, makespan), inventoryValue));
        }

        // 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() << " "
                    << tasks[i].getIntervalValue().getEnd() << std::endl;
        }
        outfile.close();
    }
};

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

    RcpspProducerConsumer 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 RcpspProducerConsumer.cs /reference:localsolvernet.dll
RcpspProducerConsumer instances\ConsProd_bl2002.rcp
using System;
using System.IO;
using localsolver;

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

    // Number of resources
    private int nbResources;

    // Number of inventories
    private int nbInventories;

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

    // Initial level of each inventory
    private int[] initLevel;

    // Duration of each task
    private int[] duration;

    // Resource weight of resource r required for task i
    private int[,] weight;
    
    // Inventory consumed at beginning of task
    private int[,] startCons;

    // Inventory produced at end of task
    private int[,] endProd;

    // 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
    private LSExpression[] tasks;

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

    public RcpspProducerConsumer(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]);
            nbInventories = int.Parse(splitted[2]);

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


            duration = new int[nbTasks];
            weight = new int[nbTasks, nbResources];
            startCons = new int[nbTasks, nbInventories];
            endProd = new int[nbTasks, nbInventories];
            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]);
                for (int r = 0; r < nbInventories; ++r) {
                    startCons[i, r] = int.Parse(splitted[2*r + nbResources + 1]);
                    endProd[i, r] = int.Parse(splitted[2*r + nbResources + 2]);
                }                   
                nbSuccessors[i] = int.Parse(splitted[2*nbInventories + nbResources + 1]);
                successors[i] = new int[nbSuccessors[i]];
                for (int s = 0; s < nbSuccessors[i]; ++s)
                    successors[i][s] = int.Parse(splitted[s + 2*nbInventories + 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
        tasks = new LSExpression[nbTasks];
        for (int i = 0; i < nbTasks; ++i)
        {
            tasks[i] = model.Interval(0, horizon);

            // Task duration constraints
            model.Constraint(model.Length(tasks[i]) == duration[i]);
        }

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

        // Makespan: end of the last task
        makespan = model.Max();
        for (int i = 0; i < nbTasks; ++i)
            makespan.AddOperand(model.End(tasks[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)
                    {
                        totalWeight.AddOperand(weight[i, r] * model.Contains(tasks[i], t));
                    }
                    return totalWeight <= capacity[r];
                }
            );
            model.Constraint(model.And(model.Range(0, makespan), capacityRespected));
        }

        // Non-negative inventories constraints
        for (int r = 0; r < nbInventories; ++r)
        {
            LSExpression inventoryValue = model.LambdaFunction(t =>
                {
                    LSExpression totalValue = model.Sum();
                    totalValue.AddOperand(initLevel[r]);
                    for (int i = 0; i < nbTasks; ++i)
                    {
                        totalValue.AddOperand(endProd[i,r] * (model.End(tasks[i]) <= t) - startCons[i,r] * (model.Start(tasks[i]) <= t));
                    }
                    return totalValue >= 0;
                }
            );
            model.Constraint(model.And(model.Range(0, makespan), inventoryValue));
        }

        // 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: RcpspProducerConsumer 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 (RcpspProducerConsumer model = new RcpspProducerConsumer(instanceFile))
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}
Compilation / Execution (Windows)
javac RcpspProducerConsumer.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. RcpspProducerConsumer instances\ConsProd_bl2002.rcp
Compilation / Execution (Linux)
javac RcpspProducerConsumer.java -cp /opt/localsolver_12_5/bin/localsolver.jar
java -cp /opt/localsolver_12_5/bin/localsolver.jar:. RcpspProducerConsumer instances/ConsProd_bl2002.rcp
import java.util.*;
import java.io.*;
import localsolver.*;

public class RcpspProducerConsumer {
    // Number of tasks
    private int nbTasks;
    // Number of resources
    private int nbResources;
    // Number of inventories
    private int nbInventories;
    // Maximum capacity of each resource
    private int[] capacity;
    // Initial level of each inventory
    private int[] initLevel;
    // Duration of each task
    private int[] duration;
    // Resource weight of resource r required for task i
    private int[][] weight;
    // Inventory consumed at beginning of task
    private int[][] startCons;
    // Inventory produced at end of task
    private int[][] endProd;
    // 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
    private LSExpression[] tasks;
    // Objective = minimize the makespan: end of the last task of the last job
    private LSExpression makespan;

    public RcpspProducerConsumer(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();
            nbInventories = input.nextInt();

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

            duration = new int[nbTasks];
            weight = new int[nbTasks][nbResources];
            startCons = new int[nbTasks][nbInventories];
            endProd = new int[nbTasks][nbInventories];
            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();
                }
                for (int r = 0; r < nbInventories; ++r) {
                    startCons[i][r] = input.nextInt();
                    endProd[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
        tasks = new LSExpression[nbTasks];
        for (int i = 0; i < nbTasks; ++i) {
            tasks[i] = model.intervalVar(0, horizon);

            // Task duration constraints
            model.constraint(model.eq(model.length(tasks[i]), duration[i]));
        }

        // 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], tasks[successors[i][s]]));
            }
        }

        // Makespan: end of the last task
        makespan = model.max();
        for (int i = 0; i < nbTasks; ++i) {
            makespan.addOperand(model.end(tasks[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) {
                    totalWeight.addOperand(model.prod(
                            weight[i][rL],
                            model.contains(tasks[i], t)));
                }
                return model.leq(totalWeight, capacity[rL]);
            });
            model.constraint(model.and(model.range(0, makespan), capacityRespected));
        }

        // Non-negative inventories constraints
        for (int r = 0; r < nbInventories; ++r) {
            final int rL = r;
            LSExpression inventoryValue = model.lambdaFunction(t -> {
                LSExpression totalValue = model.sum();
                totalValue.addOperand(initLevel[rL]);
                for (int i = 0; i < nbTasks; ++i) {
                    totalValue.addOperand(model.sub(model.prod(
                            endProd[i][rL], 
                            model.leq(model.end(tasks[i]), t)),
                        model.prod(startCons[i][rL],
                                model.leq(model.start(tasks[i]), t))));
                }
                return model.geq(totalValue, 0);
            });
            model.constraint(model.and(model.range(0, makespan), inventoryValue));
        }

        // 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() + " "
                        + tasks[i].getIntervalValue().getEnd());
            }
        }
    }

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