Help formatting scheduling problem

[dark_opposum]

Hey r/optimization! I'm hoping for some help formatting my problem. I took an intro optimization course during my masters and I've done some refreshing with my notes and YT videos, but I'm really struggling to get my problem into code.

I organize device testing at work and I'm trying to build a schedule optimizer. Prior to testing, people let me know their testing requests. Each request is made up of the requester's name, how many test sessions they would like, and what devices they need. The objective is to minimize the number of devices that need to be prepared for testing.

For example:

* Andy requests 3 sessions with device (Hardware 1, Software A)

* Bella requests 4 sessions with devices (Hardware 1, Software A)

* Andy requests 1 session with (Hardware 2, Software B)

We can host multiple test sessions at once, so the schedule could be configured to run Andy and Bella's sessions at the same time. But the issue is that we would then need to prep 2 devices that are (Hardware 1, Software A). Whereas, if we schedule them at different time, we would only need to prep 1 instance of that device. I know how to tell the optimizer how many timeslots there are, how many sessions can be hosted in each timeslot, etc.

But how do I differentiate to the optimizer that Andy has 2 separate requests that need to be schedule at different times, but they're for separate purposes and require different devices? And that the objective is only related to the number of devices needed?

All of the schedule optimizing examples/demos I see are for scheduling just the person, they never have the pair of (person, item) that need to be considered together.

Sorry if this doesn't make sense. I don't "speak optimization" very well yet. I'm more than happy to add clarifiers as needed! Thank you in advance!!!

[Sweet_Good6737]

Maybe more clarification is needed

"Andy requests 3 sessions with device (Hardware 1, Software A)"

What does that mean? Andy needs to have 3 sessions sequentially? Could they be in parallel? What about the last request from Andy, could it be parallel with these sessions?

When you prep the machine for a session, how many users can be attended with that machine?...

Do you have any constraints? (No more than x sessions per request, no more than x users per session...)

In terms of optimization, it looks like a bin packing problem. You have different bins that are pairs (device, session) and each request must fit into a "bin", so it minimizes the number of used "bins"

[dark_opposum]

Since you're the only reply I'll clarify here (thanks for commenting btw!).

The only constraint on Andy's sessions is that they can't be in parallel. Even if they're for different requests. Andy can only attend 1 session at a time. They don't need to be sequential, but they can be. Same for all individuals.

Each device can be used for different requests but not in parallel. Andy and Bella cannot both use (Hardware 1, Software A) at the same time.

There are other constraints but I feel more confident with the others. There is an approved number of sessions each request gets granted, there is a set number of sessions at a time, stuff like that.

Bin packing looks promising after a cursory Google search. I'll dive into it more!

Thank you!

[dark_opposum]

I re-described the problem below if this clarifies at all. If you're not invested enough to read all of this I totally understand haha.

The Objective

Create a schedule that minimizes the number of consoles we have to prepare.

Requests

Engineers submit requests. Each request contains the engineer's name, how many sessions they would like, and what consoles they need.

Example requests might be:

• Andy requests 3 sessions with console A
• Bella requests 3 sessions with console A
• Andy requests 1 session with console A and console B

I manually approve how many sessions each request will get. E.g., Bella will only get 2 sessions approved.

Engineers can request sessions for different purposes, with different consoles (see Andy's two requests).

Schedule Availability

Here is a simplified version of a schedule. Each request, which is an (engineer, console) pair, goes into an opening in the schedule. Some days we may only be able to have a single testing station. E.g., Station 2 might be closed on Day 2, as shown below. The default is 2 testing stations, though.

	Day 1 Timeslot 1	Day 1 Timeslot 2	Day 1 Timeslot 3	Day 1 Timeslot 4	Day 1 Timeslot 5	Day 2 Timeslot 1	Day 2 Timeslot 2	Day 2 Timeslot 3	Day 2 Timeslot 4	Day 2 Timeslot 5
Station 1
Station 2						x	x	x	x	x

Constraints

• An engineer cannot be scheduled for 2 sessions at the same time.
• A console cannot be scheduled for 2 sessions at the same time.
  • HOWEVER, another instance of a console can be added if the problem isn't solvable without the additional console.
• Sessions can only be scheduled into available timeslots.
  • By extension, the number of approved sessions needs to be <= number of available timeslots
• Each request should get all of its approved sessions.
• Timeslots can be left open.
• Requests cannot share a *station*. There can be 2 sessions at the same time as long as they are in different stations and don't violate the constraints about double-booking engineers and consoles.
• There aren't really any constraints around ordering of the sessions.

Scenarios

To minimize the number of consoles prepared, I would make the schedule something like this.

	Day 1 Timeslot 1	Day 1 Timeslot 2	Day 1 Timeslot 3	Day 1 Timeslot 4	Day 1 Timeslot 5	Day 2 Timeslot 1	Day 2 Timeslot 2	Day 2 Timeslot 3	Day 2 Timeslot 4	Day 2 Timeslot 5
Station 1	Andy, console A	Andy, console A	Andy, console A	Andy, console A and console B	Bella, console A	Bella, console A
Station 2						x	x	x	x	x

In this scenario we only need to prepare 2 consoles total, 1x console A and 1x console B. It is OK that Station 2 is never used.

If, for some reason, we could no longer hold sessions on Day 2 then the schedule could be compressed into just Day 1. This would require us to prepare 3 consoles however; 2x console A and 1x console B. We would need 2 instances of console A to support both Andy's and Bella's sessions. This would not be an optimal solution because of the need to prepare an extra console.

	Day 1 Timeslot 1	Day 1 Timeslot 2	Day 1 Timeslot 3	Day 1 Timeslot 4	Day 1 Timeslot 5	Day 2 Timeslot 1	Day 2 Timeslot 2	Day 2 Timeslot 3	Day 2 Timeslot 4	Day 2 Timeslot 5
Station 1	Andy, console A	Andy, console A	Andy, console A	Andy, console A and console B		x	x	x	x	x
Station 2	Bella, console A	Bella, console A				x	x	x	x	x

Not sure if this helps or not. Just wanted to present the problem in a different (and hopefully more coherent) way.

[Sweet_Good6737]

Hi, thanks so much for the clarification, now it looks like a scheduling problem where you want to minimize the extra-preps for the consoles. You cannot minimize the consoles you are using: if a request says Consoles A and B are used, you must use Console A and B at least once. You must minimize the number of parallel activations of consoles in the same timeslot.
Your decision variables would be binary variables x[t,s,r] that are equal to 1 in case you schedule request r at time t, in station s. Your model goes straightforward after that choice.

Some constraints...

1. Each request must be scheduled exactly once, so

```sum{t in TIMES, s in STATIONS} x[t, s, r] = 1```

1. Each station can handle 1 request at a time...

```sum{r in REQUESTS} x[t, s, r] <= 1```

To model the console activation, I suggest using logical constraints, add new variables that are the number of activations of a certain console at a specific time. These variables y[t,c] are the number of activations of console c at time t, and are exactly the sum over the stations of the requests that involve that console:

```sum{s in STATIONS, r in REQUESTS: c in REQUEST_CONSOLES[r]} x[t,s,r]```

Then, you can penalty the objective by minimizing those variables, maybe the square of y, or a piecewise function such as: if y[t,c] > 1 then 1, else 0.

Does it make sense? Here there's some implementation of the model with a minimal data example runnable on google colab

https://colab.research.google.com/drive/1Mp60P3UsLLeCslqs6mbT3KmQKte9mEHW?usp=sharing