×

Multi-objective evolutionary algorithm for university class timetabling problem. (English) Zbl 1200.90070

Dahal, Keshav P. (ed.) et al., Evolutionary scheduling. Berlin: Springer (ISBN 978-3-540-48582-7/hbk). Studies in Computational Intelligence 49, 197-236 (2007).
Summary: After their successful application to a wider range of problems, in recent years evolutionary algorithms (EAs) have also been found applicable to many challenging problems, like complex and highly constrained scheduling problems. The inadequacy of classical methods to handle discrete search spaces, huge numbers of integer and/or real variables and constraints, and multiple objectives, involved in scheduling, have drawn the attention of EAs to those problems. The academic class timetabling problem, one of such scheduling problems, is being studied for the last four decades, and a general solution technique for it is yet to be formulated. Despite multiple criteria to be met simultaneously, the problem is generally tackled as single-objective optimization problem. Moreover, most of the earlier works were concentrated on school timetabling, and only a few on university class timetabling. On the other hand, in many cases, the problem was over-simplified by skipping many complex class-structures. The authors study the problem, considering different types of class-structures and constraints that are common to most of the variants of the problem. NSGA-II-UCTO, a version of NSGA-II (an EA-based multi-objective optimizer) with specially designed representation and EA operators, is developed to handle the problem. Though emphasis is put on university class timetabling, it can also be applied to school timetabling with a little modification. The success of NSGA-II-UCTO is presented through its application to two real problems from a technical institute in India.
For the entire collection see [Zbl 1110.90002].

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI