# Binary Integer Programming Problem II

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})$$

-

Based on my experience, the quadratic term in the objective makes your formulation less than practical. I am almost sure there are codes out there to solve quadratic integer programs (I have never used one myself), I'd still go on with reformulating the problem as an integer linear program (ILP), even if losing some expressiveness, and using a standard ILP solver tool to obtain a solution.

Regarding your problem, I'd try to enforce the "all workers work about the same amount of time" constraint by making $h$ a problem variable, add the constraint

$\sum_{p=1}^{P}\sum_{t=1}^{T} u_{pt} x_{pt}^i \le h \qquad \forall i \in \{1, \ldots, n\}$

and go on with the objective

$\min h$ .

Then, any convenient modeling and solver tool would be usable (I'd try GLPK first with MathProg and, if it proves too slow, then some non-free software like IBM ILOG CPLEX).

-
Thanks for giving this some thought. I had lost hope that anyone would respond. I ended up solving this problem a couple months ago by writing up a fairly straightforward branch and bound algorithm in matlab. It worked even better when an element of randomness was included in the bounding criterion. When I have some time I will have a look at the strategy you propose. –  ben Nov 14 '11 at 20:44