CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Trans Genetic Coloring Approach for Timetabling Problem

Published on None 2011 by Mina G. Asham, Moataz M. Soliman, Rabie A. Ramadan
journal_cover_thumbnail

Artificial Intelligence Techniques - Novel Approaches & Practical Applications
Foundation of Computer Science USA
AIT - Number 1
None 2011
Authors: Mina G. Asham, Moataz M. Soliman, Rabie A. Ramadan
ff0542a7-a529-41f2-96d9-cc004db74ff7

Mina G. Asham, Moataz M. Soliman, Rabie A. Ramadan . Trans Genetic Coloring Approach for Timetabling Problem. Artificial Intelligence Techniques - Novel Approaches & Practical Applications. AIT, 1 (None 2011), 17-25.

@article{
author = { Mina G. Asham, Moataz M. Soliman, Rabie A. Ramadan },
title = { Trans Genetic Coloring Approach for Timetabling Problem },
journal = { Artificial Intelligence Techniques - Novel Approaches & Practical Applications },
issue_date = { None 2011 },
volume = { AIT },
number = { 1 },
month = { None },
year = { 2011 },
issn = 0975-8887,
pages = { 17-25 },
numpages = 9,
url = { /specialissues/ait/number1/2824-205/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Special Issue Article
%1 Artificial Intelligence Techniques - Novel Approaches & Practical Applications
%A Mina G. Asham
%A Moataz M. Soliman
%A Rabie A. Ramadan
%T Trans Genetic Coloring Approach for Timetabling Problem
%J Artificial Intelligence Techniques - Novel Approaches & Practical Applications
%@ 0975-8887
%V AIT
%N 1
%P 17-25
%D 2011
%I International Journal of Computer Applications
Abstract

Timetable problem is well known problem and is extensively studied in the literature. There are many variations of the problem based on the required hard and soft constraints to be satisfied. One variation of the problem is the exam schedule which is similar to the course schedule with different constraints. In this paper, we propose new solution for course and exam schedule problems base d on University Credit Hour System (CHS) requirements. Our solution utilizes Graph Coloring (GC) and Genetic Algorithms (GA) as a hybrid solution. The test cases used in this paper show the tradeoff between the running time of the proposed algorithm and its fitness performance compared to GA and GC algorithms.

References
  1. A. Chaudhuri and D. Kajal,‎“Fuzzy‎Genetic‎Heuristic‎for‎University‎Course‎Timetable‎Problem,”‎Int.‎J.‎Advance.‎Soft‎Computing.‎Applications, Vol. 2, No. 1, March 2010 ISSN 2074-8523; 2010.
  2. B.‎ Paechter,‎ A.‎ Cumming,‎M.‎ G.‎ Norman‎ and‎ H.‎ Luchian,‎ “Extensions‎to‎ a‎ Memetic‎ Timetabling‎ System”,‎ Proceedings‎ of‎ the‎ 1st‎ In ternational Confe- rence on the Practice and Theory of Automated Timetabling, (1995)
  3. B.‎Sigl,‎M.‎Golub,‎and‎V.‎Mornar,‎“Solving‎Timetable‎Scheduling‎Problem‎Using‎Genetic‎Algorithms”,‎25th‎International‎Conference Information Tech- nology Interfaces, Cavtat, Croatia, (2003).
  4. Burke‎ E.K.,‎ Elliman‎ D.G.‎ and‎ Weare‎ R.F.‎ (1993)‎ “A‎ University‎ Timetabling‎ System‎ Based‎ on‎ Graph‎ Colouring‎ and‎ Constraint‎ Manip ulation”,‎ in‎ the‎ Journal of Research on Computing in Education. Vol. 26.issue 4.
  5. C.‎Marco,‎B.‎Mauro‎ and‎ S.‎ Krzysztof,‎ “An‎ Effective‎ Hybrid‎ Algorithm‎ forUniversity‎ Course‎ Timetabling”,‎ Journal‎ of‎ Scheduling, Vol.9, No.5, (2006), pp.403-432.
  6. C.‎Reeves,‎“Genetic‎Algorithms”,‎Modern‎Heuristic‎Techniques‎for‎Combinatorial Problems, V. J. Rayward-Smith (Editors), McGraw-Hill International, UK, (1995), pp.151-196.
  7. D.‎ Corne,‎ H.‎ S.‎ Fang‎ and‎ C.‎ Mellish,‎ “Solving‎ the‎ Modular‎ Exam‎ Scheduling‎ Problem‎ with‎ Genetic‎ Algorithms”,‎ Proceedings‎ of‎ the 6th International Conference of Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, Edinburgh, (1993).
  8. D. De Werra, ‎“An‎introduction‎to‎Timetabling”, ‎European‎Journal‎of‎Operations‎Research, ‎Vol.19,‎ (1985),‎pp.151-162.
  9. D. Dubois and H. Prade, Possibility Theory: an Approach to Computerized Processing of Uncertainty, New York, (1988).
  10. E.‎K.‎Bruke‎and‎J.‎ P.‎Newall,‎ “Solving‎Examination‎Timetabling‎Problems‎through‎Adaptation‎of‎Heuristic‎Orderings”,‎Annals‎of‎Operations‎Research,‎Vol.129, (2004), pp.107-134.
  11. E.‎K.‎Bruke‎and‎S.‎Petrovic,‎“Recent‎Research‎directions‎in‎Automated‎Timetabling”,‎European‎Journal‎of‎Operational‎Research, Vol.140, No.2, (2002), pp.266-280.
  12. E.‎K.‎Burke‎and‎J.‎P.‎Newall,‎“A‎New‎Adaptive‎Heuristic‎Framework‎for‎Examination‎Timetabling‎Problems”,‎University‎of‎N ottingham, Working Group on Automated Timetabling, TR–2002-1, (2002).
  13. E. K. Burke,‎ B.‎ McCollum‎ and‎ A.‎ Meisels,‎ “A‎ Graph‎ based‎ Hyper‎ Heuristic‎ for‎ Educational‎ Timetabling‎ Problems”,‎ European‎ Journal‎ of‎ O perational Research, Vol.176, No.1, (2007), pp.177-192.
  14. E.K. Burke, D. Elliman, R. Weare, A genetic algorithm based university timetabling system, in: Proceedings of the 2nd East-West International Confe- rence on Computers in Education, Crimea, Ukraine, 19th–23rd September 1994, vol. 1, (1994), pp. 35–40.
  15. Even, S. Itai, A., & Shamir, A., On the Complexity of timetabling and multicommodity flow problems, SIAM Journal of Computation, Vol.5, No.4, 1976, pp.691-703.
  16. G.‎Kendall‎and‎N.‎M.‎Hussain,‎“A‎Tabu‎Search‎Hyper‎Heuristic‎Approach‎to‎the‎Examination‎Timetabling‎Problem‎at‎the‎MARA‎University of Technology”,‎ Lecture‎Notes‎in‎Computer‎Science,‎Springer‎Verlag, Vol.3616, (2005), pp.270- 293.
  17. G.‎White,‎B.‎Xie‎and‎S.‎Zonjic,‎“Using‎Tabu‎Search‎with‎Longer‎Term‎Memory‎and‎Relaxation‎to‎create‎Examination‎Timetables”,‎European‎Journal‎of‎‎Operational Research, Vol.153, No.16, (2004), pp.80-91.
  18. H. Asmuni, E. K. Burke and‎ J.‎Garibaldi, ‎“Fuzzy‎Multiple‎Heuristic‎Ordering‎for‎Course‎Timetabling”,‎Proceedings‎of‎the‎5th‎United‎Kingdom Workshop on Computational Intelligence, London, (2005).
  19. J.‎F.‎Gonçalves‎and‎J.‎R.‎De‎Almeida,‎“A‎Hybrid‎Genetic‎Algorithm‎for‎Assembly‎Line‎Balancing”,‎Journal‎of‎Heuristics,‎Vol.8,‎(2002),‎pp.629-642.
  20. K.‎ Socha,‎ J.‎ Knowles‎ and‎ M.‎ Samples,‎ “A‎ Max-Min Ant System for the University Course Timetabling‎ Problem”,‎ Proceedings‎ of‎ the‎ 3rd‎ International Workshop on Ant Algorithms, Lecture Notes in Computer Science, Springer Verlag, Vol.2463, (2002), pp.1-13.
  21. L. M. Mooney, Tabu Search Heuristics for Resource Scheduling with Course Scheduling Applications, PhD Dissertation, Purdue Un iversity, (1991).
  22. Lewis, R. (2008) 'A Survey of Metaheuristic-based Techniques for University Timetabling Problems'. OR Spectrum, vol. 30(1), pp 167-190.
  23. M.‎A.‎Saleh‎and‎P.‎Coddington,‎“A‎Comparison‎of‎Annealing‎techniques‎for‎Academic‎Course‎Scheduling”,‎Lecture‎Notes‎in‎Computer‎Science,‎Springer‎Verlag, Vol. 1408, (1998), pp.92-114.
  24. M.‎ Battarra,‎ B.‎ Golden‎ and‎ D.‎ Vigo,‎ “Tuning‎ a‎ Parametric‎ Clarke-Wright Heuristic via‎ a‎ Genetic‎ Algorithm”,‎ Università‎ di‎ Bologna,‎ Dipartimento di ElettronicaInformatica e Sistemistica, TR-DEIS OR.INGCE 2006/1R, (2006).
  25. M.‎Gendreau‎and‎J.‎Potvin,‎"Tabu‎Search”,‎Introductory‎Tutorials‎in‎Optimization,‎Decision‎Support‎and‎Search‎Methodology,‎E. K. Burke and G. Ken- dall (Editors), Springer Verlag, Chapter 6, (2005), pp.165-186.
  26. M.‎Omar,‎R.‎N.‎Ainon,‎and‎R.‎Zainuddin,‎“Using‎a‎Genetic‎Algorithm‎Optimizer‎Tool‎to‎generate‎good‎quality‎Timetables”,‎Proceedings‎of‎the‎10th‎IEEE‎‎ International Conference, Electronics, Circuits and Systems, Vol.3, (2003), pp.1300-1303.
  27. M.‎R.‎Malim,‎A.‎T.‎Khader‎and‎A‎Mustafa,‎“Artificial‎Immune‎Algorithms‎for‎University‎Timetabling”,‎Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling, Czech Republic, (2006).
  28. M.‎Tuga,‎R.‎Berretta‎and‎A.‎Mendes,‎“A‎Hybrid‎Simulated‎Annealing‎with‎Kempe‎Chain‎Neighborhood‎for‎the‎University‎Timetabling‎Problem”,‎Com- puter and Information Science, (2007).
  29. N.‎D.‎Thanh,‎“Solving‎Timetabling‎Problem‎using‎Genetic‎and‎Heuristic‎Algorithms”,‎Proceedings of 8th ACIS International Conference, (2007).
  30. N.‎D.‎Thanh,‎“Solving‎Timetabling‎Problem‎using‎Genetic‎and‎Heuristic‎Algorithms”,‎Proceedings‎of‎8th‎ACIS‎International‎Conference,‎(2007).
  31. P.‎Adamidis‎and‎P.‎Arapakis,‎“Evolutionary‎Algorithms‎in‎Lecture‎Timetabling”,‎Proceedings‎of‎the‎1999‎IEEE‎Congress‎on‎Evolutionary Computation, (1999), pp.1145-1151.
  32. P. De Causmaecker, P. Demeester, G. VandenBerghe: Evaluation of the University Course Timetabling Problem with the Linear Numberings Method, UK Plan SIG 2006, Nottingham, 14-15 December 2006, pp. 154-155.
  33. P.‎Kostuch,‎“The‎University‎Course‎Timetabling‎Problem‎with‎a‎3-phase‎Approach”,‎Proceedings‎of‎the‎5th‎International‎Conference on the Practice and Theory of Automated Timetabling, E. K. Burke, M. Trick, (Editors), Lecture Notes in Computer Science, Springer Verlag, Vol.3616, (2005), pp.109–125.
  34. P.‎Kostuch,‎“The‎University‎Course‎Timetabling‎Problem‎with‎a‎3-stage Approach”,‎Proceedings‎of‎the‎5th‎International‎Conference‎on‎the‎Practice and Theory of Automated Timetabling, (2004), pp.251-266.
  35. R.‎ Lewis‎ and‎B.‎ Paechter,‎ “Application‎ of‎ the‎ Grouping‎ Genetic‎ Algorithm‎ to‎ University‎ Course‎ Timetabling”,‎ Evolutionary‎ Comp utation in Combina- torial Optimization, V. G. Raidl and J. Gottlieb, (Editors), Lecture Notes in Computer Science, Springer Verlag, Vol.3448, (2005), pp.144-153.
  36. R.‎Lewis‎and‎B.‎Paechter,‎“New‎Crossover‎Operators‎for‎Timetabling‎with‎Evolutionary Algorithms”,‎5th‎International‎Conference‎on‎Recent‎Advances‎ in Soft Computing, Nottingham, England, (2004).
  37. R.‎Lewis,‎“A‎Survey‎of‎Metaheuristic‎based‎techniques‎for‎University‎Timetabling‎problems”,‎OR‎Spectrum,‎Vol.30,‎(2008),‎pp.1 67-190.
  38. R.‎Lewis,‎“Metaheuristics‎for‎University‎Course‎Timetabling”‎PhD‎Thesis,‎School‎of‎Computing,‎Napier‎University,‎Edinburgh, (2006).
  39. R.‎ Lewis,‎ B.‎ Paechter‎ and‎ B.‎ McCollum,‎ “Post‎ Enrolment‎ based‎ Course‎ Timetabling:‎ A‎ description‎ of‎ the‎ Problem‎ Model‎ used‎ for‎ Track Two of the Second‎International‎Timetabling”,‎Cardiff‎University,‎Cardiff‎Business School, Accounting and Finance Section, (2007).
  40. R.‎ Marti,‎ H.‎ Lourenco‎ and‎ M.‎ Laguna,‎ “Assigning‎ Proctors‎ to‎ Exams‎ with‎ Scatter‎ Search”,‎ Economics‎ Working‎ Paper‎ Seri es No.534, Department of Economics and Business, Universitat Pompeu Fabr, (2001).
  41. R.‎Qu‎and‎E.‎K.‎Burke,‎“Adaptive‎Decomposition‎and‎Construction‎for‎Examination‎Timetabling‎Problems”,‎Multidisciplinary‎International Scheduling: Theory and Applications, P. Baptiste, G. Kendall, A. Munier-Kordon, F. Sourd, (Editors.), (2007), pp.418-425.
  42. R. Qu and E. K. Burke,‎ “Adaptive‎Decomposition‎and‎Construction‎for‎Examination‎Timetabling‎Problems”,‎Multidisciplinary‎International‎Scheduling: Theory and Applications, P. Baptiste, G. Kendall, A. Munier-Kordon, F. Sourd, (Editors.), (2007), pp.418-425.
  43. S.‎Abdullah,‎E.‎K.‎Burke‎and‎B.‎McCollum,‎“A‎Hybrid‎Evolutionary‎Approach‎to‎the‎University‎Course‎Timetabling‎Problem”,‎Proc eedings of the IEEE Congress on Evolutionary Computation, Singapore, (2007).
  44. S.‎O.‎Tasan‎and‎S.‎Tunali,‎“A‎Review‎of‎the‎Current‎Applications‎of‎Genetic‎Algorithms‎in‎Assembly‎Line‎Balancing”,‎Journal‎of Intelligent Manufactur- ing, Vol.19, (2008), pp.49-69.
  45. Schaerf A., A Survey of Automated Timetabling, Tech. rep. CS-R9567, CWI, Amsterdam,(1995).
  46. Scholl and C. Becker,‎ “State-of-the-art Exact and Heuristic solution procedures for Simple Assembly‎ Line‎ Balancing”,‎ European‎ Journal‎ of‎ Operation‎ Research, Vol.168, (2006), pp.666-693.
  47. T.‎ Duong‎ and‎ K.‎ Lam,‎ “Combining‎Constraint‎ Programming‎ and‎ Simulated‎ Annealing‎ on‎ University‎ Exam‎ Timetabling”,‎ Proceedings‎ o f RIVF Confe- rence, Hanoi, Vietnam, (2004).
  48. Wren,‎Scheduling,‎“Timetabling‎and‎Rostering‎– A Special Relationship!”,‎The‎Practice‎and‎Theory‎of‎Automated‎Timetabling:‎Selected‎Papers‎from‎the 1st Int'l Conf. on the Practice and Theory of Automated Timetabling, E. K. Burke, P. Ross (Editors), Lecture Notes in Computer Science, Springer Verlag, Vol.1153, (1996), pp.46-75.
  49. Z.‎ W.‎ Geem,‎ “School‎ Bus‎ Routing‎ using‎ Harmony‎ Search”,‎ Proceedings‎ of‎ Genetic‎ and‎ Evolutionary‎ Computation‎ Conference,‎ Washington, D.C., (2005).
Index Terms

Computer Science
Information Sciences

Keywords

Time table schedule Genetic Algorithms Graph Coloring Genetic Coloring Graph Coloring Genetic Coloring