نهج تحسين حشد البكتيريا لمشاكل الجدول الزمني للدورة التدريبية القائمة على التسجيل

نهج تحسين حشد البكتيريا لمشاكل الجدول الزمني للدورة التدريبية القائمة على التسجيل

 

Bacteria Swarm Optimization Approach for Enrolment-Based Course Timetabling Problems

 

Khalid Shaker • Salwani Abdullah • Arwa Alqudsi

Article Link  

The university course timetabling problem is known as a NP-hard problem. It is also sometimes known as a class/teacher timetabling that refers to a set of courses that need to be scheduled into a given number of rooms and timeslots within a week and, at the same time, students and teachers are assigned to courses so that the meetings can take place. A novel population based approach is proposed in this paper called a Bacteria Swarm Optimisation (BSO) algorithm. BSO is developed based on the behavior of bacteria when it searches for the nutrients. The search space is divided into three regions namely, risk, null and rich regions. Differential Evolution algorithm (DE) is embedded within BSO to move the solutions toward the best solution. The performance of our approach is tested over eleven benchmark datasets (representing one large, five medium and five small problems). Experimental results show that our approach is able to generate competitive results when compared with previous available approaches. Possible extensions upon this simple approach are also discussed.

Key Words: (BSO) algorithm , Differential Evolution algorithm

References

1. Asaju La'aro Bolaji, Ahamad Tajudin Khader, Mohammed Azmi Al-Betar, Mohammed A. Awadallah: University course timetabling using hybridized artificial bee colony with hill climbing optimizer. J. Comput. Science 5(5): 809-818 (2014)

2. Abdullah, S., Burke, E.K., McCollum, B.: A hybrid evolutionary approach to the university course timetabling problem. IEEE Congress on Evolutionary Computation, ISBN: 1-4244-1340-0, pp 1764-1768 (2007)

3. Abdullah, S., Burke, E.K., McCollum, B.: An investigation of variable neighbourhood search for university course timetabling. The 2nd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), pp. 413–427 (2005)

4. Abdullah, S., Burke, E.K., McCollum, B.: Using a randomised iterative improvement algorithm with composite neighbourhood structures for university course timetabling. In Metaheuristics: Progress in complex systems optimization (Operations Research / Computer Science Interfaces Series), Chapter 8. Published by Springer, ISBN:978-0-387- 71919-1 (2007)

5. Abdullah, S., Shaker, K., McCollum, B., McMullan, P.: Dual Sequence Simulated Annealing with Round-Robin Approach for University Course Timetabling. EVOCOP 2010, LNCS 6022, Springer-Berlin /Heidelberg, pp 1–10 (2010)

6. Abdullah, S., Turabieh, H.: Generating university course timetable using genetic algorithms and local search. The Third 2008 International Conference on Convergence and Hybrid Information Technology ICCIT, vol. I, pp 254-260 (2008)

7. Khalid Shaker, Salwani Abdullah, Arwa Alqudsi, Hamid Jalab: Hybridizing Metaheuristics Approaches for Solving University Course Timetabling Problems. RSKT 2013: 374-384, (2013)

8. Khalid Shaker, Salwani Abdullah, Arwa Hatem: A Differential Evolution Algorithm for the University course timetabling problem. DMO 2012: 99-102, (2012)

9. Khalid Shaker & Salwani Abdullah: Controlling Multi Algorithms Using Round Robin for University Course Timetabling Problem. FGIT-DTA/BSBT 2010: 47-55, (2010)

10. M.A. Al-Betar, A.T. Khader, M. Zaman: University course timetabling using a hybrid harmony search metaheuristic algorithm, IEEE Trans. Syst. Man Cyber- net. C, Appl.Rev. doi.org/10.1109/TSMCC.2011.2174356, (2014)

11. Ghaith M. Jaradat, Masri Ayob: An Elitist-Ant System for Solving the Post-Enrolment Course Timetabling Problem. FGIT-DTA/BSBT 2010: 167-176 (2010)

12. Shengxiang Yang, Sadaf Naseem Jat: Genetic Algorithms with Guided and Local Search Strategies for University Course Timetabling. IEEE Transactions on Systems, Man, and Cybernetics, Part C 41(1): 93-106 (2011)

13. Al-Betar, M., Khader, A., Yi Liao, I.: A Harmony Search with Multi-pitch Adjusting Rate for the University Course Timetabling. In: Z.W. Geem: Recent Advances in Harmony Search Algorithm, SCI 270, pp. 147–161. Springer, Heidelberg (2010)

14. Burke, E., Eckersley, A., McCollum, B., Petrovic, S., Qu, R.: Hybrid variable neighbourhood approaches to university exam timetabling. Technical Report NOTTCSTR-2006-2, University of Nottingham, School of CSiT (2006)

15. Burke, E.K., Meisels, A., Petrovic, S., Qu, R.: A graph-based hyper-heuristic for timetabling problems. European Journal of Operational Research 176, pp 177-192 (2007)

16. Landa-Silva, D., Obit, J.H.: Great deluge with non-linear decay rate for solving course timetabling problem. The fourth international IEEE conference on Intelligent Systems. Varna, Bulgaria, pp. 8.11–8.18 (2008)

17. Lewis, R., Paechter, B.: New crossover operators for timetabling with evolutionary algorithms. Proceedings of the 5th International Conference on Recent Advances in Soft Computing (ed. Lotfi), UK, December 16th-18th, pp 189-194 (2004)

18. Lewis, R.: A survey of metaheuristic-based techniques for University Timetabling problems. OR Spectrum 30, 167–190 (2008)

19. Malim, M.R., Khader, A.T., Mustafa, A.: Artificial Immune Algorithms for University Timetabling. In: Burke, E.K., Rudova, H. (eds.) The 6th International Conference on Practice and Theory of Automated Timetabling, Brno, Czech Republic, pp. 234–245 (2006)

20. McCollum, B., Schaerf, A., Paechter, B., McMullan, P., Lewis, R., Parkes, A., Di Gaspero, L., Qu, R., Burke, E.: Setting the Research Agenda in Automated Timetabling: The Second International Timetabling Competition, Accepted for publication to INFORMS Journal on Computing. doi 10.1287/ijoc.1090.0320 (2009)

21. McMullan, P.: An extended implementation of the great deluge algorithm for course timetabling, Computational Science – ICCS, Part I, LNCS 4487, Springer-Verlag Berlin Heidelberg, pp 538–545 (2007)

22. Qu, R., Burke, E.K., McCollum, B., Merlot, L.T.G., and Lee, S.Y.: A Survey of Search Methodologies and Automated System Development for Examination Timetabling. Journal of Scheduling, 12(1): pp 55-89 (2009)