I've got a data set which will potentially seem like this:
user_name time_1 time_2 time_3
In which the occasions will vary hrs on the given day they're free. You will find 22 slots every week, and also the user is permitted available three and publish them. I'll have about 100-150 customers, and I am wondering what's the easiest method to start sorting them in a way that distributes the quantity of people evenly across every time slot. My best guess for any beginning approach would be to see what it really appears like if all of the customers they fit within their first slots (time_1), then 2 and three and compare which gives the greatest results, then after that, take a look at what's going to happen if your user is added or taken off a slot and just how this can affect efficiency. Any help could be appreciated when i haven't done lots of optimisation calculations.
I am responding to because previous solutions apparently break lower in instances where lots of people pick the same slot and several slots don't have any or couple of choosers. For instance, if all customers choose slots (1,2,3) for the reason that order, topological sort will give you no help.
Within the ideal situation, each individual would pick one slot, and all sorts of slots would have a similar quantity of choosers (+/- 1). Basically were handling the issue myself, I'd consider using a first-come, first-offered regime having a real-online time server, so that people can pick only from individuals slots that remain open at that time they sign in.
If online first-come, first-offered is not achievable, I'd make use of a method that inspires individuals to choose distinct slots, possibly with a component of randomness. Here's one particular method:
Let there be U people in most, competing for H time slots. (H=22.) Suppose each individual is designated to exactly one slot. Let P = [U/H] (that's, U/H cut down to integer) function as the nominal quantity of persons per slot. (U mod H slots may have P+1 persons inside them.) For slot j, let D_j be 3*R1j + 2*R2j + 1*R3j, where Rij is the amount of occasions slot j is asked for as choice i. D_j is greater for additional-preferred slots. Give each user k a score W_k = 1/D_ + 2/D_ + 3/D_, where Cik may be the i'th selection of user k. That's, a person will get more points for selecting slots with low D values, and second- or 3rd-choice choices are weighted more heavily than first-choice choices.
Now sort the slots into growing order by D_j. (The "most popular" slots is going to be filled first.) Sort the customers into lowering order by W_k scores, and refer to this as list S.
Then, for every slot j: While j isn't full,
Within the bad situation pointed out earlier, where all customers choose slots (1,2,3) so as, this process would assign random teams of individuals to all slots. Because of the problem statement, that's just like should be expected.
Update 1: Completely filling most popular slots first may put many people to their professed second or 3rd choice places once they might have been placed without conflict within their first-choice places. You will find benefits and drawbacks to filling most popular-first, which game-theoretic analysis might resolve. Absent that analysis, it now appears in my experience easier to fill through the following (simpler) method rather: As before, create sorted user list S, in lowering order by W_k scores. Now undergo list S so as, placing people in to the first available slot they chose and squeeze into, else in to the most-popular slot that also comes with an opening. For instance, 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 one kind of slots with openings and D_j is biggest.
This method could be simpler to describe to customers, is really a little simpler to program, as well as in general will come nearer to optimal. In instances where slots could be filled without turning to 3rd-place options, it is going to do so.
Case an heuristic but maybe it might work nicely enough:
- For every Timeslot calculate the amount of those who are available for your slot
- Go ahead and take timeslot using the least available people and grow it with 22/(quantity of overall people) or even the maximum number of individuals that are offered for your slot.
- Take away the added people in the pool and repeat the process for that remaining timeslots.
If you want an optimal result you might like to make use of a constraint solver or linear program solver.