Office Desk Rota Assignment problem

Question

This is not a home work and the question is not related to studies (I am not a student). I have to do the weekly desk rota at the office and thought this forum might help with suggestions. My problem is below:

I need help for desk allocation. In the office we are assigned different desk every day and we rotate. I need help on how to automate the rota (we can only use Excel in the office due to various reasons).

I wanted to ask if for example the "assignment problem" and linear programming would help here?

The problem:

We have 11 people and 11 desk location. Of these desk locations 7 should be assigned first to the people in the office for a day of the week and once they are all assigned, we should give the other 4. Also, every person in the office has different working pattern, so we are not the same number of people every day of the week:

    Mon      Tue      Wed     Thu    Fri
P1                    OFF            OFF
P2 OFF                        OFF
P3                    OFF
P4           OFF
P5  OFF                              OFF
.
.
.
P11

P = person

Requirement 1: The desk locations are 1 to 11 of which I have to assign location 1 to 7 first and only if there are more than 7 people in the office I should assign some of the 8 to 11 locations.

Requirement 2: P8, P9, P10 and P11 always have desk locations 1 to 7 assigned to them (they should never use desk 8 to 11).

Requirement 3: None of the people should get locations 8 to 11 more than 2 times in a week if possible.

Requirement 4: if anyone gets any of locations 8 to 11 twice, the days should not be consecutive (if that's too much we can drop the requirement)

I am not that familiar with LP and assignment problems but do you think that would would work? If you could help even with link to a similar problem I could try to do something myself first?

Answer 1

This is a typical operations research problem, and can be solved via integer linear programming, maybe apart from your requirement 4, which I cannot see an easy way to represent linearly. I will not discuss that requirement at first.

First I will introduce notation to set up this as a linear programming problem. All the variables will be integer variables, in fact binary variables. We need three indices, $k, i, j: k=1, \dotsc, K=11,\quad i=1,\dotsc,I=11,\quad j=1,\dotsc,J=5$ where $k$ represent desks, $i$ represents persons and $j$ represents weekdays. Then $P_{ij}$ is 1 when person $i$ works on weekday $j$, 0 else (this is input data, part of the problem definition). Then we have the decision variables $D_{kij}$ which is 1 if desk $k$ is occupied by person $i$ on weekday $j$, zero in other case.

Then we define the requirements:

• Persons $i=8,9,10,11$ do never occupy desks $k=8,9,10,11$: $$ \sum_{k=8}^{11} D_{kij} = 0 \quad \text{for all $j$, $i=8,9,10,11$}$$

• None of the people should occupy desks $k=8,9,10,11$ more than twice a week: $$\sum_{k=8}^{11}\sum_{j=1}^5 D_{kij} \le 2 \quad \text{$i=1,2,3,4,5,6,7$} $$

• Persons not working a day should not be assigned a desk that day: $$D_{kij}\le P_{ij}\quad \text{for all $k$ and all $i,j$}$$

Then your requirement 1 can be represented via the criterion function to be minimized, as

• $$\sum_{k=8}^{11}\sum_{i=1}^{11}\sum_{j=1}^5 D_{kij}\stackrel{!}{=} \text{min}$$

This can be implemented in any software offering binary integer linear programming. If that is accessible in excel I do not know. But there is some more work to do in translating my problem formulation into some software, as the requirements must be translated into the matrix inequality form $Ax \le b$, our array with three indices cannot be used directly. (I will come back and add an example of this in R. One example is here: Constrained assignment problem (Linear Programming, Genetic Algorithm, etc...))

As for requirement for, one could introduce terms of the form $D_{ki1}D_{ki2}+D_{ki2}D_{ki3}+D_{ki3}D_{ki4}+D_{ki4}D_{ki5}=0$, so is not a linear restriction. Transferring it to requirement that $D_{ki1}D_{ki2}+D_{ki2}D_{ki3}+D_{ki3}D_{ki4}+D_{ki4}D_{ki5}$ should be minimized, it could be included as part of the cost function. That would make for a quadratic cost function, so would need a program implementing binary integer quadratic programming. Another, simpler, approach would be to forget this requirement initially, but generate multiple (many) solutions to the integer programming problem, and then choose the best among them for requirement 4.