20184

17410

كارشناسي ارشد

سيستم‌هاي كلان

اصفهان : دانشگاه صنعتي اصفهان

1403

دوازده، 90ص، : جدول، نمودار

1403/12/20

كتابنامه

مهندسي صنايع

مهندسي صنايع و سيستم ها

1403/12/20

23117410

مسئله جدول‌زماني دروس دانشگاهي به تخصيص دانشجويان به كلاس‌ها و تخصيص اتاق‌ها و زمان‌ها به كلاس‌ها مي‌پردازد، به گونه‌اي كه تمامي محدوديت‌هاي سخت، رعايت شده و هزينه‌هاي ناشي از نقض محدوديت‌هاي نرم به حداقل برسد. اين مسئله به دليل پيچيدگي‌هاي ساختاري، تنوع محدوديت‌ها و ابعاد بزرگ، يكي از چالش‌برانگيزترين مسائل در مديريت منابع آموزشي است. هدف از اين پژوهش، طراحي مدلي كارآمد براي مسئله جدول زماني دروس دانشگاهي مسابقه ITC-2019 و ارائه روشي بهينه براي حل آن است كه بتواند پاسخ‌هايي با كيفيت بالا در زمان منطقي ارائه دهد. اين مسئله با در نظر گرفتن محدوديت‌هاي متعدد به دنبال دستيابي به تخصيص بهينه منابع آموزشي است .مدل ارائه‌شده بر پايه برنامه‌ريزي عدد صحيح مختلط طراحي شده است. در اين مدل، به‌منظور كاهش پيچيدگي و افزايش كارايي، تعداد متغيرها و محدوديت‌ها از طريق حذف انديس‌هاي غيرضروري و همچنين بازنويسي روابط محدوديت ها به شكل كارآمدتر، كاهش يافته است. همچنين از رويكرد هرس كردن متغيرها و محدوديت‌ها استفاده شده است كه متغيرها و محدوديت‌هاي غيرضروري را شناسايي و از مدل حذف مي‌كند. اين اقدام، ابعاد مدل را به‌طور قابل توجهي كوچك‌تر كرده و امكان حل آن را در زمان كوتاه‌تر فراهم مي‌سازد. براي حل اين مدل، از يك الگوريتم ابتكاري دو مرحله‌اي استفاده شده است. در مرحله اول، يك جواب شدني اوليه به دست مي‌آيد كه تمامي محدوديت‌هاي سخت را برآورده مي‌كند. سپس در مرحله دوم، با استفاده از جستجوي همسايگي و بهينه‌سازي تكرارشونده، كيفيت اين جواب بهبود مي‌يابد. در اين مرحله، از استراتژي‌هاي متنوع تثبيت متغيرها استفاده شده است تا فضاي جستجو به‌صورت مؤثرتري مديريت شود و الگوريتم بتواند به جواب‌هاي با كيفيت بالاتر دست يابد. نتايج عددي به‌دست‌آمده از اجراي مدل و الگوريتم پيشنهادي بر روي نمونه‌هاي مسابقه ITC-2019 نشان مي‌دهد كه روش ارائه‌شده توانسته است در موارد خوبي به نتايج رقابتي در مقايسه با بهترين جواب‌هاي شناخته‌شده دست يابد. در پنج نمونه از 30 نمونه، نتايج اين پژوهش تقريباً به بهترين جواب‌ شناخته شده رسيده و در 11 نمونه، عملكرد بهتري نسبت به مدل ارائه‌شده توسط مقاله پايه داشته است. اين پژوهش با ارائه مدلي اصلاح‌شده و استفاده از رويكردهاي تركيبي، گامي مؤثر در حل مسائل پيچيده زمان‌بندي دروس دانشگاهي برداشته است و مي‌تواند به‌عنوان پايه‌اي براي پژوهش‌هاي آينده در اين حوزه مورد استفاده قرار گيرد.

The university course timetabling problem involves allocating students to classes and assigning rooms and time periods to each class, ensuring that all hard constraints are satisfied and the penalty costs resulting from the violation of soft constraints are minimized. Due to its structural complexity, the diversity of constraints, and its large scale, this problem is considered one of the most challenging issues in educational resource management. This research aims to generate an efficient model for the ITC-2019 competition university course timetabling problem and propose an optimized solution method that delivers high-quality solutions within a reasonable timeframe. This problem aims to achieve optimal resource allocation while considering numerous constraints. The proposed model is based on mixed-integer linear programming. The number of variables and constraints has been minimized by eliminating unnecessary indices and rewriting the constraint expressions into more efficient forms to reduce complexity and enhance efficiency. Additionally, a variable and constraint pruning approach is employed to identify and remove unnecessary variables and constraints from the model. This significantly reduces the model's size and enables it to be solved in shorter runtimes. A two-stage heuristic algorithm has been used to solve the model. In the first stage, an initial feasible solution is obtained that satisfies all hard constraints. In the second stage, using local search and iterative optimization, the quality of this solution is improved. In this stage, diverse variable fixing strategies are applied to effectively manage the search space and allow the algorithm to achieve higher-quality solutions. Computational results obtained from applying the proposed model and algorithm to ITC-2019 competition instances demonstrate that the proposed approach has achieved competitive results compared to the best-known solutions in many cases. In five out of 30 instances, the results of this study have nearly reached the best-known solution, and in 11 instances, we achieved a better solution compared to the baseline paper. By presenting a refined model and employing hybrid approaches, this research has taken a significant step toward solving complex university course timetabling problems and can serve as a foundation for future studies in this field.

محمد رئيسي نافچي

قاسم مصلحي

مهدي ايران پور , حسين خسروشاهي