Preemptive Resource Constrained Project Scheduling Problem¶

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