Surgeries scheduling¶

using System;
using System.IO;
using System.Linq;
using Hexaly.Optimizer;
using System.Collections.Generic;

public class SurgeriesScheduling : IDisposable
{
    // Number of surgeries
    private int numSurgeries;
    // Number of rooms
    private int numRooms;
    // Number of nurses
    private int numNurses;
    // Minimum start of each surgery
    private int[] minStart;
    // Maximum end of each surgery
    private int[] maxEnd;
    // Duration of each surgery
    private int[] duration;
    // Number of nurses needed for each surgery
    private int [] neededNurses;
    // Earliest starting shift for each nurse
    private int [] shiftEarliestStart;
    // Latest ending shift for each nurse
    private int [] shiftLatestEnd;
    // Maximum duration of each nurse's shift
    private int maxShiftDuration;
    // Incompatible rooms for each surgery
    private int[][] incompatibleRooms;

    // Hexaly Optimizer
    private HexalyOptimizer optimizer;

    // Decision variables: time range of each surgery
    private HxExpression[] surgeries;

    // Decision variables: sequence of surgery on each room
    private HxExpression[] surgeryOrder;

    // For each surgery, the selected room
    // This variable is only used to export the solution
    private HxExpression[] selectedRoom;

    // Decision variables: the surgeries order of each nurse
    private HxExpression[] nurseOrder;

    // Objective = minimize the makespan: end of the last surgery
    private HxExpression makespan;

    public SurgeriesScheduling()
    {
        optimizer = new HexalyOptimizer();
    }

    public void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            char[] separators = new char[] { '\t', ' ' };
            string[] splitted = input
                .ReadLine()
                .Split(separators, StringSplitOptions.RemoveEmptyEntries);
            numRooms = int.Parse(splitted[0]);
            numNurses = int.Parse(splitted[1]);
            numSurgeries = int.Parse(splitted[2]);

            minStart = new int[numSurgeries];
            splitted = input
                .ReadLine()
                .Split(separators, StringSplitOptions.RemoveEmptyEntries);
            for (int s = 0; s < numSurgeries; ++s)
            {
                minStart[s] = int.Parse(splitted[s]) * 60;
            }

            maxEnd = new int[numSurgeries];
            splitted = input
                .ReadLine()
                .Split(separators, StringSplitOptions.RemoveEmptyEntries);
            for (int s = 0; s < numSurgeries; ++s)
            {
                maxEnd[s] = int.Parse(splitted[s]) * 60;
            }

            duration = new int[numSurgeries];
            splitted = input
                .ReadLine()
                .Split(separators, StringSplitOptions.RemoveEmptyEntries);
            for (int s = 0; s < numSurgeries; ++s)
            {
                duration[s] = int.Parse(splitted[s]);
            }

            neededNurses = new int[numSurgeries];
            splitted = input
                .ReadLine()
                .Split(separators, StringSplitOptions.RemoveEmptyEntries);
            for (int s = 0; s < numSurgeries; ++s)
            {
                neededNurses[s] = int.Parse(splitted[s]);
            }

            shiftEarliestStart = new int[numNurses];
            splitted = input
                .ReadLine()
                .Split(separators, StringSplitOptions.RemoveEmptyEntries);
            for (int n = 0; n < numNurses; ++n)
            {
                shiftEarliestStart[n] = int.Parse(splitted[n]) * 60;
            }

            shiftLatestEnd = new int[numNurses];
            splitted = input
                .ReadLine()
                .Split(separators, StringSplitOptions.RemoveEmptyEntries);
            for (int n = 0; n < numNurses; ++n)
            {
                shiftLatestEnd[n] = int.Parse(splitted[n]) * 60;
            }

            splitted = input
                .ReadLine()
                .Split(separators, StringSplitOptions.RemoveEmptyEntries);
            
            maxShiftDuration = int.Parse(splitted[0]) * 60;

            incompatibleRooms = new int[numSurgeries][];
            for (int s = 0; s < numSurgeries; ++s) 
            {
                splitted = input
                    .ReadLine()
                    .Split(separators, StringSplitOptions.RemoveEmptyEntries);
                incompatibleRooms[s] = new int[numRooms];
                for (int r = 0; r < numRooms; ++r) 
                {
                    incompatibleRooms[s][r] = int.Parse(splitted[r]);
                }
            } 
        }
    }

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

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

        // Sequence of surgery for each room
        surgeryOrder = new HxExpression[numRooms];
        HxExpression room = model.Array();
        for (int r = 0; r < numRooms; ++r)
        {
            surgeryOrder[r] = model.List(numSurgeries);
            room.AddOperand(surgeryOrder[r]);
        }

        // Each surgery is scheduled in a room
        model.Constraint(model.Partition(room));

        // Only compatible rooms can be selected for a surgery
        for (int s = 0; s < numSurgeries; ++s)
        {
            foreach (int r in incompatibleRooms[s]) 
            {
                model.Constraint(model.Contains(surgeryOrder[r], s) == 0);
            }
        }

        // For each surgery, the selected room
        selectedRoom = new HxExpression[numSurgeries];
        for (int s = 0; s < numSurgeries; ++s)
        {
            selectedRoom[s] = model.Find(room, s);
        }

        // Interval decisions: time range of each surgery
        surgeries = new HxExpression[numSurgeries];
        for (int s = 0; s < numSurgeries; ++s)
        {
            // Each surgery cannot start before and end after a certain time
            surgeries[s] = model.Interval(minStart[s], maxEnd[s]);

            // Each surgery has a specific duration
            model.Constraint(model.Length(surgeries[s]) == duration[s]);
        }
        HxExpression surgeryArray = model.Array(surgeries);

        // A room can only have one surgery at a time
        for (int r = 0; r < numRooms; ++r)
        {
            HxExpression sequence = surgeryOrder[r];
            HxExpression sequenceLambda = model.LambdaFunction(
                s => surgeryArray[sequence[s]] < surgeryArray[sequence[s + 1]]
            );
            model.Constraint(model.And(model.Range(0, model.Count(sequence) - 1), sequenceLambda));
        }

        // Sequence of surgery for each nurse
        nurseOrder = new HxExpression[numNurses];

        for (int n = 0; n < numNurses; ++n)
        {
            nurseOrder[n] = model.List(numSurgeries);
            HxExpression sequence = nurseOrder[n];
            HxExpression firstSurgeryStart = model.If(
                model.Count(sequence) > 0, 
                model.Start(surgeryArray[sequence[0]]),
                shiftEarliestStart[n]);
            HxExpression lastSurgeryEnd = model.If(
                model.Count(sequence) > 0, 
                model.End(surgeryArray[sequence[model.Count(sequence)-1]]),
                shiftEarliestStart[n]);
            // Each nurse has an earliest starting shift and latest ending shift to be respected
            model.Constraint(firstSurgeryStart >= shiftEarliestStart[n]);
            model.Constraint(lastSurgeryEnd <= shiftLatestEnd[n]);
            // Each nurse cannot work more than a certain amount of hours in a row
            model.Constraint(lastSurgeryEnd - firstSurgeryStart <= maxShiftDuration);
            // Each nurse can only be at one operation at a time and stays all along the surgery
            HxExpression sequenceLambda = model.LambdaFunction(
                s => surgeryArray[sequence[s]] < surgeryArray[sequence[s + 1]]
            );
            model.Constraint(model.And(model.Range(0, model.Count(sequence) - 1), sequenceLambda));
        }

        HxExpression nurseOrderArray = model.Array(nurseOrder);

        // Each surgery needs a specific amount of nurse
        for (int s = 0; s < numSurgeries; ++s)
        {
            model.Constraint(model.Sum(model.Range(0, numNurses), model.LambdaFunction(
                n => model.Contains(nurseOrderArray[n], s))) >= neededNurses[s]);
        }

        // Minimize the makespan: end of the last surgery
        makespan = model.Max();
        for (int s = 0; s < numSurgeries; ++s)
        {
            makespan.AddOperand(model.End(surgeries[s]));
        }
        model.Minimize(makespan);

        model.Close();

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

        optimizer.Solve();
    }

    /* Write the solution in a file with the following format:
     *  - for each surgery, the selected room, the start and end dates 
          the nurses working on this operation*/
    public void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            Console.WriteLine("Solution written in file " + fileName);
            List<List<int>> listNurses = new List<List<int>>();
            for (int s = 0; s < numSurgeries; ++s)
            {
                listNurses.Add(new List<int>());
            }
            for (int n = 0; n < numNurses; ++n)
            {
                HxCollection surgNurse = nurseOrder[n].GetCollectionValue();
                foreach (int s in surgNurse) 
                {
                    listNurses[s].Add(n);
                }
            }
            for (int s = 0; s < numSurgeries; ++s)
            {
                string nurseListString = "[" + string.Join(", ", listNurses[s]) + "]";
                output.WriteLine(
                    s
                        + "\t"
                        + selectedRoom[s].GetValue() 
                        + "\t"
                        + surgeries[s].GetIntervalValue().Start()
                        + "\t"
                        + surgeries[s].GetIntervalValue().End()
                        + "\t"
                        + nurseListString
                );
            }
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: SurgeriesScheduling 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] : "20";

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