FAQ

A brief description of the Scheduling Mechanism

Introduction

The following discussion is intended to be a brief, summarized description of the algorithm (referenced herein as the Mechanism) that drives data from the database through an Algorithm to seek an optimized schedule, as implemented via the Administrator: Tools-Schedule web page. The general objective is to determine how to schedule a single Division's Matches such that the desired balance of Home to Away Fields can be optimized.

While the inspiration for the actual coding work represented by the Mechanism is based in well accepted Linear Programming principles, the specialized nature of the League's requirements and the limitations on available compute power have prohibited us from implementing the ideal solution (which would be a fully optimized, 100% complete analysis of all available options).

Thus, the reader is reminded that the Mechanism falls short of being mathematically perfect. Thus, instead of finding the optimum solution, we accepted that if the Mechanism could find an overall "better" solution than prior scheduling approaches, that would be an acceptable achievement.

Operation

The scheduling mechanism is structured such that it can be operated online (Administrator: Tools-Schedule) or queued up for offline processing. In this context, "offline processing" simply means that the execution of the code occurs in the underlying operating system itself as an independent operating system task and is not directly dispatched or associated with the HTTP web service.

However, regardless of operational mode (online vs offline), the mechanism processes the identical code to optimize the results. The Online criteria offers a wider range of controls and abilities to utilize the mechanism to analyze possible alternatives. This documentation does not explore all possible uses of the online functions and, instead, focuses purely on how the Mechanism applies it's optimization logic.

Editing the Criteria

The Mechanism's logic has several checkpoints (verifications) prior to launching the data analysis itself. This "checking of the input" verifies:

1. there are values provided for PlayingLeague, Gender, AgeLevel, Bracket, PairingGrid, and Season
2. the specified Dates do not contain duplicate specifications
3. the number of Dates specified properly compares with the number required to make use of the specified PairingGrid (specified via Setting)

If the Editing operation fails, the Mechanism terminates.

Initialize the Teams Data

The Mechanism utilizes the criteria specifying the Division to be analyzed and

1. obtains the Team information from the defined Teams table (the Team's CYSAN, Name, Club, TimeSlots characteristic, and unique database Key value)
2. the number of Teams obtained from the Teams table is compared to the specified PairingGrid

If the number of Teams does not compare favorably with the number of Teams located, the Mechanism terminates.

Obtain current Balance values

The Mechanism

• examines the Teams included in the Division and extracts their associated Club
• for each Club, the Matches table is searched to obtain the number of existing Matches for each specified Date that have a HomeID that compares favorably with the Club
• each Date for each Club is also assigned a Ratio, which is computed as the {#AwayMatches/#HomeMatches} (if the #HomeMatches is greater than #AwayMatches ) or is computed as {#HomeMatches/#AwayMatches} (if the #AwayMatches is greater than the #HomeMatches

Collect Unavailable Dates

The UnavailableDates table is interrogated to extract the Dates for the Clubs and/or Teams that have been marked as being Dates the Club and/or Team would prefer to exempt from Scheduling activities.

It's important to note that while the Mechanism attempts to honor these specifications, the result of the Optimization logic does NOT guarantee that UnavailableDates will be honored. Indeed, it may not be possible to meet the requirements of the PairingGrid's specifications and the Teams and/or Clubs UnavailableDates. This is not of concern to the Mechanism, as the Optimization algorithm attempts to honor what it can, but...when a conflict producing a "deadly embrace" occurs, the UnavailableDates are ignored.

Examine

The specified PairingGrid's entries (1 to nn) are sequentially assigned to the Teams associated with the Division. This is identified as Permutation #1 and is then used to produce a possible schedule based upon specified Dates.

As the possible Schedule is produced, if a Match is produced that conflicts with a specified UnavailableDate, the Score for the permutation is incremented (reset to zero at the start of each Permutation's analysis).

The number of possible permutations in a bracket is n!, where n=the number of teams. A 6 team bracket has 720 possible permutations. A 10 team bracket has 3,628,800 possible permutations.

Algorithm=Ratio

For each Date from the Criteria, the number of resulting Home and Away games are computed (adding the Permutation's results with the existing Matches) and if ..

• the number of Home games exceeds the number of Away games, the Ratio is set to the current Ratio + ({AwayMatches/HomeMatches}
• the number of Away Games exceeds the number of Home games, the Ratio is set to the current Ratio + ({HomeMatches/AwayMatches}

If the current Permutation Score is less than the previous best score the current Score becomes the best score and the Permutation identity is retained. If there are two Permutations with the same Score, the Permutation with the largest Ratio is retained as the preferred Permutation.

Algorithm=InverseRatio

For each Date from the Criteria, the number of resulting Home and Away games are computed (adding the Permutation's results with the existing Matches) and if ..

• the number of Home games is less than the number of Away games, the Ratio is set to the current Ratio + ({AwayMatches/HomeMatches}
• the number of Away Games is less than the number of Home games, the Ratio is set to the current Ratio + ({HomeMatches/AwayMatches}

If the current Permutation Score is less than the previous best score the current Score becomes the best score and the Permutation identity is retained. If there are two Permutations with the same Score, the Permutation with the smallest Ratio is retained as the preferred Permutation.

Once the simulated generation of a Division's schedule is completely Examined, the resulting Score is compared to the current "best Score".

The assignment of PairingGrid Team numbers is iterated to the next possibility and Examine is done again (calling the same routine recursively). This recursive process proceeds as long as it necessary to complete all variations or until a Timeout interval has been expended on the effort. In either case, the "best alternative" amongst those analyzed is identified.

Generate

If the Generate or Optimize+Generate functions are requested, the Mechanism will use the identified Permutation to produce the actual Matches table entries representing the Matches. These Matches will, in turn, become a factor in performing Examine on the next Division scheduled via the Mechanism.

Notes

In practice, the Mechanism has been used to analyze hundreds of thousands of permutations within a Division to find the best alternative. But, the sequence in which the various Divisions are scheduled DO have an impact on the Mechanism's ability to locate a suitable combination for subsequent Divisions that keep the Score low.

To actually make this optimal, the Mechanism should be scheduling ALL the Matches for ALL the Divisions and then analyzing the results, varying two Teams to different spots in the various PairingGrids and repeating the process. This, sadly, would require far more compute power than is available to RedwoodSoccer at this time. Thus, we have settled on working a Division at a time in an effort to "make it better" (but, still not optimal).

Perhaps some day......

Updated: 7 February 2012