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.

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.

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.