0

This is my first question on this forum, have tried to exhaust every possible research option I could think of or find. Actually this is the first time I've posted for help with this anywhere, so maybe I should have started here... :)

I am trying to build an automated scheduling solution for a pool league, right now the process is entirely manual. I will do my best to try to describe my situation:

There are usually approximately 20 teams that play in this league, but need to accommodate situations where there could be as few as 5 teams and as many as 50 teams. In addition to the number of teams, this is a traveling league so there are multiple venues, some of which that can house only one match (two teams) and some that can house up to 6 matches (12 teams). If there are an odd number of teams, I can add a bye of course, but would really like to limit it to a single bye if I can, unless absolutely required that multiple byes be added.

I need to devise a scheduling system that allows for teams to play each other based on a round robin formula, trying as best as possible to allow for a balanced alternating home and away, and not exceeding limits on number of matches that can be played in a venue. If there are a couple instances of a team playing home or away twice in a row to accommodate the venue limits or teams that play out of the same venue to play each other, that is ok, as long as it isn't frequent (hopefully no more than once per team for no more than 3 or 4 teams in a schedule). I can be flexible on this if the algorithm requires.

I have found similar solutions, including balanced home/away round-robin tournament algorithm, but this does not allow for venues that can play multiple matches but limits them.

If anyone can point me in a direction or provide some insight, I would greatly appreciate it. I'm hoping for an asp.net/vb.net solution to this, but if anyone has a formula that helps with this I can do my best to program it out in asp.net.

I should mention that the venue/team information is going to be stored in an MSSQL database (including the match limit per venue), as well as this schedule once it is created, and it will need to be called back on queue as well.

Thanks very much for your time and effort!

EDIT

I don't believe I was specific enough on this item:

Each team must pick a venue to play out of, and that's part of the alternating home and away requirement; if a venue can hold 4 home teams, then at least 2 of those teams must play away and 2 of those teams can play home every week. The reason I say 2 of those teams must play away is to ensure that no more than 2 teams play home in that venue and exceed the limits of that venu. And the teams can play each other, one as home and one as "away".

|improve this question
  • 2
    Couldn't you break up your venues with multiple slots for matches into unique "subvenues" to satisfy the the solutions you've already found? – Jacob Hull Jul 10 '17 at 20:07
  • I'm not sure that subvenues would satisfy the requirements. I'm going to edit the question because I should have specified that teams have a "home" venue, I don't think I was clear enough on that. Each team must pick a venue to play out of, and that's part of the alternating home and away requirement; if a venue can hold 4 home teams, then at least 2 of those teams must play away and 2 of those teams can play home every week. The reason I say 2 of those teams must play away is to ensure that no more than 2 teams play home in that venue. And the teams can play each other. – user277561 Jul 12 '17 at 14:22
-1

These days, computers are so powerful that you don't need to be precious about it. You can brute force the problem and use optimization criteria to choose the best option.

Here's how I'd go about it:

  1. Define a data representation of a completed schedule, e.g. a c# struct or class or possible an XML blob. The important thing is that you can traverse the structure in code with relative ease.

  2. Define a series of hard and soft constraints. A hard constraint represents is a rule that must not be violated, e.g. "Venue X can support a maximum of 6 simultaneous teams." A soft constraint is a rule that can be violated but would be less favorable, e.g. "minimize the number of byes."

  3. Write code to fill your data model randomly.

  4. Write code to score the schedule. If it violates a hard constraint, it gets a score of 0. If it violates absolutely no soft constraints, it gets a score of 100. If it violates a few soft constraints, it should get a score somewhere in between, which you can tweak based on your knowledge of what is acceptable. For example, if a team ends up playing a home game twice in a row, perhaps you deduct 2 points from the score for each team that ends up like that.

  5. Run the program 10,000 times and generate and score 10,000 schedules.

  6. Take the schedule with the highest score.

It might be that 10,000 iterations isn't quite enough, but you can probably run it for 100,000 iterations or even 1,000,000 iterations in a reasonable amount of time.

This way you don't really have to worry about coming up with a clever algorithm, and it's fairly simple to change the rules later as you think of more constraints.

|improve this answer
  • John - thanks for your response. I like the idea of this, but don't know if this will work for my big picture. I'm going to start with a local pool league, but if the feedback is good I'm going to try to expand this management tool I'm building to a significantly larger user base. My concern is that, hypothetically speaking, if 100 leagues are all creating schedules at roughly the same time, this will cause several issues within my application. My hope was to define an algorithm so that I could have a schedule generated in one attempt. But after my research, yours might be the best option. – user277561 Jul 12 '17 at 14:33
  • I don't think this is a real brute-forceable problem. Good luck if you have 20 teams. There are already 645 million possible pairings for the first round. Now that can be done, until you find out that the next round has a possible 185 million possible pairings, so if you multiply those numbers you'll see that even after 2 rounds your brute-force attack will start running into trouble. – Pieter B Jul 12 '17 at 17:13
  • @Peter: This is not like a brute force attack. There is no one correct answer; there are probably millions. – John Wu Jul 12 '17 at 17:24
  • I agree that there could be millions of possible solutions, but it's looking like less than 1% (guesstimate) of the multi-billions of calculations (another guesstimate) for a schedule might satisfy my needs. And if this will be completed for multiple leagues at roughly the same day, this could cause issues running all the calculations. If this is what I need to do, then so be it, but I'm hoping that there is another solution. I really do appreciate the insight, this is something I hadn't considered before, so I'm closer than I was. – user277561 Jul 12 '17 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.