Search code examples
rconstraintslinear-programminginteger-programminglpsolve

lpSolve constraint for choices of start and length of shifts

I have a finite number of staff N, and I need to find an optimal schedule (using the least number of staff) meeting the demand

Hour of Day Demand
0 d0
1 d1
... ...
23 d23

where the d0, d1, ..., d23 are real numbers denoting the required amount of people on shift at that hour. Staff can only work one of a number of possible shifts with a specific start and end time given in a table. For example, it will look like this:

Person Shifts
1 0-8, 1-9, 2-10
2 8-16, 16-24
... ...
N 11-16, 15-20

So that e.g. person 1 can work from 0-8, and not work any other hour of the day, person 2 can work 8-16 and no other hour of the day, etc.

Ignoring the above constraint on the hours that each member of staff can work, the problem would reduce to:

min x1 + x2 + ... + x(N*24)

xi all binary variables

subject to the 24 constraints
x1 + x2 + ... + xN <= d0
x(N+1) + x(N+2) + ... + x(2*N) <= d1
... (similar constraints)
x(23*N+1) + x(23*N+2) + ... + x(24*N) <= d23

All of which is easy to put into lpSolve or lpSolveAPI.

I am having trouble with trying to input my constraint on the permitted shift starts/times of staff. Mathematically, for person A, this would be something like

xi + ... + x(i+7) = 8 where i is either 1, 2 or 3
xj = 0 for all other j <= 24

But I am finding this very difficult to translate into an R constraint. I have thought about using for loops but I think this is over complicating things.

Solution

  • I think you need to re-formulate your approach.

    The key decision variable here is whether person member p works shift s where the shifts appear to be particular to that person.

    So you have components:

    SETS
p ∈ People  {Bob, Tim, Cindy, ...}
s[p] ∈ Shifts, indexed by person  {1, 2, ... }
h ∈ Hours {1, ..., 24}

PARAMS
coverage[p, s[p], h] ∈ {1, 0} whether p's shift s[p] contributes to hour h
demand[h] ∈ Integers

VARS
x[p, s[p]] ∈ {1, 0} whether person p works s[p]

    With that setup, I think the problem falls into place better. It may be a little tricky to handle the indexed set for s[p] depending on the language used, but that's how I would approach this.