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

محورهای موضوعی : آمار

محمد صادق شیری ¹ (گروه رياضي کاربردي، دانشکده علوم پايه، واحد ارسنجان، دانشگاه آزاد اسلامي، ارسنجان، ايران)
سید مصطفی خرمی زاده ² (گروه بهینه‌سازی، دانشکده علوم ریاضی، دانشگاه صنعتی شیراز، شیراز، ايران)
پری فرخی ³ (گروه بهینه‌سازی، دانشکده علوم ریاضی، دانشگاه صنعتی شیراز، شیراز، ايران)

تاریخ دریافت : 1400/08/12 تاریخ پذیرش : 1400/11/11 تاریخ انتشار : 1402/10/28

کلید واژه: 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.

متن کامل:



دسترسي در سايتِ http://jnrm.srbiau.ac.ir

سال نهم، شماره چهل و دوم، خرداد و تیر 1402

شماره شاپا: X2588-588

 

 

 

 

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

 

 

محمد صادق شیری1، سید مصطفی خرمی­زاده2¹، پری فرخی3

 

(1)   گروه رياضي کاربردي، دانشکده علوم پايه، واحد ارسنجان، دانشگاه آزاد اسلامي، ارسنجان، ايران

(2و3)   گروه بهینه‌سازی، دانشکده علوم ریاضی، دانشگاه صنعتی شیراز، شیراز، ايران

 

 

تاريخ ارسال مقاله:         12/08/1400   تاريخ پذيرش مقاله: 11/11/1400

چکيده

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

 

واژه‌هاي کليدي: مساله زمان‌بندی، روش فراابتکاری، مساله بهینه‌سازی ترکیبیاتی، محدودیت سخت و نرم.

---

[1] . عهده­دار مکاتبات                                                                                      [e-mail] Email:

۱- مقدمه

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

 

1-1- مفاهیم مورد نیاز

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

آورده شده است.

سیاست‌ها، محدودیت‌ها و مطلوبیت‌های موجود در نظام آموزشی دبیرستان‌های ایران را می­توان به شرح زیر بیان کرد: 

1- در دبیرستان‌های ایران، سه پایه دهم، یازدهم و دوازدهم (چهارم) وجود دارند، که هر پایه نیز به سه رشته تخصصی، ریاضی، تجربی و انسانی تفکیک شده است. توجه کنید که در بعضی از دبیرستان‌ها ممکن است از هر پایه لزوما یک یا دو رشته تخصصی وجود داشته باشد به عنوان مثال در دبیرستان مطهر (شیراز - ناحیه یک)، فقط شامل دو رشته تحصیلی تجربی و انسانی می‌باشد.

2- کلاس‌های درس از روز شنبه تا چهارشنبه برگزار می‌شوند. با توجه به اینکه دانش آموزان سال چهارم نیاز به وقت بیشتری به منظور آمادگی در کنکور دارند، در برخی دبیرستان‌های ایران، کلاس‌های درس آن‌ها به صورت فشرده­تر و در روزهای کمتری برگزار می‌شود.

3- در هر روز کلا‌س‌های درس، از ساعت 7:30 شروع می‌شوند و حداکثر تا ساعت 2 ادامه دارند یک روز کاری در دبیرستان از چهار بازه زمانی تشکیل شده است (هر90 دقیقه یک بازه زمانی است) بازه‌های زمانی روزانه دبیرستان به همراه وقت استراحت­آن‌ها­در­جداول(2)و(3)شرح داده شده است:

4- دانش‌آموزان مربوط به هر رشته تخصصی از یک پایه به گروه‌های تقریبا مساوی تفکیک شده که هر کدام یک کلاس نامیده می‌شوند. درس‌های مربوط به هر کلاس در طول سال در یک اتاق ثابت برگزار می‌شود. به عنوان مثال در دبیرستان حضرت معصومه (شیراز - ناحیه چهار) پایه چهارم تجربی دارای سه شعبه، چهارم تجربی ۱، چهارم تجربی ۲ و چهارم تجربی ۳ می‌باشد که درس‌های مربوط به هر کد، در طول سال در یک اتاق ثابت برگزار می‌شود. 5- بعضی از دروس فقط توسط یک دبیر تدریس می‌شوند، در حالی که بعضی دروس دیگر ممکن است توسط بیش از یک دبیر تدریس شوند.

 

 

 

جدول (1): مواد درسی و ساعات تدریس هفتگی

تعداد ساعت در هفته	طول بازه زمانی هر جلسه	تعداد جلسات	نام درس
4	نود دقیقه	2	حساب دیفرانسیل پایه چهارم
2	نود دقیقه	1	فارسی 1 پایه دهم
3	صد و سی و پنج دقبقه	2	شیمی 3 پایه یازدهم

 

 

جدول (2): مربوط به بازه‌های زمانی روزانه در دبیرستان

بازه زمانی چهارم	بازه زمانی سوم	بازه زمانی دوم	بازه زمانی اول
2 – 12:30	12:20 – 10:50	10:40 – 9:10	9 – 7:30

 

 

جدول (3): مربوط به وقت استراحت بین زنگ‌های کلاسی

بازه زمانی استراحت سوم	بازه زمانی استراحت دوم	بازه زمانی استراحت اول
12:30 – 12:20	10:50 – 10:40	9:10 - 9

 

 

2- پيشينه تحقيق

در سال 1985، ورا¹ مسایل مختلف زمان‌بندی، که

در آموزش و پرورش مطرح شده را معرفی می‌کند و مدل‌های متفاوتی را برای زمان‌بندی کلاس - معلم و دروس بر اساس نظریه گراف تهیه می‌کند ]1[. اسکارف² (1999)، یک مرور کلی بر روی فرمول‌های مختلف زمان‌بندی آموزشی یعنی زمان‌بندی مدارس، زمان‌بندی دروس و زمان‌بندی امتحانات، همراه با تکنیک‌های مورد استفاده برای حل مسایل را ارایه می‌کند. وی یک بررسی کلی بر روی زمان‌بندی خودکار با یک بخش ویژه، مختص به زمان‌بندی دروس دبیرستانی، را انجام می‌دهد. در این مقاله فرمول‌بندی‌های مختلف از مساله و تکنیک‌ها و الگوریتم‌های مورد استفاده برای حل آن را مورد بررسی قرار می‌دهد و در مورد جدیدترین رویکردها و تکنیک‌های هوش مصنوعی (مانند: الگوریتم ژنتیک، جستجوی تابو و رضایت محدودیت) به طور خاص تاکید دارد ]2[. کاراسکووپاتو³ (2004)، یک برنامه کاربردی از روش‌های فراابتکاری مبتنی بر شبکه‌های عصبی را در یک مساله زمان‌بندی کلاس - معلم کشف کردند ]3[. هان و همکارانش⁴ (2006)، در یک دبیرستان هلندی، یک جدول زمان‌بندی سه مرحله‌ای مبتنی بر روش جستجوی ممنوعه را ایجاد کردند ]4[. در سال 2010 زانگ و همکارانش⁵، مقاله‌ای در مورد حل مساله زمان‌بندی دروس دبیرستانی، با استفاده از یک برش شبیه سازی شده با ساختار همسایگی جدید طراحی شده را ارایه می‌کنند. جستجو برای یافتن بهترین همسایه به طور ابتکاری، با استفاده از دنباله‌ای از مبادلات بین جفت بازه‌های زمانی، به جای مبادله بین دو بازه زمانی مشخص شده، به عنوان یک شبیه سازی یکنواخت استاندارد مطرح می‌شود. نتایج محاسباتی در این مقاله نشان می‌دهد که ابتکار پیشنهاد شده، که بر روی دو مجموعه نمونه معیاری تست شده است، بهتر از رویکردهای فعلی عمل می‌کند ]6[. پیلای (2013)، اولین و آخرین بررسی خود را فقط روی جدول زمان‌بندی مدرسه متمرکز می‌کند. این بررسی یک تعریف از جدول زمان‌بندی مدرسه، تفاوت‌های بین محدودیت‌های سخت و نرم را ارایه می‌دهد. سپس یک مرور جزیی بر روی روش‌های مورد استفاده در این مساله می‌کند ]7[. تاسوپولوس و بلیگیانیس⁶ (2012)، مساله زمان‌بندی دبیرستان را با استفاده از الگوریتم مبتنی بر بهینه سازی ذرات ترکیبی حل نمودند. به منظور نشان دادن کارآیی این الگوریتم، آن را بر روی داده‌های دنیای واقعی که از مدارس یونان گردآوری کرده بودند، اجرا نمودند ]8[. اودینی و همکاران⁷ (2015) یک اصلاح شبیه سازی شده آنالوگ را که در فرآیند حل یک مساله زمان‌بندی معمول دبیرستان مورد استفاده قرار می‌گیرد، را ارایه نمودند. رویکرد بیان شده در مقاله، اولین بار برای زمان‌بندی مدرسه فاکونل، دبیرستان جامع اسوگوو نیجریه در طول سال 2012/2013 با موفقیت به کار گرفته شد و آن را قادر به تولید جدول زمانی در مورد مسایل پیچیده نمود] 9[. در سال 2017، اسکولیس و همکاران ]11[ با استفاده از یک الگوریتم فراابتکاری ترکیبی بر اساس الگوریتم ازدحام گربه‌ها مساله زمان بندی دروس دبیرستانی را حل کردند. در سال 2017، ساوینیک و همکاران الگوریتمی بر اساس الگوریتم‌های فراابتکاری جستجوی موضعی تکراری و جستجوی همسایگی متغیر برای حل مساله ارایه دادند ]12[. در سال 2018، ساوینیک و همکاران ]5[ دو چارچوب بر اساس محاسبات موازی برای حل مساله ارایه دادند. در این مقاله ما انواع محدودیت‌های جدیدی که تا‌کنون بررسی نشده‌اند و در خصوص مساله زمان‌بندی دروس دبیرستانی مربوط به مدارس ایران است را در بخش 3 شرح می‌دهیم. سپس در بخش4 مرحله اول از حل مساله زمان‌بندی دروس دبیرستانی را که مربوط به نحوه محاسبه جواب آغازین است را بیان می‌کنیم. در این مرحله مجموعه‌ها و پارامترهای مورد نیاز مساله را معرفی و محدود‌های سخت مساله را فرمول‌بندی می‌کنیم. مرحله دوم از روش دو مرحله‌ای جدید را در بخش 5 ارایه می‌دهیم. در این مرحله، از دو روش فراابتکاری جستجوی ممنوعه و همسایگی متغیر، برای بهبود جواب شدنی حاصل از مرحله اول، استفاده می‌شود که در مورد هر کدام توضیح مختصری را بیان می‌کنیم. در بخش 6 مطالعه موردی و نتایج عددی حاصل از اجرای روش دو مرحله‌ای بر روی داده‌های واقعی دو دبیرستان، آورده شده است. در خاتمه و در بخش 7 نتیجه‌گیری و پیشنهادهای مورد نیاز برای آتی را شرح می‌دهیم.

 

3- شرح مساله و کلیات روش حل

در این بخش ابتدا به معرفی انواع محدودیت‌های سخت و نرم مساله زمان‌بندی دروس دبیرستانی در ایران می‌پردازیم.

 

3-1- محدودیت‌های سخت

محدودیت‌هایی که هر تخصیص از دروس به اتاق‌ها، معلم‌ها و دوره‌های زمانی باید لزوما در آن‌ها صدق کند، را محدودیت سخت گویند. معمولا این دسته از محدودیت‌ها مربوط به مقررات اداری، آموزشی و محدودیت منابع دبیرستان مورد نظر هستند. در ادامه باید توجه داشت که ساعت‌های تدریس درس‌ها در برنامه هفتگی دبیرستان بین 1 تا 4 ساعت هستند. درس‌های 3 ساعته در یک جلسه 2 ساعته و یک جلسه تک ساعته برگزار می‌شوند و دروس 1 ساعته نیز در یک جلسه تک ساعته برگزار می‌شوند. هر جلسه 2 ساعته معادل 90 دقیقه هست (یک بازه زمانی) و هر جلسه تک ساعته معادل 45 دقیقه هست. محدودیت‌های سخت مساله زمان‌بندی دروس دبیرستانی به شرح زیر هستند:

1- در یک بازه‌ زمانی معین بیش از یک درس نباید به یک اتاق اختصاص داده شود.

2- در یک بازه زمانی معین بیش از یک درس نباید به یک دبیر اختصاص داده شود. این محدودیت مربوط به دروسی است که در طول یک هفته باید به مدت 2 یا 4 ساعت در هفته برگزار شوند. در حالی‌که بعضی از دروس دبیرستانی، یک یا سه ساعته هستند و دروس سه ساعته در یک جلسه 2 ساعته و یک جلسه تک ساعته برگزار می‌شوند. در برنامه ریزی دروس دبیرستانی، دبیری که برای تدریس یک درس سه ساعته انتخاب شده است، می‌تواند دو تا تک ساعت را در دو کلاس مجزا و در یک بازه زمانی یکسان داشته باشد. به عنوان مثال کلاس چهارم تجربی دارای دو درس سه ساعته ریاضی عمومی و فیزیک می‌باشد. حال اگر یک دبیرستان دو کلاس چهارم تجربی داشته باشد، برنامه دبیرستان به گونه‌ای تنظیم می‌شود که یک ساعت درس ریاضی با یک ساعت درس فیزیک جفت شود. در این صورت دبیرانی که تدریس دروس ریاضی و فیزیک را برعهده دارند می‌توانند یک جلسه تدریس را در دو کلاس مجزا و به صورت دو تا 45 دقیقه برگزار کنند. با توجه به توضیحات داده شده، در مورد دروس یک و سه ساعته به تعدادی محدودیت جدید می‌رسیم. دروس تک ساعته به دو دسته تقسیم می‌شوند. دسته اول دروسی هستند که در طول هفته به مدت یک ساعت تدریس می‌شوند و دسته دوم، بخشی از یک درس سه ساعته هستند. بنابراین در برنامه زمان‌بندی دروس دبیرستانی یا این دروس به تنهایی ارایه می‌شوند و یا با دروس تک ساعته دیگر جفت می‌شوند. 

3- چون دروس سه ساعته در دو جلسه دو ساعته و یک جلسه تک ساعته برگزار می‌شوند، لذا هر دو جلسه تدریس این دروس باید به یک دبیر اختصاص یابد. 

4- دبیرانی که تدریس دروس یک یا سه ساعته را بر عهده دارند، می‌توانند دو جلسه تک ساعته از این دروس را در یک بازه زمانی یکسان و در دو کلاس مجزا ارایه دهند. به عنوان مثال اگر دبیری زیست 3 ساعته دهم تجربی و آزمایشگاه 1 ساعته یازدهم تجربی را برعهده داشته باشد. در برنامه هفتگی دبیرستان، در یک بازه زمانی این دبیر می‌تواند 45 دقیقه اول، تک ساعت از درس زیست دهم تجربی و 45 دقیقه دوم درس آزمایشگاه یازدهم تجربی را تدریس کند.

5- برای هر کلاسی و برای هر درس تک ساعته از این کلاس، باید یکی از حالت‌های ممکن و ایجاد شده برای آن درس را ارایه نمود. وقتی درس تک ساعته‌ای با دروس تک ساعته دیگر جفت می‌شود، بخش‌هایی از این درس ایجاد می‌گردد. به عنوان نمونه وقتی درس تک ساعته ریاضی دهم انسانی، با دروس تک ساعته دیگر جفت می‌شود، مجموعه بخش‌های ایجاد شده مربوط به این درس به صورت زیر می‌باشد: (ریاضی - تاریخ) و (ریاضی - آمادگی) و (ریاضی - زبان) و (ریاضی - ---) بنابراین در برنامه هفتگی دبیرستان، برای کلاس دهم انسانی و درس تک ساعته ریاضی، باید یکی از حالت‌های ممکن ارایه شود.

6- یک دبیر نمی‌تواند در یک بازه زمانی یکسان برای تدریس یک درس دو یا چهار ساعته از یک کلاس و یک درس تک ساعته از کلاسی دیگر حضور داشته باشد.

7- اتاق‌ها باید ظرفیت کافی برای برگزاری کلاس‌های مورد نظر را داشته باشند.

8- باید در هر بخش کلاسی، تمامی دروس مختص به آن کلاس ارایه شوند.

9- جلسات آموزشی برای هر درس، باید به تعداد لازم برنامه‌‌ریزی شود به عبارتی هر درس از تعدای جلسه تشکیل شده است که در یک جدول زمانی شدنی، کل جلسات باید برنامه‌ریزی شوند.

10- ساعات درسی دبیران از حد تعیین شده تجاوز نکند.

11- تعداد کل ساعات آموزشی هر بخش کلاسی باید به تعداد ساعت لازم که از قبل توسط وزارتخانه آموزش و پرورش مشخص شده، در برنامه هفتگی برنامه‌ریزی شود.

 

3-2- محدودیت‌های نرم

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

 

3-3- شرح کلی روش دو مرحله‌ای جدید

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

 

4- مرحله اول: محاسبه جواب شدنی آغازین

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

برای تعریف متغیرهای مساله فرض کنید  یک متغیر دودویی است که اگردر زمان t و در اتاق r درس  زمان‌بندی شود مقدار متغیرعدد 1 می‌باشد. علاوه براین فرض کنید  یک متغیر دودویی است که اگردر زمان t و در اتاق r درس c مقدار متغیر عدد 1 می‌باشد. ابتدا شرح می‌دهیم که چگونه می‌توان محدودیت‌های سخت را با استفاده از متغیرها و پارامترهای معرفی شده فرمول‌بندی کرد.

 

---

[1]  Werra

[2]  Schaerf

[3]  Carrasco and Pato

[4]  Haan

[5]  Zhang

[6]  Tassopoulos and Beligiannis

[7]  Odeniyi

 

جدول(4): مربوط به پارامترهای مساله

مفهوم	پارامتر
مجموعه دروس مربوط به اتاقr
مجموعه دروسی از اتاق  rکه با بیش از یک دبیر می‌توانند ارایه شوند
مجموعه اتاق‌هایی که دبیر  sمی‌تواند در آن‌ها تدریس داشته باشد
تعداد بازه‌های زمانی مجاز برای تدریس معلم  sدر روزهای کاری دبیرستان در طول یک هفته
تعدادکل بازه‌های زمانی مربوط به اتاق  rدر روزهای کاری دبیرستان در طول یک هفته
مجموعه کل دروسی که معلم  sمی‌تواند تدریس کند
تعداد جلسات ارایه درس  cدر اتاق  rدر طول یک هفته
مجموعه دروس دو ساعته یا چهار ساعته اتاقr که توسط دبیر  sتدریس می‌شوند
مجموعه دروس تک ساعته از درس سه ساعته cکه دراتاق rارایه شده و توسط دبیر  sتدریس می‌شوند
بخش دو ساعته از درس سه ساعته c که در اتاق rارایه می‌شودو توسط دبیر sتدریس می‌شود
مجموعه دروس سه ساعته اتاق r
مجموعه دروس یک ساعته اتاق r
مجموعه بخش‌های ایجاد شده مربوط به درس یک ساعته  cاز اتاق  r
جریمه اختصاص داده شده به درس از اتاق   در بازه زمانی
مجموعه بازه‌های زمانی روز dام که دبیر s می‌تواند در آن بازه‌ها تدریس داشته باشد
اولین بازه زمانی صبح در روز dام
مجموعه اتاق‌های موجود
مجموعه دوره‌های زمانی
مجموعه‌ای از روزهای کاری دبیرستان
مجموعه دبیران

 

 

در ادامه مدل پیشنهادی را برای حالتی که دروس 2 یا 4 ساعته هستند شرح می‌دهیم سپس آن را برای حالتی‌که جدول زمان‌بندی دروس دبیرستانی دارای دروس 1 و 3 ساعته نیز می‌باشد، تعمیم می‌دهیم دسته محدودیت‌های (1) و (2) بیان می‌کنند که هر درس c از اتاق r باید به تعداد بازه‌های زمانی، در برنامه‌ی هفتگی دبیرستان، زمان‌بندی شود. محدودیت (1.1) مربوط به دروسی است که فقط توسط یک دبیر تدریس می‌شوند، در حالی‌که در محدودیت (1.2) دروس می‌توانند توسط بیش از یک دبیر تدریس شوند. 

(1.1)       

(1.2)     

 

محدودیت (1.3) به این موضوع می‌پردازد که اگر درس c  از اتاقr  بتواند توسط بیش از یک دبیر تدریس شود، در زمان‌بندی هفتگی دبیرستان، می‌بایست فقط توسط یکی از دبیران مربوطه ارایه شود.

(1.3)          

منظور از محدودیت (1.4) آن است که در هر بازه زمانی، یک دبیر می‌تواند حداکثر در یک اتاق تدریس داشته باشد.

(1.4)                

 

در یک اتاق و در هر بازه زمانی، حداکثر یک درس می‌تواند زمان‌بندی شود. این موضوع در محدودیت (1.5) فرمول‌بندی شده است.

(1.5)         

 

محدودیت (1.6) بیان می‌کند که در برنامه هفتگی دبیرستان، تعداد کل بازه‌های آموزشی زمان‌بندی شده برای کل دروس اتاق r باید  بازه زمانی باشد.

(1.6)         

 

تعداد کل بازه‌های زمانی که معلم s می‌تواند در طول یک هفته روزهای کاری دبیرستان آموزش دهد، بازه زمانی  می‌باشد که در محدودیت (1.7) فرمول‌بندی شده است.

(1.7)       

 

حال برای دبیرستان‌هایی که دروس 1 و 3 ساعته نیز دارند فرمول‌های زیر به مدل بالا اضافه می‌شود: محدودیت (1.8) بیان می‌کند که یک دبیر نمی‌تواند در یک بازه زمانی یکسان، یک درس 2 یا 4 ساعته را با یک درس 1 ساعته از کلاسی دیگر تدریس کند.

(1.8) 

 

دبیرانی که تدریس دروس 1 یا 3 ساعته را بر عهده دارند، می‌توانند دو تا جلسه یک ساعته از این دروس را در یک بازه زمانی و در دو کلاس مجزا ارایه دهند. این مطلب در محدودیت (1.9) آورده شده است.

(1.9)     

 

هر درس تک ساعته از کلاس r که با دبیر s ارایه شده است یا به تنهایی ارایه می‌شود یا با یکی از دروس تک ساعته دیگر جفت می‌شود. لذا در برنامه زمان‌بندی آن کلاس باید از بین حالت‌های ممکن برای آن درس، یک حالت در بازه زمانی هفتگی آن کلاس ارایه شده باشد. که این مطلب در محدودیت‌های (1.10) و (1.11) فرمول‌بندی شده است.

(1.10)  

 

(1.11)  

 

محدودیت (1.12) بیان می‌کند که اگر دبیری تدریس دو ساعت از یک درس سه ساعته را بر عهده داشته باشد، می‌بایست تدریس تک ساعت از همین درس را بر عهده داشته باشد.

(1.12)        

 

تابع هدف مساله به صورت زیر است. در بخش 4 عملکرد تابع هدف را شرح خواهیم داد.

 

 

با حل این مدل برای مساله، یک جواب شدنی بدست می‌آید که با توجه به تابع هدف معرفی امید است جواب شدنی حاصل دارای کیفیت مناسبی نیز باشد.

 

5- مرحله دوم: بهبود جواب شدنی یافت شده

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

 

5-1- نحوه نمایش جواب مسا له زمان بندی دروس دبیرستانی

در این مقاله هر جواب را با استفاده از یک ماتریس دندانه‌دار1 نشان می‌دهیم. تعداد سطرهای این ماتریس دندانه‌دار، برابر تعداد کلاس‌های فعال درسی و تعداد ستون‌های آن برابر تعداد بازه‌های زمانی فعال برای کلاس درس متناظر می‌باشد. به عنوان مثال دبیرستانی را در نظر بگیرید که دارای سه کلاس فعال درسی  است که تعداد بازه‌های فعال زمانی آنها به ترتیب برابر 3 و6 و4 است. نمایش جواب برای این دبیرستان یک ماتریس دندانه‌دار به شکل زیر (شکل 1) است؛

هر درایه این ماتریس دندانه‌دارکد درسی است که در زمان متناظر در آن کلاس برگزار می‌شود. اگر در مرحله اول مساله که از برنامه‌ریزی خطی صحیح صفرو یک استفاده شده است  باشد، آنگاه برای درآیه‌ای که در سطر  rام و ستون t ام ازماتریس نمایش دندانه‌دار جواب قرار دارد، درسی با کد c انتخاب می‌شود؛ به عبارت دیگر داریم:.

5-2 عملکرد تابع ارزیاب

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

1) برای هر کلاس یک لیست از شماره دروس مهم و پایه‌ای مشخص گردد.

2) برای هر روز کاری در برنامه هفتگی دبیرستان، شماره‌های بازه‌ زمانی که در اولین ساعات قرار دارند، مشخص شوند. به عنوان مثال شماره‌های بازه زمانی هر روز دبیرستان حضرت معصومه که در ساعات اولیه قراردارند درجدول(5) آورده شده است؛

 

---

[1]  Variable Nighborhood Search

[2]  Tabu Search

 

 

 

شکل (1): نمایش جواب به صورت ماتریس دندانه دار¹

 

جدول (5): بازه‌های زمانی اولیه هر روز کاری در دبیرستان حضرت معصومه

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

 

---

[1]  Jagged matrix

این شماره‌های بازه زمانی در یک لیست قرار می‌گیرند. علاوه بر این شماره دروس مهم و پایه­ای کلاس چهارم ریاضی عبارتند از. بنابراین اگر یکی از این شماره دروس، در بازه‌های زمانی لیست شده ارایه نشده باشد، آنگاه این رخداد به لیست نقض محدودیت‌های نرم مساله اضافه می‌شود. محدودیت نرم دوم، بیانگر آن است که اگر تعداد بازه‌های زمانی یک درس در کلاسی، دو یا بیشتر باشد، بهتر است جلسات ارایه این درس در یک روز قرار نگیرند. به عنوان نمونه تعداد بازه‌های زمانی درس فیزیک چهارم ریاضی، برابر 2 است. بنابراین بهتر است در دو روز متفاوت ارایه شود. با توجه به این مطلب اگر این دو بازه زمانی در روز شنبه قرارگیرند، آنگاه یکی از این رخدادها به لیست نقض محدودیت‌های نرم مساله اضافه می‌شود. سومین محدودیت نرم، بیان می‌کند که بهتر است درسی که مربوط به یک دبیر است در ساعت‌های ممنوعه آن دبیر ارایه نشود. با توجه به این مطلب اگر درسی در ساعات ممنوعه یک دبیر ارایه شده باشد، آنگاه رخداد متناظر در لیست نقض محدودیت‌های نرم مساله قرار می‌گیرد. با توجه به مطالب فوق برای هر جواب، تعداد رخدادهایی که باعث نقض محدودیت‌های نرم مساله هستند، به عنوان مقدار تابع هدف فاز دوم برای آن جواب در نظر گرفته می‌شود.

 

5-3- چگونگی بهبود جواب

در این قسمت شرح می‌دهیم که چگونه با ترکیب الگوریتم‌های‌ فراابتکاری جستجوی ممنوعه و

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

1- همسایگی معاوضه (swap): در این همسایگی ابتدا یک سطر از ماتریس جواب به تصادف انتخاب می‌شود. سپس از این سطر دو درایه انتخاب شده و موقعیت این دو درایه با هم معاوضه می‌شوند. به عنوان مثال جواب زیر را در نظر بگیرید و فرض کنید از سطردرآیه‌های 9 و 15 انتخاب شده باشند. در اینصورت جواب حاصل از معاوضه این دو درایه در سمت راست نشان داده شده است.

2- همسایگی درج (insert): در این همسایگی ابتدا یک سطر به تصادف انتخاب می‌شود. سپس دو موقعیت متفاوت از سطر انتخاب می‌شوند. 2 شماره درس موقعیت اول به موقعیت دوم انتقال می‌یابد و اعداد بین آنها به طور متناظر تغییر مکان1 داده می‌شوند. به عنوان مثال در جواب زیر فرض کنید سطر انتخاب شده و درایه 11 از این سطر به موقعیت درایه 1 تغییر مکان داده باشد. بنابراین داریه‌های بین آنها به سمت چپ تغییر مکان داده‌اند. در اینصورت جواب حاصل از این تغییر مکان در سمت راست نشان داده شده است.

 

 

 

شکل (2): نمایش همسایگی معاوضه¹

 

شکل (3): نمایش همسایگی درج

 

 

شکل (4): نمایش همسایگی جایگزینی

 

 

---

[1]  Shift

3- همسایگی جایگزینی(replace) : در این همسایگی یک سطر به تصادف انتخاب می‌شود. سپس یک درآیه از سطر مربوطه انتخاب می‌شود. در نهایت یکی از درس‌هایی که در فهرست دروس سطر مربوطه است ولی در این سطر وجود ندارد، جایگزین درس موجود در موقعیت انتخاب شده می‌شود. به عنوان مثال در جواب زیر فرض کنید سطر  انتخاب شده و به جای درایه 5 درسی از این سطر با کد 21 جایگزین شده باشد. در این­صورت جواب حاصل از جایگزینی در سمت راست نشان داده شده است.

هر تکرار الگوریتم جستجوی همسایگی متغیر، دارای سه گام اساسی با عنوان‌های آشوب¹، جستجوی محلی² و حرکت³ است. در گام اول برای ایجاد آشوب در روش جستجوی همسایگی متغیر، ابتدا یکی از ساختارهای همسایگی انتخاب و سپس با استفاده از ساختار همسایگی انتخاب شده، یک جواب جدید تولید می‌شود. پس از انجام آشوب نوبت به انجام روند جستجوی محلی است. در این مقاله برای انجام روند جستجوی محلی از ایده‌های روش جستجوی ممنوعه به شرح زیر استفاده شده است. برای بیان عملکرد الگوریتم جستجوی ممنوعه بکار رفته فرض کنید s جواب شدنی فعلی⁴،  بهترین همسایه شدنی حاصل از اعمال همسایگی باشد. در حین اجرای الگوریتم جستجوی ممنوعه، وقتی همسایه‌ جدیدی جایگزین همسایه فعلی می‌شود، موقعیت سطر و ستون حرکتی که باعث ایجاد این همسایه جدید شده است، در لیستی به نام لیست ممنوعه قرار می‌گیرد. حداکثر تعداد اعضایی که این لیست می‌تواند داشته باشد را طول ممنوعه گویند. اگر تعداد اعضای لیست ممنوعه از طول ممنوعه بیشتر شد، آنگاه اولین عضو لیست ممنوعه حذف می‌شود و عضو جدید به انتهای لیست ممنوعه اضافه می‌شود (لیست ممنوعه به روز می‌شود). در اجرای الگوریتم جستجوی ممنوعه، ابتدا مقدار تابع هدف بهترین همسایه شدنی با مقدار تابع هدف جواب شدنی فعلی مقایسه می‌شود، در صورتی‌که مقدار تابع هدف  بهتر از مقدار تابع هدف  باشد، اگر موقعیت سطر و ستون حرکت مربوطه در لیست ممنوعه نباشد، آنگاه  جایگزین  می‌شود و موقعیت سطر و ستون حرکت مربوطه در لیست ممنوعه وارد شده و لیست ممنوعه به روز می‌شود. در غیر اینصورت بهترین همسایه‌ای که ممنوعه نیست جایگزین جواب شدنی فعلی  می‌شود (حتی اگر مقدار تابع هدف آن بدتر باشد). اگر پس از اجرای چندین تکرار، همسایه‌ای که مقدار تابع هدف آن از بهترین جواب شدنی یافت شده بهتر است پیدا نشد، الگوریتم جستجوی ممنوعه پایان می‌یابد. گام اساسی سوم در روش جستجوی همسایگی متغیر بعنوان حرکت شناخته می‌شود. در روند انجام حرکت اگر جواب حاصل از جستجوی ممنوعه با استفاده از ساختار همسایگی معاوضه بهتر از جواب فعلی باشد، آنگاه این جواب جایگزین جواب فعلی شده و الگوریتم به مرحله آشفتن مرحله باز می‌گردد. در غیر اینصورت الگوریتم جستجوی ممنوعه با استفاده از ساختار همسایگی درج روی جواب فعلی اجرا می‌شود. اگر جواب حاصل از الگوریتم جستجوی ممنوعه بهتر از جواب فعلی باشد، آنگاه این جواب جایگزین جواب فعلی شده و الگوریتم به آشفتن مرحله باز می‌گردد. در غیر اینصورت الگوریتم جستجوی ممنوعه با استفاده از ساختار همسایگی معاوضه روی جواب فعلی اجرا می‌شود. اگر هرسه همسایگی اعمال شود ولی جواب حاصل بهتر از جواب فعلی نباشد، آنگاه شمارنده یک واحد به جلو میرود و مجددا روند آشفتن از اولین همسایگی شروع می‌شود. پس از انجام تعداد تکرار مشخص شده، الگوریتم جستجوی همسایگی متغیر متوقف می‌شود ]10[.

 

6- مطالعه موردی و نتایج عددی

در این بخش، با اعمال روش ارایه شده بر روی مساله جدول زمان بندی دروس دبیرستانی مربوط به دو دبیرستان از نواحی مختلف شهر شیراز (حضرت معصومه و دبیرستان مطهر) کارایی الگوریتم پیشنهادی را مورد ارزیابی قرار می‌دهیم. با اعمال روش ارایه شده برای مدارس فوق کارآیی روش دو مرحله‌ای جدید را مورد ارزیابی قرار می‌دهیم. اجرای برنامه زمان‌بندی دروس دبیرستانی، در محیط سیستم عامل ویندوز 8، با استفاده از 4 گیگابایت حافظهRAM  و با استفاده از پردازشگرIntel(R) Core(TM) i5-5200U انجام شده است. آزمون‌های انجام شده با استفاده از نرم افزار CPLEX 12/6 و به زبان برنامه‌نویسی C# در محیط  Visual Studio 2013نوشته شده است. داده‌های ورودی مساله از محیط‌های

واقعی گرفته شده و به صورت تصادفی نمی‌باشند. 

 

6-1- اطلاعات آموزشی دبیرستان‌های حضرت معصومه و مطهر

دبیرستان مطهر در استان فارس و در ناحیه یک شهر شیراز واقع شده است. در این دبیرستان جدول زمان بندی کلاس‌های درس، در سال تحصیلی 97 – 96 موردبحث و بررسی قرار گرفته است. این دبیرستان دارای شش کلاس در پایه‌های مختلف می باشد که کلاس‌ها از روز شنبه تا روز چهارشنبه تشکیل می‌شوند. دبیرستان حضرت معصومه در استان فارس و در ناحیه چهار شهر شیراز واقع شده است. در این دبیرستان فقط جدول زمان بندی کلاس‌های چهارم در سال تحصیلی 96 – 95 مورد بحث و بررسی قرار گرفته است. این دبیرستان دارای پنج کلاس چهارم (دوازدهم) می‌باشد که کلاس‌ها از روز شنبه تا روز سه‌شنبه تشکیل می‌شوند. مدت زمان تدریس هر درسی در طول هفته، 2 یا 4 ساعت می‌باشد. در دبیرستان مطهر مجموعه بازه‌های زمانی و سطرها )کلاس‌های درس) به صورت زیر هستند

 

 

که در آن  نشان‌دهنده‌ی اتاق مربوط به کلاس دانش‌آموزان دهم انسانی، نشان‌دهنده‌ی اتاق مربوط به کلاس دانش‌آموزان دهم تجربی یک، نشان‌دهنده‌ی اتاق مربوط به کلاس دانش‌آموزان دهم تجربی دو،  نشان‌دهنده‌ی اتاق مربوط به کلاس دانش‌آموزان یازدهم انسانی، نشان‌دهنده‌ی اتاق مربوط به کلاس دانش‌آموزان یازدهم تجربی یک،  نشان‌دهنده‌ی اتاق مربوط به دانش‌آموزان یازدهم تجربی دو است. این دبیرستان جمعا 6 کلاس درس دارد که کلاس‌های درس از روز شنبه تا چهارشنبه برگزار می‌شوند ( تعداد 18 بازه‌زمانی). 17 نفر دبیردر این دبیرستان مشغول به تدریس هستند. در دبیرستان حضرت معصومه مجموعه بازه‌های زمانی و سطرها (کلاس‌های درس) به صورت زیر هستند: 

 

 

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

جواب بهبود یافته حاصل از اعمال مرحله دوم برنامه زمان‌بندی دروس دبیرستانی برای دبیرستان مطهر با شمارنده 6 در پیوست (1) آورده شده است. مدت زمان اجرای برنامه 30 دقیقه طول کشیده و تعداد نقض محدودیت‌های نرم آن به 58 رسیده است. تعداد نقض محدودیت‌های نرم جواب بهبود یافته مرحله دوم برای دبیرستان مطهر بعد از 30 دقیقه در جدول 7 آورده شده است.

جواب بهبود یافته حاصل از اعمال مرحله دوم برنامه زمان‌بندی دروس دبیرستانی برای دبیرستان مطهر با شمارنده 10 در پیوست (1) آورده شده است.

 

---

[1]  Shaking

[2]  Local Search

[3]  Move

[4]  Current

 

جدول (6): تعداد نقض محدودیت‌های نرم جواب شدنی مساله جدول زمان‌بندی کلاس‌های دبیرستان مطهر در ابتدای اجرای مرحله دوم مساله

محدودیت نرم	اولین محدودیت نرم	دومین محدودیت نرم	سومین محدودیت نرم	جمع
تعداد نقض	41	0	65	106

 

جدول (7): تعداد نقض محدودیت‌های نرم جواب بهبود یافته مساله جدول زمان‌بندی کلاس‌های دبیرستان مطهر پس از اجرای مرحله دوم مساله در مدت زمان 30 دقیقه

محدودیت نرم	اولین محدودیت نرم	دومین محدودیت نرم	سومین محدودیت نرم	جمع
تعداد نقض	35	0	23	58

 

 

 

مدت زمان اجرای برنامه 60 دقیقه طول کشیده و تعداد نقض محدودیت‌های نرم آن به 57 رسیده است. تعداد نقض محدودیت‌های نرم جواب بهبود یافته مرحله دوم برای دبیرستان مطهر بعد از 60 دقیقه در جدول 8 آورده شده است.

جواب بهبود یافته حاصل از اعمال مرحله دوم برنامه زمان‌بندی دروس دبیرستانی برای دبیرستان مطهر با شمارنده 20 در پیوست (1) آورده شده است. مدت زمان اجرای برنامه 3ساعت و 8 دقیقه طول کشیده و تعداد نقض محدودیت‌های نرم آن به 56 رسیده است. تعداد نقض محدودیت‌های نرم جواب بهبود یافته مرحله دوم برای دبیرستان مطهر بعد از سه ساعت و 8 دقیقه در جدول 9 آورده شده است.

اجرای مرحله دوم برنامه زمان‌بندی دروس دبیرستانی باعث می‌شود که جواب شدنی به دست آمده از مرحله اول تا میزان قابل توجهی بهبود یابد. به عنوان مثال برای دبیرستان مطهر تعداد نقض محدودیت‌های نرم جواب شدنی حاصل از اجرای مرحله اول برنامه زمان‌بندی دروس دبیرستانی 106 بوده و پس از اجرای مرحله دوم برنامه زمان‌بندی، تعداد نقض محدودیت‌های این دبیرستان به 56 رسیده و در نتیجه تقریبا 50 درصد بهبود پیدا کرده است. در صورت لزوم و با توجه به سیستم آموزشی دبیرستان‌ها ممکن است تعدای محدودیت‌ نرم جدید به مساله زمان‌بندی اضافه گردند. در اینصورت تعداد نقض محدودیت‌های نرم جواب شدنی حاصل از مرحله اول تغییر می‌کند. به عنوان مثال اگر در مساله زمان‌بندی دبیرستان مطهر محدودیت نرم (عدم تخصیص درس‌های مهم و پایه‌ای هر کلاس، به دوره‌ زمانی پایانی هر روز)، در نظر گرفته شود تعداد نقض محدودیت‌های نرم حاصل از جواب شدنی مرحله اول 116 می‌شود که در جدول 10 آورده شده است. جواب بهبود یافته حاصل از اجرای مرحله دوم با شمارنده 6 در پیوست (1) آورده شده است. تعداد نقض محدودیت‌های نرم جواب بهبود یافته نیز در جدول 11 آورده شده و تعداد نقض محدودیت‌های نرم به 61 رسیده است.

 

 

 

جدول (8): تعداد نقض محدودیت‌های نرم جواب بهبود یافته مساله جدول زمان‌بندی کلاس‌های دبیرستان مطهر پس از اجرای مرحله دوم مساله در مدت زمان 60 دقیقه

محدودیت نرم	اولین محدودیت نرم	دومین محدودیت نرم	سومین محدودیت نرم	جمع
تعداد نقض	35	0	22	57

 

جدول (9): تعداد نقض محدودیت‌های نرم جواب بهبود یافته مساله جدول زمان‌بندی کلاس‌های دبیرستان مطهر پس از اجرای مرحله دوم مساله در مدت زمان 3ساعت و 8 دقیقه

محدودیت نرم	اولین محدودیت نرم	دومین محدودیت نرم	سومین محدودیت نرم	جمع
تعداد نقض	35	0	21	56

 

جدول (10): تعداد نقض محدودیت‌های نرم جواب شدنی مساله جدول زمان‌بندی کلاس‌های دبیرستان مطهر در ابتدای اجرای مرحله دوم مساله

محدودیت نرم	اولین محدودیت نرم	دومین محدودیت نرم	سومین محدودیت نرم	چهارمین محدودیت نرم	جمع
تعداد نقض	41	0	65	10	116

 

جدول (11): تعداد نقض محدودیت‌های نرم جواب بهبود یافته مساله جدول زمان‌بندی کلاس‌های دبیرستان مطهر پس از اجرای فاز دوم مساله

محدودیت نرم	اولین محدودیت نرم	دومین محدودیت نرم	سومین محدودیت نرم	چهارمین محدودیت نرم	جمع
تعداد نقض	36	0	24	1	61

 

 

 

جداول‌ مربوط به مشخصات آموزشی کلاس‌ها و دبیران دبیرستان حضرت معصومه در پیوست (2) آورده شده است. نتایج حاصل از اجرای الگوریتم دو مرحله‌ای بر روی داده‌های واقعی دبیرستان حضرت معصومه در جداول‌ 13و 14 و پیوست (2) آورده شده است. تعداد نقض محدودیت‌های نرم جواب شدنی فاز 1 برای دبیرستان حضرت معصومه در جدول 12 آورده شده است.

تعداد نقض محدودیت‌های نرم جواب بهبود یافته فاز 2 برای دبیرستان حضرت معصومه در جدول 13 آورده شده است.

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

7- نتیجه‌گیری و پیشنهادها

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

 

 

جدول (12): تعداد نقض محدودیت‌های نرم جواب شدنی مساله جدول زمان‌بندی کلاس‌های چهارم دبیرستان حضرت معصومه در ابتدای اجرای فاز دوم مساله

محدودیت نرم	اولین محدودیت نرم	دومین محدودیت نرم	سومین محدودیت نرم	جمع
تعداد نقض	22	6	42	70

 

جدول (13): تعداد نقض محدودیت‌های نرم جواب بهبود یافته مساله جدول زمان‌بندی دبیرستان حضرت معصومه بعد از اجرای فاز دوم مساله

محدودیت نرم	اولین محدودیت نرم	دومین محدودیت نرم	سومین محدودیت نرم	جمع
تعداد نقض	8	0	16	24

 

 

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

·       همچنین می‌توانیم از ضرایب جریمه مناسب در تابع هدف مساله برنامه‌ریزی خطی صحیح شناخته شده به منظور هدایت بهتر به سمت جواب بهینه استفاده کنیم.

·       با توجه به کاربردی بودن مساله می‌توان چهارچوبی تهیه کرد که راهگشای مراکز آموزشی برای امر زمان‌بندی باشد.

از سایر روش‌های فراابتکاری برای حل مساله زمان‌بندی دروس دبیرستانی استفاده کرد و همچنین حل این مساله در ابعاد بزرگتر مورد بحث و بررسی قرار گیرد.

 

 

 

 

 

 

فهرست منابع

 

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

 

 

 

پیوست­ها

پیوست (1): نتایج حاصل از اجرای الگوریتم دو مرحله‌ای بر روی داده‌های واقعی دبیرستان مطهر در جداو‌ل 1 تا 5 آورده شده است.

 

جدول(1): نمایش جواب شدنی برای زمان‌بندی کلاس‌های دبیرستان مطهر مربوط به اجرای مرحله اول مساله زمان‌بندی

 

 

جدول (2): نمایش جواب بهبود یافته برای زمان‌بندی کلاس‌های دبیرستان مطهر مربوط بعد از 30 دقیقه( اجرای مرحله دوم مساله)

روزهای کاری	شنبه		یکشنبه				دوشنبه				سه شنبه			چهارشنبه
بازه‌های زمانی
دهم انسانی	11	4	60	10	6	12	101	5	3	9	62	13	7	8	2	0	1	59
دهم تجربی1	24	19	20	16	21	14	26	23	17	76	15	22	70	27	18	67	19	25
دهم تجربی2	20	17	15	21	26	25	71	27	22	24	79	19	18	19	14	23	68	16
یازدهم انسانی	32	42	81	86	36	82	103	34	37	35	31	33	30	40	36	39	38	41
یازدهم تجربی1	43	46	55	47	51	45	53	54	98	50	49	48	92	44	47	106	52	44
یازدهم تجربی2	54	44	47	50	43	49	45	48	92	52	44	46	47	106	53	98	55	51

 

 

جدول (3): نمایش جواب بهبود یافته برای زمان‌بندی کلاس‌های دبیرستان مطهر مربوط بعد از 60 دقیقه (اجرای مرحله دوم مساله)

روزهای کاری	شنبه					یکشنبه					دوشنبه					سه شنبه				چهارشنبه
بازه‌های زمانی
دهم انسانی	2	3	7	8	6		62	101	5	13		60	0	4	9		10	11	12		1	59
دهم تجربی1	23	19	20	16	18		14	70	21	17		76	19	22	26		67	15	25		24	27
دهم تجربی2	14	17	15	20	68		22	71	23	79		16	25	19	18		19	21	27		26	24
یازدهم انسانی	32	30	81	86	33		82	41	34	37		35	31	36	39		40	36	42		38	103
یازدهم تجربی1	43	46	49	106	55		47	48	54	52		50	51	44	98		53	45	44		47	92
یازدهم تجربی2	54	44	45	50	43		49	98	48	92		52	44	46	47		106	53	47		55	51

 

 

جدول (4): نمایش جواب بهبود یافته برای زمان‌بندی کلاس‌های دبیرستان مطهر مربوط بعد از سه ساعت و 8 دقیقه( اجرای مرحله دوم مساله)

روزهای کاری	شنبه					یکشنبه					دوشنبه					سه شنبه				چهارشنبه
بازه‌های زمانی
دهم انسانی	2	8	7	3	6		62	101	5	13		60	0	4	9		10	11	12		1	59
دهم تجربی1	23	76	25	16	70		14	20	21	17		19	15	22	24		67	18	27		19	26
دهم تجربی2	14	79	15	20	26		18	71	27	22		16	25	19	23		19	21	17		68	24
یازدهم انسانی	32	30	81	86	33		82	41	34	37		35	31	36	42		39	36	38		40	103
یازدهم تجربی1	43	46	55	54	52		47	49	106	44		50	51	48	44		98	45	47		53	92
یازدهم تجربی2	54	92	45	50	44		49	47	48	43		52	44	46	47		106	53	98		55	51

 

 

جدول (5): نمایش جواب بهبود یافته برای زمان‌بندی کلاس‌های دبیرستان مطهر مربوط بعد از اجرای مرحله دوم مساله(با افزودن یک محدودیت جدید)

روزهای کاری	شنبه					یکشنبه					دوشنبه					سه شنبه				چهارشنبه
بازه‌های زمانی
دهم انسانی	2	3	7	8	6		62	101	5	13		60	0	4	9		10	11	12		1	59
دهم تجربی1	23	19	20	16	24		14	76	21	17		18	25	22	15		67	70	27		19	26
دهم تجربی2	14	17	15	23	20		18	68	71	79		16	22	19	26		19	21	25		27	24
یازدهم انسانی	32	30	81	86	33		82	35	34	37		103	31	36	39		40	41	42		38	36
یازدهم تجربی1	43	46	55	44	51		47	98	54	52		50	49	48	92		44	45	47		53	106
یازدهم تجربی2	54	44	45	50	43		49	47	48	92		47	44	46	52		106	53	98		51	55

 

پیوست (2): نتایج حاصل از اجرای الگوریتم دو مرحله‌ای بر روی داده‌های واقعی دبیرستان حضرت معصومه در جداول‌ 6 و7 آورده شده است.

 

جدول (6): جواب شدنی برای زمان‌بندی کلاس‌های چهارم دبیرستان حضرت معصومه مربوط به اجرای فاز اول مساله

روزهای کاری	شنبه					یکشنبه					دوشنبه					سه شنبه				چهارشنبه
بازه‌های زمانی
دهم انسانی	2	0	9	7	6		62	101	5	13		60	12	4	10		3	11	8		1	59
دهم تجربی1	23	16	20	15	24		14	18	21	17		76	19	22	26		67	70	25		19	27
دهم تجربی2	14	17	15	79	20		71	68	23	22		16	25	19	18		19	21	27		26	24
یازدهم انسانی	32	42	81	82	33		34	41	86	37		35	31	36	30		40	36	39		38	103
یازدهم تجربی1	43	46	54	45	51		47	98	55	44		50	49	48	53		44	106	47		52	92
یازدهم تجربی2	54	44	45	50	98		49	47	48	43		52	44	46	47		106	53	92		55	51

 

جدول (7): جواب بهبود یافته برای مساله جدول زمان‌بندی کلاس‌های چهارم دبیرستان حضرت معصومه مربوط به اجرای فاز دوم مساله

روزهای کاری	شنبه					یکشنبه					دوشنبه					سه‌شنبه
بازه‌های زمانی
چهارم ریاضی	2	9	5	-	1		0	0	7	5		24	16	-	-		9	7	-
چهارم تجربی 1	23	6	-	-	33		6	8	17	-		27	12	3	23		8	3	12
چهارم تجربی 2	18	-	33	3	8		11	-	23	3		-	8	26	11		23	6	6
چهارم تجربی 3	8	-	11	8	11		23	-	33	27		3	-	6	3		6	18	23
چهارم انسانی	-	4	14	19	-		31	32	28	35		-	21	32	30		34	14	21

 

 

---