بررسي مسأله زمان‌بندي درسي دانشگاهي با استفاده از ترکيب الگوريتم ممتيک بهبوديافته و الگوريتم سردشدن شبيه‌سازي شده
محورهای موضوعی : مهندسی برق و کامپیوترمجید جودکی 1 , محمدعلی منتظری 2 * , سیدرسول موسوی 3
1 - دانشگاه صنعتی اصفهان
2 - دانشگاه صنعتی اصفهان
3 - دانشگاه صنعتی اصفهان
کلید واژه: الگوریتم سردشدن شبيه‌سازي شده الگوريتم ممتيک جستجوي محلي مسأله زمان‌بندي درسي دانشگاهي,
چکیده مقاله :
مسأله زمان‌بندی به‌عنوان يکی از مسایل پيچيده بهينه‌سازی شناخته می‌شود. يک نمونه از مسایل زمان‌بندی، برنامه‌ريزي درسي دانشگاهی است که هر نيم‌سال در دانشکده‌هاي يک دانشگاه انجام مي‌شود. تنوع محدوديت‌ها در اين مسأله باعث مي‌شود برنامه‌ريزي در دانشکده‌هاي مختلف به گونه‌های متفاوتی انجام شود. کارهاي زيادي براي حل اين مسأله انجام شده است که اکثر آنها از روش‌هاي فرامکاشفه‌اي بهره برده‌اند. در اين مقاله يک مسأله زمان‌بندي واقعي مورد بررسي قرار مي‌گيرد و يک روش مبتني بر الگوريتم ممتيک بهبوديافته که از الگوريتم سردشدن شبيه‌سازي شده به‌عنوان رويه جستجوی محلی خود استفاده مي‌کند، ارائه مي‌شود. منظور از بهبود در الگوريتم ممتيک، استفاده از روش‌های مکاشفه‌ای در توليد جمعيت اوليه و همچنين تغيير عملگر تقاطع در اين الگوريتم مي‌باشد. همچنين يک عملگر به نام عملگر بهبود جهت بهبود راه حل‌هاي توليدشده و کاهش تعداد نقض محدوديت‌ها طراحي شده است. به‌کارگيري روش سردشدن شبيه‌سازي شده به‌عنوان رويه جستجوي محلي در الگوريتم ممتيک باعث افزايش توانايي بهره‌برداري اين الگوريتم خواهد شد. کارآمدی اين روش در مقايسه با برخی روش‌هاي جديد، با توجه به نتايج به‌دست آمده بر روي داده‌هاي استاندارد نشان داده شده است. همچنين مقايسه نتايج حاصل از اين روش با روش انجام‌شده به‌صورت دستي بر روي داده‌هاي واقعي نشان‌دهنده برتري اين روش مي‌باشد.
Course timetabling is a complex problem, happening at the beginning of every semester at universities. One of the most important problems related to this issue is various constraints. As a result of this, timetabling is performed in various methods at different departments. Many works have been performed to solve this problem which majority of them have used metaheuristic based techniques. In this paper, an algorithm is based on hybridization of improved memetic algorithm and simulated annealing algorithm is proposed. Improvement in memetic algorithm means heuristic initializes population and modification in crossover operator. Also, an operator which is called improvement is designed for improvement of created chromosomes and decrease of violation of constraints. In addition, utilization of simulated annealing will result to increase of the exploitive search ability of memetic algorithm. The experimental results which based on standard data indicate this method is more efficient in comparison with some other new methods.
[1] E. Burke, J. Kingston, K. Jackson, and R. Weare, "Automated university timetabling: the state of the art," The Computer J., vol. 40, no. 9, pp. 565-571, 1997.
[2] R. Lewis, "A survey of metaheuristic - based techniques for university timetabling problems," Operations Research, vol. 30, no. 1, pp. 167-190, Jan. 2008.
[3] D. Costa, "A tabu search algorithm for computing an operational timetable," Eur J. Oper. Res., vol. 79, no. 1, pp. 98-110, Jul. 1994.
[4] L. Gislen, C. Peterson, and B. Soderberg, "Teachers and classes with neural networks," Int J. Neural Syst., vol. 1, no. 2, pp. 167-176, Nov. 1989.
[5] D. Corne, P. Ross, and H. Fang, "Evolving timetables," in Lance C. Chambers (ed.) The Practical Handbook of Genetic Algorithms, CRC, Florida, vol. 1, pp. 219-276, 1995.
[6] M. Carrasco and M. Pato, "A multiobjective genetic algorithm for the class/teacher timetabling problem," in E. Burke and W. Erben (eds.) Practice and Theory of Automated Timetabling (PATA T) III, Springer, Berlin, vol .2079, pp. 3-17, 2001
. [7] D. Abramson, M. Krishnamoorthy, and H. Dang, "Simulated annealing cooling schedules for the school timetabling problem," Asia Pacific Journal of Operational Research, vol. 16, pp. 1-22, 1996.
[8] E. Burke, Y. Bykov, and M. Petrovic, "A multicriteria approach to examination timetabling," in E. Burke and W. Erben (ed.) Practice and Theory of Automated Timetabling (PATAT) III, Springer, Berlin, vol. 2070, pp. 118-131, Jan. 2001.
[9] A. Alkan and E. Ozcan, "Memetic algorithms for timetabling evolutionary computation," in Proc. of the 2003 IEEE Congress on Evol. Comput., vol. 3, pp. 1796-1802, Dec. 2003.
[10] P. Moscato, On Evolution, Search, Optimization, Genetic Algorithms, and Martial Art: Towards Memetic Algorithms, Caltech Concurrent Computation Program, Technical Report, 1989.
[11] P. Moscato and C. Cotta, "A gentle introduction to memetic algorithms," Handbook of Metaheuristics, pp. 105-144, 2003.
[12] O. Rossi - Doria and B. Paechter, A Memetic Algorithm for University Course Timetabling, in Combinatorial Optimisation 2004 Book of Abstracts, Lancaster, UK, Lancaster University, 2004.
[13] J. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.
[14] E. Burke, Y. Bykov, J. Newall, and S. Petrovi, "A time-predefined approach to course imetabling," J. of Operations Research, vol. 13, no. 2, pp. 139-151, 2003.
[15] M. Nandhini and D. S. Kanmani, "A survey of simulated annealing methodology for university course timetabling," Int. J. of Recent Trends in Engineering, vol. 1, no. 2, pp. 255-257, May 2009.
[16] M. Chiarandini, K. Socha, M. Birattari, and O. Rossi - Doria, An Effective Hybrid Approach for the University Course Timetabling Problem, FG Intellektik, FB Informatik, TU Darmstadt, Germany, Tech. Rep AIDA-2003-05, 2003.
[17] A. Schaerf, "Tabu search techniques for large high - school timetabling problems," in Proc. of the 13th National Conf. on Artificial Intelligence, vol. 1, no. 13,pp. 363-368, Aug. 1996.
[18] C. H. Aladag, G. Hocaoglu, and M. A. Basaran, The Effect of Neighborhood Structures on Tabu Search Algorithm in Solving Course Timetabling Problem, Expert Systems with Applications, doi: 10.1016/j.eswa.2009.04.051, 2009.
[19] C. H. Aladag and G. Hocaoglu, "A tabu search algorithm to solve course timetabling problem," Hacettepe J. of Mathematics and Statistics, vol. 36, no. 1, pp. 53-64, Feb. 2007.
[20] R. Alvarez, E. Crespo, and J. M. Tamarit, "Design and implementation of a course scheduling system using tabu search," European J. of Operational Research, vol. 137, no. 3, pp. 512-523, Mar. 2002.
[21] S. Abdullah and H. Turabieh, "Generating university course timetabling using genetic algorithms and local search," in Proc. Int. Conf. on Convergence and Hybrid Information Technolog, vol. 1, pp. 254-260, Nov. 2008.
[22] D. Landa - Silva and J. H. Obit, "Great deluge with nonlinear decay rate for solving course timetabling problems," in Proc. of the 2008 IEEE Conf. on Intelligent Systems (IS 2008), vol. 1, pp. 8-11, Nov. 2008.
[23] D. Landa-Silva and J. Henry Obit, "Evolutionary non - linear great deluge for university course timetabling," in Proc. of the 2009 Int. Conf. on Hybrid Artificial Intelligence Systems (HAIS 2009), Lecture Notes in Artificial Intelligence, Springer, vol. 5572, pp. 269-276, Jun. 2009.
[24] D. Abramson, "Constructing school timetables using simulated annealing: sequential and parallel algorithms," Manag Sci, vol. 37, no. 1, pp. 98-113, Jan. 1991.
[25] F. Melicio and J. Caldeira, "Timetabling implementation aspects by simulated annealing," in Proc. IEEE Systems Science and Systems Engineering, vol. 1, pp. 553-557, 1998.
[26] B. Paechter, A. Cumming, M. G. Norman, and H. Luchian, "Extensions to a memetic timetabling system," in Proc. of the 1st Int. Conf. on Practice and Theory of Automated Timetabling, LNCS 1153, vol. 1153, pp. 251-265, Jul. 1996.
[27] S. Elmohamed, G. Fox, and P. Coddington, "A comparison of annealing techniques for academic course scheduling," in E. Burke and M. Carter (eds.) Practice and Theory of Automated Timetabling (PATAT) II, vol. 1408, pp. 146-166, Springer: Berlin, 1998.
[28] O. Rossi - Doria, M. Sampels, M. Birattari, M. Chiarandini, M. Dorigo, L. Gambardella, J. Knowles, M. Manfrin, M. Mastrolilli, B. Paechter, L. Paquete, and T. Stutzle, "A comparison of the performance of different metaheuristics on the timetabling problem," Lecture Notes in Computer Science 2740, vol. 2740, pp. 329-351, Aug. 2002.
[29] S. Petrovic and Y. Bykov, "A multiobjective optimisation approach for exam timetabling based on rajectories," in E. Burke and P. De Causmaecker (eds.) The Practice and Theory of Automated Timetabling (PATAT) IV, vol. 2740, pp. 181-194, Springer, Berlin, Sep. 2003.
[30] R. Dawkins, The Selfish Gene, Oxford University Press, 1976.
[31] L. Paquete and C. Fonseca, "A study of examination timetabling with multiobjective evolutionary algorithms," in Proc. of Fourth Metaheuristics Int. Conf., MIC 2001, Porto, pp. 149-154, Jul. 2001.
[32] K. Socha and M. Samples, "Ant algorithms for the university course timetabling problem with egard to the state-of-the-art," in Evolutionary Computation in Combinatorial Optimization (EvoCOP 2003), vol. 2611, pp. 334-345, Springer, Berlin, Aug. 2003.
[33] K. Socha, J. Knowles, and M. Samples, "A max - min ant system for the university course timetabling problem," in Proc. of the 3rd Int. Workshop on Ant Algorithms, ANTS 2002, Springer Lecture Notes in Computer Science, vol. 2463, pp. 1-13, Sep. 2002.
[34] http://iridia.ulb.ac.be/supp/IridiaSupp2002-001/index.html
[35] B. McCollum, "University timetabling: bridging the gap between research and practice," in Proc. of the 6th Int Conf. on the Practice and Theory of Automated Timetabling. Lecture Notes in Computer Science, vol. 3867, pp.3-23, 2006.
[36] M. A. Al - Betar, A. T. Khader, and T. A. Gani, "A harmony search algorithm for university course timetabling," in E. Burke and M. Gendreau. (eds.), The Proc. of the 7th Int. Conf. on the Practice and Theory of Automated Timetabling (PATAT 2008), Montreal, Canada, 18-22 Aug. 2008.
[37] S. Abdulla and A. R. Hamdan, "A hybrid approach for university course time tabling," IJCSNS, vol. 8, no. 8, pp. 127-131, Aug. 2008.
[38] D. J. A. Welsh and M. B. Powell, "An upper bound for the chromatic number of a graph and it's application to timetabling problems," Computer J., vol. 10, no. 1, pp. 85-86, 1967.
[39] S. Abdullah, E. K. Burke, and B. Mccollum, "A hybrid evolutionary approach to the university course timetabling problem," in Proc. of the IEEE Congress on Evolutionary Computation, vol. 1, pp. 1764-1768, Sep. 2007.
[40] E. K. Burke, B. McCollum, A. Meisels, S. Petrovic, and R. Qu, "A graph-based hyper-heuristic for educational timetabling problems," European Journal of Operational Research, vol. 176, pp. 177-192, Jan. 2007.