Algorithm or Script for Sorting Multiple User Schedules

I have a data set that will potentially look like this:

user_name
time_1
time_2
time_3

Where the times are different hours on a given day they are free. There are 22 slots each week, and the user is allowed to pick from three and submit them. I will have about 100-150 开发者_StackOverflow中文版users, and I'm wondering what is the best way to go about sorting them in such a way that distributes the amount of people evenly across each time slot. My best guess for a starting approach is to see what it looks like if all the users are put in their first slots (time_1), then 2 and 3 and compare which one gives the best results, then from there, look at what will happen if a user is added or removed from a slot and how this will affect overall performance. Any help would be appreciated as I haven't done a lot of optimization algorithms.

Regards,

I'm answering because previous answers apparently break down in cases where many people choose the same slot and many slots have no or few choosers. For example, if all users choose slots (1,2,3) in that order, topological sort will provide no help.

In the ideal situation, each person would choose one slot, and all slots would have the same number of choosers (+/- 1). If I were handling the problem myself, I'd try a first-come, first-served regime with a real-time online server, such that people can choose only from those slots that remain open at the time they log in.

If online first-come, first-served isn't feasible, I'd use a method that motivates people to choose distinct slots, possibly with an element of randomness. Here's one such method:

Let there be U people in all, vying for H time slots. (H=22.) Suppose each person is assigned to exactly one slot. Let P = [U/H] (that is, U/H truncated to integer) be the nominal number of persons per slot. (U mod H slots will have P+1 persons in them.) For slot j, let D_j be 3*R1j + 2*R2j + 1*R3j, where Rij is the number of times slot j is requested as choice i. D_j is higher for more-desired slots. Give each user k a score W_k = 1/D_{C1k} + 2/D_{C2k} + 3/D_{C3k}, where Cik is the i'th choice of user k. That is, a user gets more points for choosing slots with low D values, and 2nd- or 3rd-choice selections are weighted more heavily than 1st-choice selections.

Now sort the slots into increasing order by D_j. (The "busiest" slots will be filled first.) Sort the users into decreasing order by W_k scores, and call this list S.

Then, for each slot j: While j is not full, {Find first person k in S who chose slot j as choice 1; if found, move k from S to slot j. If none found, find first person k in S who chose slot j as choice 2; if found, move k from S to slot j. If none found, find first person k in S who chose slot j as choice 3; if found, move k from S to slot j. If none found, add the last person k from S to slot j, and remove k from S.}

In the bad case mentioned earlier, where all users choose slots (1,2,3) in order, this method would assign random sets of people to all slots. Given the problem statement, that's as good as can be expected.

Update 1: Completely filling busiest slots first may put some people into their professed 2nd or 3rd choice places when they could have been placed without conflict in their first-choice places. There are pros and cons to filling busiest-first, which game-theoretic analysis might resolve. Absent that analysis, it now seems to me better to fill via the following (simpler) method instead: As before, create sorted user list S, in decreasing order by W_k scores. Now go through list S in order, placing people into the first available slot they chose and fit into, else into the most-popular slot that still has an opening. For example, if user k chose slots p, q, r, put k into p if p has room, else q if q has room, else r if r has room, else j where j is among slots with openings and D_j is largest.

This approach would be easier to explain to users, is a little easier to program, and in general may come closer to optimal. In cases where slots can be filled without resorting to third-place choices, it will do so.

This is just an heuristic but maybe it would work well enough:

1. For each Timeslot calculate the number of people who are available for that slot
2. Take the timeslot with the least available people and fill it with 22/(amount of overall people) or the maximum number of people that are available for that slot.
3. Remove the added people from the pool and repeat the procedure for the remaining timeslots.

If you need an optimal result you might want to use a constraint solver or linear program solver.

This is graph-theory problem and can be solved with a topological sort: http://en.wikipedia.org/wiki/Topological_sorting.