آمار
| تعداد نشریات | 202 |
| تعداد شماره‌ها | 5,067 |
| تعداد مقالات | 55,663 |
| تعداد مشاهده مقاله | 91,656,790 |
| تعداد دریافت فایل اصل مقاله | 74,207,413 |
ارائۀ یک مدل برنامه‌ریزی خطی عدد صحیح دومرحله‌ای برای مسئلۀ زمان‌بندی دروس دانشگاهی | ||
| مدیریت صنعتی | ||
| مقاله 2، دوره 9، شماره 1، 1396، صفحه 19-42 اصل مقاله (418.33 K) | ||
| نوع مقاله: مقاله علمی پژوهشی | ||
| شناسه دیجیتال (DOI): 10.22059/imj.2017.217990.1007129 | ||
| نویسندگان | ||
مجید اسماعیلیان  1؛ سیده مریم عبداللهی2
| ||
| 1استادیار گروه مدیریت، دانشکدۀ علوم اداری و اقتصاد، دانشگاه اصفهان، اصفهان، ایران | ||
| 2کارشناس ارشد مدیریت صنعتی، دانشکدۀ علوم اداری و اقتصاد، دانشگاه اصفهان، اصفهان، ایران | ||
| چکیده | ||
| در این پژوهش، یک مدل برنامه‌ریزی عدد صحیح برای مسئلۀ زمان‌بندی دروس دانشگاهی ارائه شده است. برای کاهش تعداد متغیرهای تصمیم، ترکیب درس و استاد و گروه دانشجو به‌عنوان فعالیت معرفی شد و دو مدل برنامه‌ریزی عدد صحیح با عنوان مدل مبتنی بر فعالیت و مدل دومرحله‌ای مبتنی بر فعالیت بهدست آمد. در مرحلۀ اول برمبنای تعداد جلسات لازم در هفته در بازه‌های زمانی روزهای مختلف هفته، تمام فعالیت‌ها زمان‌بندی شد و در مرحلۀ دوم با درنظرگرفتن محدودیت‌های خاص، کلاس‌ها و فضاهای آموزشی به جلسات برنامه‌ریزیشده تخصیص یافت. این مدل‌ها برای یک نیمسال تحصیلی برمبنای فرایند تخصیص دروس به بازه‌های زمانی خاص در روزهای هفته با محدودیت‌های سخت در دانشکدۀ علوم اداری و اقتصاد دانشگاه اصفهان فرموله شده است. در این مطالعه، ضمن فرمولهکردن تمام قواعد تعریف جدول زمان‌بندی دروس یک نیمسال در نرم‌افزار، با استفاده از مدل دومرحله‌ای مبتنی بر فعالیت، تعداد 239 درس در زمان 556 ثانیه (9 دقیقه و 16 ثانیه) زمان‌بندی‌شده است. | ||
| کلیدواژه‌ها | ||
| برنامه‌ریزی خطی عدد صحیح؛ زمان‌بندی درس‌های دانشگاهی؛ مدل‌سازی ریاضی؛ محدودیت سخت؛ مدل دومرحله ای | ||
| عنوان مقاله [English] | ||
| Proposing a Two-Phase Integer Linear Programming for University-Course Timetabling | ||
| نویسندگان [English] | ||
| Majid Esmaelian1؛ Sayedeh Maryam Abdollahi2 | ||
| 1Assistant Prof. in Management, Faculty of Administrative Sciences and Economics, Isfahan University, Isfahan, Iran | ||
| 2MSc of Industrial Management, Faculty of Administrative Sciences and Economics, Isfahan University, , Iran | ||
| چکیده [English] | ||
| An integer linear programming model for university courses timetabling is proposed here. In order to reduce the number of decisive variables, a combination of a course, a professor schedule and the students ‘group was defined as an activity. In this context, the two integer programming models namely the activity-based model and a two-phase activity-based model were proposed. In the first model, all activities were scheduled based on the number of required weekly sessions in the weekdays intervals; however, in the second model, classes and training courses were determined according to the planned sessions considering their special restrictions. These models were formulated based on the process of assigning the university courses within specific intervals throughout the week considering fierce constraints for a given semester in the department of Economics at University of Isfahan. All regulation concerning the courses timetable of a semester were formulated in GAMS software. Then, 239 courses were successfully scheduled using the two-phase activity-based model in only 9 minutes and 16 seconds | ||
| کلیدواژه‌ها [English] | ||
| Bi-level model, Hard constraint, Integer linear programming, Mathematical modeling, University course timetabling | ||
| مراجع | ||
|
اسماعیلیان، م.، عبدالهی، س. م. (1395). زمان‌بندی کلاسهای درس با استفاده از برنامه‌ریزی عدد صحیح. مطالعات مدیریت صنعتی، 14 (41)، 187-163. بهداد، م.، دهقانی، ت.، ذاکر تولائی، م. (1385). رویکردی نوین در زمان‌بندی دروس دانشگاه با استفاده از الگوریتم ژنتیک. دوازدهمین کنفرانس سالانۀ انجمن کامپیوتر ایران. تهران: دانشگاه شهید بهشتی. جودکی، م.، منتظری، م. ع.، موسوی، س. ر. (1390). بررسی مسئلۀ زمان‌بندی درسی دانشگاهی با استفاده از ترکیب الگوریتم ممتیک بهبود یافته و الگوریتم سردشدن شبیهسازی شده. مهندسی برق و مهندسی کامپیوتر ایران، 9(4)، 202-192. راستگار امینی، ف.، میرمحمدی، س.م. (1391). مدل‌سازی و ارائۀ روش حل برای مسئلۀ زمان‌بندی دروس دانشگاهی و تخصیص استاد ـ درس (مطالعۀ موردی دانشکدۀ صنایع دانشگاه صنعتی اصفهان). نهمین کنفرانس بینالمللی مهندسی صنایع. تهران: انجمن مهندسی صنایع ایران، دانشگاه صنعتی خواجه نصیرالدین طوسی. سلیمی فرد، خ.، باباییزاده، س. (1390). یک سیستم پشتیبانی تصمیم برای زمان‌بندی کلاسهای دانشگاه (مطالعۀ موردی: دانشگاه خلیج فارس)، مدیریت فناوری اطلاعات، 3 (7)، 92-77. علیرضایی، م. ر.، منصورزاده، س. م.، خلیلی، م. (1385). برنامه‌ریزی درسی در دانشگاه به کمک مدل‌سازی دو مرحلهای برنامه‌ریزی ریاضی. دانشور، 17، 96-87. فراهانی، ر.، زندیه، ز. (1392). زمان‌بندی چند معیارۀ دروس دانشگاهی با بهکارگیری الگوریتم جستوجوی ممنوعه و فرایند تحلیل سلسهمراتبی. دهمین کنفرانس بینالمللی مهندسی صنایع ایران. منجمی، ا.ح.، مسعودیان، س.، استکی، ا.، نعمتبخش، ن. (1388). طراحی جدول زمان‌بندی خودکار برای دروس دانشگاهی با استفاده از الگوریتمهای ژنتیک. فناوری آموزش، 4 (2)، 127- 113. Aladag, C. H., Hocaoglu, G. & Basaran, M. A. (2009). The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem. Expert Systems with Applications, 36(10), 12349-12356.
Alzaqebah, M. & Abdullah, S. (2015). Hybrid bee colony optimization for examination timetabling problems. Computers & Operations Research, 54, 142-154.
Amintoosi, M. & Haddadnia, J. (2005). Fuzzy C-means clustering algorithm to group students in a course into smaller sections. ACM and Springer, 147-160.
Asmuni, H. (2008). Fuzzy methodologies for automated University timetabling solution construction and evaluation. Doctoral dissertation, University of Nottingham.
Aycan, E. & Ayav, T. (2009). Solving the course scheduling problem using simulated annealing”. In Advance Computing Conference, 2009. IACC 2009. IEEE International (pp. 462-466), IEEE.
Babaei, H., Karimpour, J. & Hadidi, A. (2015). A survey of approaches for university course timetabling problem. Computers & Industrial Engineering, 86, 43-59.
Babaizadeh, S. & Salimifard, KH. (2011). A decision support system for university course time tabling (The case: Khalijefars University). Information Technology Management, 3(7), 77-92. (in Persian)
Badoni, R. P., Gupta, D. K. & Mishra, P. (2014). A new hybrid algorithm for university course timetabling problem using events based on groupings of students. Computers & Industrial Engineering, 78, 12-25.
Barrera, D., Velasco, N. & Amaya, C. A. (2012). A network-based approach to the multi-activity combined timetabling and crew scheduling problem: Workforce scheduling for public health policy implementation. Computers & Industrial Engineering, 63(4), 802-812.
Behdad, M., Dehghani, T. & Zaker Tavalai, M. (2006). A new approach in course timetabling using genetic algorithm”, In the Twelfth Conference of Iranian Computer Science Society. Tehran. (in Persian)
Burke, E. K. & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266-280.
Burke, E. K., Kendall, G., Mısır, M., Özcan, E., Burke, E. K., Kendall, G., ... & Mısır, M. (2004). Applications to timetabling. In Handbook of Graph Theory, chapter 5.6.
Burke, E. K., Mareček, J., Parkes, A. J., &Rudová, H. (2010). A super nodal formulation of vertex coloring with applications in course timetabling. Annals of Operations Research, 179(1), 105-130.
Burke, E. K., McCollum, B., Meisels, A., Petrovic, S. & Qu, R. (2007). A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research, 176(1), 177-192.
Burke, E., de Werra, D. & Kingston, J. (2013). Applications to Timetabling .In P. Zhang (Ed.), Handbook of Graph Theory, Second Edition (pp. 530-562), Chapman and Hall/CRC.
Carter, M. W. (1989). A Lagrangian Relaxation Approach to The Classroom Assignment Problem. INFOR: Information Systems and Operational Research, 27(2), 230-246.
Chaudhuri, A. & De, K. (2010). Fuzzy genetic heuristic for university course timetable problem. International Journal of Advances in Soft Computing and its Applications, 2(1), 100-123.
Deris, S., Omatu, S. & Ohta, H. (2000). Timetable planning using the constraint-based reasoning. Computers & Operations Research, 27(9), 819-840.
Esmaelian, M. & Abdollahi, S. M. (2016). Binary integer programming for university timetabling (The Case: Faculty of administrative sciences and economics of Esfahan university). Industrial Management Studies, 14(41), 163-187. (in Persian)
Farahani, R. & Zandieh, M. (2013). Multi criteria university course scheduling applying Tabue Search algorithm and analytical hierarchical processing (AHP). In the Tenth International Conference on Industrial Management, Tehran. (in Persian)
Feizi-Derakhshi, M.R., Babaei, H. & Heidarzadeh, J. (2012). A survey of approaches for university course timetabling problem. In Proceedings of 8th international symposium on intelligent and manufacturing systems (IMS 2012), (p.p. 307-321).
Geem, Z. W., Kim, J. H. & Loganathan, G. V. (2001). A new heuristic optimization algorithm: harmony search. Simulation, 76(2), 60-68.
Golabpour, A., Shirazi, H. M., Farahi, A., Kootiani, A. Z. M. & Beigi, H. (2008). A fuzzy solution based on Memetic algorithms for timetabling. In Multimedia and Information Technology, 2008. MMIT'08. International Conference on, (p.p. 108-110), IEEE.
Henry Obit, J. (2010). Developing novel meta-heuristic, hyper-heuristic and cooperative search for course timetabling problems. Doctoral dissertation, United kingdom: University of Nottingham.
Joodaki, M., Montazeri, M. A. & Moosavi, S. R. (2011). Investigation of university course timetabling problem using a combination of improved memetic algorithm and simulated annealing algorithm. Iran’s Electronic and Computer Engineering, 9(4), 192-202. (in Persian)
Jorge, A.S.A., Martín, C., Héctor, P. & Sotelo-Figueroa, M. A. (2013). Comparison of metaheuristic algorithms with a methodology of design for the evaluation of hard constraints over the course timetabling problem. In Recent Advances on Hybrid Intelligent Systems (p.p. 289-302), Springer Berlin Heidelberg.
Jorge, S. A., Martin, C., Hector, P., Patricia, M., Hugo, T. M., Laura, C. & Marco, S. F. (2014). Generic Memetic Algorithm for Course Timetabling ITC2007. In Recent Advances on Hybrid Approaches for Designing Intelligent Systems (p.p. 481-492), Springer International Publishing.
Junginger, W. (1986). Timetabling in Germany-a survey. Interfaces, 16(4), 66-74.
Kaspi, M. & Raviv, T. (2013). Service-oriented line planning and timetabling for passenger trains. Transportation Science, 47(3), 295-311.
Khalili, M., Mansoorzadeh, M.S. & Alirezai, R.M. (2006). University course timetabling using two phase mathematical programming. Daneshvar Raftar, 17, 87-96. (in Persian)
Kostuch, P. (2004). The university course timetabling problem with a three-phase approach. In International Conference on the Practice and Theory of Automated Timetabling (p.p. 109-125), Springer Berlin Heidelberg.
Kroon, L. G. & Peeters, L. W. (2003). A variable trip time model for cyclic railway timetabling. Transportation Science, 37(2), 198-212.
Lewis, R. (2008). A survey of metaheuristic-based techniques for university timetabling problems. OR spectrum, 30(1), 167-190.
Lewis, R. (2012). A time-dependent metaheuristic algorithm for post enrolment-based course timetabling. Annals of Operations Research, 194(1), 273-289.
Lewis, R., Paechter, B. & Rossi-Doria, O. (2007). Metaheuristics for university course timetabling. In Evolutionary scheduling (p.p. 237-272), Springer Berlin Heidelberg.
Miranda, J. (2010). eClasSkeduler: a course scheduling system for the Executive Education Unit at the Universidad de Chile. Interfaces, 40(3), 196-207.
MirHassani, S. A. & Habibi, F. (2013). Solution approaches to the course timetabling problem. Artificial Intelligence Review, 39(2), 133-149.
Monajemi, S. A., Masoudian, S., Esteki, A. & Nematbakhsh, N. (2009). Automatic university course timetable designing using Genetic Algorithm. Education Technology, 4(2), 113-127. (in Persian)
Nothegger, C., Mayer, A., Chwatal, A. & Raidl, G. R. (2012). Solving the post enrolment course timetabling problem by ant colony optimization. Annals of Operations Research, 194 (1), 325-339.
Post, G., Kingston, J. H., Ahmadi, S., Daskalaki, S., Gogos, C., Kyngas, J., ... & Schaerf, A. (2014). XHSTT: an XML archive for high school timetabling problems in different countries. Annals of Operations Research, 218(1), 295-301.
Puente, J., Gómez, A., Fernández, I. & Priore, P. (2009). Medical doctor rostering problem in a hospital emergency department by means of genetic algorithms. Computers & Industrial Engineering, 56(4), 1232-1242.
Qu, R. & Burke, E. K. (2009). Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems”.Journal of the Operational Research Society, 60(9), 1273-1285.
Qu, R., Burke, E. K., McCollum, B., Merlot, L. T. & Lee, S. Y. (2009). A survey of search methodologies and automated system development for examination timetabling. Journal of scheduling, 12(1), 55-89.
RastgarAmini, F. & Mir Mohammadi, S. A. (2012). Modeling and solving method for university course timetabling problem and teacher-course allocation. In the Ninth International Conference on Industrial Management, Tehran. (in Persian)
Rossi-Doria, O., Sampels, M., Birattari, M., Chiarandini, M., Dorigo, M., Gambardella, L. M. & Paquete, L. (2002). A comparison of the performance of different metaheuristics on the timetabling problem. In International Conference on the Practice and Theory of Automated Timetabling (p.p. 329-351), Springer Berlin Heidelberg.
Santiago-Mozos, R., Salcedo-Sanz, S., DePrado-Cumplido, M. & Bousoño-Calzón, C. (2005). A two-phase heuristic evolutionary algorithm for personalizing course timetables: a case study in a Spanish university. Computers & operations research, 32(7), 1761-1776.
Schaerf, A. (1999). A survey of automated timetabling. Artificial intelligence review, 13(2), 87-127.
Shafia, M. A., Aghaee, M. P., Sadjadi, S. J. & Jamili, A. (2012). Robust Train Timetabling problem: Mathematical model and Branch and bound algorithm. IEEE Transactions on Intelligent Transportation Systems, 13(1), 307-317.
Shafia, M. A., Aghaee, M. P., Sadjadi, S. J. & Jamili, A. (2012). Robust Train Timetabling problem: Mathematical model and Branch and bound algorithm. IEEE Transactions on Intelligent Transportation Systems, 13(1), 307-317.
Shatnawi, S., Al-Rababah, K. & Bani-Ismail, B. (2010). Applying a novel clustering technique based on FP-tree to university timetabling problem: A case study. In Computer Engineering and Systems (ICCES), 2010 International Conference on (p.p. 314-319), IEEE.
Srinivasan, S., Singh, J. & Kumar, V. (2011). Multi-agent based decision support system using data mining and case based reasoning. IJCSI International Journal of Computer Science Issues, 8(4), 340-349.
Tripathy, A. (1984). School timetabling-a case in large binary integer linear programming. Management science, 30(12), 1473-1489.
Turabieh, H., Abdullah, S., McCollum, B. & McMullan, P. (2010). Fish swarm intelligent algorithm for the course timetabling problem. In International Conference on Rough Sets and Knowledge Technology (p.p. 588-595), Springer Berlin Heidelberg.
Wangmaeteekul, P. (2011). Using Distributed Agents to Create University Course Timetables Addressing Essential & Desirable Constraints and Fair Allocation of Resources. Doctoral dissertation, Durham University, United Kingdom: Durham University.
Yang, Y. & Paranjape, R. (2011). A multi-agent system for course timetabling. Intelligent Decision Technologies, 5(2), 113-131.
Yang, Y., Paranjape, R. & Benedicenti, L. (2006). An agent based general solution model for the course timetabling problem. In Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems (p.p. 1430-1432), ACM.
Zhang, L. & Lau, S. (2005). Constructing university timetable using constraint satisfaction programming approach. In International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC'06) (Vol. 2, p.p. 55-60), IEEE. | ||
|
آمار تعداد مشاهده مقاله: 631 تعداد دریافت فایل اصل مقاله: 539 |
||
