IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v239y2016i1d10.1007_s10479-013-1504-3.html
   My bibliography  Save this article

Repairing high school timetables with polymorphic ejection chains

Author

Listed:
  • Jeffrey H. Kingston

    (The University of Sydney)

Abstract

This paper introduces polymorphic ejection chains, and applies them to the problem of repairing time assignments in high school timetables while preserving regularity. An ejection chain is a sequence of repairs, each of which removes a defect introduced by the previous repair. Just as the elements of a polymorphic list may have different types, so in a polymorphic ejection chain the individual repairs may have different types. Methods for the efficient realization of these ideas, implemented in the author’s KHE framework, are given, and some initial experiments are presented.

Suggested Citation

  • Jeffrey H. Kingston, 2016. "Repairing high school timetables with polymorphic ejection chains," Annals of Operations Research, Springer, vol. 239(1), pages 119-134, April.
    • Handle: RePEc:spr:annopr:v:239:y:2016:i:1:d:10.1007_s10479-013-1504-3
    DOI: 10.1007/s10479-013-1504-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-013-1504-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-013-1504-3?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. Gerhard Post & Samad Ahmadi & Sophia Daskalaki & Jeffrey Kingston & Jari Kyngas & Cimmo Nurmi & David Ranson, 2012. "An XML format for benchmarks in High School Timetabling," Annals of Operations Research, Springer, vol. 194(1), pages 385-397, April.
    2. Jeffrey Kingston, 2012. "Resource assignment in high school timetabling," Annals of Operations Research, Springer, vol. 194(1), pages 241-254, April.
    3. Dowsland, Kathryn A., 1998. "Nurse scheduling with tabu search and strategic oscillation," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 393-407, April.
    Full references (including those not matched with items on IDEAS)

    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. Haase, Knut, 1999. "Retail business staff scheduling under complex labor relations," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 511, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    2. Yavuz, Mesut & Tufekci, Suleyman, 2006. "A bounded dynamic programming solution to the batching problem in mixed-model just-in-time manufacturing systems," International Journal of Production Economics, Elsevier, vol. 103(2), pages 841-862, October.
    3. Vanhoucke, Mario & Maenhout, Broos, 2009. "On the characterization and generation of nurse scheduling problem instances," European Journal of Operational Research, Elsevier, vol. 196(2), pages 457-467, July.
    4. Beddoe, Gareth R. & Petrovic, Sanja, 2006. "Selecting and weighting features using a genetic algorithm in a case-based reasoning approach to personnel rostering," European Journal of Operational Research, Elsevier, vol. 175(2), pages 649-671, December.
    5. Kaixiang Zhu & Lily D. Li & Michael Li, 2021. "School Timetabling Optimisation Using Artificial Bee Colony Algorithm Based on a Virtual Searching Space Method," Mathematics, MDPI, vol. 10(1), pages 1-19, December.
    6. B Maenhout & M Vanhoucke, 2009. "The impact of incorporating nurse-specific characteristics in a cyclical scheduling approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(12), pages 1683-1698, December.
    7. Václavík, Roman & Novák, Antonín & Šůcha, Přemysl & Hanzálek, Zdeněk, 2018. "Accelerating the Branch-and-Price Algorithm Using Machine Learning," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1055-1069.
    8. D. Parr & J. Thompson, 2007. "Solving the multi-objective nurse scheduling problem with a weighted cost function," Annals of Operations Research, Springer, vol. 155(1), pages 279-288, November.
    9. David Van Bulck & Dries Goossens & Jo¨rn Scho¨nberger & Mario Guajardo, 2020. "An Instance Data Repository for the Round-robin Sports Timetabling Problem," Management and Labour Studies, XLRI Jamshedpur, School of Business Management & Human Resources, vol. 45(2), pages 184-200, May.
    10. Eyjólfur Ingi Ásgeirsson & Guðríður Lilla Sigurðardóttir, 2016. "Near-optimal MIP solutions for preference based self-scheduling," Annals of Operations Research, Springer, vol. 239(1), pages 273-293, April.
    11. Belií«n, Jeroen & Demeulemeester, Erik, 2008. "A branch-and-price approach for integrating nurse and surgery scheduling," European Journal of Operational Research, Elsevier, vol. 189(3), pages 652-668, September.
    12. Gerhard Post & Luca Gaspero & Jeffrey H. Kingston & Barry McCollum & Andrea Schaerf, 2016. "The Third International Timetabling Competition," Annals of Operations Research, Springer, vol. 239(1), pages 69-75, April.
    13. Emir Demirović & Nysret Musliu, 2017. "Modeling high school timetabling with bitvectors," Annals of Operations Research, Springer, vol. 252(2), pages 215-238, May.
    14. Eyjólfur Ásgeirsson, 2014. "Bridging the gap between self schedules and feasible schedules in staff scheduling," Annals of Operations Research, Springer, vol. 218(1), pages 51-69, July.
    15. Dellaert, Nico & Jeunet, Jully & Mincsovics, Gergely, 2011. "Budget allocation for permanent and contingent capacity under stochastic demand," International Journal of Production Economics, Elsevier, vol. 131(1), pages 128-138, May.
    16. Edmund Burke & Jingpeng Li & Rong Qu, 2012. "A Pareto-based search methodology for multi-objective nurse scheduling," Annals of Operations Research, Springer, vol. 196(1), pages 91-109, July.
    17. Dorneles, Árton P. & de Araújo, Olinto C.B. & Buriol, Luciana S., 2017. "A column generation approach to high school timetabling modeled as a multicommodity flow problem," European Journal of Operational Research, Elsevier, vol. 256(3), pages 685-695.
    18. J P Oddoye & M A Yaghoobi & M Tamiz & D F Jones & P Schmidt, 2007. "A multi-objective model to determine efficient resource levels in a medical assessment unit," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1563-1573, December.
    19. Deborah L. Kellogg & Steven Walczak, 2007. "Nurse Scheduling: From Academia to Implementation or Not?," Interfaces, INFORMS, vol. 37(4), pages 355-369, August.
    20. P R Harper & N H Powell & J E Williams, 2010. "Modelling the size and skill-mix of hospital nursing teams," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(5), pages 768-779, May.

    More about this item

    Keywords

    High school timetabling; Ejection chains;

    Statistics

    Access and download statistics

    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:spr:annopr:v:239:y:2016:i:1:d:10.1007_s10479-013-1504-3. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.