A Micro-Genetic Algorithm Approach for Soft Constraint Satisfaction Problem in University Course Scheduling

A Micro-Genetic Algorithm Approach for Soft Constraint Satisfaction Problem in University Course Scheduling

A university course timetabling problem is a combination of optimization problems. The problems are more challenging when a set of events need to be scheduled in the time slot, to be located to the suitable rooms, which is subjected to several sets of hard and soft constraints. All these constraints...

Full description

Saved in:
Bibliographic Details
Main Author: Abd. Halim, Bohadean @ Bohari
Format: Thesis
Language:eng
eng
Published: 2013
Subjects:
LB2300 Higher Education
QA Mathematics
Online Access:https://etd.uum.edu.my/3856/1/s88485.pdf
https://etd.uum.edu.my/3856/7/s88485.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
id my-uum-etd.3856
record_format uketd_dc
institution Universiti Utara Malaysia
collection UUM ETD
language eng
eng
advisor Yasin, Azman
topic LB2300 Higher Education
QA Mathematics
spellingShingle LB2300 Higher Education
QA Mathematics
Abd. Halim, Bohadean @ Bohari
A Micro-Genetic Algorithm Approach for Soft Constraint Satisfaction Problem in University Course Scheduling
description A university course timetabling problem is a combination of optimization problems. The problems are more challenging when a set of events need to be scheduled in the time slot, to be located to the suitable rooms, which is subjected to several sets of hard and soft constraints. All these constraints that exist as regulations within each resource for the event need to be fulfilled in order to achieve the optimum tasks. In addition, the design of course timetables for universities is a very difficult task because it is a non-deterministic polynomial, (NP) hard problem. This problem can be minimized by using a Micro Genetic Algorithm approach. This approach, encodes a chromosome representation as one of the key elements to ensure the infeasible individual chromosome produced is minimized. Thus, this study proposes an encoding chromosome representation using one-dimensional arrays to improve the Micro Genetic algorithm approach to soft constraint problems in the university course schedule. The research contribution of this study is in developing effective and feasible timetabling software using Micro Genetic Algorithm approach in order to minimize the production of an infeasible individual chromosome compared to the existing optimization algorithm for university course timetabling where UNITAR International University have been used as a data sample. The Micro Genetic Algorithm proposed has been tested in a test comparison with the Standard Genetic algorithm and the Guided Search Genetic algorithm as a benchmark. The results showed that the proposed algorithm is able to generate a minimum number of an infeasible individual chromosome. The result from the experiment also demonstrated that the Micro Genetic Algorithm is capable to produce the best course schedule to the UNITAR International University.
format Thesis
qualification_name masters
qualification_level Master's degree
author Abd. Halim, Bohadean @ Bohari
author_facet Abd. Halim, Bohadean @ Bohari
author_sort Abd. Halim, Bohadean @ Bohari
title A Micro-Genetic Algorithm Approach for Soft Constraint Satisfaction Problem in University Course Scheduling
title_short A Micro-Genetic Algorithm Approach for Soft Constraint Satisfaction Problem in University Course Scheduling
title_full A Micro-Genetic Algorithm Approach for Soft Constraint Satisfaction Problem in University Course Scheduling
title_fullStr A Micro-Genetic Algorithm Approach for Soft Constraint Satisfaction Problem in University Course Scheduling
title_full_unstemmed A Micro-Genetic Algorithm Approach for Soft Constraint Satisfaction Problem in University Course Scheduling
title_sort micro-genetic algorithm approach for soft constraint satisfaction problem in university course scheduling
granting_institution Universiti Utara Malaysia
granting_department Awang Had Salleh Graduate School of Arts & Sciences
publishDate 2013
url https://etd.uum.edu.my/3856/1/s88485.pdf
https://etd.uum.edu.my/3856/7/s88485.pdf
_version_ 1747827655597621248
spelling my-uum-etd.38562022-04-10T02:28:53Z A Micro-Genetic Algorithm Approach for Soft Constraint Satisfaction Problem in University Course Scheduling 2013 Abd. Halim, Bohadean @ Bohari Yasin, Azman Awang Had Salleh Graduate School of Arts & Sciences Awang Had Salleh Graduate School of Arts and Sciences LB2300 Higher Education QA Mathematics A university course timetabling problem is a combination of optimization problems. The problems are more challenging when a set of events need to be scheduled in the time slot, to be located to the suitable rooms, which is subjected to several sets of hard and soft constraints. All these constraints that exist as regulations within each resource for the event need to be fulfilled in order to achieve the optimum tasks. In addition, the design of course timetables for universities is a very difficult task because it is a non-deterministic polynomial, (NP) hard problem. This problem can be minimized by using a Micro Genetic Algorithm approach. This approach, encodes a chromosome representation as one of the key elements to ensure the infeasible individual chromosome produced is minimized. Thus, this study proposes an encoding chromosome representation using one-dimensional arrays to improve the Micro Genetic algorithm approach to soft constraint problems in the university course schedule. The research contribution of this study is in developing effective and feasible timetabling software using Micro Genetic Algorithm approach in order to minimize the production of an infeasible individual chromosome compared to the existing optimization algorithm for university course timetabling where UNITAR International University have been used as a data sample. The Micro Genetic Algorithm proposed has been tested in a test comparison with the Standard Genetic algorithm and the Guided Search Genetic algorithm as a benchmark. The results showed that the proposed algorithm is able to generate a minimum number of an infeasible individual chromosome. The result from the experiment also demonstrated that the Micro Genetic Algorithm is capable to produce the best course schedule to the UNITAR International University. 2013 Thesis https://etd.uum.edu.my/3856/ https://etd.uum.edu.my/3856/1/s88485.pdf text eng public https://etd.uum.edu.my/3856/7/s88485.pdf text eng public masters masters Universiti Utara Malaysia Abdullah, S., and Hamdan, A. R. (2008). A Hybrid Approach for University Course Timetabling, The International Journal of Computer Science and Network Security, Universiti Kebangsaan Malaysia, 8 (8), 127-132. Abu-Lebdeh, G., and Benekohal, R.F. (1999). Convergence Variability and Population Sizing in Micro-Genetic Algorithms, Computer- Aided Civil and Infrastructure Engineering, Vol.14, No.5, pp. 321-334. Abdullah, S., and Turabieh, H. (2008). Generating University Course Timetable using Genetic Algorithm and Local Search. A Proceeding Paper for the 3rd International Conference on Convergence and Hybrid Information Technology 2008, A Publication of IEEE, 254 – 260. Abdullah, S., Turabieh, H., McCollum, B., and Burke, E. K. (2009). An Investigation of Genetic Algorithm and Sequential Local Search Approach for Curriculum-based Course Timetabling Problems, in Proc. Multildisciplinary International Conference on Scheduling: Theory and Applications (MISTA 2009), Dublin, Ireland (2009), pp.727- 731. Adamis, P., and Arapakis, P. (1999). Evolutionary Algorithms in Lecture Timetabling. Proceedings of the 1999 IEEE Congress on Evolutionary Computation (CEC ‘99), IEEE, 1999, 1145-1151. AlSharafat, W.S., and AlSharafat, M.S. (2010)."Adaptive Steady Genetic Algorithm for Scheduling University Exams," in Proc.Inernational Conference on Networking and Information Technology (ICNIT), pp. 70-74. Azimi, Z.N. (2004). Comparison of Metaheuristic Algorithms for Examination Timetabling Problem. Journal of Mathematics and Computing 16, 337–354. Beasley, J.E., and Chu, P.C. (1996).A genetic algorithm for the set covering problem. European Journal of Operation Research, 94(2), 392-404. BI WeiHong, REN HongMin and WU QingBiao (2006). A New Elitist Strategy in Genetic Algorithms. Journal of Zhejiang University (Science Edition), 32-35. Brailsford, S. C., Potts, C. N., and Smith, B. M. (1999). Constraint Satisfaction Problems: Algorithms and Applications. European Journal of Operational Research, 119, 557-581. Burke, E. K., and Newall, J.P. (1999). Multistage Evolutionary Algorithm for the Timetable Problem. IEEE Transactions on Evolutionary Computation, 63-74. Carter, M. W. (1986).A Survey of Practical Applications of Examination Timetabling Algorithms. Operation Research, 34, 193-202. Carter, M. W., Laporte, G., and Lee, S.Y. (1996). Examination Timetabling: Algorithmic Strategies and Applications. Journal of Operational Research Society, 43(3), 373-383. Coello, C. A., and Pulido, G. T. (2001). A Micro-genetic algorithm for multi-objective optimization. In Zitzler, E., Deb, K., Thiele, L., Coello, C. A. C., and Corne, D. W., editors, FirstInternational Conference on Evolutionary Multi-Criterion Optimization, pages 126–140. SpringerVerlag, Berlin. Colorni, A., Dorigo, M., and Maniezzo, V.(1990). Genetic Algorithms – A New Approach to the Timetable Problem. In Lecture Notes in Computer Science – NATO ASI Series, F(82), 235-239. Davis F. D. (1989), Perceived usefulness, perceived ease of use, and user acceptance of Information Technology.: MIS Quarterly (13 : 3). Eiben, A.E., Hinterding, R., and Michalewicz,Z. (1999) “Parameter control in evolutionary algorithms,” IEEE Trans. Evol. Comput., vol. 3, no. 2, pp. 124–141. Filho, G. R., and Lorena, L. A. N. (2000). A Constructive Evolutionary Approach To School Timetabling. www.lac.inpe.br/~marcos/arsig2/CGA-timet-EVOCOP.pdf Garey, M. R., and Johnson, D. S. Computers and Intractability.(1979).A guide to NP- Completeness. W.H. Freeman and Company, San Francisco, 179. Gen, M., and Cheng, R. (1994). Evolution Program for Resource Constrained Project Scheduling Problem. In Proceedings of the first IEEE conference on evolutionary computation, 736-741. Goldberg, D. E. (1989).Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, Boston, MA. Goldberg, D. E. (1989).Sizing populations for serial and parallel genetic algorithms, in Proceedings of the 3rd International Conference on Genetic Algorithms, Fairfax, V.I., 70–79. Golub, M., Kasapovic, S. (2002). Scheduling Multiprocessor Tasks with Genetic Algorithms. Proceeding of the IASTED International Conference Allplied Infomatics, Insbruck, Austria, 273-278. Gy’ori, S. Petres, Z., and Varkonyi-Koczy, A. R. (2001). Genetic Algorithms in Timetabling. A New Approach. MFT Periodika 2001-07. Hungarian Society of IFSA, Hungary. Heitkoetter, J., and Beasley, D. (2001). The Hitch-Hiker's Guide to Evolutionary Computation: A list of Frequently Asked Questions (FAQ). Jat, S. N and Yang, S. (2009)“A guided search genetic algorithm for the university course timetabling problem,” in Proc. 4th Multidisciplinary Int. Conf. Scheduling: Theory Appl., pp. 180–191. Jat, S. N and Yang, S. (2011). "Genetic Algorithms and Local Search Strategies for University Course Timetabling," IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol. 41, no. 1, pp.93-106 Joshua D. Knowles and David W. Corne. Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy. Evolutionary Computation,8(2):149 172, 2000. Karova, M. (2004). Solving Timetabling Problems Using Genetic Algorithms. The proceeding of IEEE of the 27th International Spring Seminar on Electronics Technology, Bankja, Bulgaria. Kazarlis, S.A., Papadakis, S.E., Theocharis, J.B. and Petridis, V. (2001). Microgenetic algorithms as generalized hill-climbing operators for GA Optimization. IEEE Transaction on Evolutionary Computation, 5(3): 204.217. Khan, N. (2003). Population sizing in genetic and evolutionary algorithms. Chocago: University of Illinois at Urbana-Champaign. Krishnakumar, K. (1989). Micro-genetic algorithms for stationary and non-stationary function optimization. SPIE, Intelligent Control and Adaptive Systems, pp. 289-296. Krzysztof Socha, Joshua Knowles and Michael Sampels (2002). A MAX-MIN Ant System for the University Course Timetabling Problem. Proceedings of the Third International Workshop on Ant Algorithms, 1-13, September 12-14. Kwan, A.S.K., Kwan, R.S.K., and Wren, A. (1997). Driver scheduling using genetic algorithms with embedded combinatorial traits (Technical Report 97.30). United Kingdom: University of Leeds. Lai Lien-Fu, Hsueh Nien-Lin, Huang Liang-Tsung and Chen Tien-Chun (2006), An Artificial Intelligence Approach to Course Timetabling, a publication from the Proceedings of the 18th IEEE International Conference on Tools and Artificial Intelligence (ICTAI’06), IEEE Computer Society, 0-7695-2728- 0/06. Lalescu, L., and Badica, C. (2003). Timetabling Experiments Using Genetic Algorithms. Timetabling Experiments Using Genetic Algorithms, prezentata la TAINN'03, Canakkale, Turcia, 2003.Retrieved February, 2005, from http://software.ucv.ro/Cercetare/Inginerie_Software/ inginerie_software.html. Michalewicz, Z. (1994). Genetic Algorithms + Data Structures=Evolution Programs (2nd ed.), Springer-Verlag. Najdpour, N., Feizi-Derakhshi, M.-R. (2010), A two-phase evolutionary algorithm for the university course timetabling problem, Software Technology and Engineering (ICSTE), 2010 2ndInternational Conference on ,2, 266-271. Newall, J. P. (1999). Hybrid Methods for Automated Timetabling, PhD Thesis, Department of Computer Science, University of Nottingham. Nia, M.B., and Alipouri, Y. (2009).Speeding Up the Genetic Algorithm Convergence Using Sequential Mutation and Circular Gene Methods, Intelligent Systems Design and Applications, ISDA '09. Ninth International Conference on , vol., no., pp.31-36, Nov. 30 2009-Dec. 2 2009. Nielson, J. (2006), Quantitative Studies : How many users to test Alertbox, citedon 3rd April 2009, fromhttp://www.useit.com/alertbox/quantitative_ testing.html. Paechter, B. Cumming, A. Norman, L., and Luchian, H.(2006). Extensions to a Memetic Timetabling System. In E.K Burke and PM Rosse, Eds., Proceedings of the 1st Inter. Conf. on the Practice and Theory of Automated Timetabling. Paechter, B., Cumming, A., Luchian, H., and Petriuc, M. (1994).Two Solutions to the General Timetable Problem Using Evolutionary Methods. IEEE World Congress on Computational Intelligence, 300-305. Paechter, B., Rossi-Doria, O., Blum, C., Knowles J., Sampels, M., and Socha, K.(2002). A Local Search for the Timetabling Problem, PATAT 2002 Proceedings of the 4th international conference on the Practice And Theory of Automated Timetabling, Gent, Belgium, 124-127. Perzina, R. (2007)."Solving Multicriteria University Timetabling Problem by a Self-adaptive Genetic Algorithm with Minimal Perturbation", ;in Proc. IRI, pp. 98- 103. Rich, D.C. (1996). A Smart Genetic Algorithm for University Timetabling, In: E. Burke, P. Ross (Eds.): PATAT’95, LNCS 1153, Springer-Verlag, 1996, 181-197. Sapru,V., Reddy, K., and Sivaselvan, B.(2010). "Time Table Scheduling Using Genetic Algorithms Employing Guided Mutation," in Proc. IEEE International Conference on Computational Intelligence and Computing Research (ICCIC), pp. 1-4. Sigl, B., Golub, M., Mornar, V. (2003). Solving Timetable Scheduling Problem Using Genetic Algorithms, Information Technology Interfaces, 2003. ITI 2003. Proceedings of the 25th International Conference, 519- 524. Selvi, R., Muthu, and Rajaram, R. (2011). Multiobjective optimization to provide service guarantees for window-constrained scheduling using Micro-genetic algorithm. Proceedings of the 2011 International Conference on Communication, 457-461. Vahid Lotfi, and Robert Cerveney, (1991). A Final Exam Scheduling Package. J. Opl Res. Soc. Vol. 42, 3, 205–216. Vaishnavi, V., and Kuechler, B. (2004) . Design Research in Information Systems, AISWorldNet, http://www.isworld.org/Researchdesign/drisISworld.htm, 20February 2004, last updated 5 June 2005 (accessed 15 October, 2005). Valouxis, C., and Housos, E. (2000). Hybrid Optimization Techniques for the Workshift and Rest Assignment of Nursing Personnel. Artificial Intelligence in Medicine, 20, 155-175. White, G. W., and Chan, P. W. (2002) . Towards Construction of Optimal Examination Timetables. INFOR 17, 219-229. Xie, S.T., and Pan, L.T. (2010). Selection of Machining Parameters Using Genetic Algorithms. The 5th International Conference on Computer & Education, Hefei, China. August,24-27. YakhnoT., and Tekin, E. (2002). Application of Constraint Hierarchy to Timetabling Problems, Proceedings of EurAsia-ICT 002, Springer-Verlag. Yang, H., and Luo, D. (2009). Optimal Regional Bus Timetables Using Improved Genetic Algorithm. 2nd International Conference on Intelligent Computation Technology and Automation. Yang, Y., and Petrovic, S. (2004). A Novel Similarity Measure for Heuristic Selection in Examination Timetabling. In: Burke, E.K., Trick, M. (Eds.), Selected Papers from the 5th International Conference on the Theory and Practice of Automated Timetabling (PATAT 2004) – The Theory and Practice of Automated Timetabling V, Lecture Notes in Computer Science, vol. 3616. Springer, Berlin, 247–269.

Similar Items