Workforce Scheduling Problem
SchedulingProblem
In the Workforce Scheduling Problem, a company must complete a set of tasks throughout the week. Each task requires a varying number of agents over time to meet demand. Agents have individual availability constraints—specific days and hours—and may not be qualified to perform every task. Furthermore, each task requires a certain processing time, and an agent can only work on one task at a time.
The goal is to develop a schedule that assigns agents to tasks in a way that minimizes the gap between the required and assigned number of agents at any given time. This objective is captured through three specific sub-objectives, which are detailed in the Program section.
Principles learned
- Define multi-objectives models and identify the priority of each objective
- Pre-compute indicators when possible to reduce the model’s complexity
- Learn about Hexaly Optimizer’s modeling style: distinguish decision variables from intermediate expressions
Data
The format of the data files for the Workforce Scheduling Problem is as follows:
- First line: number of agents
- Second line: number of tasks
- Third line: number of days
The following lines consist of different sections, respectively containing the following information :
- The duration of each task
- The number of agents needed each day, at each hour, for each task
- The days when each agent is available
- The hours when each agent is available on working days
- The tasks each agent is able to perform
Program
The Hexaly model for the Workforce Scheduling Problem uses Boolean decision variables to model each agent’s schedule. For each agent, task, and time, the decision variable indicates whether the agent begins this task at this time.
To reduce the complexity of the model, we do some pre-calculations. When reading the data, we concatenate each agent’s availability information with their skills to create an indicator assessing their capacity to begin a task at a given time, work on it, and finish it before the end of the day. We use this indicator to write the main constraints in the model. To ensure that no agent is assigned multiple tasks at the same time, we examine all pairs of decision variables that could result in such a conflict. Then, we enforce constraints to prevent both from being true simultaneously.
Next, we estimate each agent’s daily working time. We impose upper and lower bounds on it to better reflect a realistic professional setting. This way, we avoid situations where one agent works twelve hours a day while another only works one hour per week.
For each time step, we compute the difference between the number of agents needed and the number of agents attributed to each task. This gives us indicators for both understaffing and overstaffing per task.
We define three objectives to solve the Workforce Scheduling Problem:
- Minimizing understaffing for the tasks
- Minimizing overstaffing for the tasks
- Minimizing the length of the agents’ working days
The three objectives are optimized lexicographically: the order in which they are declared defines their order of importance. By separating understaffing and overstaffing into two distinct objectives, we prioritize meeting demand, even if it means having too many agents at times. It’s better than having significant shortages at some moments and surpluses at others. This approach also avoids compensation effects between over- and understaffing.
The third objective aims to keep agents’ working days compact, especially when only assigned a few tasks. Typically, we want to avoid situations where an agent works on a one-hour task at 7:00 AM and another at 6:00 PM, with a long idle gap in between.
- Execution
-
hexaly workforce_scheduling.hxm inFileName=instances/2tasks.txt [hxTimeLimit=] [solFileName=]
use io;
/* Function used to extract the information from the data file */
function readData(fileName) {
local inFile = io.openRead(fileName);
// Dimensions of the problem
nbAgents = inFile.readln().toInt();
nbTasks = inFile.readln().toInt();
nbDays = inFile.readln().toInt();
horizon = nbDays * 24;
MIN_WORKING_TIME = 4;
MAX_WORKING_TIME = 8;
// Tasks duration
inFile.readln();
for [i in 0...nbTasks] {
taskDuration[i] = inFile.readln().toInt();
}
// Number of agents needed for the task i at time t
// agentsNeeded[i][t] contains the number of agents needed
// for the task i at time t
inFile.readln();
for [d in 0...nbDays] {
inFile.readln();
for[i in 0...nbTasks]{
local elements = inFile.readln().trim().split(" ");
for [h in 0...24] {
local t = d * 24 + h;
agentsNeeded[i][t] = elements[h].toInt();
}
}
}
// Agent disponibility
// dayDispo[a][d] = 1 if agent a is available on day d
inFile.readln();
for [a in 0...nbAgents] {
local elements = inFile.readln().trim().split(" ");
for [d in 0...nbDays] {
dayDispo[a][d] = elements[d].toInt();
}
}
// hourDispo[a][h] = 1 if agent a is available on hour h
inFile.readln();
for [a in 0...nbAgents] {
local elements = inFile.readln().trim().split(" ");
startDay[a] = elements[0].toInt();
endDay[a] = elements[1].toInt();
hourDispo[a][h in 0...startDay[a]] = 0;
hourDispo[a][h in startDay[a]...endDay[a]] = 1;
hourDispo[a][h in endDay[a]...24] = 0;
}
// We can concatenate these two informations
// into a global indicator of agent disponibility
// agentDispo[a][t] = 1 if agent a is available
// on time t
for [a in 0...nbAgents] {
for [d in 0...nbDays] {
for [h in 0...24] {
local t = d * 24 + h;
agentDispo[a][t] = dayDispo[a][d] * hourDispo[a][h];
}
}
}
// Agent skills
// agentSkills[a][i] = 1 if agent a is able to perform the task i
inFile.readln();
for [a in 0...nbAgents] {
local elements = inFile.readln().trim().split(" ");
for [i in 0...nbTasks] {
agentSkills[a][i] = elements[i].toInt();
}
}
// We can use all these informations and task length to get an indicator
// telling us if the agent a can begin the task i at time t,
// and complete it before the end of day
for [a in 0...nbAgents] {
for [i in 0...nbTasks] {
for [d in 0...nbDays] {
for [h in 0...startDay[a]] {
local t = d * 24 + h;
agentCanStart[a][i][t] = 0;
}
for [h in startDay[a]..endDay[a] - taskDuration[i]] {
local t = d * 24 + h;
agentCanStart[a][i][t] =
agentDispo[a][t] * agentSkills[a][i];
}
for [h in endDay[a] - taskDuration[i] + 1...24] {
local t = d * 24 + h;
agentCanStart[a][i][t] = 0;
}
}
}
}
}
/* Read input data */
function input() {
local usage =
"Usage: hexaly workforce_scheduling.hxm inFileName=instanceFile "
+ "[outFileName=outputFile] [hxTimeLimit=timeLimit]";
if (inFileName == nil) throw usage;
readData(inFileName);
}
/* Returns the time steps corresponding to day d */
function timesOfDay(d) {
return (d * 24)...((d + 1) * 24);
}
/* Returns the time steps s such that
* [s, s + duration) intersects time t */
function intersectingStarts(t, duration) {
return max(t - duration + 1, 0)...(t + 1);
}
/* Declare the optimization model */
function model() {
// Definition of the decision variable :
// agentStart[a][i][t] = 1 if agent a starts the task i at time t
agentStart[a in 0...nbAgents][i in 0...nbTasks][t in 0...horizon] <- bool();
// An agent can only work if he is able to complete his task
// before the end of the day
for [a in 0...nbAgents][i in 0...nbTasks][t in 0...horizon]
constraint agentStart[a][i][t] <= agentCanStart[a][i][t];
// Each agent can only work on one task at a time
for [a in 0...nbAgents]
[i1 in 0...nbTasks][i2 in 0...nbTasks]
[t1 in 0...horizon][t2 in intersectingStarts(t1, taskDuration[i2])] {
if (i1 == i2 && t1 == t2) {
continue;
}
constraint agentStart[a][i1][t1] + agentStart[a][i2][t2] <= 1;
}
// Working time per agent per day
agentWorkingTime[a in 0...nbAgents][d in 0...nbDays] <-
sum[t in timesOfDay(d)][i in 0...nbTasks](
agentStart[a][i][t] * taskDuration[i]
);
// Minimum and maximum amount of time worked
for [a in 0...nbAgents][d in 0...nbDays : dayDispo[a][d] == 1] {
constraint agentWorkingTime[a][d] >= MIN_WORKING_TIME;
constraint agentWorkingTime[a][d] <= MAX_WORKING_TIME;
}
// Difference between needed and attributed number of agents for each task
agentsAttributed[i in 0...nbTasks][t0 in 0...horizon] <-
sum[a in 0...nbAgents][t in intersectingStarts(t0, taskDuration[i])](
agentStart[a][i][t]
);
agentDiff[i in 0...nbTasks][t in 0...horizon] <-
agentsNeeded[i][t] - agentsAttributed[i][t];
// Indicators for lack and excess of agents
agentLack <- sum[i in 0...nbTasks][t in 0...horizon](
pow(max(agentDiff[i][t], 0), 2)
);
agentExcess <- sum[i in 0...nbTasks][t in 0...horizon](
pow(max(-agentDiff[i][t], 0), 2)
);
agentDayStart[a in 0...nbAgents][d in 0...nbDays] <-
min[i in 0...nbTasks][t in timesOfDay(d)](
t + (1 - agentStart[a][i][t]) * horizon
);
agentDayEnd[a in 0...nbAgents][d in 0...nbDays] <-
max[i in 0...nbTasks][t in timesOfDay(d)](
(t + taskDuration[i]) * agentStart[a][i][t]
);
// Difference between first and last hour of agents each day
agentDayLength <- sum[a in 0...nbAgents][d in 0...nbDays](
max(agentDayEnd[a][d] - agentDayStart[a][d], 0)
);
// Objectives
minimize agentLack;
minimize agentExcess;
minimize agentDayLength;
}
/* Parameterize the solver */
function param() {
if (hxTimeLimit == nil) hxTimeLimit = 20;
}
/* Output function, printing the objective values
* and the solution found in an output file */
function output() {
if (outFileName != nil) {
outFile = io.openWrite(outFileName);
println("Solution written in file ", outFileName);
outFile.println(agentLack.value);
outFile.println(agentExcess.value);
outFile.println(agentDayLength.value);
for [a in 0...nbAgents] {
for [i in 0...nbTasks] {
for [t in 0...horizon] {
outFile.print(agentStart[a][i][t].value," ");
}
outFile.println();
}
outFile.println();
}
}
}
- Execution (Windows)
-
set PYTHONPATH=%HX_HOME%\bin\pythonpython workforce_scheduling.py instances\2tasks.txt
- Execution (Linux)
-
export PYTHONPATH=/opt/hexaly_14_0/bin/pythonpython workforce_scheduling.py instances/2tasks.txt
import hexaly.optimizer
import sys
# Function used to extract the information from the data file
def readData(filename):
with open(filename) as f:
lines = iter(f.readlines())
# Dimensions of the problem
nb_agents = int(next(lines))
nb_tasks = int(next(lines))
nb_days = int(next(lines))
horizon = nb_days * 24
min_working_time = 4
max_working_time = 8
# Tasks duration
next(lines)
task_duration = [0 for i in range(nb_tasks)]
for i in range(nb_tasks):
task_duration[i] = int(next(lines))
# Number of agents needed for the task i at time t
# agents_needed[i][t] contains the number of agents needed
# for the task i at time t
next(lines)
next(lines)
agents_needed = [[0 for t in range(horizon)] for i in range(nb_tasks)]
for d in range(nb_days):
for i in range(nb_tasks):
elements = next(lines).split(" ")
for h in range(24):
t = d * 24 + h
agents_needed[i][t] = int(elements[h])
next(lines)
# Agent disponibility
# day_dispo[a][d] = 1 if agent a is available on day d
day_dispo = [[0 for d in range(nb_days)] for a in range(nb_agents)]
for a in range(nb_agents):
elements = next(lines).split(" ")
for d in range(nb_days):
day_dispo[a][d] = int(elements[d])
# hour_dispo[a][h] = 1 if agent a is available on hour h
next(lines)
hour_dispo = [[0 for h in range(24)] for a in range(nb_agents)]
start_day = [0 for a in range(nb_agents)]
end_day = [0 for a in range(nb_agents)]
for a in range(nb_agents):
elements = next(lines).split(" ")
start_day[a] = int(elements[0])
end_day[a] = int(elements[1])
hour_dispo[a][0:start_day[a]] = [0] * start_day[a]
hour_dispo[a][start_day[a]:end_day[a]] = \
[1] * (end_day[a] - start_day[a])
hour_dispo[a][end_day[a]:24] = [0] * (24 - end_day[a])
# We can concatenate these two informations
# into a global indicator of agent disponibility
# agent_dispo[a][t] = 1 if agent a is available
# on time t
agent_dispo = [[0 for t in range(horizon)] for a in range(nb_agents)]
for a in range(nb_agents):
for d in range(nb_days):
for h in range(24):
t = d * 24 + h
agent_dispo[a][t] = day_dispo[a][d] * hour_dispo[a][h]
# Agent skills
# agent_skills[a][i] = 1 if agent a is able to perform the task i
next(lines)
agent_skills = [[0 for i in range(nb_tasks)] for a in range(nb_agents)]
for a in range(nb_agents):
elements = next(lines).split(" ")
for i in range(nb_tasks):
agent_skills[a][i] = int(elements[i])
# We can use all these informations and task length to get an indicator
# telling us if the agent a can begin the task i at time t,
# and complete it before the end of day
agent_can_start = [
[
[0 for t in range(horizon)]
for i in range(nb_tasks)
]
for a in range(nb_agents)
]
for a in range(nb_agents):
for i in range(nb_tasks):
for d in range(nb_days):
for h in range(0, start_day[a]):
t = d * 24 + h
agent_can_start[a][i][t] = 0
for h in range(start_day[a], end_day[a] - task_duration[i] + 1):
t = d * 24 + h
agent_can_start[a][i][t] = agent_dispo[a][t] * \
agent_skills[a][i]
for h in range(end_day[a] - task_duration[i] + 1, 24):
t = d * 24 + h
agent_can_start[a][i][t] = 0
return nb_agents, nb_tasks, nb_days, horizon, task_duration, agents_needed, \
day_dispo, agent_can_start, min_working_time, max_working_time
# Returns the time steps corresponding to day d
def times_of_day(d):
return range(d * 24, (d + 1) * 24)
# Returns the time steps s such that
# [s, s + duration) intersects time t
def intersecting_starts(t, duration):
return range(max(t - duration + 1, 0), t + 1)
def main(instance_file, output_file, time_limit):
nb_agents, nb_tasks, nb_days, horizon, task_duration, \
agents_needed, day_dispo, agent_can_start, \
min_working_time, max_working_time = readData(instance_file)
with hexaly.optimizer.HexalyOptimizer() as optimizer:
#
# Declare the optimization model
#
model = optimizer.model
# Definition of the decision variable :
# agent_start[a][i][t] = 1 if agent a starts the task i at time t
agent_start = [
[
[model.bool() for t in range(horizon)]
for i in range(nb_tasks)
]
for a in range(nb_agents)
]
# An agent can only work if he is able to complete his task
# before the end of the day
for a in range(nb_agents):
for i in range(nb_tasks):
for t in range(horizon):
model.constraint(
agent_start[a][i][t] <= agent_can_start[a][i][t]
)
# Each agent can only work on one task at a time
for a in range(nb_agents):
for i1 in range(nb_tasks):
for i2 in range(nb_tasks):
for t1 in range(horizon):
for t2 in intersecting_starts(t1, task_duration[i2]):
if (i1 != i2) or (t1 != t2):
model.constraint(
agent_start[a][i1][t1] +
agent_start[a][i2][t2] <= 1
)
# Working time per agent per day
agent_working_time = [
[
sum(
agent_start[a][i][t] * task_duration[i]
for i in range(nb_tasks)
for t in times_of_day(d)
)
for d in range(nb_days)
]
for a in range(nb_agents)
]
# Minimum and maximum amount of time worked
for a in range(nb_agents):
for d in range(nb_days):
if day_dispo[a][d] == 1:
model.constraint(
agent_working_time[a][d] >= min_working_time
)
model.constraint(
agent_working_time[a][d] <= max_working_time
)
# Difference between needed and attributed number of agents
# for each task
agent_attributed = [
[
sum(
agent_start[a][i][t]
for a in range(nb_agents)
for t in intersecting_starts(t0, task_duration[i])
)
for t0 in range(horizon)
]
for i in range(nb_tasks)
]
agent_diff = [
[
agents_needed[i][t] - agent_attributed[i][t]
for t in range(horizon)
]
for i in range(nb_tasks)
]
# Indicators for lack and excess of agents
agent_lack = sum(
model.pow(model.max(agent_diff[i][t], 0), 2)
for t in range(horizon)
for i in range(nb_tasks)
)
agent_excess = sum(
model.pow(model.max(-agent_diff[i][t], 0), 2)
for t in range(horizon)
for i in range(nb_tasks)
)
agent_day_start = [
[
model.min(
t + (1 - agent_start[a][i][t]) * horizon
for i in range(nb_tasks)
for t in times_of_day(d)
)
for d in range(nb_days)
]
for a in range(nb_agents)
]
agent_day_end = [
[
model.max(
(t + task_duration[i]) * agent_start[a][i][t]
for i in range(nb_tasks)
for t in times_of_day(d)
)
for d in range(nb_days)
]
for a in range(nb_agents)
]
# Difference between first and last hour of agents each day
agent_day_length = sum(
model.max(agent_day_end[a][d] - agent_day_start[a][d], 0)
for a in range(nb_agents)
for d in range(nb_days)
)
# Objectives
model.minimize(agent_lack)
model.minimize(agent_excess)
model.minimize(agent_day_length)
model.close()
# Parameterize the optimizer
optimizer.param.time_limit = time_limit
optimizer.solve()
print("I solved the model")
# Outputs if output file specified
if output_file != None:
with open(output_file, "w") as f:
print("Solution written in file", output_file)
# Objective values
f.write(str(agent_lack.value) + "\n")
f.write(str(agent_excess.value) + "\n")
f.write(str(agent_day_length.value) + "\n")
# Decision variable
for a in range(nb_agents):
for i in range(nb_tasks):
for t in range(horizon):
f.write(str(agent_start[a][i][t].value) + " ")
f.write("\n")
f.write("\n")
# Main
if __name__ == '__main__':
if len(sys.argv) < 2:
print("Usage: python workforce_scheduling.py instance_file "
+ "[output_file] [time_limit]")
sys.exit(1)
instance_file = sys.argv[1]
output_file = sys.argv[2] if len(sys.argv) >= 3 else None
time_limit = int(sys.argv[3]) if len(sys.argv) >= 4 else 30
main(instance_file, output_file, time_limit)
- Compilation / Execution (Windows)
-
cl /EHsc workforce_scheduling.cpp -I%HX_HOME%\include /link %HX_HOME%\bin\hexaly140.libworkforce_scheduling instances\2tasks.txt
- Compilation / Execution (Linux)
-
g++ workforce_scheduling.cpp -I/opt/hexaly_14_0/include -lhexaly140 -lpthread -o bin_packing_conflicts./workforce_scheduling instances/2tasks.txt
#include "optimizer/hexalyoptimizer.h"
#include <algorithm>
#include <fstream>
#include <iostream>
#include <limits>
#include <numeric>
#include <vector>
using namespace hexaly;
class WorkforceScheduling {
private:
// Number of agents
int nbAgents;
// Number of tasks
int nbTasks;
// Start of the day for each agent
std::vector<int> startDay;
// End of the day for each agent
std::vector<int> endDay;
// Time horizon : number of days
int nbDays;
// Time horizon : number of time steps
int horizon;
// Maximum and minimum worked hours per day
int MIN_WORKING_TIME = 4;
int MAX_WORKING_TIME = 8;
// Duration of each task
std::vector<int> taskDuration;
// Number of agents needed for each task at each time
std::vector<std::vector<int>> agentsNeeded;
// Daily disponibilities of each agent
std::vector<std::vector<int>> dayDispo;
// Hour disponibilities of each agent on working days
std::vector<std::vector<int>> hourDispo;
// The agent is available at time t
std::vector<std::vector<int>> agentDispo;
// The agent is able to perform the task i
std::vector<std::vector<int>> agentSkills;
// The agent is able to perform the task i and complete it
// before the end of the day
std::vector<std::vector<std::vector<int>>> agentCanStart;
// Hexaly Optimizer
HexalyOptimizer optimizer;
// Decision variable
std::vector<std::vector<std::vector<HxExpression>>> agentStart;
// Agent working time per day
std::vector<std::vector<HxExpression>> agentWorkingTime;
// Attributed number of agents for each task
std::vector<std::vector<HxExpression>> attributedAgents;
// Difference between needed number of agents and attributed number
// of agents for each task
std::vector<std::vector<HxExpression>> agentDiff;
// Indicators for lack and excess of agents
HxExpression agentLack;
HxExpression agentExcess;
// Difference between first and last hour of agents each day
std::vector<std::vector<HxExpression>> agentDayStart;
std::vector<std::vector<HxExpression>> agentDayEnd;
HxExpression agentDayLength;
public:
WorkforceScheduling(const std::string& fileName) : optimizer() {}
void readInstance(const std::string& fileName) {
std::ifstream inFile;
inFile.exceptions(std::ifstream::failbit | std::ifstream::badbit);
inFile.open(fileName.c_str());
inFile >> nbAgents;
inFile >> nbTasks;
inFile >> nbDays;
horizon = nbDays * 24;
// The duration of each task
taskDuration.resize(nbTasks);
for (int i = 0; i < nbTasks; ++i) {
inFile >> taskDuration[i];
}
// Number of agents needed for the task i at time t
// agentsNeeded[i][t] contains the number of agents needed
// for the task i at time t
agentsNeeded.resize(nbTasks);
for (int d = 0; d < nbDays; ++d) {
for (int i = 0; i < nbTasks; ++i) {
agentsNeeded[i].resize(horizon);
for (int h = 0; h < 24; ++h) {
int t = d * 24 + h;
inFile >> agentsNeeded[i][t];
}
}
}
// Agent disponibility
// dayDispo[a][d] = 1 if agent a is available on day d
dayDispo.resize(nbAgents);
for(int a = 0; a < nbAgents; ++a) {
dayDispo[a].resize(nbDays);
for(int d = 0; d < nbDays; ++d) {
inFile >> dayDispo[a][d];
}
}
// hourDispo[a][h] = 1 if agent a is available on hour h
hourDispo.resize(nbAgents);
startDay.resize(nbAgents);
endDay.resize(nbAgents);
for (int a = 0; a < nbAgents; ++a) {
hourDispo[a].resize(24);
inFile >> startDay[a];
inFile >> endDay[a];
for (int h = 0; h < 24; ++h) {
if ((h >= startDay[a]) && (h < endDay[a])) {
hourDispo[a][h] = 1;
} else {
hourDispo[a][h] = 0;
}
}
}
// We can concatenate these two informations
// into a global indicator of agent disponibility
// agentDispo[a][t] = 1 if agent a is available
// on time t
agentDispo.resize(nbAgents);
for (int a = 0; a < nbAgents; ++a) {
agentDispo[a].resize(horizon);
for (int d = 0; d < nbDays; ++d) {
for (int h = 0; h < 24; ++h) {
int t = 24 * d + h;
agentDispo[a][t] = dayDispo[a][d] * hourDispo[a][h];
}
}
}
// Agent skills
// agentSkills[a][i] = 1 if agent a is able to perform the task i
agentSkills.resize(nbAgents);
for (int a = 0; a < nbAgents; ++a) {
agentSkills[a].resize(nbTasks);
for (int i = 0; i < nbTasks; ++i) {
inFile >> agentSkills[a][i];
}
}
// We can use all these informations and task length to get an indicator
// telling us if the agent a can begin the task i at time t,
// and complete it before the end of day
agentCanStart.resize(nbAgents);
for (int a = 0; a < nbAgents; ++a) {
agentCanStart[a].resize(nbTasks);
for (int i = 0; i < nbTasks; ++i) {
agentCanStart[a][i].resize(horizon);
for (int d = 0; d < nbDays; ++d) {
for (int h = 0; h < startDay[a]; ++h) {
int t = 24 * d + h;
agentCanStart[a][i][t] = 0;
}
int endPossible = endDay[a] - taskDuration[i] + 1;
for (int h = startDay[a]; h < endPossible; ++h) {
int t = 24 * d + h;
agentCanStart[a][i][t] =
agentDispo[a][t] * agentSkills[a][i];
}
for (int h = endPossible; h < 24; ++h) {
int t = 24 * d + h;
agentCanStart[a][i][t] = 0;
}
}
}
}
inFile.close();
}
// Returns the first time step s such that
// [s, s + duration) intersects time t
int intersectionStart(int t, int duration) {
return std::max(t - duration + 1, 0);
}
void solve(int TimeLimit) {
// Declare the optimization model
HxModel model = optimizer.getModel();
// Definition of the decision variable :
// agentStart[a][i][t] = 1 if agent a starts the task i at time t
agentStart.resize(nbAgents);
for (int a = 0; a < nbAgents; ++a) {
agentStart[a].resize(nbTasks);
for (int i = 0; i < nbTasks; ++i) {
agentStart[a][i].resize(horizon);
for (int t = 0; t < horizon; ++t) {
agentStart[a][i][t] = model.boolVar();
}
}
}
// An agent can only work if he is able to complete his task
// before the end of the day
for (int a = 0; a < nbAgents; ++a) {
for (int i = 0; i < nbTasks; ++i) {
for (int t = 0; t < horizon; ++t) {
model.constraint(
agentStart[a][i][t] <= agentCanStart[a][i][t]
);
}
}
}
// Each agent can only work on one task at a time
for (int a = 0; a < nbAgents; ++a) {
for (int i1 = 0; i1 < nbTasks; ++i1) {
for (int i2 = 0; i2 < nbTasks; ++i2) {
for (int t1 = 0; t1 < horizon; ++t1) {
int t2Start = intersectionStart(t1, taskDuration[i2]);
for (int t2 = t2Start; t2 < t1 + 1; ++t2) {
if ((i1 != i2) || (t1 != t2)) {
model.constraint(
agentStart[a][i1][t1] +
agentStart[a][i2][t2] <= 1
);
}
}
}
}
}
}
// Working time per agent per day
agentWorkingTime.resize(nbAgents);
for (int a = 0; a < nbAgents; ++a) {
agentWorkingTime[a].resize(nbDays);
for (int d = 0; d < nbDays; ++d) {
agentWorkingTime[a][d] = model.sum();
for (int i = 0; i < nbTasks; ++i) {
for (int t = 24 * d; t < 24 * (d + 1); ++t) {
agentWorkingTime[a][d].addOperand(
agentStart[a][i][t] * taskDuration[i]
);
}
}
}
}
// Minimum and maximum amount of time worked
for (int a = 0; a < nbAgents; ++a) {
for (int d = 0; d < nbDays; ++d) {
if (dayDispo[a][d] == 1) {
model.constraint(
agentWorkingTime[a][d] >= MIN_WORKING_TIME
);
model.constraint(
agentWorkingTime[a][d] <= MAX_WORKING_TIME
);
}
}
}
// Difference between needed and attributed number
// of agents for each task
agentDiff.resize(nbTasks);
attributedAgents.resize(nbTasks);
for (int i = 0; i < nbTasks; ++i) {
agentDiff[i].resize(horizon);
attributedAgents[i].resize(horizon);
for (int t0 = 0; t0 < horizon; ++t0) {
attributedAgents[i][t0] = model.sum();
for (int a = 0; a < nbAgents; ++a) {
int tStart = intersectionStart(t0, taskDuration[i]);
for (int t = tStart; t < t0 + 1; ++t) {
attributedAgents[i][t0].addOperand(agentStart[a][i][t]);
}
}
agentDiff[i][t0] =
agentsNeeded[i][t0] - attributedAgents[i][t0];
}
}
// Indicators for lack and excess of agents
// Agent Lack
agentLack = model.sum();
for (int i = 0; i < nbTasks; ++i) {
for (int t = 0; t < horizon; ++t) {
HxExpression lack = model.max(agentDiff[i][t], 0);
agentLack.addOperand(model.pow(lack, 2));
}
}
// Agent Excess
agentExcess = model.sum();
for (int i = 0; i < nbTasks; ++i) {
for (int t = 0; t < horizon; ++t) {
HxExpression excess = model.max(-1 * agentDiff[i][t], 0);
agentExcess.addOperand(model.pow(excess, 2));
}
}
// Difference between first and last hour of agents each day
agentDayLength = model.sum();
for (int a = 0; a < nbAgents; ++a) {
for (int d = 0; d < nbDays; ++d) {
HxExpression endWork = model.max();
HxExpression startWork = model.min();
for (int i = 0; i < nbTasks; ++i) {
for (int t = 24 * d; t < 24 * (d + 1); ++t) {
endWork.addOperand(
(t + taskDuration[i]) * agentStart[a][i][t]
);
startWork.addOperand(
t + (1 - agentStart[a][i][t]) * horizon
);
}
}
HxExpression dayLength = model.max(endWork - startWork, 0);
agentDayLength.addOperand(dayLength);
}
}
// Objectives
model.minimize(agentLack);
model.minimize(agentExcess);
model.minimize(agentDayLength);
model.close();
// Parameterize the optimizer
optimizer.getParam().setTimeLimit(TimeLimit);
optimizer.solve();
}
/* Write the solution in a file */
void writeSolution(const std::string& fileName) {
std::ofstream outfile(fileName.c_str());
if (!outfile.is_open()) {
std::cerr << "File " << fileName << " cannot be opened."
<< std::endl;
exit(1);
}
std::cout << "Solution written in file " << fileName << std::endl;
outfile << agentLack.getDoubleValue() << std::endl;
outfile << agentExcess.getDoubleValue() << std::endl;
outfile << agentDayLength.getValue() << std::endl;
for (int a = 0; a < nbAgents; ++a) {
for (int i = 0; i < nbTasks; ++i) {
for (int t = 0; t < horizon; ++t) {
outfile << agentStart[a][i][t].getValue() << " ";
}
outfile << std::endl;
}
outfile << std::endl;
}
outfile.close();
}
};
int main(int argc, char** argv) {
if (argc < 2) {
std::cout << "Usage: workforce_scheduling instanceFile "
<< "[outputFile] [timeLimit]" << std::endl;
exit(1);
}
const char* instanceFile = argv[1];
const char* outputFile = argc > 2 ? argv[2] : NULL;
const char* strTimeLimit = argc > 3 ? argv[3] : "30";
WorkforceScheduling model(instanceFile);
try {
model.readInstance(instanceFile);
const int timeLimit = atoi(strTimeLimit);
model.solve(timeLimit);
if (outputFile != NULL)
model.writeSolution(outputFile);
return 0;
} catch (const std::exception& e) {
std::cerr << "An error occurred: " << e.what() << std::endl;
return 1;
}
}- Compilation / Execution (Windows)
-
copy %HX_HOME%\bin\Hexaly.NET.dll .csc BinPackingConflicts.cs /reference:Hexaly.NET.dllWorkforceScheduling instances\2tasks.txt
using System;
using System.IO;
using System.Collections.Generic;
using Hexaly.Optimizer;
public class WorkforceScheduling : IDisposable
{
// Number of agents
private int nbAgents;
// Number of tasks
private int nbTasks;
// Start of the day for each agent
private int[] startDay;
// End of the day for each agent
private int[] endDay;
// Time horizon : number of days
private int nbDays;
// Time horizon : number of time steps
private int horizon;
// Maximum and minimum worked hours per day
private int MIN_WORKING_TIME = 4;
private int MAX_WORKING_TIME = 8;
// Duration of each task
private int[] taskDuration;
// Number of agents needed for each task at each time
private int[,] agentsNeeded;
// Daily disponibilities of each agent
private int[,] dayDispo;
// Hour disponibilities of each agent on working days
private int[,] hourDispo;
// The agent is available at time t
private int[,] agentDispo;
// The agent is able to perform the task i
private int[,] agentSkills;
// The agent is able to perform the task i and complete it
// before the end of the day
private int[,,] agentCanStart;
// Hexaly Optimizer
private HexalyOptimizer optimizer;
// Decision variable
private HxExpression[,,] agentStart;
// Agent working time per day
private HxExpression[,] agentWorkingTime;
// Attributed number of agents for each task
private HxExpression[,] attributedAgents;
// Difference between needed number of agents and attributed number
// of agents for each task
private HxExpression[,] agentDiff;
// Indicators for lack and excess of agents
private HxExpression agentLack;
private HxExpression agentExcess;
// Difference between first and last hour of agents each day
private HxExpression[,] agentDayStart;
private HxExpression[,] agentDayEnd;
private HxExpression agentDayLength;
public WorkforceScheduling()
{
optimizer = new HexalyOptimizer();
}
public void ReadInstance(string fileName)
{
using (StreamReader input = new StreamReader(fileName))
{
nbAgents = int.Parse(input.ReadLine());
nbTasks = int.Parse(input.ReadLine());
nbDays = int.Parse(input.ReadLine());
horizon = nbDays * 24;
// The duration of each task
input.ReadLine();
taskDuration = new int[nbTasks];
for (int i = 0; i < nbTasks; ++i)
{
taskDuration[i] = int.Parse(input.ReadLine());
}
// Number of agents needed for the task i at time t
// agentsNeeded[i][t] contains the number of agents needed
// for the task i at time t
input.ReadLine();
input.ReadLine();
agentsNeeded = new int[nbTasks, horizon];
for (int d = 0; d < nbDays; ++d)
{
for (int i = 0; i < nbTasks; ++i)
{
string[] splitted = input.ReadLine().Split(' ');
for (int h = 0; h < 24; ++h)
{
int t = d * 24 + h;
agentsNeeded[i, t] = int.Parse(splitted[h]);
}
}
input.ReadLine();
}
// Agent disponibility
// dayDispo[a][d] = 1 if agent a is available on day d
dayDispo = new int[nbAgents, nbDays];
for (int a = 0; a < nbAgents; ++a)
{
string[] splitted = input.ReadLine().Split(' ');
for (int d = 0; d < nbDays; ++d)
{
dayDispo[a, d] = int.Parse(splitted[d]);
}
}
// Hour disponibility
input.ReadLine();
hourDispo = new int[nbAgents, 24];
startDay = new int[nbAgents];
endDay = new int[nbAgents];
for (int a = 0; a < nbAgents; ++a)
{
string[] splitted = input.ReadLine().Split(' ');
startDay[a] = int.Parse(splitted[0]);
endDay[a] = int.Parse(splitted[1]);
for (int h = 0; h < 24; ++h)
{
if ((h >= startDay[a]) && (h < endDay[a]))
{
hourDispo[a, h] = 1;
}
else
{
hourDispo[a, h] = 0;
}
}
}
// We can concatenate these two informations
// into a global indicator of agent disponibility
// agentDispo[a][t] = 1 if agent a is available
// on time t
agentDispo = new int[nbAgents, horizon];
for (int a = 0; a < nbAgents; ++a)
{
for (int d = 0; d < nbDays; ++d)
{
for (int h = 0; h < 24; ++h)
{
int t = 24 * d + h;
agentDispo[a, t] = dayDispo[a, d] * hourDispo[a, h];
}
}
}
// Agent skills
// agentSkills[a][i] = 1 if agent a is able to perform the task i
input.ReadLine();
agentSkills = new int[nbAgents, nbTasks];
for (int a = 0; a < nbAgents; ++a)
{
string[] splitted = input.ReadLine().Split(' ');
for (int i = 0; i < nbTasks; ++i)
{
agentSkills[a, i] = int.Parse(splitted[i]);
}
}
// We can use all these informations and task length to get an
// indicator telling us if the agent a can begin the task i
// at time t, and complete it before the end of day
agentCanStart = new int[nbAgents, nbTasks, horizon];
for (int a = 0; a < nbAgents; ++a)
{
for (int i = 0; i < nbTasks; ++i)
{
for (int d = 0; d < nbDays; ++d)
{
for (int h = 0; h < startDay[a]; ++h)
{
int t = 24 * d + h;
agentCanStart[a, i, t] = 0;
}
int endPossible = endDay[a] - taskDuration[i] + 1;
for (int h = startDay[a]; h < endPossible; ++h)
{
int t = 24 * d + h;
agentCanStart[a, i, t] =
agentDispo[a, t] * agentSkills[a, i];
}
for (int h = endPossible; h < 24; ++h)
{
int t = 24 * d + h;
agentCanStart[a, i, t] = 0;
}
}
}
}
}
}
public void Dispose()
{
optimizer.Dispose();
}
// Returns the first time step s such that
// [s, s + duration) intersects time t
public int intersectionStart(int t, int duration)
{
return Math.Max(t - duration + 1, 0);
}
public void Solve(int timeLimit)
{
// Declare the optimization model
HxModel model = optimizer.GetModel();
// Definition of the decision variable :
// agentStart[a][i][t] = 1 if agent a starts the task i at time t
agentStart = new HxExpression[nbAgents, nbTasks, horizon];
for (int a = 0; a < nbAgents; ++a)
{
for (int i = 0; i < nbTasks; ++i)
{
for (int t = 0; t < horizon; ++t)
{
agentStart[a, i, t] = model.Bool();
}
}
}
// An agent can only work if he is able to complete his task
// before the end of the day
for (int a = 0; a < nbAgents; ++a)
{
for (int i = 0; i < nbTasks; ++i)
{
for (int t = 0; t < horizon; ++t)
{
model.Constraint(
agentStart[a, i, t] <= agentCanStart[a, i, t]
);
}
}
}
// Each agent can only work on one task at a time
for (int a = 0; a < nbAgents; ++a)
{
for (int i1 = 0; i1 < nbTasks; ++i1)
{
for (int i2 = 0; i2 < nbTasks; ++i2)
{
for (int t1 = 0; t1 < horizon; ++t1)
{
int t2Start = intersectionStart(t1, taskDuration[i2]);
for (int t2 = t2Start; t2 < t1 + 1; ++t2)
{
if ((i1 != i2) || (t1 != t2))
{
model.Constraint(
agentStart[a, i1, t1] +
agentStart[a, i2, t2] <= 1
);
}
}
}
}
}
}
// Working time per agent
agentWorkingTime = new HxExpression[nbAgents, nbDays];
for (int a = 0; a < nbAgents; ++a)
{
for (int d = 0; d < nbDays; ++d)
{
agentWorkingTime[a, d] = model.Sum();
for (int i = 0; i < nbTasks; ++i)
{
for (int t = 24 * d; t < 24 * (d + 1); ++t)
{
agentWorkingTime[a, d].AddOperand(
agentStart[a, i, t] * taskDuration[i]
);
}
}
}
}
// Minimum and maximum amount of time worked
for (int a = 0; a < nbAgents; ++a)
{
for (int d = 0; d < nbDays; ++d)
{
if (dayDispo[a, d] == 1)
{
model.Constraint(
agentWorkingTime[a, d] >= MIN_WORKING_TIME
);
model.Constraint(
agentWorkingTime[a, d] <= MAX_WORKING_TIME
);
}
}
}
// Difference between needed and attributed number
// of agents for each task
agentDiff = new HxExpression[nbTasks, horizon];
attributedAgents = new HxExpression[nbTasks, horizon];
for (int i = 0; i < nbTasks; ++i)
{
for (int t0 = 0; t0 < horizon; ++t0)
{
attributedAgents[i, t0] = model.Sum();
for (int a = 0; a < nbAgents; ++a)
{
int tStart = intersectionStart(t0, taskDuration[i]);
for (int t = tStart; t < t0 + 1; ++t)
{
attributedAgents[i, t0].AddOperand(agentStart[a, i, t]);
}
}
agentDiff[i, t0] =
agentsNeeded[i, t0] - attributedAgents[i, t0];
}
}
// Indicators for lack and excess of agents
// Agent Lack
agentLack = model.Sum();
for (int i = 0; i < nbTasks; ++i)
{
for (int t = 0; t < horizon; ++t)
{
HxExpression lack = model.Max(agentDiff[i, t], 0);
agentLack.AddOperand(model.Pow(lack, 2));
}
}
// Agent Excess
agentExcess = model.Sum();
for (int i = 0; i < nbTasks; ++i)
{
for (int t = 0; t < horizon; ++t)
{
HxExpression excess = model.Max(-1 * agentDiff[i, t], 0);
agentExcess.AddOperand(model.Pow(excess, 2));
}
}
// Difference between first and last hour of agents each day
agentDayLength = model.Sum();
for (int a = 0; a < nbAgents; ++a)
{
for (int d = 0; d < nbDays; ++d)
{
HxExpression endWork = model.Max();
HxExpression startWork = model.Min();
for (int i = 0; i < nbTasks; ++i)
{
for (int t = 24 * d; t < 24 * (d + 1); ++t)
{
endWork.AddOperand(
(t + taskDuration[i]) * agentStart[a, i, t]
);
startWork.AddOperand(
t + (1 - agentStart[a, i, t]) * horizon
);
}
}
HxExpression dayLength = model.Max(endWork - startWork, 0);
agentDayLength.AddOperand(dayLength);
}
}
// Minimize the agent lack, agent excess and agent day length
model.Minimize(agentLack);
model.Minimize(agentExcess);
model.Minimize(agentDayLength);
model.Close();
// Parameterize the optimizer
optimizer.GetParam().SetTimeLimit(timeLimit);
optimizer.Solve();
}
public void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
Console.WriteLine("Solution written in file " + fileName);
output.WriteLine(agentLack.GetDoubleValue());
output.WriteLine(agentExcess.GetDoubleValue());
output.WriteLine(agentDayLength.GetValue());
for (int a = 0; a < nbAgents; ++a)
{
for (int i = 0; i < nbTasks; ++i)
{
for (int t = 0; t < horizon; ++t)
{
output.Write(agentStart[a, i, t].GetValue() + " ");
}
output.WriteLine();
}
output.WriteLine();
}
}
}
public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: WorkforceScheduling 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] : "30";
using (WorkforceScheduling model = new WorkforceScheduling())
{
model.ReadInstance(instanceFile);
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}- Compilation / Execution (Windows)
-
javac WorkforceScheduling.java -cp %HX_HOME%\bin\hexaly.jarjava -cp %HX_HOME%\bin\hexaly.jar;. WorkforceScheduling instances\2tasks.txt
- Compilation / Execution (Linux)
-
javac WorkforceScheduling.java -cp /opt/hexaly_14_0/bin/hexaly.jarjava -cp /opt/hexaly_14_0/bin/hexaly.jar:. WorkforceScheduling instances/2tasks.txt
import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;
public class WorkforceScheduling {
// Number of agents
private int nbAgents;
// Number of tasks
private int nbTasks;
// Start of the day for each agent
private int[] startDay;
// End of the day for each agent
private int[] endDay;
// Time horizon : number of days
private int nbDays;
// Time horizon : number of time steps
private int horizon;
// Maximum and minimum worked hours per day
private int MIN_WORKING_TIME = 4;
private int MAX_WORKING_TIME = 8;
// Duration of each task
private int[] taskDuration;
// Number of agents needed for each task at each time
private int[][] agentsNeeded;
// Daily disponibilities of each agent
private int[][] dayDispo;
// Hour disponibilities of each agent on working days
private int[][] hourDispo;
// The agent is available at time t
private int[][] agentDispo;
// The agent is able to perform the task i
private int[][] agentSkills;
// The agent is able to perform the task i and complete it
// before the end of the day
private int[][][] agentCanStart;
// Hexaly Optimizer
final HexalyOptimizer optimizer;
// Decision variable
private HxExpression[][][] agentStart;
// Agent working time per day
private HxExpression[][] agentWorkingTime;
// Attributed number of agents for each task
private HxExpression[][] attributedAgents;
// Difference between needed number of agents and attributed number
// of agents for each task
private HxExpression[][] agentDiff;
// Indicators for lack and excess of agents
private HxExpression agentLack;
private HxExpression agentExcess;
// Difference between first and last hour of agents each day
private HxExpression[][] agentDayStart;
private HxExpression[][] agentDayEnd;
private HxExpression agentDayLength;
public WorkforceScheduling(HexalyOptimizer optimizer) throws IOException {
this.optimizer = optimizer;
}
public void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
input.useLocale(Locale.ROOT);
nbAgents = input.nextInt();
nbTasks = input.nextInt();
nbDays = input.nextInt();
horizon = 24 * nbDays;
// Duration of each task
input.nextLine();
taskDuration = new int[nbTasks];
for (int i = 0; i < nbTasks; ++i) {
taskDuration[i] = input.nextInt();
}
// Number of agents needed for the task i at time t
// agentsNeeded[i][t] contains the number of agents needed
// for the task i at time t
input.nextLine();
input.nextLine();
agentsNeeded = new int[nbTasks][horizon];
for (int d = 0; d < nbDays; ++d) {
for (int i = 0; i < nbTasks; ++i) {
for (int h = 0; h < 24; ++h) {
int t = d * 24 + h;
agentsNeeded[i][t] = input.nextInt();
}
}
input.nextLine();
}
// Agent disponibility
// dayDispo[a][d] = 1 if agent a is available on day d
dayDispo = new int[nbAgents][nbDays];
for (int a = 0; a < nbAgents; ++a) {
for (int d = 0; d < nbDays; ++d) {
dayDispo[a][d] = input.nextInt();
}
}
// Hour disponibility
input.nextLine();
hourDispo = new int[nbAgents][24];
startDay = new int[nbAgents];
endDay = new int[nbAgents];
for (int a = 0; a < nbAgents; ++a) {
startDay[a] = input.nextInt();
endDay[a] = input.nextInt();
for (int h = 0; h < 24; ++h) {
if ((h >= startDay[a]) && (h < endDay[a])) {
hourDispo[a][h] = 1;
} else {
hourDispo[a][h] = 0;
}
}
}
// We can concatenate these two informations
// into a global indicator of agent disponibility
// agentDispo[a][t] = 1 if agent a is available
// on time t
agentDispo = new int[nbAgents][horizon];
for (int a = 0; a < nbAgents; ++a) {
for (int d = 0; d < nbDays; ++d) {
for (int h = 0; h < 24; ++h) {
int t = 24 * d + h;
agentDispo[a][t] = dayDispo[a][d] * hourDispo[a][h];
}
}
}
// Agent skills
// agentSkills[a][i] = 1 if agent a is able to perform the task i
input.nextLine();
agentSkills = new int[nbAgents][nbTasks];
for (int a = 0; a < nbAgents; ++a) {
for (int i = 0; i < nbTasks; ++i) {
agentSkills[a][i] = input.nextInt();
}
}
// We can use all these informations and task length to get an
// indicator telling us if the agent a can begin the task i
// at time t, and complete it before the end of day
agentCanStart = new int[nbAgents][nbTasks][horizon];
for (int a = 0; a < nbAgents; ++a) {
for (int i = 0; i < nbTasks; ++i) {
for (int d = 0; d < nbDays; ++d) {
for (int h = 0; h < startDay[a]; ++h) {
int t = 24 * d + h;
agentCanStart[a][i][t] = 0;
}
int endPossible = endDay[a] - taskDuration[i] + 1;
for (int h = startDay[a]; h < endPossible; ++h) {
int t = 24 * d + h;
agentCanStart[a][i][t] =
agentDispo[a][t] * agentSkills[a][i];
}
for (int h = endPossible; h < 24; ++h) {
int t = 24 * d + h;
agentCanStart[a][i][t] = 0;
}
}
}
}
}
}
// Returns the first time step s such that
// [s, s + duration) intersects time t
public int intersectionStart(int t, int duration) {
return Math.max(t - duration + 1, 0);
}
public void solve(int timeLimit) {
// Declare the optimization model
HxModel model = optimizer.getModel();
// Definition of the decision variable :
// agentStart[a][i][t] = 1 if agent a starts the task i at time t
agentStart = new HxExpression[nbAgents][nbTasks][horizon];
for (int a = 0; a < nbAgents; ++a) {
for (int i = 0; i < nbTasks; ++i) {
for (int t = 0; t < horizon; ++t) {
agentStart[a][i][t] = model.boolVar();
}
}
}
// An agent can only work if he is able to complete his task
// before the end of the day
for (int a = 0; a < nbAgents; ++a) {
for (int i = 0; i < nbTasks; ++i) {
for (int t = 0; t < horizon; ++t) {
model.constraint(
model.leq(agentStart[a][i][t], agentCanStart[a][i][t])
);
}
}
}
// Each agent can only work on one task at a time
for (int a = 0; a < nbAgents; ++a) {
for (int i1 = 0; i1 < nbTasks; ++i1) {
for (int i2 = 0; i2 < nbTasks; ++i2) {
for (int t1 = 0; t1 < horizon; ++t1) {
int t2Start = intersectionStart(t1, taskDuration[i2]);
for (int t2 = t2Start; t2 < t1 + 1; ++t2) {
if ((i1 != i2) || (t1 != t2)) {
model.constraint(
model.leq(
model.sum(
agentStart[a][i1][t1],
agentStart[a][i2][t2]
),
1
)
);
}
}
}
}
}
}
// Working time per agent
agentWorkingTime = new HxExpression[nbAgents][nbDays];
for (int a = 0; a < nbAgents; ++a) {
for (int d = 0; d < nbDays; ++d) {
agentWorkingTime[a][d] = model.sum();
for (int i = 0; i < nbTasks; ++i) {
for (int t = 24 * d; t < 24 * (d + 1); ++t) {
agentWorkingTime[a][d].addOperand(
model.prod(agentStart[a][i][t], taskDuration[i])
);
}
}
}
}
// Minimum and maximum amount of time worked
for (int a = 0; a < nbAgents; ++a) {
for (int d = 0; d < nbDays; ++d) {
if (dayDispo[a][d] == 1) {
// 4 <= agentWorkingTime <= 8
model.constraint(
model.geq(agentWorkingTime[a][d], MIN_WORKING_TIME)
);
model.constraint(
model.leq(agentWorkingTime[a][d], MAX_WORKING_TIME)
);
}
}
}
// Difference between needed and attributed number
// of agents for each task
agentDiff = new HxExpression[nbTasks][horizon];
attributedAgents = new HxExpression[nbTasks][horizon];
for (int i = 0; i < nbTasks; ++i) {
for (int t0 = 0; t0 < horizon; ++t0) {
attributedAgents[i][t0] = model.sum();
for (int a = 0; a < nbAgents; ++a) {
int tStart = intersectionStart(t0, taskDuration[i]);
for (int t = tStart; t < t0 + 1; ++t) {
attributedAgents[i][t0].addOperand(agentStart[a][i][t]);
}
}
agentDiff[i][t0] =
model.sub(agentsNeeded[i][t0], attributedAgents[i][t0]);
}
}
// Indicators for lack and excess of agents
// Agent Lack
agentLack = model.sum();
for (int i = 0; i < nbTasks; ++i) {
for (int t = 0; t < horizon; ++t) {
HxExpression lack = model.max(agentDiff[i][t], 0);
agentLack.addOperand(model.pow(lack, 2));
}
}
// Agent Excess
agentExcess = model.sum();
for (int i = 0; i < nbTasks; ++i) {
for (int t = 0; t < horizon; ++t) {
HxExpression excess = model.max(
model.prod(-1, agentDiff[i][t]),
0
);
agentExcess.addOperand(model.pow(excess, 2));
}
}
// Difference between first and last hour of agents each day
agentDayLength = model.sum();
for (int a = 0; a < nbAgents; ++a) {
for (int d = 0; d < nbDays; ++d) {
HxExpression endWork = model.max();
HxExpression startWork = model.min();
for (int i = 0; i < nbTasks; ++i) {
for (int t = 24 * d; t < 24 * (d + 1); ++t) {
endWork.addOperand(
model.prod(
(t + taskDuration[i]),
agentStart[a][i][t]
)
);
startWork.addOperand(
model.sum(
t,
model.prod(
model.sub(1, agentStart[a][i][t]),
horizon
)
)
);
}
}
HxExpression dayLength = model.max(
model.sub(endWork, startWork),
0
);
agentDayLength.addOperand(dayLength);
}
}
// Objectives
model.minimize(agentLack);
model.minimize(agentExcess);
model.minimize(agentDayLength);
model.close();
// Parameterize the optimizer
optimizer.getParam().setTimeLimit(timeLimit);
optimizer.solve();
}
public void writeSolution(String fileName) throws IOException {
try (PrintWriter output = new PrintWriter(fileName)) {
System.out.println("Solution written in file " + fileName);
output.println(agentLack.getDoubleValue());
output.println(agentExcess.getDoubleValue());
output.println(agentDayLength.getValue());
for (int a = 0; a < nbAgents; ++a) {
for (int i = 0; i < nbTasks; ++i) {
for (int t = 0; t < horizon; ++t) {
output.print(agentStart[a][i][t].getValue() + " ");
}
output.println();
}
output.println();
}
}
}
public static void main(String[] args) {
if (args.length < 1) {
System.out.println("Usage: java WorkforceScheduling instanceFile " +
"[outputFile] [timeLimit]");
System.exit(1);
}
String instanceFile = args[0];
String outputFile = args.length > 1 ? args[1] : null;
String strTimeLimit = args.length > 2 ? args[2] : "30";
try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
WorkforceScheduling model = new WorkforceScheduling(optimizer);
model.readInstance(instanceFile);
model.solve(Integer.parseInt(strTimeLimit));
if (outputFile != null) {
model.writeSolution(outputFile);
}
} catch (Exception ex) {
System.err.println(ex);
ex.printStackTrace();
System.exit(1);
}
}
}