Document Type : Research Paper
Authors
Abstract
Course timetabling is an important branch of the general scheduling problem. The course timetabling problem as a step in the course planning process in universities is one of the challenges faced by managers in the field of education. The problem is defined as assigning university courses to specific periods throughout a week for a given semester while satisfying specific constraints. In this study, we present two novel binary integer linear programming models for the university timetabling problem. Using a GAMS IP Solver, several experiments through each model are solved and the results (the number of the decision variables and solution time) are compared and analyzed. The computational comparison indicates that the second model can be used for modeling large-scaled problems and has less computational and size complexity. Therefore, the second model is applied to optimal scheduling the courses planned for the faculty of administrative science and economics (ASE) at Isfahan University for one semester and the results consist of table of courses planned for teachers, students groups, rooms and workdays are presented
Keywords
بهداد، محمد، دهقانی، تکتم، ذاکر تم یی، مهناز ) 4189 (م رویکردی نامی در زماان بنادی
درس ها ی دانشگاه با استفاده از الگامریتم ژنتصاکم دوازدهماص کنفاران باص المللای انهما
کامیصمتر ایران دانشگاه شهصد بهشتی، دانشکده مهندسی برق و کامیصمتر ،تهران، ایرانم
جاامدکی، مهصااد، منتظااری، محماادعلی، ممساامی، سااصد رساامل ) 4151 (م بررساای مساااله
زمان بندی درسی دانشاگاهی باا اساتفاده از ترکصاب الگامریتم ممتصاک بهبمدیافتاه و الگامریتم
سردشدن شبصه سازی شدهم مهندسی برق و مهندسی کامیصمتر ایران، دوره 5، شاماره 1، صا م
452 212 م -
خاتمی فصروز آبادی،ع، رحصمی مزرعه شااهی،م ، محتشامی،ع ) 4189 (م مادل ساازی مسا اله
زمان بندی دوره های تحصصلی در یک ممسسه آممزشی کمچکم مطالعاات مادیریت صانعتی
شماره 41 ، ص 91 25 م -
سلصمی فرد، خداکرم، بابایی زاده، سلمان ) 4151 (م یک سصستم پشتصبانی تصمصم بارای زماان
بندی کلاسهای دانشگاهم مدیریت فناوری اطلاعات، دوره 1، شماره 1، ص 11 55 م -
منهمی، سصد امصر حسص ، مسعمدیان، سملماز، استکی، افسانه، نعمت بخش، ناصار ) 4188 (م
طراحی جدول زمان بندی خمدکار برای درس ها دانشگاهی با استفاده از الگمریتم های ژنتصکم
فناوری آممزش، دوره 1، شماره 2، ص 441 421 م -
Agarwal, A., Colak, S., & Erenguc, S. (2011). A neurogenetic approach for the resource-constrained project scheduling problem. Computers & Operations Research, 38 (1), 44-50.
Akkoyunlu, E. A. (1973). A linear algorithm for computing the optimum university timetable. The Computer Journal, 16 (4), 347-350.
Alzaqebah, M., & Abdullah, S. (2015). Hybrid bee colony optimization for examination timetabling problems. Computers &
Operations Research, 54, 142-154.
Al-Betar, M. A., Khader, A. T., & Zaman, M. (2012). University course timetabling using a hybrid harmony search metaheuristic algorithm. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 42 (5), 664-681.
Al-Yakoob, S. M., & Sherali, H. D. (2007). A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations. European Journal of Operational Research, 180 (3), 1028-1044.
Badoni, R. P., Gupta, D. K., & Mishra, P. (2014). A new hybrid algorithm for university course timetabling problem using events based on groupings of students. Computers & Industrial Engineering, 78, 12-25.
Badri, M. A., Davis, D. L., Davis, D. F., & Hollingsworth, J. (1998). A multi-objective course scheduling model: Combining faculty preferences for courses and times. Computers & operations research, 25 (4), 303-316.
Barrera, D., Velasco, N., & Amaya, C. A. (2012). A network-based approach to the multi-activity combined timetabling and crew scheduling problem: Workforce scheduling for public health policy implementation. Computers & Industrial Engineering, 63 (4), 802-812.
Basir, N., Ismail, W., & Norwawi, N. M. (2013). A Simulated Annealing for Tahmidi Course Timetabling. Procedia Technology, 11, 437-445.
Daskalaki, S., Birbas, T., & Housos, E. (2004). An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153 (1), 117-135.
De Causmaecker, P., Demeester, P., & Berghe, G. V. (2009). A decomposed metaheuristic approach for a real-world university
timetabling problem. European Journal of Operational Research, 195 (1), 307-318.
Hao, J. K., & Benlic, U. (2011). Lower bounds for the ITC-2007 curriculum-based course timetabling problem. European Journal of Operational Research, 212 (3), 464-472.
Kahar, M. M., & Kendall, G. (2010). The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution. European Journal of Operational Research, 207 (2), 557-565.
Kaspi, M., & Raviv, T. (2013). Service-oriented line planning and timetabling for passenger trains. Transportation Science, 47 (3), 295-311.
Kostuch, P. (2005). The university course timetabling problem with a three-phase approach. In Practice and Theory of Automated Timetabling V (pp. 109-125). Springer Berlin Heidelberg.
Mcmullan, P. (2007). An extended implementation of the great deluge algorithm for course timetabling. In Computational Science–ICCS 2007 (pp. 538-545). Springer Berlin Heidelberg.
MirHassani, S. A., & Habibi, F. (2013). Solution approaches to the course timetabling problem. Artificial Intelligence Review, 39 (2), 133-149.
Nothegger, C., Mayer, A., Chwatal, A., & Raidl, G. R. (2012). Solving the post enrolment course timetabling problem by ant colony optimization. Annals of Operations Research, 194 (1), 325-339.
Nurmi, K., Goossens, D., & Kyngäs, J. (2013). Scheduling a triple round robin tournament with minitournaments for the Finnish national youth ice hockey league. Journal of the Operational Research Society, 65 (11), 1770-1779.
Phillips, A. E., Waterer, H., Ehrgott, M., & Ryan, D. M. (2015). Integer programming methods for large-scale practical classroom
assignment problems. Computers & Operations Research, 53, 42-53.
Pita, J. P., Barnhart, C., & Antunes, A. P. (2012). Integrated flight scheduling and fleet assignment under airport congestion. Transportation Science, 47 (4), 477-492.
Post, G., Kingston, J. H., Ahmadi, S., Daskalaki, S., Gogos, C., Kyngas, J., ... & Schaerf, A. (2014). XHSTT: an XML archive for high school timetabling problems in different countries. Annals of Operations Research, 218 (1), 295-301.
Shafia, M. A., Aghaee, M. P., Sadjadi, S. J., & Jamili, A. (2012). Robust Train Timetabling problem: Mathematical model and Branch and bound algorithm. Intelligent Transportation Systems, IEEE Transactions on, 13 (1), 307-317.
درس ها ی دانشگاه با استفاده از الگامریتم ژنتصاکم دوازدهماص کنفاران باص المللای انهما
کامیصمتر ایران دانشگاه شهصد بهشتی، دانشکده مهندسی برق و کامیصمتر ،تهران، ایرانم
جاامدکی، مهصااد، منتظااری، محماادعلی، ممساامی، سااصد رساامل ) 4151 (م بررساای مساااله
زمان بندی درسی دانشاگاهی باا اساتفاده از ترکصاب الگامریتم ممتصاک بهبمدیافتاه و الگامریتم
سردشدن شبصه سازی شدهم مهندسی برق و مهندسی کامیصمتر ایران، دوره 5، شاماره 1، صا م
452 212 م -
خاتمی فصروز آبادی،ع، رحصمی مزرعه شااهی،م ، محتشامی،ع ) 4189 (م مادل ساازی مسا اله
زمان بندی دوره های تحصصلی در یک ممسسه آممزشی کمچکم مطالعاات مادیریت صانعتی
شماره 41 ، ص 91 25 م -
سلصمی فرد، خداکرم، بابایی زاده، سلمان ) 4151 (م یک سصستم پشتصبانی تصمصم بارای زماان
بندی کلاسهای دانشگاهم مدیریت فناوری اطلاعات، دوره 1، شماره 1، ص 11 55 م -
منهمی، سصد امصر حسص ، مسعمدیان، سملماز، استکی، افسانه، نعمت بخش، ناصار ) 4188 (م
طراحی جدول زمان بندی خمدکار برای درس ها دانشگاهی با استفاده از الگمریتم های ژنتصکم
فناوری آممزش، دوره 1، شماره 2، ص 441 421 م -
Agarwal, A., Colak, S., & Erenguc, S. (2011). A neurogenetic approach for the resource-constrained project scheduling problem. Computers & Operations Research, 38 (1), 44-50.
Akkoyunlu, E. A. (1973). A linear algorithm for computing the optimum university timetable. The Computer Journal, 16 (4), 347-350.
Alzaqebah, M., & Abdullah, S. (2015). Hybrid bee colony optimization for examination timetabling problems. Computers &
Operations Research, 54, 142-154.
Al-Betar, M. A., Khader, A. T., & Zaman, M. (2012). University course timetabling using a hybrid harmony search metaheuristic algorithm. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 42 (5), 664-681.
Al-Yakoob, S. M., & Sherali, H. D. (2007). A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations. European Journal of Operational Research, 180 (3), 1028-1044.
Badoni, R. P., Gupta, D. K., & Mishra, P. (2014). A new hybrid algorithm for university course timetabling problem using events based on groupings of students. Computers & Industrial Engineering, 78, 12-25.
Badri, M. A., Davis, D. L., Davis, D. F., & Hollingsworth, J. (1998). A multi-objective course scheduling model: Combining faculty preferences for courses and times. Computers & operations research, 25 (4), 303-316.
Barrera, D., Velasco, N., & Amaya, C. A. (2012). A network-based approach to the multi-activity combined timetabling and crew scheduling problem: Workforce scheduling for public health policy implementation. Computers & Industrial Engineering, 63 (4), 802-812.
Basir, N., Ismail, W., & Norwawi, N. M. (2013). A Simulated Annealing for Tahmidi Course Timetabling. Procedia Technology, 11, 437-445.
Daskalaki, S., Birbas, T., & Housos, E. (2004). An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153 (1), 117-135.
De Causmaecker, P., Demeester, P., & Berghe, G. V. (2009). A decomposed metaheuristic approach for a real-world university
timetabling problem. European Journal of Operational Research, 195 (1), 307-318.
Hao, J. K., & Benlic, U. (2011). Lower bounds for the ITC-2007 curriculum-based course timetabling problem. European Journal of Operational Research, 212 (3), 464-472.
Kahar, M. M., & Kendall, G. (2010). The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution. European Journal of Operational Research, 207 (2), 557-565.
Kaspi, M., & Raviv, T. (2013). Service-oriented line planning and timetabling for passenger trains. Transportation Science, 47 (3), 295-311.
Kostuch, P. (2005). The university course timetabling problem with a three-phase approach. In Practice and Theory of Automated Timetabling V (pp. 109-125). Springer Berlin Heidelberg.
Mcmullan, P. (2007). An extended implementation of the great deluge algorithm for course timetabling. In Computational Science–ICCS 2007 (pp. 538-545). Springer Berlin Heidelberg.
MirHassani, S. A., & Habibi, F. (2013). Solution approaches to the course timetabling problem. Artificial Intelligence Review, 39 (2), 133-149.
Nothegger, C., Mayer, A., Chwatal, A., & Raidl, G. R. (2012). Solving the post enrolment course timetabling problem by ant colony optimization. Annals of Operations Research, 194 (1), 325-339.
Nurmi, K., Goossens, D., & Kyngäs, J. (2013). Scheduling a triple round robin tournament with minitournaments for the Finnish national youth ice hockey league. Journal of the Operational Research Society, 65 (11), 1770-1779.
Phillips, A. E., Waterer, H., Ehrgott, M., & Ryan, D. M. (2015). Integer programming methods for large-scale practical classroom
assignment problems. Computers & Operations Research, 53, 42-53.
Pita, J. P., Barnhart, C., & Antunes, A. P. (2012). Integrated flight scheduling and fleet assignment under airport congestion. Transportation Science, 47 (4), 477-492.
Post, G., Kingston, J. H., Ahmadi, S., Daskalaki, S., Gogos, C., Kyngas, J., ... & Schaerf, A. (2014). XHSTT: an XML archive for high school timetabling problems in different countries. Annals of Operations Research, 218 (1), 295-301.
Shafia, M. A., Aghaee, M. P., Sadjadi, S. J., & Jamili, A. (2012). Robust Train Timetabling problem: Mathematical model and Branch and bound algorithm. Intelligent Transportation Systems, IEEE Transactions on, 13 (1), 307-317.
)