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

uff. i don't follow you description, but in similar situations i have used sql to solve this kind of problem. if you are using php i guess you have sql available.

what i would suggest doing is finding a way of storing this information into a set of tables and then working out what sql query gives you the answer you want. quite often it's a lot simpler to do in sql than it is in a procedural language.

for the skipped part, for example, you might have a column which records when someone was last assigned, and then order by that (so that you select the person who has not been assigned for a long time). alternatively, you could have the number of times skipped as a column and order by that.

Answer 2

Your solution will depend on data sizes. How many employees, positions and rules are there?

Answer 3

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.

Answer 4

What I understand is there are 'm' members and 'n' positions.

Category: a group of positions -- a member who is assigned one position in the category can't have another?

Group: a group of positions -- positions in the same group must be assigned on different days.

Last thing, a Position has a list of members who can fill it.

Looking at this from a data-structure point of view, put the members in a linked list -- each member has to have an additional list of [position, day] that they are finally assigned. Then, for each position, have a list of references to the members that can fill that position. Implement categories as another list of references for a position as to which categories it is in.

The actual assignment: have a day counter = 0, and iterate through the positions. For each position P, iterate through the members that can fill it. A member M can fill the position if:

• Any position he has filled P2 doesn't share a category with P.
• Any position he has filled P2 with day = daycounter doesn't share a group with P.

If he can fill the position, the [position, day] pair is added to the member, and the member's node is moved to the END of the list (this is why references are necessary -- all the references are still valid even though the node moved). This ensures that the 'skipped' members are given highest priority, and the members who weren't reached were given next highest priority.

Once a position is filled, go to the next position. If the position shares a group with a position already assigned, skip it, iterating through all the positions until you can assign as many positions as you can on day 1. Then, increment the day counter and repeat for day 2. This should give you a maximal assignment (not sure about maximum) for all the jobs.

Tip: when moving a member to the end of the member list, to prevent having to traverse the list, keep a reference to the end -- for the next position, you need to start from the beginning anyway, so there's no point going through the whole thing.