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

نوع مقاله: مقاله علمی پژوهشی

نویسندگان

1 استادیار تحقیق در عملیات، گروه مدیریت صنعتی، دانشگاه خلیج فارس، بوشهر، ایران

2 استادیار تولید و عملیات، گروه مدیریت صنعتی، دانشگاه خلیج فارس، بوشهر، ایران

3 کارشناس ارشد مدیریت صنعتی، دانشگاه خلیج فارس، بوشهر، ایران

چکیده

زمان‎بندی درس‌های دانشگاه یک مسئلۀ پیچیدۀ بهینه‏سازی است. عوامل زیادی مانند گروه‌های آموزشی، استادان، اتاق‌ها و دانشجویان، مسئله را بزرگ و حل آن را دشوار می‎کنند. هر عامل، مجموعه‎ای از محدودیت‌ها را که معمولاً با هم در تضاد هستند، بر فضای حل تحمیل می‌کند. اگر درس‌ها در اتاق‌های متفاوت و در بازه‌های زمانی معین به‎گونه‌ای زمان‎بندی شوند که مجموعه محدودیت‌ها را برآورده کنند، مسئله حل خواهد شد. در این نوشتار برای حل مسئلۀ زمان‎بندی درس‌های دانشگاه، یک الگوریتم هیوریستیک فرادست بر مبنای گراف ارائه شده است. الگوریتم پیشنهادی یک رویۀ مدل‌سازی دو لایه است که هیوریستیک فرادست را با روش رنگ‌آمیزی گراف ترکیب می‎کند. لایۀ بالاتر، یک هیوریستیک مناسب را انتخاب می‌کند که بتواند یک حل‎شدنی خوب را برای مسئلۀ رنگ‌آمیزی گراف در لایۀ پایین ارائه دهد. الگوریتم پیشنهادی در حل یک مسئلۀ واقعی به‎کار رفته است. رویکرد پیشنهادی توانست همۀ محدودیت‌های نرم و سخت را برآورده کند. بر اساس یافته‌ها می‌توان نتیجه گرفت که رویکرد پیشنهادی یک روش مناسب و کارای محاسباتی، در یافتن حل مسئلۀ زمان‎بندی درس‌های دانشگاه است.

کلیدواژه‌ها


عنوان مقاله [English]

University Course Timetabling Using Graph-based Hyper Heuristics

نویسندگان [English]

  • Khodakaram Salimifard 1
  • Gholamreza Jamali 2
  • Salman Babaeezadeh 3
1 Assistant Prof. of Management Science, Dep. of Industrial Management, Persian Gulf University of Boushehr, Iran
2 Assistant Prof. of Management Science, Dep. of Industrial Management, Persian Gulf University of Boushehr, Iran
3 M.Sc. in Industrial Management, Dep. of Industrial Management, Persian Gulf University of Boushehr, Iran
چکیده [English]

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.

کلیدواژه‌ها [English]

  • Graph Coloring
  • Hyper heuristics
  • Local Search
  • University course timetabling