Recording optimization function

Question

I am trying to write a shadow booking system, and I ran into this problem. Let's say you have players with their privileges regarding the court number, day and hour. Each player is also rated so if there is a day / hour slot, and there are several players with preferences for this slot, you should select a priority with a priority. I am thinking about using some optimization algorithms to solve this problem, but I'm not sure what would be the best cost function and / or algorithm to use. Any advice? Another thing I'd rather use Python, but some kind of agnostic language advice is also welcome. Thank!

edit:

some explanation -

the one with the best winnings with priority and the loser moving to the nearest slot is a rather flexible question of time yes, maximizing the number of people receiving the most distant times

Answer 1

Basic algorithm

I would sort the players by their rank, since high-ranking players always repelled low-paying ones. Then you start with the player with the highest rank, give him what he requested (if he is really the highest, he will always win, so you can also give him everything that he requested). Then I will start with the second largest. If he asked for something already taken highest, try to find a slot nearby and assign him this slot. Now comes the third highest. If he asks for something already taken at the highest, move it to the slot next to it. If this slot is already occupied by the second highest, move it to the slot even further. Continue with all the other players.

Some settings to consider:

If several players can have the same rank, you may need to implement some “justice”. All players with equal rank will have a random order to each other if you sort them, for example. using quicksort. You can get some justice if you do not make this player for the player, but take the title. You start with the highest rank and the first player of that rank. Process his first request. However, before processing your second request, process the first request of the next player with the highest rank, and then the third player with the highest rank. The algorithm is the same as above, but provided that you have 10 players and player 1-4 is the highest and players 5-7 are low and players 8-10 are very low and each player makes 3 requests, you treat them like

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

So you have justice. You can also choose randomly in the ranking class every time, this can also provide some fairness.

You can realize justice even by rank. For example. if you have 4 digits you can say

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

(Only approximate values, you can use a different key than always multiply by 0.5, for example, multiply by 0.8, causing the numbers to decrease more slowly)

Now you can say that you are starting to process with rank 1, however, as soon as 50% of all Rank 1 requests are completed, you go to level 2 and make sure that 25% of their requests are completed and so on. Thus, even a Rank 4 user can defeat a Rank 1 user by defeating the original algorithm somewhat, however you offer some fairness. Even a 4th rank player can sometimes receive his request; he will not be “dry”. Otherwise, a Rank 1 player planning each request simultaneously with a Rank 4 player ensures that a 4th rank player has no chance of receiving one request. Thus, there is at least a small chance to get it.

After you make sure that each of them has processed their minimum percentage (and the higher the rank, the higher it is), you return to the beginning, starting from the first rank 1 and processing the rest of your queries, and then the rest of Rank 2, etc. d.

And last but not least:. You can determine the maximum slot offset. If a slot is taken, the application should search in the nearest slot still for free. However, what if this nearest slot is very far away? If I ask for a slot on Monday at 4 p.m., and the application finds the next free one to be on Wednesday at 9 a.m., this is not very useful for me, is it? I may not have time on Wednesday. Thus, you can limit the search for a slot on the same day and say that the slot can be no more than 3 hours. If no slots are found in this range, cancel the request. In this case, you need to tell the player "We are sorry, but we could not find any nearby slots for you, please request a slot for a different date / time, and we will see if we find a suitable slot for you."

Answer 2

This is an NP-complete problem, I think, therefore it will not be possible to have a very fast algorithm for any large datasets.

There is also a problem when you may have a schedule that cannot be done. Given that this is not the case, something like this pseudo code is probably best:

 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 time slot 

Answer 3

You describe a compliance issue. Possible links: Stony Brook Algorithm Repository and Kleinberg and Tardos Design Algorithm . If the number of players is equal to the number of ships, you can achieve a stable match - Stable marriage problem . Other formulations are complicated.

Answer 4

There are several questions that I would ask before answering this question:

• what happens if there is a conflict, i.e. worse than losing the first album, then the best player records the same court? Who is winning? what happens to the loser?
• Do you allow players to play while the match is running, or do you have fixed time intervals?
• how often the launch of planning is carried out - it runs interactively - so you can potentially say that they can play, only to say that they cannot; or it starts in more batch mode - you place requests and then tell later if you have your own slot. Or do users set up several preferred times, and then the system should maximize the number of people receiving the most preferred times?

As an aside, you can make it somewhat less complex by rewriting time as integer indices (so you are dealing with integers, not just once).

Answer 5

I would recommend using a scoring algorithm. Essentially build a formula that pulls all the values ​​that you described into one number. The one who has ever had the highest score wins this slot. For example, a simple formula could be:

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

Where N1, N2 are the scales for controlling the formula.

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

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

In addition, you can use multiple passes to assign slots per day. Use one strategy, where it goes in chronological order, one reverse chronologically, the first that does the first morning, the first that does the second day, etc. Then summarize the ratings of the players who got the spots, and then you can decide that the 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 begin to allocate slots for them. The first gets its preferred slot, then the next takes its preferred among the free ones and so on. This is the O (N) algorithm.

Answer 7

I think you should use a genetic algorithm because:

• It is best suited for large instances of problems.
• This gives reduced time complexity at the price of an inaccurate answer (not the best)
• You can easily identify restrictions and preferences by adjusting fitness penalties for non-working people.
• You can specify time limits for program execution.

• The quality of the decision depends on how much time you intend to spend on the decision of the program.

  Definition of genetic algorithms

  Genetic Algorithm Tutorial

  Class Planning Project with GA

Also look at a similar question and another

Answer 8

Money. Allocate time intervals based on who pays the most. In the event of a tie, none of them has a slot.