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, $$\text{LABS} = \bigcup_{r \in \text{REQUESTS}} \text{REQUEST_LABS}[r]$$

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: $$\sum_{t \in \text{TIMES}, s \in \text{DEPARTMENTS}} x[t, s, r] = 1 \quad \forall r \in \text{REQUESTS}$$

Department Capacity Constraint

Each department can handle at most one request at a time:

$$\sum_{r \in \text{REQUESTS}} x[t, s, r] \leq 1 \quad \forall t \in \text{TIMES}, \forall s \in \text{DEPARTMENTS}$$

Person Assignment Constraint

Each person can only be assigned to one department at any time:

$$\sum \limits_{\substack{s \in \text{DEPARTMENTS}, r \in \text{REQUESTS} : \ \text{name} = \text{name}[r]}} x[t, s, r] \leq 1 \quad \forall t \in \text{TIMES}, \forall \text{name} \in \text{NAMES}$$

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: $$y[t, c] = \sum_{\substack{s \in \text{DEPARTMENTS}, r \in \text{REQUESTS} : \ c \in \text{LABS}[r]}} x[t, s, r] \quad \forall t \in \text{TIMES}$$

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.

$$\text{minimize (first)} : \text{Penalty_Usage}$$

$$\text{minimize (second)} : \text{Penalty_Time}$$

Where: $$\text{Penalty_Usage} = \sum_{t \in \text{TIMES}, c \in \text{LABS}} \left( \text{if } y[t, c] \leq 1 \text{ then } 0 \text{ else } 1 \right)$$

$$\text{Penalty_Time} = \sum_{t \in \text{TIMES}, s \in \text{DEPARTMENTS}, r \in \text{REQUESTS}} t \cdot x[t, s, r]$$

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

previous

Jupyter Notebook Integration

next

Largest small polygon