خلاصة:
زمانبندی درسهای دانشگاه یک مسئلۀ پیچیدۀ بهینهسازی است. عوامل زیادی مانند گروههای آموزشی، استادان، اتاقها و دانشجویان، مسئله را بزرگ و حل آن را دشوار میکنند. هر عامل، مجموعهای از محدودیتها را که معمولا با هم در تضاد هستند، بر فضای حل تحمیل میکند. اگر درسها در اتاقهای متفاوت و در بازههای زمانی معین بهگونهای زمانبندی شوند که مجموعه محدودیتها را برآورده کنند، مسئله حل خواهد شد. در این نوشتار برای حل مسئلۀ زمانبندی درسهای دانشگاه، یک الگوریتم هیوریستیک فرادست بر مبنای گراف ارائه شده است. الگوریتم پیشنهادی یک رویۀ مدلسازی دو لایه است که هیوریستیک فرادست را با روش رنگآمیزی گراف ترکیب میکند. لایۀ بالاتر، یک هیوریستیک مناسب را انتخاب میکند که بتواند یک حلشدنی خوب را برای مسئلۀ رنگآمیزی گراف در لایۀ پایین ارائه دهد. الگوریتم پیشنهادی در حل یک مسئلۀ واقعی بهکار رفته است. رویکرد پیشنهادی توانست همۀ محدودیتهای نرم و سخت را برآورده کند. بر اساس یافتهها میتوان نتیجه گرفت که رویکرد پیشنهادی یک روش مناسب و کارای محاسباتی، در یافتن حل مسئلۀ زمانبندی درسهای دانشگاه است.
University course timetabling is a complex optimization problem. There are many components like departments، faculties، rooms، and students making the problem huge and difficult to solve. Each component enforces a set of normally conflicting constraints on the solution space. The problem will be solved if courses are scheduled in different rooms and within some specific time slots such that a set of constraints are satisfied. In this paper، a graph-based hyper-heuristic is proposed to find a solution to the problem. This is a two tiers modeling approach combining hyper heuristic with graph coloring technique. The upper tier heuristic is used to select a suitable heuristic to find a feasible solution on the lower tier. To find the suitability of the proposed approach، it has been applied to a real world case. The proposed approach was able to satisfy all the hard and soft constraints. Based on the research findings، it can be concluded that a graph-based hyper heuristic approach is a suitable and computationally efficient method to find a solution to university course timetabling problem.
ملخص الجهاز:
اگر درس ها در اتاق هاي متفاوت و در بـازه هـاي زمـاني معـين بـه گونـه اي زمان بندي شوند که مجموعه محدوديت ها را برآورده کنند، مسئله حل خواهد شد.
در اين نوشتار براي حل مسئلة زمان بندي درس هاي دانشگاه ، يک الگوريتم هيوريستيک فرادسـت بـر مبنـاي گراف ارائه شده است .
مسئلة زمان بندي درس ، دربرگيرندة زمان بنـدي مجموعـه اي از هـم نشسـتي ميـان اسـتاد و دانشجويان درس ، در شمار بازة زماني است ؛ به گونه اي که محدوديت هاي تعريف شـده را بـرآورده کند.
با توجه به آنچه در بالا گفته شد، مي توان نتيجه گرفت که يک برنامة زماني بايد بـه گونـه اي باشد که در آن ، هر نشست از يک گروه درسي در يک بازة زماني و يک اتاق تخصيص داده شود؛ به گونه اي که محدوديت هاي سخت برآورده شود.
روش پژوهش در اين پژوهش براي حل مسئلة زمان بندي درس هاي دانشگاه با به کارگيري رنگ آميزي گـراف ، متغير تصميم به شيوة زير تعريف شده است : رابطة ١) دورگرسنه i با استاد j در روز k و در بازه زماني l برگزار شود.
با معرفي متغير N که بيانگر شما اتاق هاي در دسترس در هر بازة زماني است ، رابطة ٥ شيوة مدل سازي اين محدوديت را براي هر بازة l در هر روز k نشان مي دهد.
), Practice and theory of automated timetabling: Selected papers from the first international conference, 1153, Edinburgh, UK, August 29 - September 1.
), Practice and Theory of Automated Timetabling II, Lecture Notes in Computer Science, 1408: 3-19.