Automated Examination Timetabling Optimization Using Greedy-Late Acceptance-Hyperheuristic Algorithm
| Autor: | Nisa Dwi Angresti, Vicha Azthanty Supoyo, Putri C Bwananesia, Ahmad Muklason, Sasmi Hidayatul Y T |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
021103 operations research
Computer science 0211 other engineering and technologies 0202 electrical engineering electronic engineering information engineering Information system 020201 artificial intelligence & image processing 02 engineering and technology Greedy algorithm Timetabling problem Hybrid algorithm Algorithm Data modeling |
| Zdroj: | 2018 International Conference on Electrical Engineering and Computer Science (ICECOS). |
| DOI: | 10.1109/icecos.2018.8605194 |
| Popis: | Due to its non-deterministic polinomial (NP)-hard nature, exam timetabling problem is one of challenging combinatorial optimisation problems. Therefore, it attracts researchers especially in operation research and artificial intelligence fields for decades. Since the problem is very complex, exam timetable in many universities is developed manually which is very time consuming. This paper presents a new hybrid algorithm, i.e. greedy-late acceptance within hyper-heuristic framework to generate and optimise exam timetable automatically. Greedy algorithm is used to generate initial solution, whereas late acceptance is used as move acceptance strategy. The algorithm is simple but proven powerfull. The algorithm is tested over two datasets from real-world exam timetabling problem from Information Systems Department, Institut Teknologi Sepuluh Nopember (ITS). Over 11 different scenarios, the experimental results show that in addition to its ability to generate feasible solution, the algorithm also could produce more optimal solutions compared to the timetables generated manually. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|