writing optimization function

Question

I'm trying to write a tennis reservation system and I got stucked with this problem. Let's say you have players with their prefs regarding court number, day and hour. Also every player is ranked so if there is day/hour slot and there are several players with preferences for this slot the one with top priority should be chosen. I'm thinking about using some optimization algorithms to solve this problem but I'am not sure what would be the best cost function and/or algorithm to use. Any advice? One more thing I would prefer to use Python but some language-agnostic advice would be welcome also. Thanks!

edit:

some clarifications-

the one with better priority wins and loser is moved to nearest slot, rather flexible time slots question yes, maximizing the number of people getting their most highly preffered times

Answer 1

This is an NP-complete problem, I think, so it'll be impossible to have a very fast algorithm for any large data sets.

There's also the problem where you might have a schedule that is impossible to make. Given that that's not the case, something like this pseudocode is probably your best bet:

sort players by priority, highest to lowest
start with empty schedule
for player in players:
    for timeslot in player.preferences():
        if timeslot is free:
            schedule.fillslot(timeslot, player)
            break
    else:
        #if we get here, it means this player couldn't be accomodated at all.
        #you'll have to go through the slots that were filled and move another (higher-priority) player's time slot

Answer 2

There are several questions I'd ask before answering this queston:

• what happens if there is a conflict, i.e. a worse player books first, then a better player books the same court? Who wins? what happens for the loser?
• do you let the best players play as long as the match runs, or do you have fixed time slots?
• how often is the scheduling run - is it run interactively - so potentially someone could be told they can play, only to be told they can't; or is it run in a more batch manner - you put in requests, then get told later if you can have your slot. Or do users set up a number of preferred times, and then the system has to maximise the number of people getting their most highly preferred times?

As an aside, you can make it slightly less complex by re-writing the times as integer indexes (so you're dealing with integers rather than times).

Answer 3

Money. Allocate time slots based on who pays the most. In case of a draw don't let any of them have the slot.

Answer 4

You are describing a matching problem. Possible references are the Stony Brook algorithm repository and Algorithm Design by Kleinberg and Tardos. If the number of players is equal to the number of courts you can reach a stable matching - The Stable Marriage Problem. Other formulations become harder.

Answer 5

I would advise using a scoring algorithm. Basically construct a formula that pulls all the values you described into a single number. Who ever has the highest final score wins that slot. For example a simple formula might be:

FinalScore = ( PlayerRanking * N1 ) + ( PlayerPreference * N2 )

Where N1, N2 are weights to control the formula.

This will allow you to get good (not perfect) results very quickly. We use this approach on a much more complex system with very good results.

You can add more variety to this by adding in factors for how many times the player has won or lost slots, or (as someone suggested) how much the player paid.

Also, you can use multiple passes to assign slots in the day. Use one strategy where it goes chronologically, one reverse chronologically, one that does the morning first, one that does the afternoon first, etc. Then sum the scores of the players that got the spots, and then you can decide strategy provided the best results.

Answer 6

Basically, you have the advantage that players have priorities; therefore, you sort the players by descending priority, and then you start allocating slots to them. The first gets their preferred slot, then the next takes his preferred among the free ones and so on. It's a O(N) algorithm.

Answer 7

The basic Algorithm

I'd sort the players by their rank, as the high ranked ones always push away the low ranked ones. Then you start with the player with the highest rank, give him what he asked for (if he really is the highest, he will always win, thus you can as well give him whatever he requested). Then I would start with the second highest one. If he requested something already taken by the highest, try to find a slot nearby and assign this slot to him. Now comes the third highest one. If he requested something already taken by the highest one, move him to a slot nearby. If this slot is already taken by the second highest one, move him to a slot some further away. Continue with all other players.

Some tunings to consider:

If multiple players can have the same rank, you may need to implement some "fairness". All players with equal rank will have a random order to each other if you sort them e.g. using QuickSort. You can get some some fairness, if you don't do it player for player, but rank for rank. You start with highest rank and the first player of this rank. Process his first request. However, before you process his second request, process the first request of the next player having highest rank and then of the third player having highest rank. The algorithm is the same as above, but assuming you have 10 players and player 1-4 are highest rank and players 5-7 are low and players 8-10 are very low, and every player made 3 requests, you process them as

Player 1 - Request 1
Player 2 - Request 1
Player 3 - Request 1
Player 4 - Request 1
Player 1 - Request 2
Player 2 - Request 2
:

That way you have some fairness. You could also choose randomly within a ranking class each time, this could also provide some fairness.

You could implement fairness even across ranks. E.g. if you have 4 ranks, you could say

Rank 1 - 50%
Rank 2 - 25%
Rank 3 - 12,5%
Rank 4 - 6,25%

(Just example values, you may use a different key than always multiplying by 0.5, e.g. multiplying by 0.8, causing the numbers to decrease slower)

Now you can say, you start processing with Rank 1, however once 50% of all Rank 1 requests have been fulfilled, you move on to Rank 2 and make sure 25% of their requests are fulfilled and so on. This way even a Rank 4 user can win over a Rank 1 user, somewhat defeating the initial algorithm, however you offer some fairness. Even a Rank 4 player can sometimes gets his request, he won't "run dry". Otherwise a Rank 1 player scheduling every request on the same time as a Rank 4 player will make sure a Rank 4 player has no chance to ever get a single request. This way there is at least a small chance he may get one.

After you made sure everyone had their minimal percentage processed (and the higher the rank, the more this is), you go back to top, starting with Rank 1 again and process the rest of their requests, then the rest of the Rank 2 requests and so on.

Last but not least: You may want to define a maximum slot offset. If a slot is taken, the application should search for the nearest slot still free. However, what if this nearest slot is very far away? If I request a slot Monday at 4 PM and the application finds the next free one to be Wednesday on 9 AM, that's not really helpful for me, is it? I might have no time on Wednesday at all. So you may limit slot search to the same day and saying the slot might be at most 3 hours off. If no slot is found within that range, cancel the request. In that case you need to inform the player "We are sorry, but we could not find any nearby slot for you; please request a slot on another date/time and we will see if we can find a suitable slot there for you".