Popular in Sciences

Formal Sciences

Diameter rigidity for Kähler manifolds with positive bisectional curvature

Indian Institute of Science Ved Datar

Biology

Plasticity and microevolution of diatoms

University of Technology Sydney Martina Doblin

Chemistry

Statistical Mechanics for Chemistry and Materials Science

Indian Institute of Science Biman Bagchi

Formal Sciences

Rank-Based Multivariate Sarmanov for Modeling Dependence

McMaster University Anas Abdallah

Chemistry

Polyfluorene-Wrapped Carbon Nanotubes Decorated with Photocleavable Side-Chains

McMaster University Alex Adronov

Biology

Analysis of rare coding variants reveals novel genetic risk factors for type 2 diabetes

University College London David Curtis

Life Sciences

The Mouse Cortical Connectome Maintains Specificity by Distinct Connectivity Profiles

Monash University Răzvan Gămănuţ

Combining optimisation and simulation using logic-based Benders decomposition

View more insights in Sciences - Mathematics - Formal Sciences

View more figures from University of Queensland

View the page of Michael Forbes

Read the Study

Operations Research practitioners often want to model complicated functions that are difficult to encode in their underlying optimisation framework. Michael Forbes discusses a new approach to integrating simulation into the optimisation model itself.

Image courtesy of interviewee. May 30, 2024

Generating Workspace

Export as PDF

This video discusses a case study involving a student researching staff scheduling in nursing homes to minimize client waiting times under a fixed budget. The study highlights the challenges of linking the simulation of waiting times with the optimization of staff schedules. Traditional literature has not adequately addressed this problem, which is similar to staffing issues in airline check-in environments.

The goal is to combine simulation and optimization processes to create a more efficient staffing model, avoiding the need for separate iterative steps. The conversation includes exploring the implications of this combined approach in various contexts, such as emergency services and hospital emergency rooms, where demand and service times are unpredictable.

Key findings include that a relatively small number of simulated scenarios—around hundreds rather than thousands—can yield stable and useful results. The research indicates that it's feasible to integrate simulated effects directly into the optimization framework, leading to a general model for managing queues in uncertain environments. This video approach also opens up opportunities to address more complex queue management issues while still ensuring that the solutions remain practical, albeit without a guarantee of mathematical optimality. This video concludes by acknowledging the potential for further investigation into various queuing arrangements and the development of solutions that are "close enough" to optimal.

Language:

Export as PDF

X-TIMESTAMP-MAP:LOCAL=00:00:00.000,MPEGTS=900000

00:00.365 --> 00:03.845
I had a student who was looking at a nursing home

00:04.895 --> 00:06.045
issue to start off with.

00:06.265 --> 00:10.925
So, scheduling staff in nursing home, they had a fixed,

00:11.225 --> 00:14.045
budget and they wanted to schedule those staff so as

00:14.045 --> 00:18.765
to minimize the waiting time that, the,

00:19.065 --> 00:22.125
the, the, clients in the nursing home had

00:22.125 --> 00:24.085
to wait when they, had a request.

00:24.225 --> 00:27.845
And, a lot of the, some of the requests were timetabled,

00:27.845 --> 00:29.805
like you knew when you were going to have

00:29.805 --> 00:31.285
to take a meal to somebody.

00:31.595 --> 00:34.485
Some of them had quite loose time windows, like activities,

00:34.485 --> 00:35.965
like making beds and these sorts of things.

00:36.545 --> 00:40.605
But there are a lot of ad hoc unplanned activities such as,

00:40.945 --> 00:42.525
that essentially when people

00:42.525 --> 00:43.765
press the buzzer in their room.

00:44.745 --> 00:47.685
And, the idea was to try

00:47.685 --> 00:49.965
and work out within the fixed budget

00:50.225 --> 00:52.125
how the staff should be scheduled,

00:52.315 --> 00:54.965
like when the half hour time unit session start on,

00:54.965 --> 00:58.085
and when the shifts would be so as to minimize the overall,

00:58.385 --> 01:01.315
waiting time of the,

01:01.975 --> 01:03.395
of the occupants of the nursing home.

01:04.015 --> 01:06.635
Now, to estimate that waiting time,

01:06.635 --> 01:08.555
you've gotta run a simulation,

01:09.335 --> 01:12.675
and trying to link together the optimization step.

01:12.735 --> 01:16.275
And the simulation step was, was the difficulty.

01:16.415 --> 01:18.395
So that's where the problem originally came from.

01:18.905 --> 01:21.275
Most of the literature in the nursing home context hadn't,

01:21.375 --> 01:24.435
really considered the problem in this way.

01:24.435 --> 01:26.675
There was some, we found some literature in

01:27.395 --> 01:28.915
checking counters for airlines.

01:29.065 --> 01:30.235
It's sort of a similar problem.

01:30.255 --> 01:33.155
You've gotta staff your checking counters,

01:33.575 --> 01:35.595
and there you're really looking at a trade off

01:35.595 --> 01:39.955
between the cost of, staff on the checking counters

01:40.095 --> 01:43.875
and the cost of the cuing time of passengers

01:43.875 --> 01:45.835
that has some sort of long-term costs,

01:45.895 --> 01:47.995
at least in that context.

01:48.165 --> 01:50.515
There were some optimization models that really,

01:51.695 --> 01:54.755
in the optimization part of it, had a very,

01:54.905 --> 01:59.315
very course approximation of the QME time,

02:00.495 --> 02:03.315
and then subsequently ran some simulations

02:03.535 --> 02:05.995
and then sort of tried to update the approximation.

02:05.995 --> 02:07.915
And they were very clunky. It wasn't obvious

02:07.915 --> 02:09.475
that they gave very good solutions at all.

02:10.095 --> 02:14.795
Um, so because they weren't considering the, the impact

02:14.795 --> 02:16.275
of the simulation of queuing time

02:16.275 --> 02:18.195
during the optimization directly.

02:18.775 --> 02:21.075
Uh, so that was the, the state of the art that we found

02:21.075 --> 02:23.475
before we started, looking at it.

02:23.815 --> 02:27.675
And, it's something that, we'd been thinking about

02:27.695 --> 02:29.795
for quite a long time was whether it was going

02:29.795 --> 02:32.675
to be possible to combine, simulation

02:32.675 --> 02:35.755
and optimization without a,

02:36.225 --> 02:37.675
essentially an outer loop.

02:37.855 --> 02:39.595
The, so

02:39.595 --> 02:42.635
to combine them while you're doing the optimization in the

02:42.635 --> 02:45.475
past, people would do some optimization,

02:45.705 --> 02:46.875
then do some simulation,

02:46.975 --> 02:49.155
and then change the parameters of the optimization

02:49.455 --> 02:51.035
and, and run around it.

02:51.035 --> 02:53.675
But we wanted to, to, to combine them into one process.

02:54.185 --> 02:56.755
It's essentially designed for queuing environments

02:57.015 --> 03:01.605
and for queuing environments where, you can,

03:02.025 --> 03:04.685
you, you have times where you get to change,

03:05.425 --> 03:07.125
the level of service.

03:07.465 --> 03:10.005
So, and checking counters are a good example,

03:10.145 --> 03:12.085
but any sort of killing environment like that

03:12.615 --> 03:15.125
where there's some randomness with the arrival patterns

03:15.185 --> 03:16.365
and with the service times.

03:16.785 --> 03:21.485
And, and this is true in, in both those contexts,

03:21.665 --> 03:22.925
airlines and,

03:23.705 --> 03:25.405
and nursing homes, airline checking

03:25.405 --> 03:26.525
counters and nursing homes.

03:26.585 --> 03:29.325
But there could be, you know, lots of other examples.

03:29.745 --> 03:33.525
Uh, you know, perhaps even in things like taxi ranks,

03:33.525 --> 03:35.685
there was a related problem which we didn't include in the

03:35.885 --> 03:40.445
paper, which, worked fine, which was for allocating,

03:40.705 --> 03:43.125
ambulance crews to ambulance stations.

03:44.105 --> 03:47.565
So, so it has applications in the emergency services

03:47.565 --> 03:51.605
context, so that, you know, a wide variety

03:51.605 --> 03:54.005
of applications where you demand is uncertain

03:54.065 --> 03:56.085
and you're trying to get a trade off between

03:56.825 --> 04:01.405
either a fixed budget or, or cost of resources.

04:01.545 --> 04:02.925
So a fixed budget for resources

04:02.925 --> 04:04.205
or resources costing something,

04:04.425 --> 04:06.685
and you're trying within that to minimize

04:06.685 --> 04:11.445
or to trade off the, the delay cost to the customers.

04:11.795 --> 04:14.605
This is really something you look at in a

04:15.005 --> 04:16.205
a planning context.

04:16.705 --> 04:21.285
So at the moment, I would say it's, it's, it's not,

04:21.395 --> 04:22.805
it's not the realtime decision.

04:22.865 --> 04:25.045
The realtime decision is a simulation decision.

04:25.715 --> 04:30.085
This is the decision around what your staffing levels or,

04:30.305 --> 04:31.365
or, or are going

04:31.365 --> 04:34.445
to be in each time period over your planning horizon.

04:34.945 --> 04:36.845
And it's, it's really the, the sort

04:36.845 --> 04:37.965
of the day ahead problem.

04:38.625 --> 04:43.205
Uh, so this is the, the day ahead short term,

04:44.075 --> 04:45.725
plan, but it's not the day

04:45.725 --> 04:47.885
of operations live decision making.

04:48.195 --> 04:50.125
Okay? There are other things to consider in the day

04:50.125 --> 04:51.725
of operations life decision making,

04:52.185 --> 04:54.485
but that day ahead, it can definitely be done.

04:54.665 --> 04:57.165
So, and, and should be done.

04:57.625 --> 04:59.365
How many cases do you have to simulate?

04:59.505 --> 05:01.245
So while we're running the optimization,

05:01.305 --> 05:03.365
we have a standard set of scenarios

05:03.365 --> 05:05.445
that we're repeatedly simulating,

05:06.305 --> 05:09.765
but also where we can take an approximation of

05:09.765 --> 05:11.805
that simulation and consider it dynamically

05:11.805 --> 05:12.885
during the optimization.

05:13.185 --> 05:16.605
The issue is how many scenarios do you need for the

05:17.255 --> 05:19.165
simulation results to be stable?

05:19.875 --> 05:21.485
Okay? So,

05:21.555 --> 05:24.685
because the more scenarios you considering,

05:24.825 --> 05:28.165
the the slower it's going to be to run,

05:28.345 --> 05:30.125
but there will be a trade off

05:30.125 --> 05:31.405
where adding more simulations

05:31.405 --> 05:32.525
just doesn't change the answer.

05:32.985 --> 05:36.205
Uh, and we discovered that that was a relatively,

05:36.905 --> 05:40.805
low numbers of scenarios being simulated, so sort

05:40.805 --> 05:42.845
of like the low hundreds, rather than having

05:42.845 --> 05:45.925
to simulate thousands or tens of thousands of scenarios.

05:46.185 --> 05:47.405
And this is really important.

05:47.665 --> 05:50.565
So, that was an important aspect of,

05:50.745 --> 05:54.765
of recognizing the stability that you get in the solution

05:54.765 --> 05:57.005
with relatively low numbers of simulations.

05:58.245 --> 06:02.975
Another important conclusion was that the, the number

06:03.115 --> 06:04.335
of times we have

06:04.335 --> 06:08.495
to consider those simulations is way less than if you did a

06:08.585 --> 06:11.535
brute force search of the simulation space, so

06:11.635 --> 06:12.695
of the solution space.

06:13.035 --> 06:17.095
So you might have a solution space who's, whose size is,

06:17.395 --> 06:20.455
say approximately sort of 10 to, to 25

06:20.475 --> 06:22.575
or something like that candidate solution.

06:22.575 --> 06:24.615
She can't possibly search all of those.

06:25.515 --> 06:29.815
Uh, and in finding the optimal solution over

06:29.815 --> 06:33.775
that solution space, we only have to do, let's say,

06:34.735 --> 06:37.455
a million solutions, a million simulations.

06:37.835 --> 06:41.495
So, this is really the, the key implication is

06:41.495 --> 06:44.895
that we don't have to run, we don't have

06:44.895 --> 06:48.135
to simulate the scenarios many times in the absolute scheme

06:48.135 --> 06:50.215
of things, you know, a millions still a decent number,

06:50.235 --> 06:53.255
but it's not, it's nothing right handed the 25.

06:54.075 --> 06:56.975
And that we don't have to have many scenarios

06:56.975 --> 06:58.415
that we simulate to get good answers.

06:58.515 --> 07:01.695
So those, those implications were great

07:01.875 --> 07:05.535
and it means that there's now a general framework

07:05.595 --> 07:09.575
for including, simulate simulations

07:09.995 --> 07:11.615
inside the optimization.

07:12.035 --> 07:14.775
So rather than separating those steps, so rather than having

07:14.835 --> 07:17.015
to approximate the impact of simulations

07:17.635 --> 07:20.855
before we do optimizations,

07:21.555 --> 07:23.055
we can consider them dynamically.

07:23.995 --> 07:26.215
And this opens up a whole bunch of areas.

07:26.835 --> 07:29.895
The, the main areas we consider we're just a couple of,

07:30.595 --> 07:32.255
we just wanna have a couple of reference areas,

07:32.435 --> 07:35.455
but we think it has quite a lot of,

07:35.885 --> 07:39.895
extensibility even into more dynamic queuing situations.

07:40.075 --> 07:44.435
So one area we didn't consider in the paper was queuing in,

07:44.815 --> 07:48.275
in emergency rooms at hospitals.

07:48.295 --> 07:50.275
So this is a, this is a big issue

07:50.275 --> 07:52.115
because you have to look at how

07:52.115 --> 07:53.995
to allocate your staff into different areas

07:53.995 --> 07:56.435
because people move from one queue into another queue,

07:56.785 --> 07:58.315
they effectively get triaged

07:58.415 --> 08:00.515
and they move from one queue to other queues.

08:00.615 --> 08:03.195
And, the allocation of staff

08:03.375 --> 08:05.675
to the different areas in which they queue then

08:05.675 --> 08:06.955
becomes very important.

08:08.175 --> 08:09.515
Now, there'll be problems

08:09.515 --> 08:14.035
where the simulation process doesn't meet the strict

08:14.315 --> 08:18.035
mathematical requirements to give

08:18.635 --> 08:20.635
a guaranteed optimal solution.

08:20.945 --> 08:23.755
Okay? So the vendor's decomposition framework we use

08:23.755 --> 08:27.295
for this, the, there's sort

08:27.295 --> 08:29.335
of strict rules about guaranteeing

08:29.445 --> 08:30.935
that you have the optimal solution.

08:31.465 --> 08:34.335
We're also interested in similar problems

08:34.345 --> 08:37.935
where while we can't guarantee the optimal solution, we sort

08:37.935 --> 08:40.095
of get close enough solution

08:40.095 --> 08:42.095
and we can give some ality guarantee.

08:42.115 --> 08:44.535
We can say, well, this might not be the optimal solution.

08:44.535 --> 08:47.895
We can't be sure, but you'll be within 1%

08:47.995 --> 08:49.055
or, or close enough.

08:49.235 --> 08:52.175
So we call this sort of close enough vendors decomposition

08:52.475 --> 08:54.855
and, we're investigating that space as

08:54.855 --> 08:55.855
Well. So

08:55.855 --> 08:58.525
yeah, more complicated queuing arrangements

08:58.945 --> 09:02.445
and situations in which while we can't guarantee

09:02.445 --> 09:05.565
mathematically op mathematical optimality anymore, we can,

09:06.105 --> 09:08.205
give very, very good practical solutions.

00:00 - I had a student who was looking at a nursing home issue to start off with. So, scheduling staff in nursing home, they had a fixed, budget and they wanted to schedule those staff so as to minimize the waiting time that, the, the, the, clients in the nursing home had

00:22 - to wait when they, had a request. And, a lot of the, some of the requests were timetabled, like you knew when you were going to have to take a meal to somebody. Some of them had quite loose time windows, like activities, like making beds and these sorts of things. But there are a lot of ad hoc unplanned activities such as, that essentially when people press the buzzer in their room. And, the idea was to try

00:47 - and work out within the fixed budget how the staff should be scheduled, like when the half hour time unit session start on, and when the shifts would be so as to minimize the overall, waiting time of the, of the occupants of the nursing home. Now, to estimate that waiting time, you've gotta run a simulation, and trying to link together the optimization step. And the simulation step was, was the difficulty.

01:16 - So that's where the problem originally came from. Most of the literature in the nursing home context hadn't, really considered the problem in this way. There was some, we found some literature in checking counters for airlines. It's sort of a similar problem. You've gotta staff your checking counters, and there you're really looking at a trade off between the cost of, staff on the checking counters and the cost of the cuing time of passengers

01:43 - that has some sort of long-term costs, at least in that context. There were some optimization models that really, in the optimization part of it, had a very, very course approximation of the QME time, and then subsequently ran some simulations and then sort of tried to update the approximation. And they were very clunky. It wasn't obvious that they gave very good solutions at all. so because they weren't considering the, the impact

02:14 - of the simulation of queuing time during the optimization directly. so that was the, the state of the art that we found before we started, looking at it. And, it's something that, we'd been thinking about for quite a long time was whether it was going to be possible to combine, simulation and optimization without a, essentially an outer loop. The, so

02:39 - to combine them while you're doing the optimization in the past, people would do some optimization, then do some simulation, and then change the parameters of the optimization and, and run around it. But we wanted to, to, to combine them into one process. It's essentially designed for queuing environments and for queuing environments where, you can, you, you have times where you get to change, the level of service.

03:07 - So, and checking counters are a good example, but any sort of killing environment like that where there's some randomness with the arrival patterns and with the service times. And, and this is true in, in both those contexts, airlines and, and nursing homes, airline checking counters and nursing homes. But there could be, you know, lots of other examples. you know, perhaps even in things like taxi ranks,

03:33 - there was a related problem which we didn't include in the paper, which, worked fine, which was for allocating, ambulance crews to ambulance stations. So, so it has applications in the emergency services context, so that, you know, a wide variety of applications where you demand is uncertain and you're trying to get a trade off between either a fixed budget or, or cost of resources. So a fixed budget for resources or resources costing something,

04:04 - and you're trying within that to minimize or to trade off the, the delay cost to the customers. This is really something you look at in a a planning context. So at the moment, I would say it's, it's, it's not, it's not the realtime decision. The realtime decision is a simulation decision. This is the decision around what your staffing levels or, or, or are going to be in each time period over your planning horizon.

04:34 - And it's, it's really the, the sort of the day ahead problem. so this is the, the day ahead short term, plan, but it's not the day of operations live decision making. Okay? There are other things to consider in the day of operations life decision making, but that day ahead, it can definitely be done. So, and, and should be done. How many cases do you have to simulate?

04:59 - So while we're running the optimization, we have a standard set of scenarios that we're repeatedly simulating, but also where we can take an approximation of that simulation and consider it dynamically during the optimization. The issue is how many scenarios do you need for the simulation results to be stable? Okay? So, because the more scenarios you considering,

05:24 - the the slower it's going to be to run, but there will be a trade off where adding more simulations just doesn't change the answer. and we discovered that that was a relatively, low numbers of scenarios being simulated, so sort of like the low hundreds, rather than having to simulate thousands or tens of thousands of scenarios. And this is really important. So, that was an important aspect of,

05:50 - of recognizing the stability that you get in the solution with relatively low numbers of simulations. Another important conclusion was that the, the number of times we have to consider those simulations is way less than if you did a brute force search of the simulation space, so of the solution space. So you might have a solution space who's, whose size is, say approximately sort of 10 to, to 25 or something like that candidate solution.

06:22 - She can't possibly search all of those. and in finding the optimal solution over that solution space, we only have to do, let's say, a million solutions, a million simulations. So, this is really the, the key implication is that we don't have to run, we don't have to simulate the scenarios many times in the absolute scheme of things, you know, a millions still a decent number, but it's not, it's nothing right handed the 25. And that we don't have to have many scenarios

06:56 - that we simulate to get good answers. So those, those implications were great and it means that there's now a general framework for including, simulate simulations inside the optimization. So rather than separating those steps, so rather than having to approximate the impact of simulations before we do optimizations, we can consider them dynamically. And this opens up a whole bunch of areas.

07:26 - The, the main areas we consider we're just a couple of, we just wanna have a couple of reference areas, but we think it has quite a lot of, extensibility even into more dynamic queuing situations. So one area we didn't consider in the paper was queuing in, in emergency rooms at hospitals. So this is a, this is a big issue because you have to look at how to allocate your staff into different areas because people move from one queue into another queue,

07:56 - they effectively get triaged and they move from one queue to other queues. And, the allocation of staff to the different areas in which they queue then becomes very important. Now, there'll be problems where the simulation process doesn't meet the strict mathematical requirements to give a guaranteed optimal solution. Okay? So the vendor's decomposition framework we use

08:23 - for this, the, there's sort of strict rules about guaranteeing that you have the optimal solution. We're also interested in similar problems where while we can't guarantee the optimal solution, we sort of get close enough solution and we can give some ality guarantee. We can say, well, this might not be the optimal solution. We can't be sure, but you'll be within 1% or, or close enough.

08:49 - So we call this sort of close enough vendors decomposition and, we're investigating that space as Well. So yeah, more complicated queuing arrangements and situations in which while we can't guarantee mathematically op mathematical optimality anymore, we can, give very, very good practical solutions.

Faculti AI can make mistakes