مدل‌سازی و حل مسئله برنامه‌ریزی دروس دانشگاهی با منابع محدود در جهت برقراری حداکثری قیود سخت و نرم

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

نویسندگان

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

2 دانشجوی کارشناسی ارشد ریاضی کاربردی، دانشکده ریاضی، دانشگاه علم وصنعت ایران، تهران، ایران

چکیده

مسئله برنامه‌ریزی دروس دانشگاهی، به ارائه یک جدول زمان‌بندی می‌پردازد که هدف آن، تخصیص دروس به بازه‌های زمانی مختلف در طول هفته و تعیین چینشی از دروس است که ضمن رعایت مقررات آموزشی از نظر مدرس، دانشجو و امکانات دانشگاه قابل قبول و انجام پذیر باشد. در این مقاله سعی شده است، یک مسئله برنامه‌ریزی را مورد بررسی قرار گرفته که همه محدودیت‌های برنامه ریزی و فشرده بودن برنامه درسی، توزیع برنامه دروس در چارچوب زمانی بررسی شده، ترجیحات اساتید، حداقل تعداد روزهای کاری، حداکثر ظرفیت و پابرجایی کلاس‌ها (با هدف حداقل کردن رفت و آمد روزانه دانشجویان بین کلاس‌ها) رعایت شوند. جهت مدل سازی مساله، یک مسئله برنامه‌ریزی ریاضی از نوع غیرخطی عدد صحیح و با ابعاد بزرگ را در نظر گرفته ایم. حل مدل ریاضی به کمک نرم افزارها GAMS انجام و نتایج برنامه ریزی درسی برای ترم دوم کارشناسی ارشد ریاضی کاربردی دانشگاه علم و صنعت در پایان گزارش شده است.

کلیدواژه‌ها


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

Modeling and solving Course Timetabling Problem in order to maximize the efficiency of hard and soft constraints

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

  • Mahboubeh Molavi-Arabshahi 1
  • Javad Vahidi 1
  • Samira Talebi 2
1 Assistant Professor, Department of Applied Mathematics, Faculty of Mathematics, Iran University of Science and Technology, Tehran, Iran
2 Master's student in Applied Mathematics, Faculty of Mathematics, Iran University of Science and Technology, Tehran, Iran
چکیده [English]

The problem of course timetabling problem deals with the creation of a timetable, the purpose of which is to assign courses to different time periods in the week and to determine an arrangement of courses that is acceptable and feasible for teachers, students, and higher education institutions while complying with the educational regulations.
In this work, we attempted to consider a scheduling problem in which the compactness of the curriculum, the distribution of the course schedule in the time frame, the preferences of the professors, the minimum number of working days, the maximum capacity, and the sustainability of the classes (with the goal of minimizing the daily commute of students between classes) should be considered. To model the problem, we considered a mathematical programming problem of nonlinear integer type with large dimensions. The solution of the mathematical model with using the software GAMS and the results of course planning for the second semester of the master's program in applied mathematics at Iran University of Science and Technology are reported at the end.

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

  • University course timetabling
  • Curriculum
  • Integer programming
  • mathematical modeling
[1] Almond, M., An algorithm for constructing university timetables, Computer Journal, vol.8, pp.331-340,1966.
[2] Abdennadher, S. and Marte, M., University course timetabling using Constraint Handling Rules, Journal of Applied Artificial Intelligence, vol.14, No.4, pp.311–326,2000.
[3] Wren A. on “Scheduling, timetabling and rostering-A special relationship? Lecture Notes” in Computer Science, vol. 1153, pp.46-75,1996.
[4] Even S. and Itai A. and Shamir A. On “The Complexity of Time Table and Multicommodity Flow Problems” in SIAM J. Comput., vol. 5, pp.691-703, 1976.
[5] Chen, C. C. and Smith, S. F., “Applying constraint satisfaction techniques to job shop scheduling,” Annals of Operations Research, vol.70, pp.327-357,1997.
[6] Cavdur, F. and Kose, M. “A fuzzy logic and binary-goal programming-based approach for solving the exam timetabling problem to create a balanced-exam schedule,” International Journal of Fuzzy Systems, Vol. 18, pp. 119-129, 2016.
[7] Chahal, N. and de Werra, D., “An interactive system of constructing timetables on a PC,” European Journal of Operational Research, vol.40, pp.32-37, 1989.
[8] Deris S. and Omatu S. and Ohta H., “Timetable Planning using the Constraint-based Reasoning,” Computer and Operations Research, Vol.27,819-840, 2000.
[9] Asadi, Z., Valipour khatir, M., Safaei, A., “Modeling and solving Multi-objective Vehicle Routing Problem of Distribution Companies with Fuzzy and Stochastic Constraints (Case Study)”, Modern Researches in Decision Making, 4(1), 1-24, 2019.
[10] Tarin, N., Azar, A., Ebrahimi, A., “Design of multi-period Reverse logistic model with different product recovery routes under uncertainty”, Modern Researches in Decision Making, 2(4), 29-56, 2018.
[11] Costa, D., “A tabu search algorithm for computing an operational timetable,” European Journal of Operational Research, vol.76, No.1, pp.98–110,1994.
[12] Mulvey, J., “A classroom time assignment model”, European Journal of Operational Research, vol.9, pp.64-70, 1982.
[13] Feng, X., Lee, Y. and Moon, I., “An integer program and a hybrid genetic algorithm for the university timetabling problem,” Optimization Methods and Software, Vol. 32, pp. 625- 649, 2017.
[14] Yang, S., and Jat, S. N., “Genetic algorithms with guided and local search strategies for university course timetabling,” IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), Vol. 41, pp. 93-106, 2011.
[15] Babaei, H. , Karimpour, J., and Hadidi, A. “A survey of approaches for university course timetabling problem,” Computers & Industrial Engineering, Vol. 86, 43-59, 2015.
[16] Daskalaki, S., Birbas, T. and Housos, E. “An integer programming formulation for a case study in university timetabling,” European Journal of Operational Research, Vol. 153, pp. 117-135, 2004.
 [17]Rossi Doria O. and  Paechter B. “A memetic algorithm for university course timetabling,” Proceedings of Combinatorial Optimization (CO 2004), pp. 56. 2004.
[18] Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., zcan, E., and Qu, R., “Hyper-heuristics: A survey of the state of the art,” Journal of the Operational Research Society, Vol. 64, pp. 1695-1724, 2013.
[19] Nandhini, M. and Kanmani, “A survey of simulated annealing methodology for university course timetabling,” International Journal of Recent Trends in Engineering, Vol. 1,255-262, 2009.
[20] Mahdavi, A., “Designing Quality Measurement Model of Information System Services Based on Genetic Algorithm”, The Journal of Management Research in Iran, 11(20), 235-263, 2007.  
[21] Ghalehgolabi, M. and Rezaeipanah, A. “Intrusion Detection System Using Genetic Algorithm and Data Mining Techniques Based on the Reduction Features,” International Journal of Computer Applications Technology and Research, Vol. 6, pp. 461- 466, 2016.
[22] Ramani A., Aloul F., Markov I.  and Sakallah K., “Breaking instance independent symmetries in Exact Graph Coloring,” Journal of Artificial Intelligence Research, Vol.26, pp.289-322,2006.
[23] Akbari, M., “A model for production and inventory control in crisis condition”, The Journal of Management Research in Iran, 19(4), 45-70, 2016.
[24] Datta, K. Deb, Fonseca, C. M., “Multi-objective evolutionary algorithm for university class timetabling problem,” Evolutionary scheduling, Springer, Berlin, Heidelberg, pp. 197- 236, 2017.
[25] Werra, D. De, “An introduction to Timetabling”, European Journal of Operations Research, Vol.19, ,151-162,1985.
[26] Lewis R., “A Survey of Metaheuristic based techniques for University Timetabling problems”, OR Spectrum, Vol.30,167-190,2008.
[27] Rogalska, M., Bożejko, W. and Hejducki, Z., “Time/cost optimization using hybrid evolutionary algorithm in construction project scheduling,” Automation in Construction, Vol. 18, pp. 24-31, 2008.
[28] Lei, Y., Gong, M., Jiao, L.  and Zuo, Y., “A memetic algorithm based on hyper-heuristics for examination timetabling problems,” International Journal of Intelligent Computing and Cybernetics, Vol. 8, pp. 139-151, 2015.