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

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

a two-phased metaheuristic method for solving high school course timetabling

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.