3

I was wondering whether there is an AI system which could be used to resolve the class clashes problem which mostly happens in universities. In almost every university students face this problem, where two or more courses that many students want to take together get scheduled at the same time. Does anyone know about a system which resolves this issue or someone who works on this problem?

John Doucette
  • 9,147
  • 1
  • 17
  • 52
Israr Ali
  • 103
  • 5
  • In terms of constraint satisfaction, you may want to look into how Latin squares have been used in scheduling problems. The most basic scheduling applications are trivial, but here's a paper on a more complex form: [MALS: multiple access scheduling based on Latin squares](https://ieeexplore.ieee.org/document/1493287) – DukeZhou Apr 22 '19 at 20:02

1 Answers1

4

Welcome to AI.SE @Israr Ali.

The problem of scheduling a timetable is an example of a constraint satisfaction problem, a topic long studied in AI.

There are many possible techniques to apply to this kind of problem. They can be organized into three broad categories:

  1. Global search algorithms, like backtracking search can be used to try and find an assignment of times to classes that results in no conflicts at all. With proper heuristics, these can be quite fast in practice, even though their worst-case runtimes are poor. Russell & Norvig's AI: A Modern Approach has a very good overview of these approaches in Chapter 6.

  2. Local search algorithms, like hill climbing search start by assigning every class a randomly selected time, and then making small adjustments that monotonically decrease the number of conflicts (e.g. swapping the times of two classes). These are often faster than backtracking approaches and are especially so if you are willing to accept a "pretty good" schedule that might still have fewer conflicts than an optimal one. Chapter 4 of AI: A Modern Approach provides a good introduction.

  3. Planning approaches, particularly non-classical algorithms like GraphPlan can also be used for these domains. They make use of the structure of planning or scheduling problems in particular to re-frame the search problems addressed by Backtracking techniques. By using this domain-specific representation, they are able to achieve very high-quality solutions very quickly. Chapter 11 of AI: A Modern Approach covers Graph Plan in some detail, and could be a good introduction to these more specialized techniques.

John Doucette
  • 9,147
  • 1
  • 17
  • 52