یک روش دو مرحله‌ای ریاضی - ابتکاری برای حل مساله زمان‌بندی دروس دبیرستانی در ایران
محورهای موضوعی : آمار
محمد صادق شیری
1
,
سید مصطفی خرمی زاده
2
,
پری فرخی
3
1 - گروه رياضي کاربردي، دانشکده علوم پايه، واحد ارسنجان، دانشگاه آزاد اسلامي، ارسنجان، ايران
2 - گروه بهینه‌سازی، دانشکده علوم ریاضی، دانشگاه صنعتی شیراز، شیراز، ايران
3 - گروه بهینه‌سازی، دانشکده علوم ریاضی، دانشگاه صنعتی شیراز، شیراز، ايران
کلید واژه: Optimization, timetabling, Metaheuristic, soft constrain, hard constraint,
چکیده مقاله :
این مقاله جدول زمان‌بندی دروس دبیرستانی مورد مطالعه قرار می‌گیرد. این مساله هر سال باید توسط معاونان مساله حل شود. لذا وجود الگوریتمی در این زمینه می تواند بسیار مفید باشد. ابتدا محدودیت‌های سخت و نرم مرتبط با مساله معرفی می‌شوند سپس یک روش دو مرحله‌ای کارا برای حل مساله جدول زمان‌بندی دروس دبیرستانی ارایه می‌شود. روش ارایه شده ترکیبی از روش‌های ریاضی دقیق و روش‌های فراابتکاری است. در مرحله اول برای بدست آوردن یک جواب شدنی، یک مدل برنامه‌ریزی خطی صحیح برای مساله معرفی شده و به طور دقیق حل می‌شود. در مرحله دوم برای بهبود کیفیت جواب شدنی بدست آمده از مرحله اول، یک روش فراابتکاری که ترکیبی از روش‌های جستجوی ممنوعه و جستجوی همسایگی متغیر است، برای حل مساله ارایه می‌شود. در پایان به بررسی نتایج عددی پرداخته و با اعمال روش‌های معرفی شده بر روی مساله جدول زمان‌بندی در دو دبیر‌ستان از نواحی مختلف شیراز، آنها را مورد تجزیه وتحلیل قرار می‌دهیم.
In this paper, the high school timetabling problem is studied. Here, an efficient hybrid algorithm is presented for the resolution of the problem. The presented algorithm has two phases. In the first phase hard constraints are handled using an integer programming problem. Moreover, suitable decision variables and constraints are introduced to express the problem of the first phase as an integer programming problem. Many constraints are being considered in this paper for the first time and are specific to the high schools in Iran. The feasible solution obtained in the first phase is used as the input of the second phase. In the second phase an efficient hybrid metaheuristic algorithm is presented for improving the quality of the feasible solution of the first phase. The presented metaheuristic algorithm is a combination of the variable neighborhood search algorithm and Tabu search algorithm. The presented algorithm of the second phase, is applied on the solution obtained from the first phase to improve its quality. Finally, numerical results on real world instance are presented to justify the efficiency of the proposed algorithm. The test instances are taken from real world applications that corresponds to two high schools in Shiraz city. The numerical results show that our presented algorithm is able to compute high quality solutions for the real world instances that have been considered in this paper. It is also possible to apply the presented algorithm of the second phase only to improve the quality of existing timetabling provided by experience.
[1] Werra D., “An introduction to timetabling”, European Journal of Operational Research, 19(2), 151-162 (1985).
[2] Schaerf A., “A survey of automated timetabling”, The Artificial Intelling Revolution, 13(2), 87-127 (1999).
[3] Carrasco M. P. and Pato M. V., “A comparison of discrete and continuous neural network approaches to solve the class/teacher timetabling problem”, European Journal of Operational Research, 153(2) 63-79 (2004).
[4] de Haan P., Landman R., Post G and Ruizenaar H., “A case study for timetabling in a Dutch secondary school”, Lecture Notes in Computer Science, Springer-Verlag, In Burke EK, Rudova H (Eds). Proceedings of PATAT , 3867, 267-279 (2006).
[5] L. Saviniec, M. O. Santos and A. M. Costa, Parallel local search algorithms for high school timetabling problems, European journal of Operations Research, 265(1), 81-98, 2018.
[6] Zhang D., Liu Y., M’Hallah R. and Leung S., “A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems”, European Journal of Operational Research, 203(3), 550-558 (2010).
[7] Pillay N., “A survey of school timetabling research”, Annals of Operations Research, ISSN 0254-5330 (2013).
[8] Tassopoulos I. X. and Beligiannis G. N., “A hybrid particle swarm optimization based algorithm for high school timetabling problems”, Applied Soft Computing, 3472-3489 (2012).
[9] Odeniyi O. A., Omidiora E. O., Olabiyisi S. O. and Aluko., “Development of a modified simulated annealing to school timetabling problem”, International Journal of Applied Information Systems, 8(2), 16-24 (2015).
[10] Ghazali Talbi E.L., “Metaheuristics from Design to Implementation”, Wiley, University of Lille-Cnrs-Inria, (2009).
[11] V. I. Skoullis, I. X. Tassopoulos and G. N. Beligiannis, Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm, Applied Soft Computing, 52, 277-289, 2017.
[12] L. Saviniec and A. A. Constantino, Effective local search algorithms for high school timetabling problems, Applied Soft Computing, 60, 363-373, 2017.