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

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

نویسندگان

1 بخش مدیریت / دانشگاه شیراز

2 هیات علمی

3 دانش آموخته بخش مدیریت دانشگاه شیراز

چکیده

این مقاله به مدلسازی و حل مساله جدول‌بندی زمانی دروس دانشگاهی می‌پردازد. در مدلسازی ریاضی این مسأله، دو قسمتی بودن برخی دروس 3 و 4 واحدی در طول هفته، و همچنین تعلق برخی کلاس‌ها به برخی گروه‌های اموزشی در نظر گرفته شد. برای حل این مسأله، یک الگوریتم ابرابتکاری بر اساس الگوریتم رقابت استعماری توسعه داده شد که شامل 9 ابتکار سطح پایین است که بر اساس 5 استراتژی نحوه تخصیص را مشخص می‌سازد. الگوریتم ابرابتکاری پیشنهادی با داده‌های واقعی از دانشگاه شیراز آزمون شد. نتایج نشان داد که این الگوریتم قادر به تولید 10 جدول زمانی متفاوت طی 17 ساعت اجرا و بدون دخالت انسان است. بهترین جدول زمانی تولید شده بوسیله ابرابتکاری توسعه داده شده قادر است حدود 11 درصد بهره‌برداری از کلاس را افزایش داده و زمان انتظار دانشجویان برای شروع کلاس بعدی را بطور متوسط حدود یک ساعت در هفته کاهش داده است.

کلیدواژه‌ها


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

Automated University Course Timetabling Using Hyper-Heuristic Approach

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

  • Seyed-Hadi Mirghaderi 1
  • moslem alimohammadlo 2
  • Maryam Fotovvati 3
1 Department of Management, Shiraz University
2 faculty member
3 Alumnus from department of management, Shiraz University
چکیده [English]

The university course timetabling problem (UCTP) is a complex and important problem which there is no simple solution for it. However new approach for producing solutions automatically is hyper-heuristics algorithms. This paper aims to produce timetables by considering hard and soft constraints and developing a hyper-heuristic algorithm. The hard constraint in this research are: (1) Each course event must occur in a predefined time length; (2) Each course must occur in a class; (3) Each course must occur following its occurring pattern; (4) Each course must occur in a class with sufficient capacity for students of the course; (5) For each course groups, time overlaps must be zero; (6) A professors’ courses must not have overlap; (7) The number of classes are limited; (8) Each course occur respect to their units; (9) Each class in a specific time dedicated to just one course. Soft constraints may be violated at the expense of some penalty cost which makes the value of objective function more undesirable. The categories of soft constraint penalties in the research are (1) Slot utilization penalty; (2) Course pattern penalty; (3) Class utilization penalty. The proposed hyper-heuristic is based on an imperialist competitive algorithm as a high-level heuristic and uses 9 low-level heuristics, 5 strategies of utilizing low-level heuristics, and 4 heuristics for selecting slots. The hyper-heuristic algorithm programmed in Matlab software and ran on a PC. The results revealed that the hyper-heuristic algorithm is able to produce a variety of timetables in a reasonable time, therefore, provide an opportunity for selection a timetable from a number of time tables. The produced timetables can reduce the student waiting time up to one hour per week and increase the class utilization by 11% which means that the produced timetables can decrease the waiting time of students for starting the next course up to 1 hour per week. The average location similarity between the current and suggested timetable is 31% and the average time similarity is 16%..

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

  • Course
  • Timetable
  • Hyper-heuristic
  • Metaheuristic
  • Algorithm