search

gaelrenoux / gaston

Slot scheduler
Apache License 2.0
2 stars 0 forks source link

readme

Gaston

Gaston is a tool to build schedules for conventions and such. It was build for RPG conventions.

It works by generating schedules and adjusting them, trying to get the best possible global score. The global score is a function giving more importance to people with a low score (ensuring the end schedule is fair, not sacrificing completely a person's satisfaction so that other can have a great schedule).

Running Gaston

Clone the repository, and build with: sbt assembly

This produces a fat jar in target/scala-2.12, which you can then run with:

java -jar target/scala-2.12/gaston-assembly-0.2-SNAPSHOT.jar --from problem.conf

To get the full list of command line options, use:

java -jar target/scala-2.12/gaston-assembly-0.2-SNAPSHOT.jar --help

Input file

The input file describes the problem to solve. It follows the HOCON format, and should be in UTF-8. To give you an idea the values of the scores, each person has 1000 points distributed over their wishes.

You can generate an input file with old default values with:

java -jar target/scala-2.12/gaston-assembly-0.2-SNAPSHOT.jar --generate-input

Example

gaston = {

  settings.default-max-topics-per-slot = 3

  slots = [
    [
      {
        "name": "D1-afternoon",
        "max-topics": 4
      }, {
        "name": "D1-evening"
      }
    ], [
      {
        "name": "D2-afternoon",
        "max-topics": 4
      }, {
        "name": "D2-evening"
      }
    ]
  ]

  persons = [
    {
      absences = ["D1-afternoon"]
      name = "Anatole"
      weight = 1.0
      mandatory = ["Gamma"]
      forbidden = ["Alpha"]
      wishes = {
        "Beta" = 10
        "Gamma" = 10
        "Delta" = 10
      }
    }
    {
      incompatible = ["Anatole", "Colin"]
      name = "Bernadette"
      weight = 1.0
      mandatory = ["Alpha"]
      wishes = {
        "Delta" = 10
      }
    }
    {
      absences = ["D1-afternoon", "D1-evening"]
      name = "Colin"
      weight = 1.5
      mandatory = ["Beta"]
      wishes = {
        "Alpha" = 1
        "Delta" = 10
      }
    }
    {
      name = "Dominique"
      weight = 1.5
      mandatory = ["Beta"]
      wishes = {
        "Alpha" = 1
        "Delta" = 10
      }
    }
    {
      name = "Eric"
    }
    {
      name = "Françoise"
    }
    {
      name = "Garfield"
    }
    {
      name = "Harley"
    }
  ]

  topics = [
    {
      max = 5
      name = "Alpha"
    }
    {
      max = 4
      min = 4
      name = "Beta"
    }
    {
      name = "Gamma"
    }
    {
      min = 5
      name = "Delta"
    }
    {
      max = 6
      min = 3
      name = "Epsilon"
    }
    {
      max = 6
      min = 3
      name = "Zeta"
      forced = true
    }
    {
      max = 6
      min = 3
      name = "Eta"
      presence = -100
    }
  ]

  constraints = {
    simultaneous = [
      {topics = ["Eta", "Zeta"]}
    ]
    exclusive = [
      {topics = ["Eta", "Zeta"]}
      {topics = ["Beta", "Gamma"], exemptions = ["Eric"]}
    ]
  }
}

Importing a table

Quite often, the wishes of the participant will be expressed in a double-entry table. The importing feature can transform this table into a HOCON file.

The table must have the topics in lines, and each person in a column (this may become selectable in the future). To import a table:

java -jar target/scala-2.12/gaston-assembly-0.2-SNAPSHOT.jar --from params.conf --from-table table.txt --generate-input

The configuration file will hold the information necessary to properly import the table, as well as basic information not present in the tables (settings and slots).

Note that you can use directly the table to generate schedules (by omitting the --generate-input option) but this is not recommended. You should generate the input, check it (and possibly modifiy it), then generate schedules using the input.

The parameters for the import are in the tableSettings section of the input file. All indexes start at 0 (first line is index 0, second line is index 1, and so on).

Example input

gaston {

  settings {
      default-max-topics-per-slot = 3
  }

  table-settings {
      separator = "\t"
      persons-row: 0
      wishes-start-row = 1
      persons-start-col = 4
      topic-col = 0
      topic-occurrence-count-col = null
      mandatory-person-col = 1
      min-persons-col = 2
      max-persons-col = 3
      persons-count-add = 0
      mandatory-person-weight = 1.5
      forbidden-person-marker = 0
      preferences-score-mapping = {
        "+" = 1.0
        "++" = 2.0
        "+++" = 5.0
      }
  }

  slots = [
    [
      {
        "name": "D1-afternoon",
        "max-topics": 4
      }, {
        "name": "D1-evening"
      }
    ], [
      {
        "name": "D2-afternoon",
        "max-topics": 4
      }, {
        "name": "D2-evening"
      }
    ]
  ]
}

Developer's corner

Brain dump

Some vocabulary:

The Engine produces a lazy list of schedules, each new schedule being better than the next one. The list ends when no further improvement can be found, which never happens on real-world examples. It starts with a seed for all random operations.

The Engine is CPU-bound and monothreaded. Typically, you would run multiple Engines in parallel, one per CPU, with different seeds.

An Engine run (in Engine.lazySeq) starts with an initial schedule respecting all constraints, but with probably a terrible score.

Then, the Engine generates a lazy-list by improving the state step-by-step. There are two Engines implemented, GreedyEngine and TabuSearchEngine. Only the first one is currently being used.

In GreedyEngine, a generation step starts from the latest generated schedule, and procedes with the following steps: