Skip to content
2000
  1. Home
  2. A-Z Publications
  3. The Chinese Journal of Artificial Intelligence
  4. Volume 1, Issue 2
  5. Article
Volume 1, Issue 2
  • ISSN: 2666-7827
  • E-ISSN: 2666-7835

Abstract

Background

Examination Timetabling Problem that tries to find an optimal examination schedule for schools, colleges, and universities, is a well-known NP-hard problem. This paper presents a Genetic Algorithm variant approach to solve a specific examination timetabling problem common in Japanese colleges and universities.

Methods

The proposed algorithm uses a direct chromosome representation Genetic Algorithm and implements constraint-based initialization and constraint-based crossover operations to satisfy the hard and soft constraints. An island model with varying crossover and mutation probabilities and an improvement approach called pre-training are applied to the algorithm to further improve the result quality.

Results

The proposed model is tested on synthetic as well as real datasets obtained from Sophia University, Japan and shows acceptable results. The algorithm was fine-tuned with different penalty point combinations and improvement combinations.

Conclusion

The comparison results support the idea that the initial population pre-training and the island model are effective approaches to improve the result quality of the proposed model. Although the current island model used only four islands, incorporating a greater number of islands, and some other diversity maintenance approaches such as memetic structures are expected to further improve the diversity and the result quality of the proposed algorithm on large scale problems.

© 2022 Bentham Science Publishers
Loading

Article metrics loading...

/content/journals/cjai/10.2174/2666782701666220610145137
2022-08-25
2025-01-19

  • From This Site

    /content/journals/cjai/10.2174/2666782701666220610145137
    dcterms_title,dcterms_subject,pub_keyword
    -contentType:Contributor -contentType:Concept -contentType:Institution
    10
    5
Loading full text...

Full text loading...

References

  1. QuR. BurkeE. McCollumB. MerlotL. LeeS. A survey of search methodologies and automated system development for examina-tion timetabling.J. Sched.2008121558910.1007/s10951‑008‑0077‑5
     [Google Scholar]
  2. CarterM. LaporteG. Recent developments in practical examination time-tabling.International conference on the practice and theory of automated timetablingSpringer: Berlin19951153121
     [Google Scholar]
  3. ThompsonJ. DowslandK. Variants of simulated annealing for the examination timetabling problem.Ann. Oper. Res.199663110512810.1007/BF02601641
     [Google Scholar]
  4. ThompsonJ. DowslandK. A robust simulated annealing based examination timetabling system.Comput. Oper. Res.1998257-863764810.1016/S0305‑0548(97)00101‑9
     [Google Scholar]
  5. Di GasperoL. SchaerfA. Tabu search techniques for examination timetabling.International Conference on the Practice and Theory of Automated TimetablingSpringer: Berlin2020104117
     [Google Scholar]
  6. AbdullahS. AhmadiS. BurkeE. DrorM. McCollumB. A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem.J. Oper. Res. Soc.200758111494150210.1057/palgrave.jors.2602258
     [Google Scholar]
  7. Naji AzimiZ. Hybrid heuristics for examination timetabling problem.Appl. Math. Comput.2005163270573310.1016/j.amc.2003.10.061
     [Google Scholar]
  8. van LaarhovenP. AartsE. Simulated annealing. Simulated annealing: Theory and applications.DordrechtSpringer198771510.1007/978‑94‑015‑7744‑1_2
     [Google Scholar]
  9. TusonA. GloverF. LagunaM. Tabu search.J. Oper. Res. Soc.199950110610.2307/3010402
     [Google Scholar]
  10. GalletlyJ.E. An overview of genetic algorithms.Kybernetes199221263010.1108/eb005943
     [Google Scholar]
  11. DorigoM. GambardellaL.M. Ant colony system: A cooperative learning approach to the traveling salesman problem.IEEE Trans. Evol. Comput.199711536610.1109/4235.585892
     [Google Scholar]
  12. EleyM. Ant algorithms for the exam timetabling problemInternational Conference on the Practice and Theory of Automated TimetablingSpringer: Berlin20063867364382
     [Google Scholar]
  13. MandalA.K. KaharM.N.M. Solving examination timetabling problem using partial exam assignment with great deluge algorithm.Inter-national Conference on Computer, Communications, and Control Technology2015I4CT53053410.1109/I4CT.2015.7219635
     [Google Scholar]
  14. SongY. WanF. ChenX. An improved genetic algorithm for numerical function optimization.Appl. Intell.20194951880190210.1007/s10489‑018‑1370‑4
     [Google Scholar]
  15. RozaimeeA. ShafeeA. HadiN. MohamedM. A framework for university’s final exam timetable allocation using genetic algorithm.World Appl. Sci. J.201735712101215
     [Google Scholar]
  16. ShatnawiA. FraiwanM. Al-QahtaniH.S. Exam scheduling: A case study.2017 Ninth International Conference on Advanced Compu-tational Intelligence (ICACI)201713714210.1109/ICACI.2017.7974498
     [Google Scholar]
  17. DenerM. CalpM.H. olving the exam scheduling problems in central exams with genetic algorithms. arXiv preprint2019190201360
     [Google Scholar]
  18. EzikeJ.O.J. OyeleyeC.A. OlabiyisiS.O. OmidioraE.O. Development of a hybrid tabu search and genetic algorithms for the exami-nation timetabling problem.J. Sci. Technol. Res.20202312710.37933/nipes/2.3.2020.14
     [Google Scholar]
  19. NgoS. JaafarJ. AzizI. NguyenG. BuiA. Genetic algorithm for solving multi-objective optimization in examination timetabling problem.Int. J. Emerging Technol. Learning20211611410.3991/ijet.v16i11.21017
     [Google Scholar]
  20. KurdiM. An effective new island model genetic algorithm for job shop scheduling problem.Comput. Oper. Res.20166713214210.1016/j.cor.2015.10.005
     [Google Scholar]
  21. Palomo-RomeroJ.M. Salas-MoreraL. García-HernándezL. An island model genetic algorithm for unequal area facility layout prob-lems.Expert Syst. Appl.20176815116210.1016/j.eswa.2016.10.004
     [Google Scholar]
  22. García-HernándezL. Salas-MoreraL. Carmona-MuñozC. Garcia-HernandezJ.A. Salcedo-SanzS. A novel island model based on coral reefs optimization algorithm for solving the unequal area facility layout problem.Eng. Appl. Artif. Intell.20208910344510.1016/j.engappai.2019.103445
     [Google Scholar]
  23. GozaliA. KurniawanB. WengW. FujimuraS. Solving university course timetabling problem using localized island model genetic algorithm with dual dynamic migration policy.IEEJ Trans. Electr. Electron. Eng.201915338940010.1002/tee.23067
     [Google Scholar]
  24. RezaeipanahA. MatooriS.S. AhmadiG. A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search.Appl. Intell.202151146749210.1007/s10489‑020‑01833‑x
     [Google Scholar]
  25. LeiteN. FernandesC.M. MelicioF. RosaA.C. A cellular memetic algorithm for the examination timetabling problem.Comput. Oper. Res.20189411813810.1016/j.cor.2018.02.009
     [Google Scholar]
  26. MillerB.L. GoldbergD.E. Genetic algorithms, tournament selection, and the effects of noise.Complex Syst.199593193212
     [Google Scholar]
  27. YadavS.L. SohalA.A. Comparative study of different selection techniques in genetic algorithm.Int. J. Eng. Sci. Mathematics201763174180
     [Google Scholar]
  28. DuH. WangZ. ZhanW. GuoJ. Elitism and distance strategy for selection of evolutionary algorithms.IEEE Access20186445314454110.1109/ACCESS.2018.2861760
     [Google Scholar]
  29. ReedP.M. MinskerB.S. GoldbergD.E. The practitioner’s role in competent search and optimization using genetic algorithms.Bridging the Gap.Meeting the World's Water and Environmental Resources Challenges200119
     [Google Scholar]
  30. AhnC.W. RamakrishnaR.S. Elitism-based compact genetic algorithms.IEEE Trans. Evol. Comput.20037436738510.1109/TEVC.2003.814633
     [Google Scholar]
  31. SchoenauerM. XanthakisS. Constrained GA optimization.Proc. 5th International Conference on Genetic AlgorithmsMorgan Kaufmann1993573580
     [Google Scholar]
  32. MengQ. WuJ. EllisJ. KennedyP.J. Dynamic island model based on spectral clustering in genetic algorithm2017 International Joint Conference on Neural Networks (IJCNN)20171724173110.1109/IJCNN.2017.7966059
     [Google Scholar]
  33. LiC.C. LinC.H. LiuJ.C. Parallel genetic algorithms on the graphics processing units using island model and simulated annealing.Adv. Mech. Eng.20179711410.1177/1687814017707413
     [Google Scholar]
  34. Cantu-PazE. Efficient and accurate parallel genetic algorithms.NewyorkSpringer Science & Business Media2000
     [Google Scholar]
  35. WhitleyD. RanaS. HeckendornR.B. The island model genetic algorithm: On separability, population size and convergence.CIT J. Comput. Inf. Technol.1999713347
     [Google Scholar]
  36. GozaliA.A. FujimuraS. DM-LIMGA: Dual migration localized island model genetic algorithm—a better diversity preserver island model.Evol. Intell.201912452753910.1007/s12065‑019‑00253‑2
     [Google Scholar]
  37. SunX. ChouP. WuC.C. ChenL.R. Quality-oriented study on mapping island model genetic algorithm onto CUDA GPU.Symmetry (Basel)201911331810.3390/sym11030318
     [Google Scholar]
  38. GongG. DengQ. ChiongR. GongX. HuangH. An effective memetic algorithm for multi-objective job-shop scheduling.Knowl. Base. Syst.201918210484010.1016/j.knosys.2019.07.011
     [Google Scholar]
  39. HornbyG.S. ALPS: The age-layered population structure for reducing the problem of premature convergence.Proceedings of the 8th annual conference on Genetic and evolutionary computation200681582210.1145/1143997.1144142
     [Google Scholar]
  40. HutterM. LeggS. Fitness uniform optimization.IEEE Trans. Evol. Comput.200610556858910.1109/TEVC.2005.863127
     [Google Scholar]
  41. Souad. “A survey of particle swarm optimization techniques for solving university examination timetabling problem.Artif. Intell. Rev.201544453754610.1007/s10462‑015‑9437‑7
     [Google Scholar]
  42. MuklasonA. BwananesiaP.C. S. H.Y.T. AngrestiN.D. SupoyoV.A. Automated examination timetabling optimization using greedy-late acceptance-hyperheuristic algorithm2018 International Conference on Electrical Engineering and Computer Science (ICECOS)201820120610.1109/ICECOS.2018.8605194
     [Google Scholar]
/content/journals/cjai/10.2174/2666782701666220610145137
Loading
A Variant Genetic Algorithm for a Specific Examination Timetabling Problem in a Japanese University
Chin J Arti Intel 1, e100622205848 (2022); https://doi.org/10.2174/2666782701666220610145137
/content/journals/cjai/10.2174/2666782701666220610145137
/content/journals/cjai/10.2174/2666782701666220610145137
Loading

Data & Media loading...

Supplements

file format download Download

  • Article Type:     Research Article
Keyword(s): direct chromosome representation; evolutionary algorithms; Examination timetabling problem; genetic algorithm; Island model; meta-heuristic algorithms; parallel genetic algorithm

Most Cited Most Cited RSS feed

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error
Please enter a valid_number test