روش برنامه‌ریزی عدد صحیح در مساله تخصیص کلاس درس در دانشگاه با مقیاس بزرگ

نویسندگان
غلام حسن شیردل 1
مصطفی محمدی 2
1 دانشگاه قم
2 دانشگاه آزاد قزوین
10.52547/jde.1.4.81
چکیده
جدول زمان‌بندی دروس دوره­های دانشگاهی یک مسئله‌ی بزرگ تخصیص منابع است، که در آن‌هم زمان و هم‌مکان برای هر جلسه‌ی کلاس تعیین می‌شوند.که اکثر ادبیات‌های علمی راه‌حل کاملاً اکتشافی را مطرح می‌کنند. برخی از روش‌ها در مورد برنامه‌ریزی زمان‌بندی کلاس‌ها مطرح‌شده‌اند اما این روش‌ها تنها برای دانشگاه‌های کوچک یا یک بخش و گروه در دانشگاه بزرگ‌تر مطرح‌شده‌اند، برای دانشگاه‌های بزرگ باید تجزیه‌ای بین بخش­های آن صورت بگیرد و به بخش‌های کوچک‌تر تقسیم شود سپس آن را حل کنند که هم هزینه‌بر و هم‌زمان بر است و برای دانشگاه‌های بزرگ مناسب نیست. در این پژوهش به زمان‌بندی امتحانات با در نظر گرفتن اطلاعات( کلاس‌ها و امتحانات و ظرفیت کلاس‌ها و تعداد شرکت‌کنندگان امتحانات و ویژگی‌های خاص کلاس‌ها و امتحانات) به بررسی زمان‌بندی امتحانات در دانشگاه آزاد اسلامی قزوین پرداخته شد. این پژوهش کاربردی و ازنظر روش کمی-ریاضی است و برای همه دانشگاه‌ها و مؤسسات کوچک و بزرگ برای یافتن جواب بهینه برای تخصیص امتحانات و دروس به کلاس‌ها به‌صورت مستقیم و بدون نیاز به تجزیه بخش‌ها قابل‌استفاده است. همچنین این روش برای مسائل بزرگ منعطف است و در صرف زمان و هزینه صرفه‌جویی می‌شود. برای این منظور ابتدا مسئله با استفاده از الگوی برنامه­ریزی عدد صحیح[1] تعریف شد و سپس با استفاده از الگوریتم فرا ابتکاری ژنتیک[2] حل می‌شود. خروجی محاسبات عدد دودویی بود که تعلق امتحان به کلاس را تعریف می­کرد به‌طوری‌که هزینه تخصیص نادرست به صفر نزدیک شد.




[1] Integer Programming



[2] Genetic Algorithms
کلیدواژه‌ها
برنامه‌ریزی عدد صحیح
تخصیص کلاس درس
مقیاس بزرگ

عنوان مقاله English

Integer programming methods for large-scale classroom assigment problem

نویسندگان English

Gholam Hassan Shirdel 1
Mostafa Mohammadi 2
1 Universiyu of Qom
چکیده English

In this paper we present an integer programming method for solving the Classroom Assignment Problem in University CourseTime tabling.We introduce a novel formulation of the problem which generalizes existing models and maintain stractability even for large instances. The model isvalidated through computation a lresults base do nourexperiencesat the University of Auckland,and on instances from the 2007 International Timetabling Competition.We also expand uponexistingresultsin to the computational difficulty of roomassignment problems

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

Integer programming
Classroom Assigment problem
Large-scale problem
Phillips, A. E., Waterer, H., Ehrgott, M., & Ryan, D. M. (2015). Integer programming methods for large-scale practical classroom assignment problems. Computers & Operations Research, 53, 42-53.
Reisman, A., Kumar, A., Motwani, J., 1997. Flowshop scheduling/sequencing research: A statistical review of the literature, 1952–1994. IEEE Transactions on Engineering Management 44, 316–329.
Stafford EF. On the development of a mixed-integer linear programming model for the flowshop sequencing problem. Journal of the Operational Research Society 1988;39:1163-74.
Stafford EF., Tseng FT. Two models for a family of flowshop sequencing problems. European Journal of Operational Research 2002; 142 282-93