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

نویسندگان

1 دانشکده مهندسی صنایع و مکانیک، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران.

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

3 دانشگاه آزاد اسلامی قزوین

چکیده

جدول زمانبندی درسی، مسئله تخصیص هفتگی یک مجموعه درس و استاد به مکان و زمان بنا بر یکسری محدودیت های سخت و نرم در دانشگاه می‌باشد. در هر نیمسال، مدیران گروه‌های آموزشی برای تولید جدول زمانبندی درسی از جدول‌‌های نیمسال‌های گذشته و روش سعی و خطا استفاده می‌کنند؛ هر چند تغییر سریع نیازمندی‌های دانشگاه در هر نیمسال، محدودیتها و قوانین حاکم سبب گردیده این روش راه حل مناسبی به شمار نمی‌آید. در این پژوهش به طراحی و توسعه مدل ریاضی دو هدفه با در نظر گرفتن ترجیحات دانشجویان و اساتید پرداختیم، از آنجایی که مدل به دلیل پیچیدگی از روش های مرسوم مسائل غیرخطی قابل حل نبود از الگوریتم متاهیوریستک تبریدشبیه سازی شده برای حل مدل ریاضی در دو مرحله، بهره‌برده ایم. در مرحله اول ، سیستم به صورت خودکار جواب هایی را تولید می‌کند که در آن کلیه محدودیت های سخت برآورده می‌شود. سپس، این جواب ها در مرحله دوم با لحاظ کردن ساختارهای همسایگی مختلف بهبود می‌یابند، این مجموعه در بسته نرم افزار کامپیوتری با محیط کاربری توسط زبان برنامه نویسی C# و بکارگیری پایگاه دادهSQL پیاده سازی شده است. این سیستم، توسط داده‌هایی که از دانشگاه آزاد گرد آمده است، امتحان گردیده و نتایج حاکی از پیشرفت چشمگیری‌ است که نسبت به فرآیند دستی وجود دارد. در کل سیستم انعطاف پذیر و آسان برای امتحان سناریوهای مختلف زمانبندی است.

کلیدواژه‌ها

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

Development of multi-objective simulated annealing based decision support system for course timetabling with consideration preferences of teachers and students

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

  • shaghayegh Vaziri 1
  • Arash Zaretalab 2
  • Mani Sharifi 3

1 Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran

2 Department of Industrial Engineering, Amirkabir University of Technology, 424 Hafez Avenue, Tehran, Iran.

چکیده [English]

Course timetabling problem is a weekly assignment a set of course and teacher to the time and space with considering a lot of hard and soft constraints in universities. In each semester, heads of educational institutes take too much time and effort to prepare a timetable by using trial and error method or last semester's timetable, although the rapid changing needs, resources and rules of each semester causes this method are not the perfect solutions. In this study, we design and develop a novel multi objective mathematical model which taking into account the preferences of students and teachers, Due to the complexity, we have benefited the metaheuristic algorithm to solve nonlinear model. Simulated Annealing algorithm is used to solve the mathematical model in two stages. In the first stage, the system automatically generates feasible solutions that will meet all the hard constraints. Then, the solutions are improved with spotting different neighborhood's structures. This collection is in the form of computer software application which is implemented the C# language programing and SQL database. This system is tested the data gathered by Azad University data and the results compared to the manual process showed the great progress is achieved. The entire system is flexible and easy to test different scenarios

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

  • Course timetabling
  • multi-objective simulated annealing
  • preferences' function
  • Decision Support System
اسماعیلیان, عبدالهی. زمان بندی کلاس های درس با استفاده از برنامه ریزی عدد صحیح. مطالعات مدیریت صنعتی 14.41 (2016): 163-187.
جودکی, منتظری, موسوی سیدرسول. بررسی مساله زمان بندی درسی دانشگاهی با استفاده از ترکیب الگوریتم ممتیک بهبودیافته و الگوریتم سردشدن شبیه سازی شده.(2013) 192-202.
سلیمی فرد, جمالی، بابایی زاده,. زمان‎ بندی درس‌های دانشگاه با به‎ کارگیری هیوریستیک فرادست بر مبنای گراف. نشریه مدیریت صنعتی ،5.2 (2013), 49-70.
شمس شمیرانی, بشیری, مدرس یزدی. طراحی مدل ریاضی زمانبندی امتحانات در دانشگاه و تحلیل جوابهای حاصل از آن. مطالعات مدیریت صنعتی 15.44 (2017): 27-50.
Abdullah S, Turabieh H. On the use of multi neighbourhood structures within a Tabu-based memetic approach to university timetabling problems. Information Sciences. 2012 May 15;191:146-68.
Bagger, Niels-Christian F., Matias Sørensen, and Thomas R. Stidsen. "Benders’ decomposition for curriculum-based course timetabling." Computers & Operations Research 91 (2018): 178-189.‏
Burke EK, Eckersley AJ, McCollum B, Petrovic S, Qu R. Hybrid variable neighbourhood approaches to university exam timetabling. European Journal of Operational Research. 2010 Oct 1;206(1):46-53.
Carter M, Laporte G. Recent developments in practical course timetabling. Practice and Theory of Automated Timetabling II. 1998:3-19.
Daskalaki S, Birbas T, Housos E. An integer programming formulation for a case study in university timetabling. European Journal of Operational Research. 2004 Feb 16;153(1):117-35.
de Werra D. An introduction to timetabling. European journal of operational research. 1985 Feb 1;19(2):151-62.
Deb K, Sundar J. Reference point based multi-objective optimization using evolutionary algorithms. InProceedings of the 8th annual conference on Genetic and evolutionary computation 2006 Jul 8 (pp. 635-642). ACM.
Di Gaspero L, McCollum B, Schaerf A. The second international timetabling competition (ITC-2007): Curriculum-based course timetabling (track 3). Technical Report QUB/IEEE/Tech/ITC2007/CurriculumCTT/v1. 0, Queen’s University, Belfast, United Kingdom; 2007 Aug.
Dimopoulou M, Miliotis P. An automated university course timetabling system developed in a distributed environment: A case study. European Journal of Operational Research. 2004 Feb 16;153(1):136-47.
Dorneles ÁP, de Araújo OC, Buriol LS. A fix-and-optimize heuristic for the high school timetabling problem. Computers & Operations Research. 2014 Dec 31;52:29-38.
e Costa CA, Oliveira MD. A multicriteria decision analysis model for faculty evaluation. Omega. 2012 Aug 31;40(4):424-36.
Eglese RW. Simulated annealing: a tool for operational research. European journal of operational research. 1990 Jun 15;46(3):271-81.
‏Fonseca, George HG, et al. Integer programming techniques for educational timetabling. European Journal of Operational Research 262.1 (2017): 28-39.
Ghodsypour SH, O'Brien C. A decision support system for supplier selection using an integrated analytic hierarchy process and linear programming. International journal of production economics. 1998 Sep 20;56:199-212.
Goh, Say Leng, Graham Kendall, and Nasser R. Sabar. Improved local search approaches to solve the post enrolment course timetabling problem. European Journal of Operational Research 261.1 (2017): 17-29.‏
Gotlieb CC. The construction of class-teacher timetables. InProc. IFIP Congress 1963 Jan 1 (Vol. 62, pp. 73-77).
Gunawan A, Ng KM, Poh KL. A hybridized Lagrangian relaxation and simulated annealing method for the course timetabling problem. Computers & Operations Research. 2012 Dec 31;39(12):3074-88.
Head C, Shaban S. A heuristic approach to simultaneous course/student timetabling. Computers & Operations Research. 2007 Apr 30;34(4):919-33.
Ismayilova NA, SağIr M, Gasimov RN. A multiobjective faculty–course–time slot assignment problem with preferences. Mathematical and Computer Modelling. 2007 Oct 31;46(7):1017-29.
Jafari H, Salmasi N. Maximizing the nurses’ preferences in nurse scheduling problem: mathematical modeling and a meta-heuristic algorithm. Journal of Industrial Engineering International. 2015 Sep 1;11(3):439-58.
Kirkpatrick S, Gelatt CD, Vecchi MP. Optimization by simulated annealing. science. 1983 May 13;220(4598):671-80.
Lee HY, Lin YC. A decision support model for scheduling exhibition projects in art museums. Expert Systems with Applications. 2010 Mar 31;37(2):919-25.
Lewis R, Thompson J. On the application of graph colouring techniques in round-robin sports scheduling. Computers & Operations Research. 2011 Jan 31;38(1):190-204.
McCollum B, Burke EK. The practice and theory of automated timetabling. Annals of Operations Research. 2014 Jul 1;218(1):1-2.
Michalewicz, Zbigniew. "A survey of constraint handling techniques in evolutionary computation methods." Evolutionary programming 4 (1995): 135-155.‏
‏Nagata, Yuichi. Random partial neighborhood search for the post-enrollment course timetabling problem. Computers & Operations Research 90 (2018): 84-96.
Pereira, V., & Gomes Costa, H. (2016). Linear integer model for the course timetabling problem of a faculty in Rio de Janeiro. Advances in Operations Research, 2016.
Power DJ, Sharda R. Model-driven decision support systems: Concepts and research directions. Decision Support Systems. 2007 Apr 30;43(3):1044-61.
Qu R, Burke EK, McCollum B, Merlot LT, Lee SY. A survey of search methodologies and automated system development for examination timetabling. Journal of scheduling. 2009 Feb 1;12(1):55-89.
Schaerf A. A survey of automated timetabling. Artificial intelligence review. 1999 Apr 1;13(2):87-127.
Song, K., Kim, S., Park, M., Lee, H. S. Energy efficiency-based course timetabling for university buildings. Energy, 139, (2017). 394-405.
Turban E. Decision support and expert systems: management support systems. Prentice Hall PTR; 1990 Nov 1.
Van Laarhoven PJ, Aarts EH, Lenstra JK. Job shop scheduling by simulated annealing. Operations research. 1992 Feb;40(1):113-25.
Vermuyten, Hendrik, et al. "Developing compact course timetables with optimized student flows." European Journal of Operational Research 251.2 (2016): 651-661.‏
Wang YZ. An application of genetic algorithm methods for teacher assignment problems. Expert Systems with Applications. 2002 May 31;22(4):295-302.
White G, Chan PW. Towards the construction of optimal examination schedules. INFOR: Information Systems and Operational Research. 1979 Aug 1;17(3):219-29.
Zaretalab A, Hajipour V, Sharifi MShahriari MR. A knowledge-based archive multi-objective simulated annealing algorithm to optimize series–parallel system with choice of redundancy strategies. Computers & Industrial Engineering. 2015 Feb 28;80:33-44.