Answers.Body: <p>Welcome to AI.SE @Israr Ali.</p>
  
  <p>The problem of scheduling a timetable is an example of a <a href="https://en.wikipedia.org/wiki/Constraint_satisfaction_problem" rel="nofollow noreferrer">constraint satisfaction problem</a>, a topic long studied in AI.</p>
  
  <p>There are many possible techniques to apply to this kind of problem. They can be organized into three broad categories:</p>
  
  <ol>
  <li><p>Global search algorithms, like <a href="https://en.wikipedia.org/wiki/Backtracking" rel="nofollow noreferrer">backtracking search</a> 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 &amp; Norvig's <a href="http://aima.cs.berkeley.edu/" rel="nofollow noreferrer">AI: A Modern Approac</a>h has a very good overview of these approaches in Chapter 6. </p></li>
  <li><p>Local search algorithms, like <a href="https://en.wikipedia.org/wiki/Hill_climbing" rel="nofollow noreferrer">hill climbing search</a> 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.</p></li>
  <li><p>Planning approaches, particularly non-classical algorithms like <a href="https://en.wikipedia.org/wiki/Graphplan" rel="nofollow noreferrer">GraphPlan</a> 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.</p></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-22T18:35:10.577Z
Answers.LastActivityDate: 2019-04-22T18:35:10.577Z
Answers.UserDisplayName: John Doucette
Body: <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-22T20:02:58.247Z
Comments.Text: 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)
Comments.UserDisplayName: DukeZhou
Tags: <planning><symbolic-ai>
Title: Is there any AI system for finding the best way to schedule university classes?
UserDisplayName: Israr Ali
ThreadText: # Is there any AI system for finding the best way to schedule university classes?
  
  (Asked by: username_0 on 2019-04-22)
  
  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?
  
  **Tags:** planning, symbolic-ai
  > **Comments:**
  > **username_1**: 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)  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-04-22. Score: 4 | Accepted answer
  
  Welcome to AI.SE @Israr Ali.
  
  The problem of scheduling a timetable is an example of a [constraint satisfaction problem](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Backtracking) 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 Approac](http://aima.cs.berkeley.edu/)h has a very good overview of these approaches in Chapter 6.
  2. Local search algorithms, like [hill climbing search](https://en.wikipedia.org/wiki/Hill_climbing) 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](https://en.wikipedia.org/wiki/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.
  
  
  ---
  
  