Labs scheduling#
Description: Model for laboratories scheduling. Some labs are needed to handle requests from researchers, and departments have to assign labs and locations to the requests.
The problem is a MILP with two objectives for penalties, solved with Ampl + Highs using advanced modeling techniques.
Tags: facility location, highs, mip, mixed-integer-linear, scheduling, multi-objective, mp
Notebook author: Marcos Dominguez Velad <marcos@ampl.com>
Model author: Marcos Dominguez Velad <marcos@ampl.com>
# Install dependencies
%pip install -q amplpy
# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook
ampl = ampl_notebook(
modules=["highs"], # modules to install
license_uuid="default", # license to use
) # instantiate AMPL object and register magics
The problem#
The problem consists in scheduling a list of request to book laboratory rooms in order avoid conflicts.
There are multiple departments containing laboratories, and each laboratory is different. Staff in charge of the departments is limited, so it is necessary to minimize the simultaneous usage of a same type of lab in different departments. The reservations are related to a certain timeslot.
Each request consists on a person-in-charge name and a list of laboratories.
There is a list of departments.
There is a list of available timeslots.
Rules:
Each request must be attended once.
Each department can handle only one request in a timeslot.
A person may have ordered more than one request, but they cannot be attended in the same timeslot (even if they are in different departments).
Ideally, a lab may be used in a single department at a time. If a lab of the same type may be used in other departments in parallel, but this should only be done if there are no available timeslots.
Solving the problem with ampl community edition + highs open-source MILP solver.
https://amplpy.ampl.com/en/latest/
https://highs.dev
Data#
Example with 7 timeslots. Three people are ordering labs, Adam, Bella, and Charlie. Adam request to book a Lab of type ‘A’ and a Lab of type ‘B’ in the same session, a session in a Lab A, and another session in a Lab B. Similarly, Bella needs a session in Labs A and B, and another session only in Lab A. Finally, Charlie needs to book simultaneously Labs A and C.
We assume there are 2 departments. Each department has a lab of each type available.
# Sample data
times = range(1,7)
departments = ['Department 1', 'Department 2']
requests = [('Adam',['Lab A', 'Lab B']),
('Adam',['Lab A']),
('Bella',['Lab A', 'Lab B']),
('Bella',['Lab A']),
('Adam',['Lab B']),
('Charlie',['Lab A', 'Lab C'])
]
requests_id_name = {i: name for i,(name,c) in enumerate(requests)}
A valid scheduling for the data would be:
Requests |
1 |
2 |
3 |
4 |
5 |
|---|---|---|---|---|---|
Department 1 |
R4 |
R0 |
R1 |
R2 |
R3 |
Department 2 |
R5 |
In the first timeslot, Adam’s request for Lab B is scheduled in Department 1, and Charlie’s request will be scheduled in Department 2.
In the second timeslot, we will let Adam use Labs A and B in Department 1.
In the third slot, Adam will use Lab A. In the fourth slot, Bella will use Labs A and B, and in the fifth slot, Bella will use Lab A.
Only 5 slots were necessary to handle the requests, and the staff of the same kind of Lab do not split over departments, as it was desired.
In the following section, we are going to describe a model to solve this problem for larger instances.
Model#
Sets#
TIMES: Set of time slots.DEPARTMENTS: Set of departments.REQUESTS: Set of requests.REQUEST_LABS[r]: Set of labs required for request r.LABS: Set of all labs,
Parameters#
REQUEST_NAME[r]: Person name associated with request r.
Variables#
x[t, s, r]: Binary variable, equals 1 if request r is assigned to department s at time t, otherwise 0.y[t, c]: Number of usages of lab c at time t.Penalty_Usage: Penalty incurred for using a lab more than once at a timeslot.Penalty_Time: Penalty for the timing of requests.
Constraints#
Assignment Constraint#
Each request must be assigned exactly once:
Department Capacity Constraint#
Each department can handle at most one request at a time:
Person Assignment Constraint#
Each person can only be assigned to one department at any time:
Should loop over the name space and look for constraints such that name = name[r].
Usage Count#
The number of usages of lab c at time t is:
Objective Function#
We are going to have 2 objective functions so that we can first minimize the simultaneous usage of the same Lab in different departments. After that, we are going to minimize the number of necessary timeslots to accomplish the schedule.
Where:
The penalty will count the number of labs of the same type that are used more than once at the same time. If there are more than one, the penalty for that kind of Lab will be 1 (for each timeslot). Notice that the expression inside the sum of Penalty_Usage is a non-linear expression that is being reformulated with Ampl into a linear constraint. Read more about automatic reformulations and advanced modeling features in
https://mp.ampl.com/model-guide.html
See how multi-objectives are handled below in the model.
%%writefile labs.mod
reset;
set TIMES; # Set of time slots 1..t
set DEPARTMENTS; # Set of departments
set REQUESTS; # id
set REQUEST_LABS {REQUESTS};
param REQUEST_NAME {REQUESTS} symbolic;
# total labs
set LABS := union{r in REQUESTS} REQUEST_LABS[r];
var x{TIMES, DEPARTMENTS, REQUESTS} binary; # Assignment variable
# Schedule a request once
subject to assign_once{r in REQUESTS}:
sum{t in TIMES, s in DEPARTMENTS} x[t, s, r] = 1; # Each request is assigned exactly once
# each time, each department, at most 1 request
subject to department_capacity{t in TIMES, s in DEPARTMENTS}:
sum{r in REQUESTS} x[t, s, r] <= 1; # Each request is assigned at most once
# each person only at one department at most
# so no more than 1 request with the same person at the same time
subject to person_in_one_department{ t in TIMES, r in REQUESTS }:
sum{s in DEPARTMENTS, rr in REQUESTS: REQUEST_NAME[r] == REQUEST_NAME[rr]} x[t,s,rr] <= 1;
# number of usages of lab c in time t
var y {t in TIMES, c in LABS}
= sum{s in DEPARTMENTS, r in REQUESTS: c in REQUEST_LABS[r]} x[t,s,r];
# if we used a lab more than once, add '1' to the objective (as a penalty that should be minimized)
# while if the lab is used only once, add '0' to the objective (so add nothing)
var Penalty_Usage = sum{t in TIMES, c in LABS} (if y[t,c] <= 1 then 0 else 1);
# do it as soon as possible
var Penalty_Time = sum{t in TIMES, s in DEPARTMENTS, r in REQUESTS} t * x[t, s, r];
# Suffix to assign priority to the multiple objectives
suffix objpriority;
# this is a penalty over number of usages per lab, y[t,c] is ideally 1, if more, it penalties the objective
minimize Extra_Usages: Penalty_Usage
suffix objpriority 10; # most prioritary objective
# this is a penalty over time, the latest we assign, the bigger the penalty
minimize Delay: Penalty_Time
suffix objpriority 1; # least prioritary objective
Overwriting labs.mod
Solving#
# Define data for the problem
def simple_problem():
times = range(1,6+1)
departments = ['Department 1', 'Department 2']
requests = [('Adam',['Lab A', 'Lab B']),
('Adam',['Lab A']),
('Bella',['Lab A', 'Lab B']),
('Bella',['Lab A']),
('Adam',['Lab B']),
('Charlie',['Lab A', 'Lab C'])
]
requests_id_name = {i: name for i,(name,c) in enumerate(requests)}
return (times, departments, requests, requests_id_name)
# Define data for the problem
def bigger_problem():
times = range(1,12+1)
departments = ['Department 1', 'Department 2', 'Department 3']
requests = [('Adam',['Lab A', 'Lab B']),
('Adam',['Lab A']),
('Bella',['Lab A', 'Lab B']),
('Bella',['Lab C']),
('Bella',['Lab A', 'Lab B']),
('Adam',['Lab B', 'Lab D', 'Lab A']),
('Adam',['Lab C']),
('Adam',['Lab B', 'Lab D', 'Lab C']),
('Charlie',['Lab A', 'Lab C']),
('Charlie',['Lab A', 'Lab B', 'Lab C', 'Lab D']),
('Dave',['Lab A', 'Lab C']),
('Dave',['Lab C']),
('Charlie',['Lab A', 'Lab C']),
('Emilia',['Lab A', 'Lab B']),
('Dave',['Lab B']),
('Charlie',['Lab A', 'Lab C']),
('Dave',['Lab A', 'Lab D']),
('Dave',['Lab B', 'Lab C']),
('Emilia',['Lab D', 'Lab B']),
('Emilia',['Lab C', 'Lab A'])
]
requests_id_name = {i: name for i,(name,c) in enumerate(requests)}
return (times, departments, requests, requests_id_name)
problem_data = bigger_problem()
from amplpy import AMPL
def load_data(model, problem_data):
times, departments, requests, requests_id_name = problem_data
model.set['TIMES'] = times
model.set['DEPARTMENTS'] = departments
model.set['REQUESTS'] = [i for i in requests_id_name.keys()]
# labs are in the second element of requests[i], so requests[i][1]
model.set['REQUEST_LABS'] = {i:requests[i][1] for i in requests_id_name.keys()}
model.param['REQUEST_NAME'] = requests_id_name
# Debug or show the model
# model.display('REQUESTS')
# model.display('REQUEST_LABS')
# model.display('REQUEST_NAME')
# model.display('DEPARTMENTS')
# model.display('TIMES')
# model.eval('expand;')
# create an ampl object to read the model
ampl.read('labs.mod')
load_data(ampl, problem_data)
# solve with solver highs
solver='highs'
ampl.option['highs_options'] = 'obj:multi=2 outlev=1' # verbose output and multi-objective
ampl.solve(solver=solver)
HiGHS 1.7.1: obj:multi = 2
tech:outlev = 1
==============================================================================
MULTI-OBJECTIVE MODE: starting with 2 objectives (2 combined) ...
==============================================================================
==============================================================================
Running HiGHS 1.7.1 (git hash: dcf3813): Copyright (c) 2024 HiGHS under MIT licence terms
MULTI-OBJECTIVE MODE: objective 1 (out of 2) ...
==============================================================================
Coefficient ranges:
Matrix [1e+00, 4e+01]
Cost [1e+00, 1e+00]
Bound [1e+00, 5e+01]
RHS [1e+00, 4e+01]
Presolving model
392 rows, 816 cols, 6012 nonzeros 0s
164 rows, 768 cols, 3612 nonzeros 0s
164 rows, 768 cols, 3612 nonzeros 0s
Objective function is integral with scale 1
Solving MIP model with:
164 rows
768 cols (768 binary, 0 integer, 0 implied int., 0 continuous)
3612 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s
R 0 0 0 0.00% 0.0263157895 10 99.74% 0 0 0 74 0.0s
C 0 0 0 0.00% 0.0263157895 9 99.71% 202 16 0 142 0.1s
L 0 0 0 0.00% 0.0263157895 1 97.37% 352 56 0 801 1.3s
Solving report
Status Optimal
Primal bound 1
Dual bound 1
Gap 0% (tolerance: 0.01%)
Solution status feasible
1 (objective)
0 (bound viol.)
1.44328993201e-15 (int. viol.)
0 (row viol.)
Timing 1.34 (total)
0.02 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 1517 (total)
0 (strong br.)
727 (separation)
714 (heuristics)
MULTI-OBJECTIVE MODE: objective 2 (out of 2) ...
==============================================================================
Coefficient ranges:
Matrix [1e+00, 4e+01]
Cost [1e+00, 1e+01]
Bound [1e+00, 5e+01]
RHS [1e+00, 4e+01]
Presolving model
393 rows, 817 cols, 6061 nonzeros 0s
165 rows, 769 cols, 3661 nonzeros 0s
165 rows, 768 cols, 3660 nonzeros 0s
Objective function is integral with scale 1
Solving MIP model with:
165 rows
768 cols (768 binary, 0 integer, 0 implied int., 0 continuous)
3660 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s
0 0 0 0.00% 77 inf inf 0 0 2 145 0.0s
R 0 0 0 0.00% 79.53888918 121 34.27% 877 121 46 3372 0.9s
Symmetry detection completed in 0.0s
Found 27 generators
L 0 0 0 0.00% 92.39830098 109 15.23% 1276 33 46 6931 7.5s
B 11 0 2 3.32% 92.39830098 108 14.45% 1295 33 299 11962 7.7s
B 35 1 15 4.69% 92.39830098 107 13.65% 1340 33 1509 14332 8.1s
Solving report
Status Optimal
Primal bound 107
Dual bound 107
Gap 0% (tolerance: 0.01%)
Solution status feasible
107 (objective)
0 (bound viol.)
2.59126053948e-13 (int. viol.)
0 (row viol.)
Timing 10.86 (total)
0.03 (presolve)
0.00 (postsolve)
Nodes 688
LP iterations 39038 (total)
7755 (strong br.)
5476 (separation)
4993 (heuristics)
==============================================================================
MULTI-OBJECTIVE MODE: done.
HiGHS 1.7.1: optimal solution; objective 1
Individual objective values:
_sobj[1] = 1
_sobj[2] = 107
39038 simplex iterations
688 branching nodes
------------ WARNINGS ------------
WARNING: "Tolerance violations"
Type MaxAbs [Name] MaxRel [Name]
objective(s) 5E+00 8E-01
Documentation: mp.ampl.com/modeling-tools.html#automatic-solution-check.
Objective = Extra_Usages
Solution#
Retrieve solution and generate a markdown table with the schedule
# Retrieve results
solution = ampl.get_solution(flat=False, zeros=False)
for t,s,r in solution['x'].keys():
print('Time ', t, ' Department ', s, ' Req ', r)
# Also, to see other outputs or objective values:
print('Objective value:', ampl.getObjective('Extra_Usages').value())
Time 1 Department Department 1 Req 1
Time 1 Department Department 1 Req 14
Time 1 Department Department 1 Req 15
Time 1 Department Department 2 Req 4
Time 1 Department Department 3 Req 12
Time 1 Department Department 3 Req 16
Time 2 Department Department 1 Req 10
Time 2 Department Department 2 Req 14
Time 2 Department Department 2 Req 16
Time 2 Department Department 3 Req 3
Time 2 Department Department 3 Req 18
Time 3 Department Department 1 Req 19
Time 3 Department Department 2 Req 0
Time 3 Department Department 2 Req 14
Time 4 Department Department 1 Req 2
Time 4 Department Department 3 Req 6
Time 5 Department Department 1 Req 3
Time 5 Department Department 1 Req 11
Time 5 Department Department 2 Req 5
Time 6 Department Department 1 Req 1
Time 6 Department Department 3 Req 17
Time 7 Department Department 1 Req 0
Time 7 Department Department 1 Req 8
Time 7 Department Department 1 Req 14
Time 7 Department Department 2 Req 11
Time 7 Department Department 3 Req 13
Time 7 Department Department 3 Req 18
Time 8 Department Department 3 Req 9
Time 9 Department Department 1 Req 7
Time 10 Department Department 2 Req 0
Time 10 Department Department 2 Req 8
Time 10 Department Department 2 Req 13
Time 11 Department Department 2 Req 12
Time 12 Department Department 3 Req 8
Objective value: 6.0
def print_solution_table(data):
table_data = {(str(department), str(time)):str(req) for time, department, req in data}
times = [str(t) for t in sorted(set([int(time) for department, time in table_data.keys()]))]
departments = sorted(set([department for department, time in table_data.keys()]))
# Step 3: Generate the markdown table
# Create the header row (with times as columns)
header = "| Slots | " + " | ".join(times) + " |"
separator = "|---" * (len(times) + 1) + "|"
# Create the rows (one row for each department)
rows = []
for department in departments:
row = f"| {department} | " + " | ".join([table_data[department, time] if table_data.get((department, time)) else "" for time in times ]) + " |"
rows.append(row)
# Combine header, separator, and rows
markdown_table = "\n".join([header, separator] + rows)
return markdown_table
# Print the markdown table
print(print_solution_table(solution['x'].keys()))
print('Extra Lab usages:', ampl.getObjective('Extra_Usages').value())
| Slots | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Department 1 | 15 | 10 | 19 | 2 | 11 | 1 | 14 | | 7 | | | |
| Department 2 | 4 | 16 | 14 | | 5 | | 11 | | | 13 | 12 | |
| Department 3 | 16 | 18 | | 6 | | 17 | 18 | 9 | | | | 8 |
Extra Lab usages: 6.0
This would be an optimal solution for the problem with 12 timeslots and 6 extra Lab usages.
Slots |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
Department 1 |
15 |
10 |
19 |
2 |
11 |
1 |
14 |
7 |
||||
Department 2 |
4 |
16 |
14 |
5 |
11 |
13 |
12 |
|||||
Department 3 |
16 |
18 |
6 |
17 |
18 |
9 |
8 |
What if we want to minimize the number of timeslots?
ampl.eval('let Delay.objpriority := 100;') # main objective
ampl.option['highs_options'] = 'obj:multi=2' # multi-objective
ampl.solve(solver=solver, verbose=False)
solution = ampl.get_solution(flat=False, zeros=False)
print(print_solution_table(solution['x'].keys()))
print('Extra Lab usages:', ampl.getObjective('Extra_Usages').value())
| Slots | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Department 1 | 4 | 12 | 13 | 2 | 16 | 6 | 5 |
| Department 2 | 18 | 10 | 14 | 1 | 0 | 9 | 3 |
| Department 3 | 17 | 19 | 7 | 8 | 15 | 11 | |
Extra Lab usages: 8.0
Solution with 7 slots and 8 extra Lab usages
Slots |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|---|---|---|---|---|---|---|---|
Department 1 |
4 |
12 |
13 |
2 |
16 |
6 |
5 |
Department 2 |
18 |
10 |
14 |
1 |
0 |
9 |
3 |
Department 3 |
17 |
19 |
7 |
8 |
15 |
11 |
AMPL Website | AMPL Colab | Community Edition | Twitter | LinkedIn