Job scheduling problem

Question

I'm working on an application where I need to automatically schedule jobs for members on a rotating schedule. I'm not very good at explaining rules, so here's some data to help out:

Positions: A job title, with rules such as Mondays and Wednesdays weekly.
Categories: A set of positions
Groups: Another set of positions. Positions in the same group cannot be assigned on the same day
Members: Users assigned to positions on a given date.

For each date in the month, members are assigned to positions (both in ascending order). If a member is assigned to a position in one category, the next time a position in the same category comes up, the next member alphabetically (or the beginning of the list) gets assigned eg.

Members: M1, M2, M3, M4
Positions in Category C1: P1, P2, P3
Members in Position P1: M1, M2, M3, M4
Members in Position P2: M1, M2, M3
Members in Position P2: M1, M3, M4

If M1 is assigned for P1, if P2 comes next, M2 will be assigned. An additional layer of complexity is introduced where if P3 comes next instead, M3 gets assigned. The system has to keep track of the fact that M2 was 'skipped' and assign M2 next if available, then assign M4 next, or wait until it gets to a position where M2 is available (this becomes additionally complex when there are many 'skipped' members).

A member will also be skipped if he has indicated he won't be available on that date. The system needs to place priority on skipped members, somehow identify them when they come up and then jump to the next logical person in the list. Skipping also applies to groups due to date clashes.

I already have a temporary [and messy] solution which I no longer understand even though I have a lot of comments in it explaining each step. Its weaknesses are in dealing with the skipped members.

If you were going to code this how would you go about it? I'm implementing this in PHP but pseudocode would work as well.

Answer 1

My solution: You need a PriorityQueue (which is available in PHP under SplPriorityQueue). The PriorityQueue gives you elements with descending priority (sorted by values, the smallest value has the highest priority).

Each member gets an assigned value. This value is an ASCII number with n digits (you could use 8 digits for convenience), filled up with zeroes to n positions. After that you append the name. You also add to each member the available positions

So (n=5):

• M1 value: 99999Albert P1,P2,P3
• M2 value: 99999Susi P1,P2
• M3 value: 99999Bob P1,P3

This makes it easy to sort members by priority and name.

Preparation:

A sunny day. You are retrieving the assigned positions and a category for a given day. Each member is loaded on a long list. Each member who is not showing up on work is not loaded, but gets his value decreased by minus two. Bob is not here, so its new value gets 99997Bob. This means that Bob will be selected automatically the next time. All other members get their value decreased by minus one.

The positions assigned for a specific Day are mapped (use SplObjectStorage):

P1->M1,M2,M3,M4 etc. P2-> etc.

The map contains only the positions which must be assigned this day. After the

Filter: You must look up the groups and delete any positions on the map which cannot be assigned this day. Your group description is a bit unclear.

Assign:

• You choose the position to assign
• Get list of members which can fill the position
• Remove available members from list and put them into the PriorityQueue
• Assign the position by extract() from PriorityQueue (correct assignment is done automaticially). Each member which is assigned will gets its value increased by one (So the decrease and increase levels out if you are here and working). If you are here and not assigned to a position for whatever reason, you get a small penalty of one. If you not here, you get a penalty of two.
• After completion, put remaining members on the list again, clear the PQueue and continue with the next assignment.

Caveats:

• You must be careful that there are always enough people for a position.