_____

Multi scheduler internals

Language

The program is written in JavaScript/jQuery and runs in a browser (Firefox, chrome, ...).

Computing the schedule, using a genetic algorithm

The following numbers are defined:

  • ND: the number of days the schedule is spanning
  • NP: the total number of available players
  • NDP: the number of players that are to play on a given day
  • A,B: teams are named A, B, C, ... A team consists of one or two players.

The chromosomes

A chromosome consists of an array with ND rows and NDP columns. A number of random chromosomes is created, taken in consideration:

  • choose only players that can play on the given day
  • schedule nothing on a 'free' day
  • do not place players in the same team if that is not desired

An example (NP=6, NDP=4):

  3  4  1  5
  -1 0  3  2
  etc..

In this example, on the first day players 3 and 4 are scheduled in team A, while players 1 and 5 are scheduled in team B. On the second day, apparently there are not enough players available, so team A has only player 0, and team B has players 3 and 2.

Combining chromosomes

An offspring of two chromosomes is computed by taking m rows of the first chromosome adding ND-m rows of the second chromosome.

Mutation

Mutation is accomplished by replacing a row of a chromosome with a new random row, taking into account the considerations above.

Fitness function

The fitness function takes into consideration:

  • Every player should play the same number of games in total
  • The number of not-playing-days after each other should be minimized
  • Teams should preferably consist of a male and a female
  • Players should be distributed among teams as much as possible
  • The teams that play against each other should be of equal strength

Random numbers

The specifications of JavaScript do not specify how the function Math.random() computes random numbers. Moreover, one cannot set a seed for the random number generator. Therefore, using Math.random() would possibly yield different results for different browsers and different results in the same browser because of probably different starting points on each session. These problems are circumvented by using a random generator, written in JavaScript, equipped with a seed, so that the generator can be started at a defined point. The algorithm is taken from the article Random number generators: good ones are hard to find.

The machinery

During many iterations, two chromosomes are chosen at random and combined at a random row. The offspring is sometimes mutated in a random row. From the three chromosomes (the original two and the offspring), the one with the worst fitness is removed. The algorithm ends, when all chromosomes seem to have the same fitness, or when a number of iterations has been done.