I have been researching on finding optimal solutions to generating University Time Table using Genetic Algorithm. I am searching for a Academic Paper, that properly defines the University Time Table design problem and proves it is NPC.

  • 1
    $\begingroup$ What is time table scheduling? $\endgroup$ Jan 24 '16 at 15:06
  • $\begingroup$ taking -> giving ​ ? ​ ​ ​ ​ $\endgroup$
    – user12859
    Jan 24 '16 at 15:25
  • $\begingroup$ Isn't this just three-dimensional matching with a bunch more constraints? Also, what's "TTS"? $\endgroup$ Jan 24 '16 at 16:57
  • $\begingroup$ TTS is Time Table Scheduling. Having more constraints does make it more hard to solve computationally. But my question is directed towards the question of someone actually proving that this problem is NPC $\endgroup$ Jan 24 '16 at 17:25

Simple Google search reveals a thesis from 2010 that defines and proves the complexity of scheduling university courses as NP-Complete. See Fig. 42 towards the end.

Lovelace, April L. "On the complexity of scheduling university courses." (2010).

There is also a technical report dating back to 1995 that does the same thing:

Cooper, Tim B., and Jeffrey H. Kingston. The complexity of timetable construction problems. Springer Berlin Heidelberg, 1996.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.