An Evolutionary Non-Linear Great Deluge Approach for Solving Course Timetabling Problems
The aim of this paper is to extend our non-linear great deluge algorithm into an evolutionary approach by incorporating a population and a mutation operator to solve the university course timetabling problems. This approach might be seen as a variation of memetic algorithms. The popularity of evolutionary computation approaches has increased and become an important technique in solving complex combinatorial optimisation problems. The proposed approach is an extension of a non-linear great deluge algorithm in which evolutionary operators are incorporated. First, we generate a population of feasible solutions using a tailored process that incorporates heuristics for graph colouring and assignment problems. The initialisation process is capable of producing feasible solutions even for large and most constrained problem instances. Then, the population of feasible timetables is subject to a steady-state evolutionary process that combines mutation and stochastic local search. We conducted experiments to evaluate the performance of the proposed algorithm and in particular, the contribution of the evolutionary operators. The results showed the effectiveness of the hybridisation between non-linear great deluge and evolutionary operators in solving university course timetabling problems.
Keywords: Evolutionary Algorithm, Non-linear Great Deluge and Course Timetabling.
Download Full-Text
ABOUT THE AUTHORS
Joe Henry Obit
Dr. Joe Henry Obit is a Senior Lecturer in the School of Informatics Science in E-Commerce Department at the Universiti Malaysia Sabah, Labuan International Campus. His main research interest lies at the interface of Operational Research and Computer Science. In particular, the exploration and development of innovative Operational Research, Artificial Intelligence, and Distributed Artificial Intelligence models and methodologies for automatically producing high quality solutions to a wide range of real world combinatorial optimisation and scheduling problems. Dr. Joe Obtained his Bachelor Degree in Finance at Universiti Kebangsaan Malaysia in 1999, an MSc Information Technology from Universiti Putra Malaysia in 2001and a PhD in Computer Science from the School of Computer Science at the University of Nottingham. His PhD thesis is Developing a Novel Meta-heuristic, Hyper-heuristic and Cooperative Search, and it was under the supervision of Associate Professor Dr. Dario Landa-Silva.
Djamila Ouelhadj
Author Dr. Djamila Ouelhadj is a Senior Lecturer in Operational Research Department of Mathematics at the University of Portsmouth. Her main research interest lies at the interface of Operational Research and Computer Science. In particular, the exploration and development of innovative Operational Research, Artificial Intelligence, and Distributed Artificial Intelligence models and methodologies for automatically producing high quality solutions to a wide range of real world combinatorial optimisation and scheduling problems. Dr. Djamila Ouelhadj obtained her PhD in Computer Science from the School of Computer Science at the University of Nottingham in 2002.
Dario Landa-Silva
Author Dr. Dario Landa-Silva is an Associate Professor in Computer Science for the School of Computer Science at the University of Nottingham. He is a member of the Automated Scheduling, Optimisation and Planning (ASAP) research group. He is also a member of the Institute for Operations Research and Management Sciences (INFORMS), the Operational Research Society (ORS) and a member of the editorial board for the Neural Computing and Application Journal. Dario Landa-Silva obtained a Technical Professional Qualification in Electro-mechanics from the CBTis 13 (Mexico) in 1987, a BEng in Industrial Electronic Engineering from Instituto Tecnologico de Veracruz (Mexico) in 1991, an MSc in Engineering-Computer Science from DEPI in the Instituto Tecnologico de Chihuahua in 1997 and a PhD in Computer Science from the School of Computer Science at the University of Nottingham in 2003.
Rayner Alfred
Dr. Rayner Alfred is a Senior Lecturer in Software Engineering Department for the School of Engineering and Information Technology at Universiti Malaysia Sabah. His main research interest lies at the Machine Learning in Knowledge Discovery. Dr. Rayner Alfred obtained his BSc in Computer Science at Polytechnic University of Brooklyn, New York, United States of America in 1994, an MSc in Computer Science from Western Michigan University, Michigan, United States of America in 1997 and a PhD in Computer Science from the School of Computer Science at the University of York, UK in 2008.
Joe Henry Obit
Dr. Joe Henry Obit is a Senior Lecturer in the School of Informatics Science in E-Commerce Department at the Universiti Malaysia Sabah, Labuan International Campus. His main research interest lies at the interface of Operational Research and Computer Science. In particular, the exploration and development of innovative Operational Research, Artificial Intelligence, and Distributed Artificial Intelligence models and methodologies for automatically producing high quality solutions to a wide range of real world combinatorial optimisation and scheduling problems. Dr. Joe Obtained his Bachelor Degree in Finance at Universiti Kebangsaan Malaysia in 1999, an MSc Information Technology from Universiti Putra Malaysia in 2001and a PhD in Computer Science from the School of Computer Science at the University of Nottingham. His PhD thesis is Developing a Novel Meta-heuristic, Hyper-heuristic and Cooperative Search, and it was under the supervision of Associate Professor Dr. Dario Landa-Silva.
Djamila Ouelhadj
Author Dr. Djamila Ouelhadj is a Senior Lecturer in Operational Research Department of Mathematics at the University of Portsmouth. Her main research interest lies at the interface of Operational Research and Computer Science. In particular, the exploration and development of innovative Operational Research, Artificial Intelligence, and Distributed Artificial Intelligence models and methodologies for automatically producing high quality solutions to a wide range of real world combinatorial optimisation and scheduling problems. Dr. Djamila Ouelhadj obtained her PhD in Computer Science from the School of Computer Science at the University of Nottingham in 2002.
Dario Landa-Silva
Author Dr. Dario Landa-Silva is an Associate Professor in Computer Science for the School of Computer Science at the University of Nottingham. He is a member of the Automated Scheduling, Optimisation and Planning (ASAP) research group. He is also a member of the Institute for Operations Research and Management Sciences (INFORMS), the Operational Research Society (ORS) and a member of the editorial board for the Neural Computing and Application Journal. Dario Landa-Silva obtained a Technical Professional Qualification in Electro-mechanics from the CBTis 13 (Mexico) in 1987, a BEng in Industrial Electronic Engineering from Instituto Tecnologico de Veracruz (Mexico) in 1991, an MSc in Engineering-Computer Science from DEPI in the Instituto Tecnologico de Chihuahua in 1997 and a PhD in Computer Science from the School of Computer Science at the University of Nottingham in 2003.
Rayner Alfred
Dr. Rayner Alfred is a Senior Lecturer in Software Engineering Department for the School of Engineering and Information Technology at Universiti Malaysia Sabah. His main research interest lies at the Machine Learning in Knowledge Discovery. Dr. Rayner Alfred obtained his BSc in Computer Science at Polytechnic University of Brooklyn, New York, United States of America in 1994, an MSc in Computer Science from Western Michigan University, Michigan, United States of America in 1997 and a PhD in Computer Science from the School of Computer Science at the University of York, UK in 2008.
