Untitled Document
   
You are from : ( )  
     
Untitled Document
Untitled Document
 

International Journal of Information Technology & Computer Science ( IJITCS )

Abstract :

The course distribution has always been a difficult work at many universities and need a complex system which operates under multiple constraints, including teacher knowledge, preferences and others. Therefore, generating a satisfactory solution that meets the needs of all related factors is not an easy task and it becomes an extremely difficult to obtain a strategy that is inclusive of all critical issues in distributing courses. This paper presented the integration of two different techniques: Genetic Algorithm and Asynchronous Cooperative Parallel Search, the resulting algorithm is referred as Asynchronous Cooperative Parallel Genetic Algorithm or ACoPGA. The integration between the two techniques was very promising in terms of the gains in performance, scalability and reducing the large execution times that are associated with simple genetic algorithms. The computational results indicated that the proposed algorithm yields high satisfied solutions in reasonable  computing time when compared to the traditional GA.

Keywords :

Asynchronous Cooperative Search, Genetic Algorithm, Parallel implementation, Teacher Assignment problem.

References :

[1] A.Carvalho, ``A Cooperative Coevolutionary Genetic Algorithm for Learning Bayesian Network Structures,'' David Cheriton School of Computer Science University of Waterloo, July 12–16, 2011.
[2] A.Gunawan and K. Ng, ``Solving the Teacher Assignment Problem by Two Metaheuristics,'' Singapore Management University and National University of Singapore, pp. 73-14, 2011.
[3] A.Gunawan and K. M. Ng, ``A Genetic Algorithm for the Teacher Assignment Problem for a University in Indonesia,'' National University of Singapore Information and Management Sciences, 2005.
[4] D. Beasle and D. Bull, ``An Overview of Genetic Algorithms Part Fundamentals,'' UK: University Committee on Computing, 1993.
[5] D. Gong, Y. Zhou and T.Li, ``Cooperative Interactive Genetic Algorithm Based on User’s Preference,'' Int. J. Inform. Technology , vol. 11, no. 10, p. 10, 2005.
[6] E. Alba and J.M. Troya, ``Analyzing synchronous and asynchronous parallel distributed genetic algorithms,'' Future Generation Comput. Syst., no. 17, 2001.
[7] E. Cantú-Paz, ``A Survey of Parallel Genetic Algorithms,'' Department of Computer Science and Illinois Genetic Algorithms Laboratory University of Illinois at Urbana-Champaign, 2000.
[8] J. Majumdar and A. Bhunia, ``Penalty approaches for Assignment Problem with single side constraint via Genetic Algorithms,'' India: Journal of Mathematical Modelling and Application, 2010.
[9] K. Bryan and Y. Shibberu, ``Penalty Functions and Constrained Optimization,'' p. 6.
[10] K. Kazunori, M. Himshi and I.Masaaki, ``Asynchronous Parallel Distributed GA using Elite Server,''Evolutionary Computation, 2003. CEC '03, Vol.4 , Dec 8-12 2003.
[11] K. Kojima, M. Ishigame, G. Chakraborty, H. Hatsuo, and S. Makino, ``Asynchronous Parallel Distributed Genetic Algorithm with Elite Migration,'' World Academy of Science, Engineering and Technology, 2008.
[12] M. Nowostawski and, R. Poli,``Parallel Genetic Algorithm Taxonomy,'' Proceedings of Third International Conference on Knowledge-based Intelligent Information Engineering Systems KES’99, May 13, 1999.
[13] M. Ohki, S. Uneme and H. Kawano, ``Parallel Processing of Cooperative Genetic Algorithm for Nurse Scheduling,'' Intelligent Systems, 2008. IS '08. 4th International IEEE Conference , p. Page(s): 10-36 - 10- 41,2008.
[14] R. Eriksson and B. Olsson, ``cooperartive coevolution in inventory control optimisation,'' Department of computer science,university of skovde, 17 July 1997.
[15] R. Chakraborty, ``Foundamentals of Genetic Algorithms,'' June 01 , 2010.
[16] R. Shonkwiler, ``Parallel Genetic Algorithms,'' Atlanta: 1993. A. [17 ] R.E. Smith, S. Forrest and A.S. Perelson, ``Searching for Diverse, Cooperative Populations with Genetic Algorithms,'' 1993.
[18] R. Venkateswaran, Z.Obradovic and C.S. Reghavendra, ``Cooperative Genetic Algorithm for Optimization Problem in Distributed Computer System,'' Washington state university, 1994.
[19] Y. Guan, B. Xu and K.R. Leung, ``Parallel Genetic Algorithms with Schema Migration,'' 2010.
[20] Y.Z. Wang, ``An application of genetic algorithm method for teacher assignment problems,'' Department of business administration, far east college, Tainan, Taiwan, ROC, p. 295, 2002.
[21] C. Blum, ``Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison,'' ACM Computing Surveys, September 2003.
[22] S.N.Sivanandam and S.N.Deepa, ``Introduction to Genetic Algorithms,'' New York: Springer Berlin Heidelberg, 2008.
[23] J. Puchinger and G.R. Raidl, ``Combining Metaheuristics and Exact Algorithms in Combinatorial Optimization,'' Artificial Intelligence and Knowledge Engineering Applications, 2005.
[24] E. Alba, ``Parallel Metaheuristics,'' Canada: John Wiley and Sons, 2005.
[25] R. Alvarez, F. Parreno, J.Tamarit ," A Tabu Search algorithm for assigning teachers to courses," Departamento de Estadística e Investigación Operativa , Universitat de Valencia, Spain ,2002
[26] S. Tongchim, " Coarse-Grained Parallel Genetic Algorithm for Solving the Timetable Problem ," Department of Computer Engineering, Faculty of Engineering, Chulalongkorn University, Bangkok 10330, Thailand.
[27] J. Thizy, P. Mercier ,"An interactive course assignment system," University of Ottawa, Canada
[28] TB Cooper and JH Kingston, “The Complexity of Timetable Construction Problems,” in the Practice and Theory of Automated Timetabling, ed. EK Burke and P Ross, pp. 283-295, Springer-Verlag (Lecture Notes in Computer Science), 1996. Basser Department of Computer Science, University of Sydney, Australia
[29] Burke, E. K. and Petrovic, S., Recent research directions in automated timetabling, European Journal of Operational Research, Vol. 140, No. 2, pp. 266-280, 2002.
[30] Kwan, R. S. K., Bus and train driver scheduling, in Leung, J. (Eds.), Handbook of Scheduling: Algorithms, Models and Performance, Boca Raton: CRC Press, Chapters 51, 2004.
[31] Schaerf, A. and Meisels, A, Solving employee timetabling problems by generalized local search, in Lamma, E. and Mello, P. (Eds.), AI*IA 99: Advances in Artificial Intelligence: 6th Congress of the Italian Association for Artificial Intelligence, Lecture Notes in Computer Science, Springer- Verlag, Berlin, Vol. 1792, pp. 380-389, 2000.
[32] Bellanti, F., Carello, G., Croce, F. D. and Tadei, R., A greedy-based neighborhood search approachto a nurse rostering problem, European Journal of Operational Research, Vol. 153, No. 1, pp. 28-40,2004.
[33] Burke, E. K., de Causmaecker, P., Berghe, G. V. and Landeghem, H. V., The state of the art of nurse rostering, Journal of Scheduling, Vol. 7, No. 6, pp. 441-499, 2004.
[34] Gunawan, A. and Lau, H. C., Master physician scheduling problem, the proceedings of the 4th Multidisciplinary International Scheduling Conference, 10-12 August 2009, Dublin, Ireland.
[35] Sch¨onberger, J., Mattfeld, D. C. and Kopfer, H, Memetic algorithm timetabling for non-commercial sport leagues, European Journal of Operational Research, Vol. 153, No. 1, pp. 102-116, 2004.
[36] D. de Werra, “An introduction to timetabling”. European Journal of Operational Research, 19:151-162, 1985
[37] Carter, M.W. and Laporte, G., Recent developments in practical course timetabling, in Burke, E. andCarter, M. (Eds.), Practice and Theory of Automated Timetabling II, Lecture Notes in ComputerScience, Springer-Verlag, Berlin, Vol. 1408, pp. 3-19, 1998.
[38] Y. Wang, Y. Cheng &T.Chang, S.JEN, "On the Application of Data Mining Technique and Genetic Algorithm to an Automatic Course Scheduling System," p. 400-405, 2008.
[39] Klicos, Nicholas; Winzeler, John; York, Daniel; Tai, Brian; Bailey, Reid, "Developing an algorithm-based course scheduling tool," Proc. 2008 IEEE Syst. Inform., p. 112-117, 2008.
[40] H. Alfaro & G. Teran, "Solving the Classroom Assignment Problem With Simulated Annealing," p. 3703-3708, 1998.
[41] H. Alfaro, J. Minero&G.Alanis, N. Leal, "USING SIMULATED ANNEALING TO SOLVE THE CLASSROOM ASSIGNMENT PROBLEM," p. 370-377, 1996.
[42] L. Yong-xian, H. Xiang-pei&L.Jun, "A Heuristic Search Algorithm for Vehicle Routing Problems and the GIS-based Vehicle Routing System Onboard," pp. 94–99.
[43] H. Bui, S. Venkatesh&D.Kieronska, "A Multi-agent Incremental Negotiation Scheme for Meetings Scheduling," pp. 175–180.
[44] A. Alsheddy, " Empowerment Scheduling: A Multi-objective Optimization Approach Using Guided Local Search " Ph.D. thesis, Dept. comp. scien., Essex Univ., United Kingdom, 2011.
[45]A. Wren, “Scheduling, Timetabling and Rostering – A Special Relationship?,”, in The Practice and Theory of Automated Timetabling: Selected Papers from the 1st Int'l Conf. on the Practice and Theory of Automated Timetabling, Burke, E., Ross, P. (Eds.) Springer Lecture Notes in Computer Science Series, Vol. 1153, 1996, pp. 46-75.\

Untitled Document
     
Untitled Document
   
  Copyright © 2013 IJITCS.  All rights reserved. IISRC® is a registered trademark of IJITCS Properties.