LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Soria-Alcaraz, Jorge A.; Özcan, Ender; Swan, Jerry; Kendall, Graham; Carpio, Martin (2016)
Publisher: Elsevier
Languages: English
Types: Article
Subjects:
Hyper-heuristics are (meta-)heuristics that operate at a higher level to choose or generate a set of low-level (meta-)heuristics in an attempt of solve difficult optimization problems. Iterated local search (ILS) is a well-known approach for discrete optimization, combining perturbation and hill-climbing within an iterative framework. In this study, we introduce an ILS approach, strengthened by a hyper-heuristic which generates heuristics based on a fixed number of add and delete operations. The performance of the proposed hyper-heuristic is tested across two different problem domains using real world benchmark of course timetabling instances from the second International Timetabling Competition Tracks 2 and 3. The results show that mixing add and delete operations within an ILS framework yields an effective hyper-heuristic approach.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • Figure 3: Example of o ered timeslots M onday and W ednesday T uesday and T hursday F riday t1 t2 t9 t3 t4 t10 t5 t6 t11 t7 t8 t12
    • [1] E. O zcan, B. Bilgin, E. E. Korkmaz, A comprehensive analysis of hyperheuristics, Intell. Data Anal. 12 (1) (2008) 3{23.
    • [2] E. K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. Ozcan, R. Qu, Hyper-heuristics: A survey of the state of the art, J Oper Res Soc 64 (12) (2013) 1695{1724.
    • [3] P. Cowling, G. Kendall, E. Soubeiga, A hyperheuristic approach to scheduling a sales summit, in: E. Burke, W. Erben (Eds.), Practice and Theory of Automated Timetabling III, Vol. 2079 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2001, pp. 176{190.
    • [4] E. K. Burke, M. Hyde, G. Kendall, G. Ochoa, E. Ozcan, J. Woodward, Handbook of Metaheuristics, Vol. 146 of International Series in Operations Research & Management Science, Springer, 2010, Ch. A Classi cation of Hyperheuristic Approaches, pp. 449{468, chapter 15.
    • [5] S. Even, A. Itai, A. Shamir, On the complexity of timetable and multicommodity ow problems, SIAM J. Comput. 5 (4) (1976) 691{703.
    • [6] T. B. Cooper, J. H. Kingston, The compexity of timetable construction problems, Ph.D. thesis, The University of Sydney (1995).
    • [7] R. J. Willemen, School timetable constructrion: Algorithms and complexity, Ph.D. thesis, Institutefor Programming research and Algorithms (2002).
    • [8] B. McCollum, A. Schaerf, B. Paechter, P. McMullan, R. Lewis, A. J. Parkes, L. D. Gaspero, R. Qu, E. K. Burke, Setting the research agenda in automated timetabling: The second international timetabling competition, Informs Journal on computing 22 (1) (2010) 120{130.
    • [9] R. Lewis, Metaheuristics for university course timetabling, Ph.D. thesis, University of Notthingham. (August 2006).
    • [10] E. K. Burke, G. Kendall, E. Soubeiga, A tabu-search hyperheuristic for timetabling and rostering, Journal of Heuristics 9 (6) (2003) 451{470.
    • [11] H. Fisher, G. L. Thompson, Probabilistic learning combinations of local jobshop scheduling rules, in: J. F. Muth, G. L. Thompson (Eds.), Industrial Scheduling, Prentice-Hall, Inc, New Jersey, 1963, pp. 225{251.
    • [12] W. B. Crowston, F. Glover, G. L. Thompson, J. D. Trawick, Probabilistic and parametric learning combinations of local job shop scheduling rules, ONR Research memorandum, GSIA, Carnegie Mellon University, Pittsburgh (117).
    • [13] Y. Hamadi, E. Monfroy, F. Saubion (Eds.), Autonomous Search, Springer, 2012.
    • [14] R. Battiti, M. Brunato, F. Mascia, Reactive Search and Intelligent Optimization, Vol. 45 of Operations Research/Computer Science Interfaces Series, Springer, 2009.
    • [15] J. Maturana, F. Lardeux, F. Saubion, Autonomous operator management for evolutionary algorithms, Journal of Heuristics 16 (2010) 881{909.
    • [16] Y. S. Ong, M. H. Lim, N. Zhu, K. W. Wong, Classi cation of adaptive memetic algorithms: a comparative study, IEEE Transactions on Systems, Man, and Cybernetics, Part B 36 (1) (2006) 141{152.
    • [17] M. Birattari, Tuning Metaheuristics: A Machine Learning Perspective, Springer, 2009.
    • [18] F. Lobo, C. Lima, Z. Michalewicz (Eds.), Parameter Setting in Evolutionary Algorithms, Vol. 54 of Studies in Computational Intelligence, Springer, 2007.
    • [19] J. Swan, E. O zcan, G. Kendall, Co-evolving add and delete heuristics, in: Proceedings of the Ninth International Conference on the Practice and Theory of Automated Timetabling (PATAT 2012), 2012, pp. 395{399.
    • [20] G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt, G. Dueck, Record breaking optimization results using the ruin and recreate principle, Journal of Computational Physics 159 (2) (2000) 139{171.
    • [23] P. Ross, Hyper-heuristics, in: E. K. Burke, G. Kendall (Eds.), Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Springer, 2005, Ch. 17, pp. 529{556.
    • [24] E. K. Burke, M. R. Hyde, G. Kendall, G. Ochoa, E. O zcan, J. R. Woodward, Exploring hyper-heuristic methodologies with genetic programming, in: J. Kacprzyk, L. C. Jain, C. L. Mumford, L. C. Jain (Eds.), Computational Intelligence, Vol. 1 of Intelligent Systems Reference Library, Springer Berlin Heidelberg, 2009, pp. 177{201.
    • [25] E. O zcan, A. J. Parkes, Policy matrix evolution for generation of heuristics, in: Proceedings of the 13th annual conference on Genetic and evolutionary computation, GECCO '11, ACM, New York, NY, USA, 2011, pp. 2011{2018.
    • [26] D. de Werra, An introduction to timetabling, European Journal of Operational Research 19 (2) (1985) 151 { 162.
    • [27] M. Carter, A survey of practical applications of examination timetabling algorithms, Operations Research 34 (1986) 193{202.
    • [34] K. Socha, J. Knowles, M. Samples, A max-min ant system for the university course timetabling problem, in: M. Dorigo, G. D. caro, M. Samples (Eds.), Proceedings of Ants 2002 - Third International Workshop on Ant Algorithms, Lecture Notes in Computer Science, Berlin: Springer-Verlag, 2002, pp. 1{13.
    • [35] E. Burke, A. Eckersley, B. McCollum, S. Petrovic, R. Qu, Hybrid variable neighbourhood approaches to university exam timetabling, European Journal of Operational Research 206 (1) (2010) 46 { 53.
    • [36] J. M. Thompson, K. A. Dowsland, A robust simulated annealing based examination timetabling system, Computers and Operations Research 25 (1998) 637{648.
    • [37] H. Rudova, T. Muller, K. Murray, Complex university course timetabling, Journal of Scheduling 14 (2011) 187{207.
    • [38] H. Cambazard, E. Hebrard, B. OSullivan, A. Papadopoulos, Local search and constraint programming for the post enrolment-based course timetabling problem, Annals of Operations Research 194 (2012) 111{135.
    • [39] E. K. Burke, B. McCollum, A. Meisels, S. Petrovic, R. Qu, A graph-based hyper-heuristic for educational timetabling problems, European Journal of Operational Research 176 (1) (2007) 177 { 192.
    • [40] J. A. Soria-Alcaraz, H. Terashima-Marin, M. Carpio, Academic timetabling design using hyper-heuristics, Advances in Soft Computing, ITT SpringerVerlag 1 (2010) 158{164.
    • [41] R. Qu, E. K. Burke, B. McCollum, Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems, European Journal of Operational Research 198 (2) (2009) 392 { 404.
    • [42] M. Atsuta, K. Nonobe, T. Ibaraki1, Itc-2007 track2: An approach using general csp solver, International Timetabling Compertition 2007.
    • [43] K. Nonobe, T. Ibaraki, An improved tabu search method for the weighted constraint satisfaction problem, INFOR 39 (2) (2001) 131{151.
    • [46] S. Jat, S. Yang, A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling, Journal of Scheduling 14 (6) (2011) 617{637.
    • [47] T. Muller, Itc2007 solver description: a hybrid approach, Annals OR 172 (1) (2009) 429{446.
    • [48] Z. Lu, J.-K. Hao, Adaptive tabu search for course timetabling, European Journal of Operational Research 200 (1) (2010) 235{244.
    • [49] J.-K. Hao, U. Benlic, Lower bounds for the itc-2007 curriculum-based course timetabling problem, European Journal of Operational Research 212 (3) (2011) 464{472.
    • [50] R. As n Acha, R. Nieuwenhuis, Curriculum-based course timetabling with sat and maxsat, Annals of Operations Research (2012) 1{21.
    • [51] V. Cacchiani, A. Caprara, R. Roberti, P. Toth, A new lower bound for curriculum-based course timetabling, Computers & Operations Research 40 (10) (2013) 2466{2477.
    • [52] H. Lourenco, O. Martin, T. Stutzle, Iterated local search, in: F. Glover, G. Kochenberger, F. S. Hillier (Eds.), Handbook of Metaheuristics, Vol. 57 of International Series in Operations Research & Management Science, Springer New York, 2003, pp. 320{353.
    • [56] J. Derrac, S. Garc a, D. Molina, F. Herrera, A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms, Swarm and Evolutionary Computation 1 (1) (2011) 3 { 18.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article