Using genetic algorithms to solve high school course timetabling problems

Title from first page of PDF file (viewed November 19, 2010)Includes bibliographical references (p. 55-57)Timetabling problems are optimization problems and can be thought of as a subset of scheduling problems. Computationally, timetabling problems are NP complete problems. NP complete problems are problems that can't be solved in polynomial time. The amount of time to solve NP complete problems is vastly larger than a problem that can be solved in polynomial time such that a brute force solution would not be feasible Genetic algorithms are among those that can be used to find approximate solutions to NP complete problems and more specifically can be used to solve timetabling problems. Smart operators are employed during the mutation process in order to solve two high school course timetabling problems, one with a fixed master schedule and the second were the master schedule is not defined. These smart operators are Violation-directed Mutation (VDM), Event-Freeing Mutation (EFM), Stochastic Violation-directed Mutation (SVDM) and Stochastic Event-Freeing Mutation (SEFM