Flexible Resource Constrained Project Scheduling Problem¶

using System;
using System.IO;
using System.Linq;
using localsolver;

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

    // 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
    private int[][] taskProcessingTimeData;

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

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

    // For each task, the selected resource
    private LSExpression[] taskResource;

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

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

    private static string[] ReadNextLine(StreamReader input) {
        return input.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
    }

    private void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] splitted = ReadNextLine(input);
            if (splitted.Length == 0)
                splitted = ReadNextLine(input);
            nbTasks = int.Parse(splitted[0]);
            nbResources = int.Parse(splitted[1]);

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

            taskProcessingTimeData = new int[nbTasks][];
            for (int i = 0; i < nbTasks; i++)
                taskProcessingTimeData[i] = new int[nbResources];

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

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

            nbSuccessors = new int[nbTasks];
            successors = new int[nbTasks][];

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

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

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

        resourcesTasks = new LSExpression[nbResources];

        for (int r = 0; r < nbResources; ++r)
            resourcesTasks[r] = model.Set(nbTasks);

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

        // 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)
                {
                    model.Constraint(model.Contains(resourcesTasks[r], i) == 0);
                }
            }
        }

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

        taskResource = new LSExpression[nbTasks];
        for (int i = 0; i < nbTasks; ++i)
        {
            // For each task, the selected resource
            taskResource[i] = model.Find(resources, i);
        }

        tasks = new LSExpression[nbTasks];
        for (int i = 0; i < nbTasks; ++i)
        {
            // Interval decisions: time range of each task
            tasks[i] = model.Interval(0, horizon);

            // Task duration constraints
            LSExpression iExpr = model.CreateConstant(i);
            LSExpression duration = model.At(taskProcessingTime, iExpr, taskResource[i]);
            model.Constraint(model.Length(tasks[i]) == duration);
        }

        // Create a LocalSolver array to be able to access it with "at" operator
        LSExpression tasksArray = model.Array();
        for (int i = 0; i < nbTasks; ++i)
            tasksArray.AddOperand(tasks[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 taskWeight = model.LambdaFunction(i =>
                    {
                        LSExpression rExpr = model.CreateConstant(r);
                        return model.At(weight, rExpr, i) * model.Contains(tasksArray[i], t);
                    });
                    LSExpression totalWeight = model.Sum(resourcesTasks[r], taskWeight);
                    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 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() + " "
                        + tasks[i].GetIntervalValue().End());
                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[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "60";

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