یک روش دو مرحله‌ای ریاضی - ابتکاری برای حل مساله زمان‌بندی دروس دبیرستانی در ایران

الموضوعات :

محمد صادق شیری ¹ , سید مصطفی خرمی زاده ² , پری فرخی ³

1 - گروه رياضي کاربردي، دانشکده علوم پايه، واحد ارسنجان، دانشگاه آزاد اسلامي، ارسنجان، ايران
2 - گروه بهینه‌سازی، دانشکده علوم ریاضی، دانشگاه صنعتی شیراز، شیراز، ايران
3 - گروه بهینه‌سازی، دانشکده علوم ریاضی، دانشگاه صنعتی شیراز، شیراز، ايران

تاريخ الإرسال : 28 الأربعاء , ربيع الأول, 1443 تاريخ التأكيد : 28 الإثنين , جمادى الثانية, 1443 تاريخ الإصدار : 06 الخميس , رجب, 1445

الکلمات المفتاحية: Optimization, timetabling, Metaheuristic, soft constrain, hard constraint,

ملخص المقالة :

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

المصادر:


[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.