IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v242y2015i3p798-806.html
   My bibliography  Save this article

Search with evolutionary ruin and stochastic rebuild: A theoretic framework and a case study on exam timetabling

Author

Listed:
  • Li, Jingpeng
  • Bai, Ruibin
  • Shen, Yindong
  • Qu, Rong

Abstract

This paper presents a state transition based formal framework for a new search method, called Evolutionary Ruin and Stochastic Recreate, which tries to learn and adapt to the changing environments during the search process. It improves the performance of the original Ruin and Recreate principle by embedding an additional phase of Evolutionary Ruin to mimic the survival-of-the-fittest mechanism within single solutions. This method executes a cycle of Solution Decomposition, Evolutionary Ruin, Stochastic Recreate and Solution Acceptance until a certain stopping condition is met. The Solution Decomposition phase first uses some problem-specific knowledge to decompose a complete solution into its components and assigns a score to each component. The Evolutionary Ruin phase then employs two evolutionary operators (namely Selection and Mutation) to destroy a certain fraction of the solution, and the next Stochastic Recreate phase repairs the “broken” solution. Last, the Solution Acceptance phase selects a specific strategy to determine the probability of accepting the newly generated solution. Hence, optimisation is achieved by an iterative process of component evaluation, solution disruption and stochastic constructive repair. From the state transitions point of view, this paper presents a probabilistic model and implements a Markov chain analysis on some theoretical properties of the approach. Unlike the theoretical work on genetic algorithm and simulated annealing which are based on state transitions within the space of complete assignments, our model is based on state transitions within the space of partial assignments. The exam timetabling problems are used to test the performance in solving real-world hard problems.

Suggested Citation

  • Li, Jingpeng & Bai, Ruibin & Shen, Yindong & Qu, Rong, 2015. "Search with evolutionary ruin and stochastic rebuild: A theoretic framework and a case study on exam timetabling," European Journal of Operational Research, Elsevier, vol. 242(3), pages 798-806.
  • Handle: RePEc:eee:ejores:v:242:y:2015:i:3:p:798-806
    DOI: 10.1016/j.ejor.2014.11.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714009060
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2014.11.002?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. S Abdullah & S Ahmadi & E K Burke & M Dror & B McCollum, 2007. "A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(11), pages 1494-1502, November.
    2. Cheang, B. & Li, H. & Lim, A. & Rodrigues, B., 2003. "Nurse rostering problems--a bibliographic survey," European Journal of Operational Research, Elsevier, vol. 151(3), pages 447-460, December.
    3. Li, Jingpeng & Burke, Edmund K. & Curtois, Tim & Petrovic, Sanja & Qu, Rong, 2012. "The falling tide algorithm: A new multi-objective approach for complex workforce scheduling," Omega, Elsevier, vol. 40(3), pages 283-293.
    4. K A Dowsland & J M Thompson, 2005. "Ant colony optimization for the examination scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(4), pages 426-438, April.
    5. Burke, E.K. & Eckersley, A.J. & McCollum, B. & Petrovic, S. & Qu, R., 2010. "Hybrid variable neighbourhood approaches to university exam timetabling," European Journal of Operational Research, Elsevier, vol. 206(1), pages 46-53, October.
    6. Burke, Edmund K. & Li, Jingpeng & Qu, Rong, 2010. "A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems," European Journal of Operational Research, Elsevier, vol. 203(2), pages 484-493, June.
    7. Qu, Rong & Burke, Edmund K. & McCollum, Barry, 2009. "Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems," European Journal of Operational Research, Elsevier, vol. 198(2), pages 392-404, October.
    8. White, George M. & Xie, Bill S. & Zonjic, Stevan, 2004. "Using tabu search with longer-term memory and relaxation to create examination timetables," European Journal of Operational Research, Elsevier, vol. 153(1), pages 80-91, February.
    9. Ruiz, Ruben & Stutzle, Thomas, 2007. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2033-2049, March.
    10. Carl H. Häll & Anders Peterson, 2013. "Improving paratransit scheduling using ruin and recreate methods," Transportation Planning and Technology, Taylor & Francis Journals, vol. 36(4), pages 377-393, June.
    11. R Qu & E K Burke, 2009. "Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(9), pages 1273-1285, September.
    12. Burke, Edmund K. & McCollum, Barry & Meisels, Amnon & Petrovic, Sanja & Qu, Rong, 2007. "A graph-based hyper-heuristic for educational timetabling problems," European Journal of Operational Research, Elsevier, vol. 176(1), pages 177-192, January.
    13. Carl H. Häll & Anders Peterson, 2013. "Improving paratransit scheduling using ruin and recreate methods," Transportation Planning and Technology, Taylor & Francis Journals, vol. 36(4), pages 377-393, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Rahimian, Erfan & Akartunalı, Kerem & Levine, John, 2017. "A hybrid Integer Programming and Variable Neighbourhood Search algorithm to solve Nurse Rostering Problems," European Journal of Operational Research, Elsevier, vol. 258(2), pages 411-423.
    2. Xu, Guoning & Lin, Yupeng & Wu, Zhiying & Chen, Qingxin & Mao, Ning, 2023. "Research on the scheduling method of ground resource under uncertain arrival time," Operations Research Perspectives, Elsevier, vol. 11(C).
    3. De Boeck, Liesje & Beliën, Jeroen & Creemers, Stefan, 2016. "A column generation approach for solving the examination-timetabling problemAuthor-Name: Woumans, Gert," European Journal of Operational Research, Elsevier, vol. 253(1), pages 178-194.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Johnes, Jill, 2015. "Operational Research in education," European Journal of Operational Research, Elsevier, vol. 243(3), pages 683-696.
    2. Turabieh, Hamza & Abdullah, Salwani, 2011. "An integrated hybrid approach to the examination timetabling problem," Omega, Elsevier, vol. 39(6), pages 598-607, December.
    3. Mohammed Al-Betar & Ahamad Khader & Iyad Doush, 2014. "Memetic techniques for examination timetabling," Annals of Operations Research, Springer, vol. 218(1), pages 23-50, July.
    4. Abdul Rahman, Syariza & Bargiela, Andrzej & Burke, Edmund K. & Özcan, Ender & McCollum, Barry & McMullan, Paul, 2014. "Adaptive linear combination of heuristic orderings in constructing examination timetables," European Journal of Operational Research, Elsevier, vol. 232(2), pages 287-297.
    5. Burke, E.K. & Eckersley, A.J. & McCollum, B. & Petrovic, S. & Qu, R., 2010. "Hybrid variable neighbourhood approaches to university exam timetabling," European Journal of Operational Research, Elsevier, vol. 206(1), pages 46-53, October.
    6. De Boeck, Liesje & Beliën, Jeroen & Creemers, Stefan, 2016. "A column generation approach for solving the examination-timetabling problemAuthor-Name: Woumans, Gert," European Journal of Operational Research, Elsevier, vol. 253(1), pages 178-194.
    7. Edmund Burke & Rong Qu & Amr Soghier, 2014. "Adaptive selection of heuristics for improving exam timetables," Annals of Operations Research, Springer, vol. 218(1), pages 129-145, July.
    8. Martin Geiger, 2012. "Applying the threshold accepting metaheuristic to curriculum based course timetabling," Annals of Operations Research, Springer, vol. 194(1), pages 189-202, April.
    9. R Qu & E K Burke, 2009. "Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(9), pages 1273-1285, September.
    10. Barry McCollum & Paul McMullan & Andrew Parkes & Edmund Burke & Rong Qu, 2012. "A new model for automated examination timetabling," Annals of Operations Research, Springer, vol. 194(1), pages 291-315, April.
    11. Alejandro Cataldo & Juan-Carlos Ferrer & Jaime Miranda & Pablo A. Rey & Antoine Sauré, 2017. "An integer programming approach to curriculum-based examination timetabling," Annals of Operations Research, Springer, vol. 258(2), pages 369-393, November.
    12. Edmund Burke & Graham Kendall & Mustafa Mısır & Ender Özcan, 2012. "Monte Carlo hyper-heuristics for examination timetabling," Annals of Operations Research, Springer, vol. 196(1), pages 73-90, July.
    13. Nelishia Pillay, 2016. "A review of hyper-heuristics for educational timetabling," Annals of Operations Research, Springer, vol. 239(1), pages 3-38, April.
    14. Soria-Alcaraz, Jorge A. & Ochoa, Gabriela & Sotelo-Figeroa, Marco A. & Burke, Edmund K., 2017. "A methodology for determining an effective subset of heuristics in selection hyper-heuristics," European Journal of Operational Research, Elsevier, vol. 260(3), pages 972-983.
    15. Dessouky, Maged M & Hu, Shichun, 2021. "Dynamic Routing for Ride-Sharing," Institute of Transportation Studies, Working Paper Series qt6qq8r7hz, Institute of Transportation Studies, UC Davis.
    16. Ran Liu & Xiaolan Xie, 2018. "Physician Staffing for Emergency Departments with Time-Varying Demand," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 588-607, August.
    17. R. A. Oude Vrielink & E. A. Jansen & E. W. Hans & J. Hillegersberg, 2019. "Practices in timetabling in higher education institutions: a systematic review," Annals of Operations Research, Springer, vol. 275(1), pages 145-160, April.
    18. García-Villoria, Alberto & Salhi, Said & Corominas, Albert & Pastor, Rafael, 2011. "Hyper-heuristic approaches for the response time variability problem," European Journal of Operational Research, Elsevier, vol. 211(1), pages 160-169, May.
    19. Lü, Zhipeng & Hao, Jin-Kao, 2010. "Adaptive Tabu Search for course timetabling," European Journal of Operational Research, Elsevier, vol. 200(1), pages 235-244, January.
    20. T. Godwin, 2022. "Obtaining quality business school examination timetable under heterogeneous elective selections through surrogacy," OPSEARCH, Springer;Operational Research Society of India, vol. 59(3), pages 1055-1093, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:242:y:2015:i:3:p:798-806. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.