CODEWITHSUNDEEP
algorithmoptimizationschedulingapproximation
Ewybe
Ewybe

Reputation: 405

Schedule shifts for people working in pairs

I would schedule shifts in a way that people works in pair.
1. The principal constraint is that from time to time each person should not work with the person which he have worked in the previous shift.
2. There aren't constraint about the time of the shifts, I just need to match a pair with a day.

For example if {A,B.. F} representing people then
Day 1: A-B Day 2: C-D Day 3: E-F Day 4: A-B <--- Wrong, because so (1.) is violated

My solution is:
Define a fitness function T, so then T(A) is equal to 0 if A worked today or T(A)=c if A worked for the last time c days ago.
The steps would be:

  1. Inizialize pairs randomly (respecting the costraints obviously)
  2. Create a new pair (i,j) : take the element(the person) i with the highest fitness and the element j with the second highest fitness values provinding that T(j)!=T(i). (In way to don't ensure different a pair each time)
  3. Update

There are a better way to solve a problem? There is something similar in literature so I can consult? Like similar problems for examples? Is the nurse shitfs problems similar to this?

Thank you.

Upvotes: 1

Views: 955

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58310

Your problem is underspecified, leading to trivial solutions. For example, pick any three people, {A, B, C}, and schedule AB, AC, BC (repeating).

If you want a fairer solution: keep picking a random pair each day until you find a viable pair. There's at most N non-viable pairs and N(N-1)/2 possible pairs.

Here's one way to do it:

import random

def schedule(folk):
    excluded = dict((p, None) for p in folk)
    while True:
        while True:
            a, b = random.sample(folk, 2)
            if excluded[a] != b and excluded[b] != a:
                break
        excluded[a], excluded[b] = b, a
        yield a, b

for a, b in schedule('ABCDE'):
    print '%s%s' % (a, b),

Upvotes: 1

Related Questions