نویسندگان

• محمدرضا علیرضائی
• مسعود خلیلی
• سیدمهدی منصورزاده

چکیده

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

کلیدواژه‌ها

• : برنامه‌ریزی درسی
• جدول زمان‌بندی
• مسأله برنامه‌ریزی خطی با اعداد صحیح
• الگوریتم‌های ابتکاری

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

University Timetabling Problem with Mathematical Two Stage Modeling

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

• M.R. Alirezaee
• M. Khalili
• S.M. Mansourzadeh

چکیده [English]

 In the university timetabling problem, necessity of considering variables corresponding to lessons, teachers, classes, days of the week and hours bring about a large scale mix integer linear programming problem. Usually the problem is so big that the exact mathematical programming solvers can not solve them in a small period of time. So variety of heuristic algorithms is proposed to solve such problems. In this paper we describe the problem and formulate it as a mix integer linear problem (MILP) then we decompose the problem into two smaller (MILP) that can be solved by exact solvers at the small period of time. Based on proposed model, we have made software for timetabling the lessons at the university. This software is used for scheduling the lessons in mathematics faculty of Iranian university of science and technology at second semester of 1382-1383. The result is presented and compared with the traditional timetabling.

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

• University timetabling
• Mix integer linear program
• Heuristic algorithms