Workforce Shift Scheduling Problem

import hexaly.optimizer
import sys

# Activity class represents a work item with its scheduling constraints
#   - id: Unique identifier for the task
#   - min_start: minimum possible start time (in seconds)
#   - max_end: maximum possible end time (in seconds)
#   - duration: Duration of the task (in seconds)
class Activity:
    def __init__(self, id, min_start, max_end, duration):
        self.id = id #int
        self.min_start = min_start #int
        self.max_end = max_end #int
        self.duration = duration #int

# Agent class represents an employee with their availability window
#   - id: Unique identifier for the agent
#   - availability_start: Start of availability period (in seconds)
#   - availability_end: End of availability period (in seconds)
class Agent:
    def __init__(self, id, av_start, av_end):
        self.id = id #int
        self.availability_start = av_start #int
        self.availability_end = av_end #int

# Shift class represents a work item with its scheduling constraints
#   - id: Unique identifier for the shift
#   - activity_id: ID of the activity performed
#   - shift_start: Start time of the shift (in seconds)
#   - shift_end: End time of the shift (in seconds)
class Shift:
    def __init__(self, id, activity_id, shift_start, shift_end):
        self.id = id #int
        self.activity_id = activity_id #int
        self.shift_start = shift_start #int
        self.shift_end = shift_end #int


#  Generates all possible shifts for activities with given time increment
#  @param activities Array of Activity objects
#  @param shift_increment Time increment in seconds
#  @return Array of generated Shift objects
def generateShifts(activities, shift_increment):
    i = 0
    shifts = []
    for a in activities:
        current_time = a.min_start
        while current_time + a.duration <= a.max_end:
            shifts.append(Shift(i, a.id, current_time, current_time + a.duration))
            i += 1
            current_time += shift_increment
    return shifts


# Checks if two shifts are compatible
#   @param slot1 First shift
#   @param slot2 Second shift
#   @return true if shifts overlap, false otherwise
def incompatibleShifts(shift1, shift2):
    startShift1 = shift1.shift_start
    endShift1 = shift1.shift_end
    startShift2 = shift2.shift_start
    endShift2 = shift2.shift_end
    return not (startShift1 >= endShift2 or endShift1 <= startShift2)


# Checks if there is at least a one-hour break between two shifts
#   @param slot1 First shift
#   @param slot2 Second shift
#   @return true if there is not enough break, false otherwise
def notEnoughBreak(shift1, shift2):
    startShift1 = shift1.shift_start
    endShift1 = shift1.shift_end
    startShift2 = shift2.shift_start
    endShift2 = shift2.shift_end
    return not (startShift1 >= endShift2 + 3600 or endShift1 + 3600 <= startShift2)


# Checks if two time intervals overlap
#   @param interval1Start Start of first interval
#   @param interval1End End of first interval
#   @param interval2Start Start of second interval
#   @param interval2End End of second interval
#   @return true if intervals overlap, false otherwise
def overlappingIntervals(int1_start, int1_end, int2_start, int2_end):
    return not (int1_start >= int2_end or int1_end <= int2_start)


if len(sys.argv) < 2:
    print("Usage: python tsp.py inputFile [outputFile] [timeLimit]")
    sys.exit(1)

# Filters out comments from a text file
#   @param filename Path to input file
def read_elem(filename):
    with open(filename) as f:
        lines = f.readlines()
        result = []
        for line in lines:
            line = line.split("#")[
                0
            ].strip()  # Split at '#' and take the part before it
            if line:  # Only add non-empty lines
                result.extend(
                    line.split()
                )  # Split the line into elements and add them to the result
    return result


# Validates the instance data for consistency
def validateInstance():
    # Check if all activities can be completed within their time windows
    for activity in activities:
        if activity.duration > (activity.max_end - activity.min_start):
            raise ValueError(
                "Activity "
                + activity.id
                + " duration ("
                + (activity.duration / 3600)
                + "h) exceeds its time window"
            )

    # Check if workers' availability windows are valid
    for agent in agents:
        if agent.availability_start >= agent.availability_end:
            raise ValueError("Agent " + agent.id + " has invalid availability window")

    # Check if activities can be performed within workers' availability
    earliest_start = min([act.min_start for act in activities])
    latest_end = max([act.max_end for act in activities])

    for agent in agents:
        if (
            agent.availability_start > earliest_start
            or agent.availability_end < latest_end
        ):
            print(
                "Warning: Agent "
                + str(agent.id)
                + " availability might not cover all tasks"
            )


with hexaly.optimizer.HexalyOptimizer() as optimizer:
    #
    # Read path of input file
    #
    file_it = iter(read_elem(sys.argv[1]))

    # Read dimensions of the problem
    nb_agents = int(next(file_it))
    nb_activities = int(next(file_it))
    time_horizon = int(next(file_it))
    shift_increment = round(float(next(file_it)) * 60)

    # Read activities informations
    # Duration time of each activity
    activities = []
    for i in range(nb_activities):
        activities.append(Activity(i, 0, 0, int(next(file_it)) * 3600))
    # Maximum end and minimum possible start hour of each activity
    for i in range(nb_activities):
        activities[i].min_start = int(next(file_it)) * 3600
        activities[i].max_end = int(next(file_it)) * 3600

    # Read agents informations
    # Availability period in the day of each agent
    agents = [
        Agent(i, int(next(file_it)), int(next(file_it))) for i in range(nb_agents)
    ]

    # Generation of all possible shifts for each activity with a given increment
    shifts = generateShifts(activities, shift_increment)

    # Validates the instance data
    validateInstance()

    #
    # Declare the optimization model
    #
    model = optimizer.model

    # Decision variables : agent_shift[a][s] is true when the agent a works the shift s
    agent_shift = [[model.bool() for j in range(len(shifts))] for i in range(nb_agents)]

    # Constraints
    # 1. The shifts performed by an agent must not overlap
    for a in range(nb_agents):
        for s1 in shifts:
            for s2 in shifts:
                if incompatibleShifts(s1, s2) and s1 != s2:
                    model.constraint(agent_shift[a][s1.id] + agent_shift[a][s2.id] <= 1)

    # 2. An agent must take at least a one-hour break between two shifts
    for a in range(nb_agents):
        for s1 in shifts:
            for s2 in shifts:
                if notEnoughBreak(s1, s2) and s1 != s2:
                    model.constraint(agent_shift[a][s1.id] + agent_shift[a][s2.id] <= 1)

    # 3. Each agent must work exactly two shifts in the day
    for a in range(nb_agents):
        model.constraint(sum([agent_shift[a][s.id] for s in shifts]) == 2)

    # Objective 1 :  Minimize understaffing
    # For each activity and at each interval of time of the increment length
    total_understaffing = 0
    for activity in activities:
        current_time = activity.min_start
        while current_time < activity.max_end:
            # Current interval of time
            current_interval_start = current_time
            current_interval_end = current_time + shift_increment
            # The activity will not be pursued after its maximum possible end
            if current_interval_end > activity.max_end:
                current_interval_end = activity.max_end
            # Shifts performed in the current time interval
            shifts_at_current = []
            for shift in shifts:
                if shift.activity_id != activity.id:
                    continue
                if overlappingIntervals(
                    current_interval_start,
                    current_interval_end,
                    shift.shift_start,
                    shift.shift_end,
                ):
                    shifts_at_current.append(shift)
            # Number of agents currently performing the task
            total_agents_working = 0
            for shift in shifts_at_current:
                agents_working = sum(
                    [agent_shift[a][shift.id] for a in range(nb_agents)]
                )
                total_agents_working += agents_working
            # Number of agents missing
            total_understaffing += model.max(0, 1 - total_agents_working)
            current_time += shift_increment
    total_understaffing *= shift_increment
    model.minimize(total_understaffing)

    # Objective 2 : Minimize the total worktime of all the agents
    total_working_time = 0
    for a in range(nb_agents):
        total_working_time += sum(
            [agent_shift[a][s.id] * activities[s.activity_id].duration for s in shifts]
        )
    model.minimize(total_working_time)
    model.close()

    # Parameterize the optimizer
    if len(sys.argv) >= 4:
        optimizer.param.time_limit = int(sys.argv[3])
        optimizer.param.verbosity = 2
    else:
        optimizer.param.time_limit = 5
    optimizer.solve()

#include "optimizer/hexalyoptimizer.h"
#include <algorithm>
#include <fstream>
#include <iostream>
#include <set>
#include <string.h>
#include <vector>

using namespace hexaly;
using namespace std;

/**
 * Activity class represents a work item with its scheduling constraints
 * - id: Unique identifier for the activity
 * - minStart: minimum possible start time (in seconds)
 * - maxEnd: maximum possible end time (in seconds)
 * - duration: Duration of the activity (in seconds)
 */
class Activity {
  public:
    int id;
    int minStart;
    int maxEnd;
    int duration;

    Activity(int ID, int minS, int max, int d) {
        id = ID;
        minStart = minS;
        maxEnd = maxEnd;
        duration = d;
    }
};

/**
 * Agent class represents an employee with their availability window
 * - id: Unique identifier for the agent
 * - availabilityStart: Start of availability period (in seconds)
 * - availabilityEnd: End of availability period (in seconds)
 */
class Agent {
  public:
    int id;                // int
    int availabilityStart; // int
    int availabilityEnd;   // int

    Agent(int ID, int avStart, int avEnd) {
        id = ID;
        availabilityStart = avStart;
        availabilityEnd = avEnd;
    }
};

/**
 * Shift class represents a scheduled work period for an activity
 * - id: Unique identifier for the shift
 * - activityId: ID of the activity performed
 * - shiftStart: Start time of the shift (in seconds)
 * - shiftEnd: End time of the shift (in seconds)
 */
class Shift {
  public:
    int id;         // int
    int activityId; // int
    int shiftStart; // int
    int shiftEnd;   // int

    Shift(int ID, int actId, int shiftS, int shiftE) {
        id = ID;
        activityId = actId;
        shiftStart = shiftS;
        shiftEnd = shiftE;
    }
};

/**
 * Generates all possible shifts for activities with given time increment
 * @param activities Array of Activity objects
 * @param shiftIncrement Time increment in seconds
 * @return Array of generated Shift objects
 */
void generateShifts(vector<Shift> &shifts, vector<Activity> activities, int shiftIncrement) {
    int i = 0;
    for (int j = 0; j < activities.size(); j++) {
        int currentTime = activities[j].minStart;
        while (currentTime + activities[j].duration <= activities[j].maxEnd) {
            Shift s = Shift(i, activities[j].id, currentTime, currentTime + activities[j].duration);
            shifts.push_back(s);
            currentTime += shiftIncrement;
            i += 1;
        }
    }
};

/**
 * Checks if two  shifts are compatible
 * @param shif1 First shift
 * @param shift2 Second shift
 * @return true if shifts overlap, false otherwise
 */
bool incompatibleShifts(Shift shift1, Shift shift2) {
    int startShift1 = shift1.shiftStart;
    int endShift1 = shift1.shiftEnd;
    int startShift2 = shift2.shiftStart;
    int endShift2 = shift2.shiftEnd;
    int actId1 = shift1.activityId;
    int actId2 = shift2.activityId;
    return !(startShift1 >= endShift2 || endShift1 <= startShift2);
};

/**
 * Checks if there is at least a one-hour break between two shifts
 * @param shift1 First shift
 * @param shift2 Second shift
 * @return true if there is not enough break, false otherwise
 */
bool notEnoughBreak(Shift shift1, Shift shift2) {
    int startShift1 = shift1.shiftStart;
    int endShift1 = shift1.shiftEnd;
    int startShift2 = shift2.shiftStart;
    int endShift2 = shift2.shiftEnd;
    int actId1 = shift1.activityId;
    int actId2 = shift2.activityId;
    return !(startShift1 >= endShift2 + 3600 || endShift1 + 3600 <= startShift2);
};

/**
 * Checks if two time intervals overlap
 * @param interval1Start Start of first interval
 * @param interval1End End of first interval
 * @param interval2Start Start of second interval
 * @param interval2End End of second interval
 * @return true if intervals overlap, false otherwise
 */
bool overlappingIntervals(int int1Start, int int1End, int int2Start, int int2End) {
    return !(int1Start >= int2End || int1End <= int2Start);
};

class WorkshopSchedulingShifts {
  private:
    // Number of agents
    int nbAgents;
    // Number of activities
    int nbActivities;
    // Number of days
    int timeHorizon;
    // Increment
    int shiftIncrement;

    // Activities informations
    vector<Activity> activities;
    // Agents informations
    vector<Agent> agents;
    // Possible shifts
    vector<Shift> shifts;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;
    // Decision variables: time range of each task
    vector<vector<HxExpression>> agentShift;
    // Objective = minimize the missing agent time and total working time of the agents
    HxExpression totalUnderstaffing;
    HxExpression totalWorkingTime;

  public:
    // The input files follow the "Taillard" format
    void readInstance(const string &fileName) {
        ifstream infile;
        if (!infile) {
            cerr << "Unable to open file: " << fileName << endl;
        }
        infile.open(fileName.c_str());

        std::string line;
        std::vector<std::string> elements;

        while (std::getline(infile, line)) {
            std::istringstream iss(line);
            std::string elem;
            while (iss >> elem) {
                if (elem[0] == '#')
                    break; // Ignore the rest of the line if a comment is found
                elements.push_back(elem);
            }
        }

        // Read problem dimensions
        auto it = elements.begin();
        nbAgents = std::stoi(*it++);
        nbActivities = std::stoi(*it++);
        timeHorizon = std::stoi(*it++);
        shiftIncrement = std::stof(*it++) * 3600;
        infile.ignore(numeric_limits<streamsize>::max(), '\n');

        // Read activities informations
        // Duration time of each activity
        for (int i = 0; i < nbActivities; i++) {
            int activityDuration;
            activityDuration = stoi(*it++);
            activities.push_back(Activity(i, 0, 0, activityDuration * 3600));
        }
        // Maximum end and minimum possible start hour of each activity
        for (int i = 0; i < nbActivities; i++) {
            int minStart = std::stoi(*it++);
            int maxEnd = std::stoi(*it++);
            activities[i].minStart = minStart * 3600;
            activities[i].maxEnd = maxEnd * 3600;
        }

        // Read agents informations
        for (int i = 0; i < nbAgents; i++) {
            int availabilityStart = std::stoi(*it++);
            int availabilityEnd = std::stoi(*it++);
            infile >> availabilityStart >> availabilityEnd;
            agents.push_back(Agent(i, availabilityStart * 3600, availabilityEnd * 3600));
        }
        // Generation of all possible shifts for each activity with a given increment
        generateShifts(shifts, activities, shiftIncrement);

        // Validates the instance data
        validateInstance();
        infile.close();
    }

    /**
     * Validates the instance data for consistency
     */
    void validateInstance() {
        // Check if all activities can be completed within their time windows
        for (Activity activity : activities) {
            if (activity.duration > (activity.maxEnd - activity.minStart)) {
                throw("Activity " + to_string(activity.id) + " duration (" + to_string(activity.duration / 3600) +
                      "h) exceeds its time window");
            }
        }

        // Check if workers' availability windows are valid
        for (Agent agent : agents) {
            if (agent.availabilityStart >= agent.availabilityEnd) {
                throw("Agent " + to_string(agent.id) + " has invalid availability window");
            }
        }

        // Check if activities can be performed within workers' availability
        auto earliestStartIt =
            std::min_element(activities.begin(), activities.end(),
                             [](const Activity &a, const Activity &b) { return a.minStart < b.minStart; });
        auto latestEndIt =
            std::max_element(activities.begin(), activities.end(),
                             [](const Activity &a, const Activity &b) { return a.minStart < b.minStart; });
        int earliestStart = earliestStartIt->minStart;
        int latestEnd = latestEndIt->maxEnd;

        for (Agent agent : agents) {
            if (agent.availabilityStart > earliestStart || agent.availabilityEnd < latestEnd) {
                cout << "Warning: Agent " << agent.id << " availability might not cover all tasks" << endl;
            }
        }
    }

    void solve(int timeLimit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        // Decision variables : AgentShift[a][s] is true when the agent a works the shift s
        agentShift.resize(nbAgents);
        for (unsigned int i = 0; i < nbAgents; i++) {
            agentShift[i].resize(shifts.size());
            for (unsigned int j = 0; j < shifts.size(); j++) {
                agentShift[i][j] = model.boolVar();
            }
        }
        // Constraints
        // 1. The shifts performed by an agent must not overlap
        for (int a = 0; a < nbAgents; a++) {
            for (auto s1 = shifts.begin(); s1 != shifts.end(); s1++) {
                for (auto s2 = shifts.begin(); s2 != shifts.end(); s2++) {
                    if (incompatibleShifts(*s1, *s2) && s1 != s2) {
                        model.constraint(agentShift[a][s1->id] + agentShift[a][s2->id] <= 1);
                    }
                }
            }
        }

        // 2. An agent must take at least a one-hour break between two shifts
        for (int a = 0; a < nbAgents; a++) {
            for (auto s1 = shifts.begin(); s1 != shifts.end(); s1++) {
                for (auto s2 = shifts.begin(); s2 != shifts.end(); s2++) {
                    if (notEnoughBreak(*s1, *s2) && s1 != s2) {
                        model.constraint(agentShift[a][s1->id] + agentShift[a][s2->id] <= 1);
                    }
                }
            }
        }

        // 3. Each agent must work exactly two shifts in the day
        for (int a = 0; a < nbAgents; a++) {
            HxExpression shiftsDone = model.sum();
            for (int id = 0; id < shifts.size(); id++) {
                shiftsDone.addOperand(agentShift[a][id]);
            }
            model.constraint(shiftsDone == 2);
        }

        // Objective 1 : Minimize understaffing
        HxExpression totalUnderstaffing = model.sum();
        for (auto activity = activities.begin(); activity != activities.end(); activity++) {
            int currentTime = activity->minStart;
            while (currentTime < activity->maxEnd) {
                // Current interval of time
                int currentIntervalStart = currentTime;
                int currentIntervalEnd = currentTime + shiftIncrement;
                // The activity will not be pursued after its maximum possible end
                if (currentIntervalEnd > activity->maxEnd) {
                    currentIntervalEnd = activity->maxEnd;
                }
                // Shifts performed in the current time interval
                vector<Shift> shiftsAtCurr;
                for (auto shift = shifts.begin(); shift != shifts.end(); shift++) {
                    if (shift->activityId != activity->id) {
                        continue;
                    }
                    if (overlappingIntervals(currentIntervalStart, currentIntervalEnd, shift->shiftStart,
                                             shift->shiftEnd)) {
                        shiftsAtCurr.push_back(*shift);
                    }
                }
                // Number of agents currently performing the task
                HxExpression totalAgentsWorking = model.sum();
                for (auto shift = shiftsAtCurr.begin(); shift != shiftsAtCurr.end(); shift++) {
                    for (int a = 0; a < nbAgents; a++) {
                        totalAgentsWorking.addOperand(agentShift[a][shift->id]);
                    }
                }
                // Number of agents missing
                totalUnderstaffing.addOperand(shiftIncrement * model.max(0, 1 - totalAgentsWorking));
                currentTime += shiftIncrement;
            }
        }
        model.minimize(totalUnderstaffing);

        // Objective 2 : Minimize the total worktime of all the agents
        HxExpression totalWorkingTime = model.sum();
        for (int a = 0; a < nbAgents; a++) {
            for (auto shift = shifts.begin(); shift != shifts.end(); shift++) {
                totalWorkingTime.addOperand(agentShift[a][shift->id] * activities[shift->activityId].duration);
            }
        }
        model.minimize(totalWorkingTime);
        model.close();

        // Parametrize the optimizer
        optimizer.getParam().setTimeLimit(10);
        optimizer.solve();
    }
};

int main(int argc, char **argv) {
    if (argc < 2) {
        cerr << "Usage: workforce_scheduling_shifts inputFile [outputFile] [timeLimit]" << endl;
        return 1;
    }
    const char *instanceFile = argv[1];
    const char *strTimeLimit = argc > 2 ? argv[2] : "5";
    try {
        WorkshopSchedulingShifts model;
        model.readInstance(instanceFile);
        model.solve(atoi(strTimeLimit));
    } catch (const exception &e) {
        cerr << "An error occurred: " << e.what() << endl;
        return 1;
    }
};

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

/**
 * Activity class represents a work item with its scheduling constraints
 * - id: Unique identifier for the activity
 * - minStart: minimum possible start time (in seconds)
 * - maxEnd: maximum possible end time (in seconds)
 * - duration: Duration of the activity (in seconds)
 */
class Activity
{
    public int activityId;
    public int actMinStart;
    public int actMaxEnd;
    public int actDuration;

    public Activity(int actId, int actMinStart, int actMaxEnd, int actDuration)
    {
        this.activityId = actId;
        this.actMinStart = actMinStart;
        this.actMaxEnd = actMaxEnd;
        this.actDuration = actDuration;
    }
}

/**
 * Agent class represents an employee with their availability window
 * - id: Unique identifier for the agent
 * - availabilityStart: Start of availability period (in seconds)
 * - availabilityEnd: End of availability period (in seconds)
 */
class Agent
{
    public int agentId;
    public int availabilityStart;
    public int availabilityEnd;

    public Agent(int agentId, int avStart, int avEnd)
    {
        this.agentId = agentId;
        this.availabilityStart = avStart;
        this.availabilityEnd = avEnd;
    }
}

/**
 * Shift class represents a scheduled work period for an activity
 * - id: Unique identifier for the shift
 * - activityId: ID of the activity performed
 * - shiftStart: Start time of the shift (in seconds)
 * - shiftEnd: End time of the shift (in seconds)
 */
public class Shift
{
    public int shiftId;
    public int shiftActivity;
    public int shiftStart;
    public int shiftEnd;

    public Shift(int id, int actId, int start, int end)
    {
        this.shiftId = id;
        this.shiftActivity = actId;
        this.shiftStart = start;
        this.shiftEnd = end;
    }
}

public class WorkforceSchedulingShifts : IDisposable
{
    // Dimensions of the problem
    int nbAgents;
    int nbActivities;
    int timeHorizon;
    int shiftIncrement;

    // Activities
    Activity[] activities;

    // Agents
    Agent[] agents;

    // Shifts
    int nbShifts;
    Shift[] shifts;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    HxExpression[,] agentShift;

    // Objectives
    HxExpression totalUnderstaffing;
    HxExpression totalWorkingTime;

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

    private void Solve(int limit)
    {

        // Declare the optimization model
        HxModel model = optimizer.GetModel();
        // Decision variables : agentShift[a, s] is true when the agent a works the shift s
        agentShift = new HxExpression[nbAgents, nbShifts];
        for (int i = 0; i < nbAgents; i++)
        {
            for (int j = 0; j < nbShifts; j++)
            {
                agentShift[i, j] = model.Bool();
            }
        }

        // Constraints
        // 1. The shifts performed by an agent must not overlap
        for (int a = 0; a < nbAgents; a++)
        {
            for (int s1 = 0; s1 < nbShifts; s1++)
            {
                for (int s2 = 0; s2 < nbShifts; s2++)
                {
                    if (OverlappingShifts(shifts[s1], shifts[s2]) && s1 != s2)
                    {
                        model.Constraint(model.Leq(model.Sum(agentShift[a, s1], agentShift[a, s2]), 1));
                    }
                }
            }
        }

        // 2. An agent must take at least a one-hour break between two shifts
        for (int a = 0; a < nbAgents; a++)
        {
            for (int s1 = 0; s1 < nbShifts; s1++)
            {
                for (int s2 = 0; s2 < nbShifts; s2++)
                {
                    if (NotEnoughBreak(shifts[s1], shifts[s2]) && s1 != s2)
                    {
                        model.Constraint(model.Leq(model.Sum(agentShift[a, s1], agentShift[a, s2]), 1));
                    }
                }
            }
        }

        // 3. Each agent must work exactly two shifts in the day
        for (int a = 0; a < nbAgents; a++)
        {
            HxExpression shiftsDone = model.Sum();
            for (int id = 0; id < nbShifts; id++)
            {
                shiftsDone.AddOperand(agentShift[a, id]);
            }
            model.Constraint(model.Eq(shiftsDone, 2));
        }

        // Objective 1 : Minimize understaffing
        HxExpression totalUnderstaffing = model.Sum();
        for (int i = 0; i < nbActivities; i++)
        {
            int currentTime = activities[i].actMinStart;
            while (currentTime < activities[i].actMaxEnd)
            {
                // Current interval of time
                int currentIntervalStart = currentTime;
                int currentIntervalEnd = currentTime + shiftIncrement;
                // The activity will not be pursued after its maximum possible end 
                if (currentIntervalEnd > activities[i].actMaxEnd)
                {
                    currentIntervalEnd = activities[i].actMaxEnd;
                }
                // Shifts performed in the current time interval 
                HxExpression totalAgentsWorking = model.Sum();
                for (int j = 0; j < nbShifts; j++)
                {
                    if (shifts[j].shiftActivity != i)
                    {
                        continue;
                    }
                    if (OverlappingIntervals(currentIntervalStart, currentIntervalEnd, shifts[j].shiftStart, shifts[j].shiftEnd))
                    {
                        for (int a = 0; a < nbAgents; a++)
                        {
                            totalAgentsWorking.AddOperand(agentShift[a, j]);
                        }
                    }
                }
                // Number of agents missing
                totalUnderstaffing.AddOperand(model.Prod(shiftIncrement, model.Max(0, model.Sub(1, totalAgentsWorking))));
                currentTime += shiftIncrement;
            }
        }
        model.Minimize(totalUnderstaffing);

        // Objective 2 : Minimize the total worktime of all the agents
        HxExpression totalWorkingTime = model.Sum();
        for (int a = 0; a < nbAgents; a++)
        {
            for (int s = 0; s < nbShifts; s++)
            {
                totalWorkingTime.AddOperand(model.Prod(agentShift[a, s], activities[shifts[s].shiftActivity].actDuration));
            }
        }
        model.Minimize(totalWorkingTime);
        model.Close();

        // Parametrize the optimizer
        optimizer.GetParam().SetTimeLimit(10);
        optimizer.Solve();
    }

    /**
    * Reads and parses input data from file
    * @param fileName Path to input file
    */
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] splitted;
            // Read problem dimensions
            nbAgents = int.Parse(ReadLineIgnoringComments(input));
            nbActivities = int.Parse(ReadLineIgnoringComments(input));
            timeHorizon = int.Parse(ReadLineIgnoringComments(input));
            shiftIncrement = (int)(double.Parse(ReadLineIgnoringComments(input), CultureInfo.InvariantCulture) * 3600);

            // Read activities informations
            // Activity duration
            activities = new Activity[nbActivities];
            for (int i = 0; i < nbActivities; i++)
            {
                activities[i] = new Activity(0, 0, 0, int.Parse(ReadLineIgnoringComments(input)) * 3600);
            }
            // Possible period to do the activity
            for (int i = 0; i < nbActivities; i++)
            {
                splitted = ReadLineIgnoringComments(input).Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                activities[i].actMinStart = int.Parse(splitted[0]) * 3600;
                activities[i].actMaxEnd = int.Parse(splitted[1]) * 3600;
            }

            //Read agents information
            agents = new Agent[nbAgents];
            // Availability period in the day of each agent
            for (int i = 0; i < nbAgents; i++)
            {
                splitted = ReadLineIgnoringComments(input).Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                agents[i] = new Agent(i, int.Parse(splitted[0]) * 3600, int.Parse(splitted[1]) * 3600);
            };

            // Generation of all possible shifts for each activity with a given increment
            shifts = GenerateShifts(activities, shiftIncrement, shifts);

            // Validates the instance data
            ValidateInstance();
        }
    }

    /**
     * Validates the instance data for consistency
     */
    public void ValidateInstance()
    {
        // Check if all activities can be completed within their time windows
        foreach (Activity activity in activities)
        {
            if (activity.actDuration > (activity.actMaxEnd - activity.actMinStart))
            {
                throw new ArgumentException($"Activity {activity.activityId} duration ({activity.actDuration / 3600}h) exceeds its time window");
            }
        }

        // Check if workers' availability windows are valid
        foreach (Agent agent in agents)
        {
            if (agent.availabilityStart >= agent.availabilityEnd)
            {
                throw new ArgumentException($"Agent {agent.agentId} has invalid availability window");
            }
        }

        // Check if activities can be performed within workers' availability
        int earliestStart = activities.Min(a => a.actMinStart);
        int latestEnd = activities.Max(a => a.actMaxEnd);

        foreach (Agent agent in agents)
        {
            if (agent.availabilityStart > earliestStart || agent.availabilityEnd < latestEnd)
            {
                Console.WriteLine($"Warning: Agent {agent.agentId} availability might not cover all tasks");
            }
        }
    }

    /**
     * Ignore comments in a text file
     * @param input scanner object, reading data
     * @return next line in the file, ignoring comments
     */
    string ReadLineIgnoringComments(StreamReader input)
    {
        string line;
        do
        {
            line = input.ReadLine();
            if (line == null) return null;
            line = line.Split('#')[0].Trim();
        } while (string.IsNullOrEmpty(line));
        return line;
    }

    /**
    * Generates all possible shifts for activities with given time increment
    * @param activities Array of Activity objects
    * @param shiftIncrement Time increment in seconds
    * @return Array of generated Shift objects
    */
    Shift[] GenerateShifts(Activity[] activities, int shiftIncrement, Shift[] shifts)
    {
        int i = 0;
        for (int j = 0; j < nbActivities; j++)
        {
            int currentTime = activities[j].actMinStart;
            while (currentTime + activities[j].actDuration <= activities[j].actMaxEnd)
            {
                Array.Resize(ref shifts, i + 1);
                shifts[i] = new Shift(i, j, currentTime, currentTime + activities[j].actDuration);
                currentTime += shiftIncrement;
                i += 1;
            }
        }
        nbShifts = i;
        return shifts;
    }

    /**
    * Checks if there is at least a one-hour break between two shifts
    * @param s1 First shift
    * @param s2 Second shift
    * @return true if there is not enough break, false otherwise
    */
    bool NotEnoughBreak(Shift s1, Shift s2)
    {
        return !(s1.shiftStart >= s2.shiftEnd + 3600 || s1.shiftEnd + 3600 <= s2.shiftStart);
    }

    /**
    * Checks if two shifts are compatible
    * @param s1 First shift
    * @param s2 Second shift
    * @return true if shifts overlap, false otherwise
    */
    bool OverlappingShifts(Shift s1, Shift s2)
    {
        return !(s1.shiftStart >= s2.shiftEnd || s1.shiftEnd <= s2.shiftStart);
    }

    /**
    * Checks if two time intervals overlap
    * @param interval1Start Start of first interval
    * @param interval1End End of first interval
    * @param interval2Start Start of second interval
    * @param interval2End End of second interval
    * @return true if intervals overlap, false otherwise
    */
    bool OverlappingIntervals(int interval1Start, int interval1End, int interval2Start, int interval2End)
    {
        return !(interval1Start >= interval2End || interval1End <= interval2Start);
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: WorkforceSchedulingShifts inputFile [solFile] [timeLimit]");
            Environment.Exit(1);
        }
        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "20";

        using (WorkforceSchedulingShifts model = new WorkforceSchedulingShifts())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
        }
    }
}

import java.util.*;
import java.io.*;

import com.hexaly.optimizer.*;

/**
 * Activity class represents a work item with its scheduling constraints
 * - id: Unique identifier for the activity
 * - minStart: minimum possible start time (in seconds)
 * - maxEnd: maximum possible end time (in seconds)
 * - duration: Duration of the activity (in seconds)
 */
class Activity{
    int activityId;
    int actMinStart;
    int actMaxEnd;
    int actDuration;

    Activity(int actId, int actMinStart, int actMaxEnd, int actDuration){
        this.activityId = actId;
        this.actMinStart = actMinStart;
        this.actMaxEnd = actMaxEnd;
        this.actDuration = actDuration;
    }
}

/**
 * Agent class represents an employee with their availability window
 * - id: Unique identifier for the agent
 * - availabilityStart: Start of availability period (in seconds)
 * - availabilityEnd: End of availability period (in seconds)
 */
class Agent{
    int agentId;
    int availabilityStart;
    int availabilityEnd;

    Agent(int agentId, int avStart, int avEnd){
        this.agentId = agentId;
        this.availabilityStart = avStart;
        this.availabilityEnd = avEnd;
    }
} 

/**
 * Shift class represents a scheduled work period for an activity
 * - id: Unique identifier for the shift
 * - activityId: ID of the activity performed
 * - shiftStart: Start time of the shift (in seconds)
 * - shiftEnd: End time of the shift (in seconds)
 */
class Shift{
    int shiftId;
    int shiftActivity;
    int shiftStart;
    int shiftEnd;

    Shift(int shiftId, int shiftActivity, int shiftStart,  int shiftEnd){
        this.shiftId = shiftId;
        this.shiftActivity = shiftActivity;
        this.shiftStart = shiftStart;
        this.shiftEnd = shiftEnd;
    }
}

public class WorkforceSchedulingShifts {
    private final HexalyOptimizer optimizer;
    // Dimensions of the problem
    int nbAgents;
    int nbActivities;
    int timeHorizon;
    int shiftIncrement;

    // Activities
    Activity[] activities;

    // Agents
    Agent[] agents;

    // Shifts
    int nbShifts;
    Shift[] shifts;

    // Decision variables: time range of each task
    HxExpression[][] agentShift;
    // Objective = minimize the missing agent time and total working time of the agents
    HxExpression totalUnderstaffing;
    HxExpression totalWorkingTime;

    private WorkforceSchedulingShifts(HexalyOptimizer optimizer) {
        this.optimizer = optimizer;
    }

    private void solve(int limit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();
        agentShift = new HxExpression[nbAgents][nbShifts];
        for(int i = 0; i< nbAgents; i++){
            for(int j = 0 ; j < nbShifts; j++){
                agentShift[i][j] = model.boolVar();
            }
        }
        // Constraints
        // 1. The shifts performed by an agent must not overlap
        for (int a = 0; a < nbAgents; a++){
            for(int s1 = 0 ; s1 < nbShifts; s1++){
                for(int s2 = 0; s2 < nbShifts; s2++){
                    if(overlappingShifts(shifts[s1], shifts[s2]) && s1 != s2){
                        model.constraint(model.leq(model.sum(agentShift[a][s1], agentShift[a][s2]), 1));
                    }
                }
            }
        }
        // 2. An agent must take at least a one-hour break between two shifts
        for (int a=0; a < nbAgents; a++){
            for(int s1 = 0; s1 < nbShifts; s1++){
                for(int s2 = 0; s2 < nbShifts; s2++){
                    if(notEnoughBreak(shifts[s1], shifts[s2]) && s1 != s2){
                        model.constraint(model.leq(model.sum(agentShift[a][s1], agentShift[a][s2]), 1));
                    }
                }
            }
        }
        // 3. Each agent must work exactly two shifts in the day
        for(int a = 0; a < nbAgents; a++){
            HxExpression shiftsDone = model.sum();
            for(int id = 0; id < nbShifts; id++){
                shiftsDone.addOperand(agentShift[a][id]);
            }
            model.constraint(model.eq(shiftsDone, 2));
        }

        // Objective 1 : Minimize understaffing
        HxExpression totalUnderstaffing=model.sum();
        for(int i = 0; i < nbActivities; i++){
            int currentTime = activities[i].actMinStart;
            while (currentTime < activities[i].actMaxEnd){
                // Current interval of time
                int currentIntervalStart = currentTime;
                int currentIntervalEnd = currentTime + shiftIncrement;
                // The activity will not be pursued after its maximum possible end 
                if (currentIntervalEnd > activities[i].actMaxEnd){
                    currentIntervalEnd = activities[i].actMaxEnd;
                } 
                // Shifts performed in the current time interval 
                HxExpression totalAgentsWorking=model.sum();
                for(int j = 0 ; j < nbShifts; j++){
                    if(shifts[j].shiftActivity != i){
                        continue;
                    }
                    if(overlappingIntervals(currentIntervalStart, currentIntervalEnd, shifts[j].shiftStart, shifts[j].shiftEnd)){
                        for(int a = 0; a < nbAgents; a++){
                            totalAgentsWorking.addOperand(agentShift[a][j]);
                        }
                    }
                }
                // Number of agents missing
                totalUnderstaffing.addOperand(model.prod(shiftIncrement, model.max(0, model.sub(1, totalAgentsWorking))));
                currentTime += shiftIncrement;
            }
        }
        model.minimize(totalUnderstaffing);
        // Objective 2 : Minimize the total worktime of all the agents
        HxExpression totalWorkingTime = model.sum();
        for (int a = 0; a < nbAgents; a++){
            for(int s = 0; s < nbShifts; s++){
                totalWorkingTime.addOperand(model.prod(agentShift[a][s], activities[shifts[s].shiftActivity].actDuration));
            }
        }
        model.minimize(totalWorkingTime);
        model.close();
        // Parametrize the optimizer
        optimizer.getParam().setTimeLimit(10);
        optimizer.solve();
    }

    /**
     * Ignore comments in a text file
     * @param input scanner object, reading data
     * @return next int in the file, ignoring comments
     */
    private static int nextIntIgnoringComments(Scanner input) {
        while (input.hasNextLine()) {
            String line = input.nextLine().split("#")[0].trim(); 
            if (!line.isEmpty()) {
            Scanner lineScanner = new Scanner(line);
            if (lineScanner.hasNextInt()) {
                return lineScanner.nextInt();
            }
        }
        }
        throw new IllegalArgumentException("No valid integer found");
    }

    /**
     * Ignore comments in a text file
     * @param input scanner object, reading data
     * @return next double in the file, ignoring comments
     */
    private static double nextDoubleIgnoringComments(Scanner input) {
        while (input.hasNextLine()) {
            String line = input.nextLine().split("#")[0].trim();
            if (!line.isEmpty()) {
                Scanner lineScanner = new Scanner(line).useLocale(Locale.ROOT);
                if (lineScanner.hasNextDouble()) {
                    return lineScanner.nextDouble();
                }
            }
        }
        throw new IllegalArgumentException("No valid double found");
    }

    /**
     * Ignore comments in a text file
     * @param input scanner object, reading data
     * @return next line in the file, ignoring comments
     */
    private static String nextLineIgnoringComments(Scanner input) {
        while (input.hasNextLine()) {
            String line = input.nextLine().split("#")[0].trim();
            if (!line.isEmpty()) {
                return line;
            }
        }
        throw new IllegalArgumentException("No valid line found");
    }

    /* 
    * Read instance data
    */
    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            // Read problem dimensions
            input.useLocale(Locale.ROOT);
            nbAgents = nextIntIgnoringComments(input);
            nbActivities = nextIntIgnoringComments(input);
            timeHorizon = nextIntIgnoringComments(input);
            shiftIncrement = (int) (nextDoubleIgnoringComments(input) * 3600);

            // Read activities informations
            activities = new Activity[nbActivities]; 
            for(int i = 0; i < nbActivities; i++){
                activities[i]= new Activity(i, 0, 0, 0);
                activities[i].actDuration = nextIntIgnoringComments(input) * 3600;
            }
            for(int i = 0; i < nbActivities; i++){
                String line = nextLineIgnoringComments(input);
                Scanner lineScanner = new Scanner(line);
                activities[i].actMinStart = lineScanner.nextInt() * 3600;
                activities[i].actMaxEnd = lineScanner.nextInt() * 3600;
            }

            // Read agents informations
            agents = new Agent[nbAgents];
            for(int i = 0; i < nbAgents; i++){
                String line = nextLineIgnoringComments(input);
                Scanner lineScanner = new Scanner(line);
                agents[i] = new Agent(i, 0, 0);
                agents[i].availabilityStart = lineScanner.nextInt() * 3600;
                agents[i].availabilityEnd = lineScanner.nextInt() * 3600;
            }
            // Generation of all possible shifts for each activity with a given increment
            generateShifts(activities, shiftIncrement); 

            // Validates the instance data
            validateInstance();
        }
    }

    /**
     * Generates all possible shifts for activities with given time increment
     * @param activities Array of Activity objects
     * @param shiftIncrement Time increment in seconds
     * @return Array of generated Shift objects
     */
    void generateShifts(Activity[] activities, int shiftIncrement){
        int i = 0;
        shifts = new Shift[]{};
        for(int j =0; j< nbActivities ; j++){
            int currentTime = activities[j].actMinStart;
            while(currentTime+activities[j].actDuration <= activities[j].actMaxEnd){
                Shift[] newshifts = Arrays.copyOf(shifts, shifts.length + 1);
                shifts = newshifts;
                shifts[i] = new Shift(i, 0, 0, 0);
                shifts[i].shiftId = i;
                shifts[i].shiftActivity = j;
                shifts[i].shiftStart = currentTime;
                shifts[i].shiftEnd = currentTime + activities[j].actDuration;
                currentTime += shiftIncrement;
                i += 1;
            }
        }
        nbShifts = i;
    }

    /**
     * Checks if there is at least a one-hour break between two shifts
     * @param shift1 First shift
     * @param shift2 Second shift
     * @return true if there is not enough break, false otherwise
     */
    boolean notEnoughBreak(Shift s1, Shift s2){
        return !(s1.shiftStart >= s2.shiftEnd + 3600 || s1.shiftEnd + 3600 <= s2.shiftStart);
    }

    /**
     * Checks if two shifts are compatible
     * @param shift1 First shift
     * @param shift2 Second shift
     * @return true if shifts overlap, false otherwise
     */    
    boolean overlappingShifts(Shift s1, Shift s2){
        return !(s1.shiftStart >= s2.shiftEnd || s1.shiftEnd <= s2.shiftStart);
    }

    /**
     * Checks if two time intervals overlap
     * @param interval1Start Start of first interval
     * @param interval1End End of first interval
     * @param interval2Start Start of second interval
     * @param interval2End End of second interval
     * @return true if intervals overlap, false otherwise
     */
    boolean overlappingIntervals(int interval1Start, int interval1End, int interval2Start, int interval2End){
        return !(interval1Start >= interval2End || interval1End <= interval2Start);
    }

    /**
     * Validates the instance data for consistency
     */
    void validateInstance() {
        // Check if all activities can be completed within their time windows
        for (Activity activity : activities) {
            if (activity.actDuration > (activity.actMaxEnd - activity.actMinStart)) {
                throw new IllegalArgumentException("Activity " + activity.activityId + " duration (" + (activity.actDuration / 3600) + "h) exceeds its time window");
            }
        }

        // Check if workers' availability windows are valid
        for (Agent agent : agents) {
            if (agent.availabilityStart >= agent.availabilityEnd) {
                throw new IllegalArgumentException("Agent " + agent.agentId + " has invalid availability window");
            }
        }

        // Check if activities can be performed within workers' availability

        Activity earliestStartActivity = Arrays.stream(activities).min(Comparator.comparingInt(a -> a.actMinStart)).orElseThrow();
        Activity latestEndActivity = Arrays.stream(activities).max(Comparator.comparingInt(a -> a.actMaxEnd)).orElseThrow();

        int earliestStart = earliestStartActivity.actMinStart;
        int latestEnd = latestEndActivity.actMaxEnd;
        
        for (Agent agent : agents) {
            if (agent.availabilityStart > earliestStart || agent.availabilityEnd < latestEnd) {
                System.out.println("Warning: Agent " + agent.agentId + " availability might not cover all tasks");
            }
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Usage: java WorkforceSchedulingShifts inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }
        try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            String instanceFile = args[0];
            String outputFile = args.length > 1 ? args[1] : null;
            String strTimeLimit = args.length > 2 ? args[2] : "20";

            WorkforceSchedulingShifts model = new WorkforceSchedulingShifts(optimizer);
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}