Choose N pairs of (job, time slot) with a constraint on the number of different jobs

Question

I am making a solver to choose the best assignment to a set of people for an event, given their availability (chosen in a set $T$ of time slots), jobs preferences (among $J$ possible jobs) and some of other predefined constraints. We refer to a particular pair of (job, time slot) as a "shift".

I'm not optimizing the entire workforce at once but instead I assign one person at a time.* Here's an overview of how I modeled the sub-problem:

• Enumerate the set $S$ of all possible shifts ($|S| = |J|\times|T| = 90$ in my case)
• Use an objective function related to the number of people already assigned to each shift (and the need for that shift)
• Find solution $x \in \{0,1\}^{|S|}$ that associates to each element of $S$ a value in $\{0, 1\}$

The constraints are the following:

• Each person can be assigned up to N shifts (depending on their preference)
• Up to 2 shifts during the same day
• No consecutive shifts except when the job remains the same
• Each person can do only up to two different jobs during the entire event

I managed to encode all the constraints as a linear program except the last one. Any idea on how that could be done ? If that is not possible at all (which I suspect), what tool can I use to solve this problem ?

---

* I know that is sub-optimal, but finding a better algorithm will probably be the subject of another question ;)

Answer 1

The last constraint is also no problem. You already have variables $x_{j,t}$, that say if the person works the $j$th job on the time slot $t$. Now you can introduce new binary variables $y_j$, that represent, if the person works at the job $j$ or not. Then you can model the constraint by:

$$\sum_{j \in J} y_j \le 2$$

The only part left is how you connect the information from the $x_{j,t}$ with $y_j$. But that is also not hard. If any of the $x_{j,t}$ is $1$, then you can force $y_j$ to also be $1$ with the constraints

$$y_j \ge x_{j,t}\qquad\forall t \in T, \forall j \in J$$

and force $y_j$ to $0$ if all $x_{j,t}$ are $0$. This can be done with:

$$y_j \le \sum_{t \in T} x_{j,t}\qquad\forall j \in J$$