SOLVER PENJADWAL UJIAN OTOMATIS DENGAN ALGORITMA MAXIMAL CLIQUE DAN HYPER-HEURISTICS
Abstract
Permasalahan penjadwalan ujian adalah permasalahan berulang yang terjadi setidaknya satu kali dalam satu semester di lingkungan akademik, baik sekolah maupun perguruan tinggi. Menentukan jadwal dengan memastikan tidak ada satupun mahasiswa yang harus menempuh ujian dua mata kuliah di waktu yang sama, penentuan ruang ujian, dan penjadwalan pengawas ujian adalah pekerjaan yang sangat menyita waktu. Karena itu solver penjadwal ujian otomatis sangat diperlukan. Lebih dari itu, secara teoritis, permasalahan optimasi penjadwalan ujian ini merupakan NP-complete problem, dimana belum ada algoritma eksak yang mampu menyelesaiakan permasalahan ini dalam waktu non-polinomial. Sehingga permasalahan ini banyak menarik perhatian para peneliti, khususnya di bidang riset operasi dan kecerdasan buatan selama puluhan tahun belakangan ini. State-of-the-art pendekatan untuk memecahkan permasalahan ini adalah metode heuristic sekuensial berdasarkan permalahan pewarnaan graf dan meta-heuristic. Makalah ini membahas usulan metode baru yaitu metode heuristic sekuensial berdasarkan konsep maximal clique pada teori graf digabung dengan metode hyper-heuristic. Hasil penelitian komputasi menunjukkan bahwa metode ini sangat efektif untuk memecahkan permasalahan penjadwalan ujian dan lebih unggul jika dibandingkan dengan hasil penelitian sebelumnya dengan metode yang lain.
Full Text:
PDFReferences
Eugene L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt Rinehart and Winston, 1976.
Edmund K. Burke, Graham Kendall, Mustafa Misir, Ender Ozcan, EK Burke, G Kendall, and M Misir. Applications to timetabling. In Handbook of Graph Theory, chapter 5-6, pages 445–474, 2004.
Edmund K. Burke, Graham Kendall, Mustafa Misir, and Ender Ozcan. Monte Carlo hyper-heuristics for examination timetabling. Annals of Operations Re- search, 196(1): 73–90, 2012.
Tim B. Cooper and Jeffrey H. Kingston. The complexity of timetable construction problems. In Edmund Burke and Peter Ross, editors, Practice and Theory of Automated Timetabling, volume 1153 of Lecture Notes in Computer Science, pages 281–295. Springer Berlin Heidelberg, 1996.
Michael W. Carter, Gilbert Laporte, and Sau Y. Lee. Examination timetabling: Algorithmic strategies and applications. Journal of the Operational Research Society, 47(3): 373–383, 1996.
Barry McCollum, Paul McMullan, Andrew J. Parkes, Edmund K. Burke, and Rong Qu. A new model for automated examination timetabling. Annals of Operations Research, 194(1): 291–315, 2012.
Muklason A., Parkes A.J., McCollum B. and Ozcan E. Fairness in Examination Timetabling Problems, Journal of Applied Soft Computing, 55:302-318, 2017. DOI:10.1016/j.asoc.2017.01.026
Rong Qu, Edmund K. Burke, Barry McCollum, Liam T.G. Merlot, and Sau Y. Lee. A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling, 12(1): 55–89, 2009.
Jonathan M. Thompson and Kathryn A. Dowsland. General cooling schedules for a simulated annealing based timetabling system. In Edmund Burke and Peter Ross, editors, Practice and Theory of Automated Timetabling, volume 1153 of Lecture Notes in Computer Science, pages 345–363. Springer Berlin Heidelberg, 1996.
Edmund K. Burke, Yuri Bykov, James Newall, and Sanja Petrovic. A time- predefined local search approach to exam timetabling problems. IIE Transactions, 36(6):509–528, 2004.
A. Hertz. Tabu search for large scale timetabling problems. European Journal of Operational Research, 54(1):39–47, 1991.
Salwani Abdullah, Samad Ahmadi, Edmund K. Burke, and Moshe Dror. In- vestigating Ahuja-Orlin’s large neighbourhood search approach for examination timetabling. OR Spectrum, 29(2):351–372, 2007.
Samad Ahmadi, Rossano Barone, Peter Cheng, Edmund K. Burke, Peter Cowl- ing, and Barry McCollum. Perturbation based variable neighbourhood search in heuristic space for examination timetabling problem. In multidisciplinary inter- national scheduling: theory and applications (MISTA 2003), pages 155–171, 2003.
Edmund K. Burke, Tim Curtois, Matthew Hyde, Graham Kendall, Gabriela Ochoa, Sanja Petrovic, Jos ́e A. Va ́zquez-Rodr ́ıguez, and Michel Gendreau. Iter- ated local search vs. hyper-heuristics: Towards general-purpose search algorithms. In IEEE congress on evolutionary computation, pages 1–8. IEEE, 2010.
S. Casey and J. Thompson. GRASPing the examination scheduling problem. In E. Burke and P. DeCausmaecker, editors, Practice and Theory of Automated Timetabling IV, volume 2740 of Lecture Notes in Computer Science, pages 232– 244, 2003.
Edmund K. Burke, James P. Newall, and Rupert F. Weare. A memetic algo- rithm for university exam timetabling. In Edmund Burke and Peter Ross, editors, Practice and Theory of Automated Timetabling, volume 1153 of Lecture Notes in Computer Science, pages 241–250. Springer Berlin Heidelberg, 1996.
Bashar A. Aldeeb, Norita Md Norwawi, Mohammed A. Al-Betar, and Mohd Za- lisham Bin Jali. Solving university examination timetabling problem using intel- ligent water drops algorithm. In Bijaya Ketan Panigrahi, Ponnuthurai Nagarat- nam Suganthan, and Swagatam Das, editors, Swarm, Evolutionary, and Memetic Computing, volume 8947 of Lecture Notes in Computer Science, pages 187–200. Springer International Publishing, 2015.
Nelishia Pillay and W. Banzhaf. An informed genetic algorithm for the examination timetabling problem. Applied Soft Computing, 10(2):457–467, 2010.
K.A. Dowsland and J.M. Thompson. Ant colony optimization for the examination scheduling problem. Journal of the Operational Research Society, 56:426–438, 2005.
M. R. Malim, A. T. Khader, and A. Mustafa. Artificial immune algorithms for university timetabling. In E. K. Burke and H. Rudova, editors, 6th international conference on practice and theory of automated timetabling, pages 234–245, 2006.
Mohammed Azmi Al-Betar, Ahamad Tajudin Khader, and Iman Yi Liao. A harmony search with multi-pitch adjusting rate for the university course timetabling. In Zong Woo Geem, editor, Recent Advances In Harmony Search Algorithm, vol- ume 270 of Studies in Computational Intelligence, pages 147–161. Springer Berlin Heidelberg, 2010.
Jingpeng Li, Ruibin Bai, Yindong Shen, and Rong Qu. Search with evolutionary ruin and stochastic rebuild: A theoretic framework and a case study on exam timetabling. European Journal of Operational Research, 242(3):798–806, 2015.
Hamza Turabieh and Salwani Abdullah. A hybrid fish swarm optimisation algorithm for solving examination timetabling problems. In CarlosA.Coello Coello, editor, Learning and Intelligent Optimization, volume 6683 of Lecture Notes in Computer Science, pages 539–551. Springer Berlin Heidelberg, 2011.
Nasser R. Sabar, Masri Ayob, Graham Kendall, and Rong Qu. A honey-bee mating optimization algorithm for educational timetabling problems. European Journal of Operational Research, 216(3):533 – 543, 2012.
Malek Alzaqebah and Salwani Abdullah. Hybrid artificial bee colony search al- gorithm based on disruptive selection for examination timetabling problems. In Weifan Wang, Xuding Zhu, and Ding-Zhu Du, editors, Combinatorial Optimiza- tion and Applications, volume 6831 of Lecture Notes in Computer Science, pages 31–45. Springer Berlin Heidelberg, 2011.
Cheng Weng Fong, Hishammuddin Asmuni, Barry McCollum, Paul McMullan, and Sigeru Omatu. A new hybrid imperialist swarm-based optimization algorithm for university timetabling problems. Information Sciences, 283:1–21, 2014.
Souad Larabi Marie-Sainte. A survey of particle swarm optimization techniques for solving university examination timetabling problem. Artificial Intelligence Review, pages 1–10, 2015.
Edmund K. Burke, Matthew Hyde, Graham Kendall, Gabriela Ochoa, Ender Ozcan, and Rong Qu. A survey of hyper-heuristics. Technical report, University of Nottingham, 2009.
Quan-Ke Pan, M. Fatih Tasgetiren, P. N. Suganthan, and T. J. Chua. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Information Sciences, 181(12):2455–2468, 2011.
Gunter Dueck. New optimization heuristics: The great deluge algorithm and the record-to-record travel. Journal of Computational Physics, 104(1):86–92, 1993.
Edmund K. Burke and Y. Bykov. The late acceptance hill-climbing heuristic. Technical report, Computing Science and Mathematics, University of Stirling, 2012.
Edmund K. Burke, Graham Kendall, Mustafa Misir, and Ender O ̈zcan. Monte Carlo hyper-heuristics for examination timetabling. Annals of Operations Re- search, 196(1):73–90, 2012.
Nasser R. Sabar, Masri Ayob, Rong Qu, and Graham Kendall. A graph coloring constructive hyper-heuristic for examination timetabling problems. Applied Intelligence, 37(1):1–11, 2012.
SyarizaAbdul-Rahman,AndrzejBargiela,EdmundK.Burke,EnderO ̈zcan,Barry McCollum, and Paul McMullan. Adaptive linear combination of heuristic order- ings in constructing examination timetables. European Journal of Operational Research, 232(2):287–297, 2014.
Edmund K. Burke, Rong Qu, and Amr Soghier. Adaptive selection of heuristics for improving exam timetables. Annals of Operations Research, 218(1):129–145, 2014.
Salwani Abdullah and Malek Alzaqebah. A hybrid self-adaptive bees algorithm for examination timetabling problems. Applied Soft Computing, 13(8):3608–3620, 2013.
Refbacks
- There are currently no refbacks.
FAKULTAS SAINS DAN TEKNOLOGI
UIN SUSKA RIAU
Kampus Raja Ali Haji
Gedung Fakultas Sains & Teknologi UIN Suska Riau
Jl.H.R.Soebrantas No.155 KM 18 Simpang Baru Panam, Pekanbaru 28293
Email: sntiki@uin-suska.ac.id