Given an m×n matrix P of schedule
preferences (lower is better) for m employees and
n shifts, output an m×n binary matrix
S schedule containing only zeros and ones. Each column of
S must contain exactly one 1 (all shifts must be covered). The
number of 1's in any pair of rows of S may differ by at most
one (everyone gets the same number of shifts).
We start with an identity-ish matrix of diagonal 1's of size
m×n. We randomly shuffle this matrix using Fisher-Yates.
The shuffled matrices are candidate S schedules. For each
candidate schedule, take the element-wise Hadamard product P*S.
The value P*S=C represents the costs per shift. The sum of all
elements in C is the value we want to minimize.
This scheduler imposes no specific meaning to preference values. The user
might use only values 1 and 2, where positions along the row marked 1 are
desired and positions marked 2 are not. Equivalently, the user might use
values 0 and 1, and will likely obtain very similar results. Alternatively,
the user may wish to represent intermediate preferences. For example, a user
might use the values 1, 10, and 10000 in an effort to prevent undesired
assignments. Yet another possible usage for this program might be to rank
preferences from 1..n.
There are n! possible schedules S with
n columns. We do not want to compute all of these possible
shift combinations. A greedy approach is not safe.
[ 0 1 1 ]
P = [ 1 3 3 ]
[ 1 3 3 ].
A greedy approach produces the schedule
[ 1 0 0 ]
S = [ 0 1 0 ]
[ 0 0 1 ],
but the cost of this schedule is
[ 0 0 0 ]
C = P * S = [ 0 3 0 ]
[ 0 0 3 ]
which has a sum of 6. This is not optimal; a better solution is
[ 0 1 0 ]
S' = [ 1 0 0 ]
[ 0 0 1 ],
which gives a cost of
[ 0 1 0 ]
C' = P * S' = [ 1 0 0 ]
[ 0 0 3 ]
for a total of 5.
Maybe there is a good way to solve this problem, perhaps with dynamic programming, but this feels like a problem where local search might be appropriate.
Local search is an algorithmic technique for attempting to solve intractable problems. We randomly generate some candidate solutions. From these, we look to see if we can improve them. We continue making minor tweaks until we can do no better. Local search will identify some local minimum in the search space, but there is no guarantee that this local minimum is anywhere near the global minimum.
This program begins the local search with the best candidate solution S
from our shuffle. We create ln(n)² searches S' from S
by swapping at most ln(n) columns. The use of ln(n) and ln(n)²
are not rooted in scientific rigor...they just seemed reasonable.
The process continues until the solution be improved further.