Genetic Algorithm for lecturing schedule optimization

https://doi.org/10.22146/ijccs.43038

David Kristiadi(1*), Rudy Hartanto(2)

(1) Sekolah Tinggi Multi Media Yogyakarta
(2) Departemen Teknik Elektro dan Teknologi Informasi, Fakultas Teknik UGM
(*) Corresponding Author

Abstract


Scheduling is a classic problem in lecturing. Rooms, lecturers, times and scheduling constraints must be managed well to get an optimal schedule. University of Boyolali (UBY) also encounter the same scheduling problems. The problem was tried to be solved by building a library based on Genetic Algorithm (GA). GA is a computation method which inspired by natural selection. The computation consists of some operators i.e. Tournament Selection, Uniform Crossover, Weak Parent Replacement and two mutation operators (Interchanging Mutation and Violated Directed Mutation (VDM)). The two mutation method are compared to find which better mutation operator. The library was planned to have a capability to define custom constraints (scheduling requirements that were not accommodated by the library) without core program modifications. The test results show that VDM is more promising for optimal solutions than Interchanging Mutation. In UBY cases, optimal solution (fitness value=1) is reached in 12 minutes 41 second with adding 6 new room and inactivated 2 constraint i.e. lecturing begins at 14.00 except for 3rd semester of science law study program with morning class and lecturing participants must not over classroom capacity.


Keywords


Genetic algorithm;Violated Directed Mutation;VDM vs Interchanging Mutation

Full Text:

PDF


References

[1]    Forlap Dikti, “Profil Perguruan Tinggi (Universitas Boyolali),” Pangkalan Data Pendidikan Tinggi, Kementerian Riset, Teknologi dan Pendidikan Tinggi, 2017. [Online]. Available: https://forlap.ristekdikti.go.id/perguruantinggi/detail/NzgxNkEzMzItODhGQi00NDJDLUI1OUQtMUU5NDQxMTUyOERG. [Accessed: 04-Oct-2017].

[2]    A. Darmawan and R. M. Hasibuan, “Penjadwalan Mata Kuliah Menggunakan Algoritma Genetika Dengan Mempertimbangkan Team-teaching,” Simp. Nas. RAPI XIII, 2014.

[3]    R. Erama and R. Wardoyo, “Modifikasi Algoritma Genetika untuk Penyelesaian Permasalahan Penjadwalan Pelajaran Sekolah,” IJCCS (Indonesian J. Comput. Cybern. Syst., vol. 8, no. 2, pp. 111–120, Jul. 2014.

[4]    N. L. G. P. Suwirmayanti, I. M. Sudarsana, and S. Darmayasa, “Penerapan algoritma Genetika untuk Masalah Penjadwalan,” J. Appl. Intell. Syst., vol. 1, no. 3, pp. 220–233, 2016.

[5]    C. Setya Pratama, F. Nhita, and A. Aditsania, “Optimasi Penjadwalan Perkuliahan dengan Menggunakan Pendekatan Metode Hybrid Algoritma Genetika Adaptif dan Algoritma Koloni Lebah Buatan (Studi Kasus: Penjadwalan perkuliahan pada Fakultas Teknik Universitas Telkom),” Indosc 2016, no. August, pp. 245–256, 2016.

[6]    S. Parera, H. T. Sukmana, and L. K. Wardhani, “Application of Genetic Algorithm for Class Scheduling (Case study: Faculty of science and technology UIN Jakarta),” in Proceedings of 2016 4th International Conference on Cyber and IT Service Management, CITSM 2016, 2016, pp. 3–7.

[7]    H. P. Hariyadi, T. Widiyaningtyas, M. Z. Arifin, and S. Sendari, “Implementation of Genetic Algorithm to Academic Scheduling System,” in 2016 IEEE Region 10 Conference (TENCON), pp. 2013–2016, 2016.

[8]    K. Sylejmani, A. Halili, and A. Rexhepi, “Balancing Academic Curricula by Using a Mutation-only Genetic Algorithm,” 2017 40th Int. Conv. Inf. Commun. Technol. Electron. Microelectron. MIPRO 2017 - Proc., pp. 1189–1194, 2017.

[9]    P. M. Chauhan, K. B. Parmar, and M. B. Mendapara, “Solving Time Table Scheduling Problem by Novel Chromosome Representation Using Genetic Algorithm,” 2015 Int. Conf. Circuit, Power Comput. Technol. [ICCPCT], pp. 1–6, 2015.

[10]  R. E. Febrita and W. F. Mahmudy, “Modified Genetic Algorithm for High School Time-table Scheduling with Fuzzy Time Window,” Proc. - 2017 Int. Conf. Sustain. Inf. Eng. Technol. SIET 2017, vol. 2018–Janua, pp. 88–92, 2018.

[11]  M. Assi, B. Halawi, and R. A. Haraty, “Genetic Algorithm Analysis using the Graph Coloring Method for Solving the University Timetable Problem,” Procedia Comput. Sci., vol. 126, pp. 899–906, 2018.

[12]  S. S. A. Alves, S. A. F. Oliveira, and A. R. R. Neto, “A Novel Educational Timetabling Solution Through Recursive Genetic Algorithms,” in 2015 Latin America Congress on Computational Intelligence (LA-CCI), pp. 1–6, 2015.

[13]  S. Yang and S. N. Jat, “Genetic Algorithms With Guided and Local Search Strategies for University Course Timetabling,” IEEE Trans. Syst. Man, Cybern. Part C (Applications Rev., vol. 41, no. 1, pp. 93–106, Jan. 2011.

[14]  S. N. Sivanandam and S. N. Deepa, Introduction to Genetic Algorithms. Berlin Heidelberg: Springer, 2008.

[15]  Suyanto, An Informed Genetic Algorithm for University Course and Student Timetabling Problems. Berlin, Heidelberg: Springer, 2010.



DOI: https://doi.org/10.22146/ijccs.43038

Article Metrics

Abstract views : 1762 | views : 1161

Refbacks

  • There are currently no refbacks.




Copyright (c) 2019 IJCCS (Indonesian Journal of Computing and Cybernetics Systems)

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.



Copyright of :
IJCCS (Indonesian Journal of Computing and Cybernetics Systems)
ISSN 1978-1520 (print); ISSN 2460-7258 (online)
is a scientific journal the results of Computing
and Cybernetics Systems
A publication of IndoCEISS.
Gedung S1 Ruang 416 FMIPA UGM, Sekip Utara, Yogyakarta 55281
Fax: +62274 555133
email:ijccs.mipa@ugm.ac.id | http://jurnal.ugm.ac.id/ijccs



View My Stats1
View My Stats2