I need to schedule shifts in $p$ workplaces over $T$ days for $n$ workers. And I must do it in such a way that all workers work about the same amount of time over the $T$ days, and so that each worker gets r days of rest during the $T$ days.
I would appreciate some advice on how I might go about solving it (branch and bound?), or if it is even solvable at all.
I have attempted to formulate the problem below. For the objective function I chose the sum of squared deviations from an equal distribution of labor among the $n$ workers. The constant $h$ is a judiciously chosen target value that should be close to the amount of hours each worker is contracted to work over the T days, but also big enough so that $ h \gt \sum_{p=1}^{P} \sum_{t=1}^{T} x_{pt}^{i} u_{pt} .$ By minimizing this objective function, the work burden is most equitably distributed.
The $u_{pt}$ variable represents a shift on a particular day (indexed by $t$) and in a particular workplace (indexed by $p$), expressed in units of hours. The $x_{pt}^{i}$ variable is a binary integer variable ($0$ or $1$). In addition to the $p,t$ indices, the "$i$" superscript indexes the worker filling the shift. For example, $x_{pt}^{i}=0$ indicates that worker $i$ is not filling the shift at place $p$ on day $t$.
The three constraints ensure, respectively, 1) The workers are in one place at one time; 2) There is only one worker in a given time and workplace; 3) Workers receive $r$ days of rest during the $T$ day work period.
If I'm not mistaken, this means there are $Tn+PT+n$ constraints. In the concrete problem I am trying to solve, $T=7,n=7,P=7,r=2$.
$\min_{x_{pt}^{i}}\; \; \;\sum_{i=1}^{n}\left [ h- \sum_{p=1}^{P}\sum_{t=1}^{T}x_{pt}^{i}u_{pt} \right ]^2 $
s.t.
$\sum_{p=1}^{P}x_{pt}^{i}=1 \quad \forall t,i \quad (nT \text{ constraints})$
$ \sum_{i=1}^{n} x_{pt}^{i}=1 \quad \forall p,t \quad (PT \text{ constraints}) $
$ \sum_{p=1}^{P} \sum_{t=1}^{T} x_{pt}^{i} = T-r \quad \forall i \quad (n \text{ constraints}) $