Project Scheduling Problem with Production and Consumption of Resources¶

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);
        }
    }
}