0
$\begingroup$

A workforce scheduling problem MIP formulation Decision variable $x_{ij} = 1$ if shift $i$ is assigned to worker $j$, $0$ otherwise.

Objective is a sum of multiple objectives

  1. Maximize demand coverage
  2. Minimize cost
  3. Staggered meal breaks (penalize when meal breaks overlap for two shifts within an overlapping time period)
  4. Maximize worker preferences ...

Subject to

  1. One shift per day
  2. Worker min/max daily and weekly hours
  3. Worker max work days ...

For this MIP, we have a set of shifts generated by a heuristic considering the min and max shift length config from the customers. There are multiple ways to come up with this initial set of assignable shifts

  1. All possible permutations of shifts wihin min and max shift lengths and demand lengths. For example, for a set of 30 min demands starting at 9am and ending at 5pm and min shift = 2hrs and max shift = 8 hours we generate shifts like 9am-11am, 9:30am-11:30am, ..., 9am-5pm.
  2. Make the shift generation smarter by generating shifts of varying sizes and shapes for peak period but for lul periods generate only essential size and shapes (only 8 hrs shifts with a demand period deemed as 1 hr demand)
  3. Make the shift generation even smarter by incorporating worker availability and qualification -- generate less flexible shifts for the workers that are avaiable all time and for the roles that don't have varying demand

We have done #2 and #3 already but still see a huge number of shifts sent over to the optimization solver. Are there any better techniques that we can use to reduce it further. I know column generation can be a way to combine shift generation + assignment but if we want to keep the two separate, are there any ways to generate only an essential set of shifts?

Improve this question
$\endgroup$
4
  • $\begingroup$ I had worked with a similar problem last year. So, sharing a few thoughts along the same line. Happy to connect offline for deeper discussion. Instead of creating all shifts, 9:00-11:00, 9:00-11:30, 9:00-12:00, and so on, I created only sub-shifts. So, 9:00-11:00 and 11:00-13:00 put together will represent 9:00-13:00. To ensure that only one shift is used by a crew in a day, I need to ensure that the sub-shifts they are assigned to are consecutive. The requirement of number of hours is met by summing all sub-shifts they are assigned to during the day. $\endgroup$ Commented Sep 16 at 13:06
  • $\begingroup$ This process introduces some binary variables and few more constraints, but worked well for me. It is a long discussion. So, I cannot give more details here. Happy to connect over a google meet and show my model to you. My email is [email protected] $\endgroup$ Commented Sep 16 at 13:10
  • $\begingroup$ Thank you so much. I am interested in understanding your approach. Can we connect offline? $\endgroup$ Commented Sep 19 at 15:50
  • $\begingroup$ Sure. Please ping me [email protected] $\endgroup$ Commented Sep 20 at 16:54

1 Answer 1

Reset to default
-1
$\begingroup$

The number of shifts is not the primary problem.

We do demand based scheduling with 70 000 shifts and more in a single dataset. Reducing that number through pre-filtering qualification/skills/availability (#3), following the demand curve (#2) and limiting granularity (#1) are good things, but it will only get you that far. Any further tricks risk hurting schedule output quality.

The primary problem is how the memory consumption of binary variables scales in a MIP solver.

If you have 5 000 employees and 70 000 shifts, that 350 000 000 binary variables. If each of them is involved in 200 constraints formulas, that's billions of constraints. Those simply don't fit into memory. Even if you succeed into cut the number of shifts in half.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ "If each of them is involved in 200 constraints formulas, that's billions of constraints." No. That does not follow. $\endgroup$ Commented Sep 12 at 21:09
  • $\begingroup$ Why not? Let's do the math. Take a simple constraint like "at least 10 hours between two shifts". With 70k shifts across a planning horizon of 20 days, that's means on average each shift collides with around 1000 shifts. Now we add a constraint for each employee (5k), for every shift(70k) with every colliding shift (1k), that's 70b constraint instances. $\endgroup$ Commented Sep 23 at 4:48
  • $\begingroup$ @ErwinKalvelagen Or did I make a mistake in my math? $\endgroup$ Commented Sep 23 at 4:52
  • $\begingroup$ If each variable is involved in 200 constraints, we can only say that there are at least 200 constraints. (If precisely 200 constraints, we would have a completely dense block of constraints.) $\endgroup$ Commented Sep 24 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.