KULLANICI TERCİHLERİNİN DİKKATE ALINMASI DURUMUNDA ÜNİVERSİTE DERS ÇİZELGELEME PROBLEMİ

Yıl 2016, Cilt: 27 Sayı: 1, 2 - 16, 25.03.2016

Zehra Kamışlı Öztürk , Nergiz Kasımbeyli , Müjgan Sağır Özdemir , Müge Soyuöz Acar Erdener Özçetin Mehmet Alegöz Gürhan Ceylan

Öz

Bu çalışmada, üniversitelerde bir eğitim döneminde en az iki defa karşılaşılan bir eğitimsel zaman çizelgeleme problemi için kaliteli çözümlerin elde edilmesi amacıyla, çok amaçlı 0-1 tamsayılı bir matematiksel model sunulmuştur. Faaliyetlerin (ders) kaynaklara (derslik-zaman) atandığı ders-derslik-zaman çizelgeleme problemi kısıt ve değişken sayıları açısından büyük boyutlu bir problemdir. Bu problemin çözümü, yoğun iş gücü ve kaynak gerektirmektedir. Dolayısıyla, eğitim kurumları açısından önemli olduğu kadar, zor da bir problemdir. Temel atama kısıtlarının yanı sıra, kurumdan kuruma değişmekle birlikte, her problemin kendine özgü kısıt ve amaç fonksiyonları bulunmaktadır. Çalışmada, çok ölçütlü bir karar verme modeli ile kullanıcı tercih ve istekleri de dikkate alınarak geliştirilen matematiksel model, Anadolu Üniversitesi bünyesinde bir bölüme ait veriler ile ağırlıklı toplam skalerleştirme yöntemi kullanılarak çözdürüldüğünde, kabul edilebilir bir sürede en iyi çözüme ulaşılmıştır. Elde edilen çizelge mevcut çizelge ile karşılaştırıldığında, önerilen sistemin öğrenciler, öğretim üyeleri ve kaynak kullanımı açısından genel performansı arttırıcı yönde iyi sonuç verdiği görülmüştür.

Anahtar Kelimeler

Çok ölçütlü karar verme, ders-derslik-zaman çizelgeleme problemi, matematiksel modelleme

Destekleyen Kurum

ANADOLU ÜNİVERSİTESİ

Proje Numarası

14053F070

Teşekkür

Bu çalışma, 14053F070 numaralı Anadolu Üniversitesi BAP tarafından desteklenmiştir. Desteklerinden dolayı Anadolu Üniversitesi'ne teşekkür ederiz.

UNIVERSITY COURSE SCHEDULING PROBLEMS IN CASE OF CONSIDERATION OF THE USER PREFERENCES

Öz

In this study, a multi objective 0-1 integer mathematical model is proposed for the purpose of obtaining high-quality solutions to an educational timetabling problem faced a few times in each term in the universities.  The course-room-time slot scheduling problem which assigns events (course) to resources (room-time slot) is a big dimensional problem based on the number of constraints and variables. The solution to this problem requires intensive labor and resources. Thus, the problem is important for educational institutions, and also is a difficult problem. Beside the main assignment constraints, each of them has its own specific constraint and objectives changing from one institution to another. The mathematical model which is developed by considering the user preferences with a multi criteria decision making model was experimented by using the data of a department in Anadolu University. During the solution step, the weighted sum scalarization method is used and it is seen that the mathematical model found the optimal solution within a reasonable time. The outcome is compared with the current schedule. The proposed approach gives better solutions will increase overall performance of the educational systems from the point of students and instructors.  

Anahtar Kelimeler

Multi cirteria decision making, course-room-time slot scheduling problem, mathematical modelling

Proje Numarası

14053F070

Kaynakça

• 1. Abuhamdah, A., Ayob, M. 2009. “Experimental Result of Particle Collision Algorithm For Solving Course Timetabling Problems,” International Journal of Computer Science and Network Security, vol. 9 (9), p. 134-142.
• 2. Abuhamdah, A., Ayob, M., Kendall, G., Sabar, N. 2014. “Population Based Local Search for University Course Timetabling Problems,” Applied Intelligence, vol. 40, p. 44–53.
• 3. Achá, R., Nieuwenhuis, R. 2014. “Curriculum-Based Course Timetabling with SAT and Maxsat,” Annals of Operations Research, vol. 218, p. 71–91.
• 4. Akyol, E., Saraç, T. 2012, “Plastik Parçalar Üreten bir Firmanın Montaj Hatlarının Çizelgelenmesi,” MMO Endüstri Mühendisliği Dergisi, sayı 23 (2), s. 28-41.
• 5. Al-Betar, M., Khader, A., Zaman, M. 2012, “University Course Timetabling Using a Hybrid Harmony Search Metaheuristic Algorithm,” IEEE Transactıons On Systems, Man and Cybernetıcs—Part C: Applıcatıons and Reviews, vol. 42 (5), p. 664-680.
• 6. Azimi, Z. N. 2005. “Hybrid Heuristics for Examination Timetabling Problem,” Applied Mathematics and Computation, vol. 163, p. 705-733.
• 7. Azmat, C. S., Widmer, M. 2004. “A Case Study of Single Shift Planning and Scheduling Under Annualized Hours: A Simple Three-Step Approach,” European Journal of Operational Research, vol. 153, p. 148–175.
• 8. Badri, M. A. 1996. “A Two-Stage Multiobjective Scheduling Model For Faculty-Course-Time Assignments,” European Journal of Operational Research, vol. 94, p. 16–28.
• 9. Beligiannis, G. N., Moschopoulosa, C. N., Kaperonisa, G. P., Likothanassisa, S. D. 2008. “Applying Evolutionary Computation To The School Timetabling Problem: The Greek Case,” Computers and Operations Research, vol. 35 (4), p. 1265-1280.
• 10. Bolaji, A. L., Kahader, A. T., Al-Betar, M. A. 2014. “University Course Timetabling Using Hybridized Artificial Bee Colony with Hill Climbing Optimizer,” Journal of Computational Science, vol. 5, p. 809-818.
• 11. Boronico, J. 2000. “Quantitative Modeling and Technology Driven Departmental Course Scheduling,” Omega, vol. 28, p. 327-346.
• 12. Burke, E. K., Newall, J. P., Weare, R. F. 1996. “A Memetic Algorithm For University Exam Timetabling,” Lecture Notes in Computer Science, 1153. The Practice and Theory of Automated Timetabling: Selected Papers (ICPTAT 95), Burke, E. K., Ross, P. (Ed.), Springer-Verlag, Berlin, Heidelberg, New York, p. 241-250.
• 13. Burke, E. K., Kendall, G., Soubeiga, E. 2003. “A Tabu Search Hyperheuristic for Timetabling and Rostering,” Journal of Heuristics, vol. 9 (6), p. 451-470.
• 14. Burke, E. K., McCollum, B., Meisels, A., Petrovic, S., Qu, R. 2007. “A Graph-Based Hyper-Heuristic for Educational Timetabling Problems,” European Journal of Operational Research, vol. 176, p. 177-192.
• 15. Carrasco, M. P., Pato, M. V. 2004. “A Comparision of Discrete and Continuous Neural Network Approaches to Solve The Class/Teacher Timetabling Problem,” European Journal of Operational Research, vol. 153, p. 65-79.
• 16. Chen, R., Shih, H. 2013. “Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search,” Algorithms, vol. 6, p. 227-244.
• 17. Chiarandini, M., Birattari, M., Socha, K., Rossi-Doria, O. 2006. “An Effective Hybrid Algorithm for University Course Timetabling,” Journal of Scheduling, vol. 9, p. 403-432.
• 18. Corne, D., Ross, P., Fang, H. 1994. “Evolutionary Timetabling: Practice, Prospects and Work in Progress,” Presented at the UK Planning and Scheduling SIG Workshop, Strathclyde.
• 19. Corr, P., McCollum, B., McGreevy, M., McMullan, P. 2006. “A New Neural Network Based Construction Heuristic for The Examination Timetabling Problem,” PPSN IX, Lecture Notes in Computer Science, vol. 4193, p. 392-401.
• 20. Daskalaki, S., Birbas, T., Housos, E. 2004. “An Integer Programming Formulation for a Case Study in University Timetabling,” European Journal of Operational Research, vol. 153, p. 117–135.
• 21. Dinkel, J. J., Mote, J., Venkataramanan, M. A. 1989. “An Efficient Decision Support System for Academic Course Scheduling,” Operations Research, vol. 37 (6), p. 853-864.
• 22. Dowsland, K. A. 1990. “A Timetabling Problem in Which Clashes are Inevitable,” Journal of Operations Research, vol. 41 (10), p. 907-918.
• 23. Gani, T. A., Khader, A. T., Budiarto, R. 2004. “Optimizing Examination Timetabling Using a Hybrid Evolution Strategies,” 2nd International Conference on Autonomous Robots and Agents, Palmerston North, New Zealand, p. 345-349.
• 24. Gunawan, A., Ng, K. M., Poh, K. L. 2007. “Solving The Teacher Assignment-Course Scheduling Problem by a Hybrid Algorithm,” International Journal of Computer, Information, and Systems Science, and Engineering, vol. 1 (2), p. 136-141.
• 25. Harwood, G. B., Lawless, R. W. 1975. “Optimizing Organizational Goals in Assigning Faculty Teaching Schedules,” Decision Sciences, vol. 6 (3), p. 513–524.
• 26. Ismayilova, N., Sagir Özdemir, M., Gasimov, R. 2007. “A Multiobjective Faculty-Course-Time Slot Assignment Problem with Preferences,” Mathematical and Computer Modelling, vol. 46 (7-8), p. 1017-1029.
• 27. Koçanlı, M. M., Aydınbeyli, Y. E. Saraç, T. 2013. “Eti Şirketler Grubu’nda Üretim Çizelgeleme Problemi için bir Hedef Programlama Modeli ve Genetik Algoritma,” MMO Endüstri Mühendisliği Dergisi, vol. 23 (3), p. 4-21.
• 28. Kostuch, P. 2005. “The University Course Timetabling Problem with A Three-Phase Approach,” Practice and Theory of Automated Timetabling V, Lecture Notes in Computer Science, vol. 3616, p. 109-125.
• 29. Köçken, H. G., Özdemir, R. Ahlatcıoğlu, M. 2014. “Üniversite Ders Zaman Çizelgeleme Problemi İçin Ikili Tamsayılı Bir Model ve Bir Uygulama,” İstanbul Üniversitesi İşletme Fakültesi Dergisi, vol. 43 (1), p. 28-54.
• 30. Liebchen, C., Möhring, R. H. 2002. “A Case Study in Periodic Timetabling,” Electronic Notes in Theoretical Computer Science, vol. 66 (2), p. 1–14.
• 31. MirHassani, S. A. 2006. “A Computational Approach to Enhancing Course Timetabling with Integer Programming,” Applied Mathematics and Computation, vol. 175 (1), p. 814-822.
• 32. Ozdemir, M. S., Gasimov, R. N. 2004. “The Analytic Hierarchy Process and Multiobjective 0-1 Faculty Course Assignment,” European Journal of Operational Research, vol. 157, p. 398-408.
• 33. Paquete, L. F., Fonseca, C. M. 2001. “A Study of Examination Timetabling with Multiobjective Evolutionary Algorithms,” MIC‘2001 - 4th Metaheuristics International Conference, 16-20 July 2001, Porto, Portugal, p. 149-153.
• 34. Petrovic, S., Burke, E. K. 2004. “University Timetabling,” J. Leung (Ed.) In Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapter 45. Chapman Hall/CRC Press, New York, Washington.
• 35. Qaurooni, D., Akbarzadeh-T, M. 2013. “Course Timetabling Using Evolutionary Operators,” Applied Soft Computing, vol. 13, p. 2504-2514.
• 36. Santiago-Mozos, R., Salcedo-Sanz, S., dePrado-Cumplido, M., Bousoño-Calzón, C. 2005. “A Two-Phase Heuristic Evolutionary Algorithm for Personalizing Course Timetables: A Case Study in a Spanish University,” Computers and Operations Research, vol. 32, p. 1761-1776.
• 37. Schaerf, A. 1999. “A Survey of Automated Timetabling,” Artificial Intelligence Review, vol. 13 (2), p. 87-127.
• 38. Shiau, D. F. 2011. “A Hybrid Particle Swarm Optimization for a University Course Scheduling Problem with Flexible Preferences,” Expert Systems with Applications, vol. 38, p. 235–248.
• 39. Smith, K. A., Abramson, D., Duke, D. 2003. “Hopfield Neural Networks for Timetabling: Formulations, Methods, and Comparative Results,” Computers & Industrial Engineering, vol. 44 (2), p. 283–305.
• 40. Socha, K., Knowles, J., Samples, M. 2003. “A Max-Min and System for the University Course Timetabling Problem,” In Proceedings of the 3rd International Workshop on Ant Algorithms, ANTS 2002, Springer Lecture Notes in Computer Science, vol. 2463 (10), p. 1-13.
• 41. Wehrer, A., Yellen, J. 2014. “The Design and Implementation of an Interactive Course-Timetabling System,” Annals of Operations Research, vol. 218, p. 327–345.