زمان بندی کلاس های درس با استفاده از برنامه ریزی عدد صحیح

نوع مقاله: مقاله پژوهشی

نویسندگان

1 استادیار گروه مدیریت ، دانشکده علوم اداری و اقتصاد، دانشگاه اصفهان

2 دانش آموخته کارشناسی ارشد مدیریت صنعتی

چکیده

زمان بندی کلاس های درس یکی از شاخه های مهم مسااله هاای عماممی زماان بنادی اساتم مسااله زماان بنادی
درس ها، به عنمان یک گام از فرایند برنامه ریزی درسی در دانشگاه ها، از جمله چالش هایی است که برنامه ریزان
حمزه آممزش با آن مماجه هستندم مساله عبارت است از تخصاص درس هاای دانشاگاهی باه دوره هاای زماانی
خاص در طمل هفته برای یک نصم سال تحصاصلی باه طامری کاه محادودیت هاای معصنای ار اا گردنادم در ایا
پژوهش، دو مدل برنامه ریزی خطی 1 4 عدد صحصح برای مساله زمان بندی کلاس های درسی ارائه شده اساتم -
چند مساله نممنه با استفاده از هر دو مدل، مدلسازی و با نارم افازار GAMS حا و نتصهاه هاای بدسات آماده
)تعداد متغصرها و زمان ح ( مقایسه و تحلص شده اندم مقایسه نتصههها نشان می دهد که مادل دوم، تماناایی مادل -
سازی مسالههای با اندازه هاای بازرر را داشاته و از پصگصادگی انادازه و محاساباتی کمتاری برخامردار اساتم
بنابر ای ، ای مدل برای زمان بندی بهصنه درس های یاک ناصم ساال تحصاصلی در دانشاکده ااتصااد و علامم اداری
دانشگاه اصفهان استفاده شده و نتصهههای آن شام جداول زمانبندی دروس اسااتصد، گاروه هاای دانشاهمیان،
کلاسهای درس و روزهای هفته ارائه گردیده استم

کلیدواژه‌ها


عنوان مقاله [English]

Binary Integer Programming for University Timetabling (The Case: Faculty of Administrative Sciences and Economics of Esfahan University)

نویسندگان [English]

  • Majid Esmaelian 1
  • Sayedeh Maryam Abdollahi 2
چکیده [English]

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

کلیدواژه‌ها [English]

  • Course timetabling problem
  • integer linear programming
  • Optimization
بهداد، محمد، دهقانی، تکتم، ذاکر تم یی، مهناز ) 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.