optimize days between work shift

Question

For a work shift optimization problem, I've defined a binary variable in PuLP as follows:

pulp.LpVariable.dicts('VAR', (range(D), range(N)), 0, 1, 'Binary')

where

1. $D =$ # days in each schedule we create (= 28, or 4 weeks)
2. $N =$ # of workers

and the variable $VAR$ represents whether worker $J$ works in Day $I$ or not.

I want to ensure that work is evenly distributed over the 28 days (a.k.a $VAR$ for worker $J$ should look more like [1,0,0,0,1,0,0,0,0,1,...,var[i=27][J]] rather than [1,1,1,0,0,0,0,0,...,var[i=27][J]] where work is clustered in the beginning). Since I can't add if statements/access the values of variables before they are defined, an approach where we minimize the range in days between work shifts doesn't seem feasible (since the work shifts themselves haven't been allocated yet). What could be a way to model this optimization problem?

Answer 1

You can enforce "no more than $w$ workdays in any consecutive $d$-day period" via linear constraints $$\sum_{i=t}^{t+d-1} x_i \le w \quad \text{for all $t$}$$

Answer 2

If you cannot enforce a specific maximum days policy as Rob Pratt suggests, another possibility is to penalize the lumpiness of the work distribution. Pick a window size $d$ (Rob's "$d$-day period"), and add two new variables $y$ and $z$ along with the constraints $$y \ge \sum_{i=t}^{t+d-1} x_i \quad \forall t \in \lbrace1,\dots,D-d+1\rbrace$$and $$z \le \sum_{i=t}^{t+d-1} x_i \quad \forall t \in \lbrace1,\dots,D-d+1\rbrace.$$Now penalize $y-z$ in your objective function.

Answer 3

Maybe you could approach it from the opposite direction?

Instead of imposing a penalty on uneven distributions, first generate a set of highly even candidate work schedules. Then if the optimizer fails to find a solution, iteratively generate and add less evenly distributed work schedules.

This method would allow you to use whatever metric you like for "evenness". The major costs being that you'd almost certainly be unable to achieve optimality, and that you might not find a solution for complex problems.