Batch Scheduling Problem¶

using System;
using System.IO;
using Hexaly.Optimizer;

public class BatchScheduling : IDisposable
{
    // Number of tasks
    private int nbTasks;
    // Number of resources
    private int nbResources;
    // Capacity of each resource
    private int[] capacity;

    // Number of tasks assigned to each resource
    private int[] nbTasksPerResource;
    // Types of tasks assigned to each resource
    private int[][] typesInResources;
    // Tasks assigned to each resource
    private int[][] tasksInResource;
    // Index of task i on resource[i]
    private int[] taskIndexInResource;

    // Type of task i
    private int[] type;
    // Resource required for task i
    private int[] resource;
    // Duration of task i
    private int[] duration;
    // Number of tasks that must succeed task i
    private int[] nbSuccessors;
    // Task names that must succeed task i
    private int[][] successors;

    // Longest possible time horizon
    private int timeHorizon;

    // Hexaly Optimizer
    private HexalyOptimizer optimizer;
    // Decision variables: collection of sets (representing batches)
    private HxExpression[][] batchContent;
    // Decision variables: intervals of batches on a resource
    private HxExpression[][] batchInterval;
    // Decision variables: interval of a task
    private HxExpression[] taskInterval;
    // Objective = minimize the makespan: end of the last task of the last job
    private HxExpression makespan;

    public BatchScheduling(string fileName)
    {
        optimizer = new HexalyOptimizer();
    }
    public static string[] ReadNextLine(StreamReader input) {
        return input.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
    }

    public void ReadInstance(string fileName) 
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] splitted = ReadNextLine(input);

            // first line has number of tasks, number of resources
            nbTasks = int.Parse(splitted[0]);
            nbResources = int.Parse(splitted[1]);

            // second line has the capacity of each resource
            capacity = new int[nbResources];
            splitted = ReadNextLine(input);
            for (int r = 0; r < nbResources; ++r) {
                capacity[r] = int.Parse(splitted[r]);
            }
            // initialize
            type = new int[nbTasks];
            resource = new int[nbTasks];
            duration = new int[nbTasks];
            nbSuccessors = new int[nbTasks];
            successors = new int[nbTasks][];
            taskIndexInResource = new int[nbTasks];
            typesInResources = new int[nbResources][];
            tasksInResource = new int[nbResources][];
            nbTasksPerResource = new int[nbResources];
            for (int j = 0; j < nbResources; ++j)
                nbTasksPerResource[j] = 0;

            // Task information: [type, machine, duration, nbSuccessors, [successors]]
            for (int i = 0; i < nbTasks; ++i) 
            {
                splitted = ReadNextLine(input);

                type[i] = int.Parse(splitted[0]);
                resource[i] = int.Parse(splitted[1]);
                duration[i] = int.Parse(splitted[2]);
                nbSuccessors[i] = int.Parse(splitted[3]);

                // collect which tasks that must succeed task i
                successors[i] = new int[nbSuccessors[i]];
                for (int j = 0; j < nbSuccessors[i]; j++) {
                    successors[i][j] = int.Parse(splitted[4+j]);
                }

                // Index of task i on resource[i]
                taskIndexInResource[i] = nbTasksPerResource[resource[i]];
                // Incremenet number of tasks required by this resource
                nbTasksPerResource[resource[i]] += 1;

                // Add task time to the overall trivial time horizon
                timeHorizon += duration[i];
            }

            // Mapping task list to resource task lists
            int[] temp_nbTasksPerResource = new int[nbResources];
            for (int r = 0; r < nbResources; ++r)
            {
                typesInResources[r] = new int[nbTasksPerResource[r]];
                tasksInResource[r] = new int[nbTasksPerResource[r]];
                temp_nbTasksPerResource[r] = 0;
            }
            for (int i = 0; i < nbTasks; ++i) {
                int r = resource[i];
                int index = temp_nbTasksPerResource[r];
                // Map from name of task i on resource[i] to task i type
                typesInResources[r][index] = type[i];
                // Map from name of task i on resource[i] to task i
                tasksInResource[r][index] = i;

                // increment
                temp_nbTasksPerResource[r] += 1;
            }
        }
    }

    public void Dispose()
    {
        if (optimizer != null)
            optimizer.Dispose();
    }

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

        // For each resource, the contents of each batch of tasks performed
        batchContent = new HxExpression[nbResources][];
        for (int r = 0; r < nbResources; ++r)
        {
            batchContent[r] = new HxExpression[nbTasksPerResource[r]];
            for (int b = 0; b < nbTasksPerResource[r]; ++b)
                batchContent[r][b] = model.Set(nbTasksPerResource[r]);
        }

        // Create HexalyOptimizer arrays in order to be able to access them with "at" operators
        HxExpression[] batchContentArray = new HxExpression[nbResources];
        for (int r = 0; r < nbResources; ++r)
            batchContentArray[r] = model.Array(batchContent[r]);

        // All tasks are assigned to a batch
        for (int r = 0; r < nbResources; ++r)
            model.Constraint( model.Partition(batchContentArray[r]) );

        // Create HexalyOptimizer arrays in order to be able to access them with "at" operators
        HxExpression[] typesInResourcesArray = new HxExpression[nbResources];
        for (int r = 0; r < nbResources; ++r) 
            typesInResourcesArray[r] = model.Array(typesInResources[r]);

        // Each batch must consist of tasks with the same type
        for (int r = 0; r < nbResources; ++r) {
            HxExpression resourceTypeLambda = model.LambdaFunction( i =>
            {
                return typesInResourcesArray[r][i];
            });
            for (int b = 0; b < nbTasksPerResource[r]; ++b)
                model.Constraint(model.Count( 
                    model.Distinct(batchContent[r][b], resourceTypeLambda)) <= 1);
        }

        // Each batch cannot exceed the maximum capacity of the resource
        for (int r = 0; r < nbResources; ++r)
        {
            for (int b = 0; b < nbTasksPerResource[r]; ++b)
                model.Constraint(model.Count(batchContent[r][b]) <= capacity[r]);
        }

        // Interval decisions: time range of each batch of tasks
        batchInterval = new HxExpression[nbResources][];
        for (int r = 0; r < nbResources; ++r)
        {
            batchInterval[r] = new HxExpression[nbTasksPerResource[r]];
            for (int b = 0; b < nbTasksPerResource[r]; ++b)
                batchInterval[r][b] = model.Interval(0, timeHorizon);
        }

        // Create HexalyOptimizer arrays in order to be able to access them with "at" operators
        HxExpression[] batchIntervalArray = new HxExpression[nbResources];
        for (int r = 0; r < nbResources; ++r)
            batchIntervalArray[r] = model.Array(batchInterval[r]);

        // Non-overlap of batch intervals on the same resource
        for (int r = 0; r < nbResources; ++r)
        {
            for (int b = 1; b < nbTasksPerResource[r]; ++b)
                model.Constraint(batchInterval[r][b-1] < batchInterval[r][b]);
        }

        // Interval decisions: time range of each task
        taskInterval = new HxExpression[nbTasks];
        for (int t = 0; t < nbTasks; ++t) {
            // Retrieve the batch index and resource for this task
            int r = resource[t];
            HxExpression b = model.Find(batchContentArray[r], taskIndexInResource[t]);
            // Task interval associated with task t
            taskInterval[t] = batchIntervalArray[r][b];
        }

        // Task durations
        for (int t = 0; t < nbTasks; ++t)
            model.Constraint(model.Length(taskInterval[t]) == duration[t]);

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

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

        // Parameterize the optimizer
        optimizer.GetParam().SetTimeLimit(timeLimit);

        optimizer.Solve();
    }

    /* Write the solution in a file with the following format:
     *  - makespan
     *  - machine number
     *  - preceeding lines are the ordered intervals of the tasks 
          for the corresponding machine number */
    public void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            Console.WriteLine("Solution written in file " + fileName);
            output.WriteLine(makespan.GetValue());
            for (int r = 0; r < nbResources; ++r)
            {
                output.Write(r);
                output.WriteLine();
                for (int b = 0; b < nbTasksPerResource[r]; ++b)
                {
                    int t = tasksInResource[r][b];
                    long start = taskInterval[t].GetIntervalValue().Start();
                    long end = taskInterval[t].GetIntervalValue().End();
                    output.Write(t + " " + start + " " + end);
                    output.WriteLine();
                }
            }
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: batching_scheduling.cs 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 (BatchScheduling model = new BatchScheduling(instanceFile))
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}