Resource Constrained Project Scheduling Problem (RCPSP)¶

using System;
using System.IO;
using localsolver;

public class Rcpsp : 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 t
    private int[,] weight;

    // Number of successors
    private int[] nbSuccessors;

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

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

    // LocalSolver
    private LocalSolver localsolver;

    // Decision variables: start times of the tasks
    private LSExpression[] taskStart;

    // End times for each task
    private LSExpression[] taskEnd;

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

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

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

            // The maximum capacity of each resource
            capacity = new int[nbResources];
            splitted = input.ReadLine().Split(new [] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            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 t = 0; t < nbTasks; ++t)
            {
                splitted = input.ReadLine().Split(new [] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                if (splitted.Length == 0)
                    splitted = input.ReadLine().Split(new [] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                duration[t] = int.Parse(splitted[0]);
                for (int r = 0; r < nbResources; ++r)
                    weight[t, r] = int.Parse(splitted[r + 1]);
                nbSuccessors[t] = int.Parse(splitted[nbResources + 1]);
                successors[t] = new int[nbSuccessors[t]];
                for (int s = 0; s < nbSuccessors[t]; ++s)
                    successors[t][s] = int.Parse(splitted[s + nbResources + 2]) - 1;
                horizon += duration[t];
            }
        }
    }

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

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

        // Integer decisions: start time of each task
        taskStart = new LSExpression[nbTasks];
        taskEnd = new LSExpression[nbTasks];
        for (int t = 0; t < nbTasks; ++t)
        {
            taskStart[t] = model.Int(0, horizon);
            taskEnd[t] = taskStart[t] + duration[t];
        }

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

        // Makespan: end of the last task
        makespan = model.Max();
        for (int t = 0; t < nbTasks; ++t)
            makespan.AddOperand(taskEnd[t]);

        // Cumulative resource constraints
        for (int r = 0; r < nbResources; ++r)
        {
            LSExpression capacityRespected = model.LambdaFunction(d =>
                {
                    LSExpression totalWeight = model.Sum();
                    for (int t = 0; t < nbTasks; ++t) 
                    {
                        totalWeight.AddOperand(weight[t,r] * model.And(taskStart[t] <= d, taskEnd[t] > d));
                    }
                    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 */
    public void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            Console.WriteLine("Solution written in file " + fileName);
            output.WriteLine(makespan.GetValue());
            for (int t = 0; t < nbTasks; ++t)
            {
                output.Write((t + 1) + " " + taskStart[t].GetValue() + " " + taskEnd[t].GetValue());
                output.WriteLine();
            }
        }
    }

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

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

        using (Rcpsp model = new Rcpsp(instanceFile))
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}