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. 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.
    2. 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.
    3. Jeffrey Kingston, 2012. "Resource assignment in high school timetabling," Annals of Operations Research, Springer, vol. 194(1), pages 241-254, 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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. Farasat, Alireza & Nikolaev, Alexander G., 2016. "Signed social structure optimization for shift assignment in the nurse scheduling problem," Socio-Economic Planning Sciences, Elsevier, vol. 56(C), pages 3-13.
    14. Topaloglu, Seyda, 2009. "A shift scheduling model for employees with different seniority levels and an application in healthcare," European Journal of Operational Research, Elsevier, vol. 198(3), pages 943-957, November.
    15. Blochliger, Ivo, 2004. "Modeling staff scheduling problems. A tutorial," European Journal of Operational Research, Elsevier, vol. 158(3), pages 533-542, November.
    16. Chiaramonte, Michael V. & Chiaramonte, Laurel M., 2008. "An agent-based nurse rostering system under minimal staffing conditions," International Journal of Production Economics, Elsevier, vol. 114(2), pages 697-713, August.
    17. Tom Rihm & Philipp Baumann, 2018. "Staff assignment with lexicographically ordered acceptance levels," Journal of Scheduling, Springer, vol. 21(2), pages 167-189, April.
    18. Hadi W. Purnomo & Jonathan F. Bard, 2007. "Cyclic preference scheduling for nurses using branch and price," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 200-220, March.
    19. Frederik Knust & Lin Xie, 2019. "Simulated annealing approach to nurse rostering benchmark and real-world instances," Annals of Operations Research, Springer, vol. 272(1), pages 187-216, January.
    20. Brucker, Peter & Qu, Rong & Burke, Edmund, 2011. "Personnel scheduling: Models and complexity," European Journal of Operational Research, Elsevier, vol. 210(3), pages 467-473, 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.