IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v180y2010i1p145-16410.1007-s10479-008-0491-2.html
   My bibliography  Save this article

Greedy scheduling with custom-made objectives

Author

Listed:
  • Carsten Franke
  • Joachim Lepping
  • Uwe Schwiegelshohn

Abstract

We present a methodology to automatically generate an online job scheduling method for a custom-made objective and real workloads. The scheduling problem comprises independent parallel jobs and parallel identical machines and occurs in Massively Parallel Processing systems and computational Grids. The system administrator defines the scheduling objective that may consider job properties and priorities of users or user groups. Our scheduling method combines a Greedy scheduling algorithm with the dynamic sorting of the waiting queue. This sorting algorithm uses a criterion that is modifiable by a set of parameters. Finding good parameter settings for the sorting criterion is viewed as a nonlinear optimization problem which is solved with the help of Evolution Strategies. We evaluate our scheduling method with real workload data and compare it to approximated optimal offline solutions and to the online results of the standard EASY backfill algorithm. Copyright Springer Science+Business Media, LLC 2010

Suggested Citation

  • Carsten Franke & Joachim Lepping & Uwe Schwiegelshohn, 2010. "Greedy scheduling with custom-made objectives," Annals of Operations Research, Springer, vol. 180(1), pages 145-164, November.
    • Handle: RePEc:spr:annopr:v:180:y:2010:i:1:p:145-164:10.1007/s10479-008-0491-2
    DOI: 10.1007/s10479-008-0491-2
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-008-0491-2
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-008-0491-2?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. 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.
    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. Carlos Contreras Bolton & Gustavo Gatica & Víctor Parada, 2013. "Automatically Generated Algorithms for the Vertex Coloring Problem," PLOS ONE, Public Library of Science, vol. 8(3), pages 1-9, March.
    2. Jacek Blazewicz & Edmund Burke & Graham Kendall & Wojciech Mruczkiewicz & Ceyda Oguz & Aleksandra Swiercz, 2013. "A hyper-heuristic approach to sequencing by hybridization of DNA sequences," Annals of Operations Research, Springer, vol. 207(1), pages 27-41, August.
    3. Song, Kwonsik & Kim, Sooyoung & Park, Moonseo & Lee, Hyun-Soo, 2017. "Energy efficiency-based course timetabling for university buildings," Energy, Elsevier, vol. 139(C), pages 394-405.
    4. De Causmaecker, Patrick & Demeester, Peter & Vanden Berghe, Greet, 2009. "A decomposed metaheuristic approach for a real-world university timetabling problem," European Journal of Operational Research, Elsevier, vol. 195(1), pages 307-318, May.
    5. R Bai & E K Burke & G Kendall, 2008. "Heuristic, meta-heuristic and hyper-heuristic approaches for fresh produce inventory control and shelf space allocation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(10), pages 1387-1397, October.
    6. Christine Mumford, 2010. "A multiobjective framework for heavily constrained examination timetabling problems," Annals of Operations Research, Springer, vol. 180(1), pages 3-31, November.
    7. 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.
    8. Kahar, M.N.M. & Kendall, G., 2010. "The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution," European Journal of Operational Research, Elsevier, vol. 207(2), pages 557-565, December.
    9. Bhuvnesh Sharma & M. Ramkumar & Nachiappan Subramanian & Bharat Malhotra, 2019. "Dynamic temporary blood facility location-allocation during and post-disaster periods," Annals of Operations Research, Springer, vol. 283(1), pages 705-736, December.
    10. 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.
    11. Thepphakorn, Thatchai & Pongcharoen, Pupong & Hicks, Chris, 2014. "An ant colony based timetabling tool," International Journal of Production Economics, Elsevier, vol. 149(C), pages 131-144.
    12. 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.
    13. G N Beligiannis & C Moschopoulos & S D Likothanassis, 2009. "A genetic algorithm approach to school timetabling," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 23-42, January.
    14. Jaime Miranda, 2010. "eClasSkeduler: A Course Scheduling System for the Executive Education Unit at the Universidad de Chile," Interfaces, INFORMS, vol. 40(3), pages 196-207, June.
    15. Mallol-Poyato, R. & Salcedo-Sanz, S. & Jiménez-Fernández, S. & Díaz-Villar, P., 2015. "Optimal discharge scheduling of energy storage systems in MicroGrids based on hyper-heuristics," Renewable Energy, Elsevier, vol. 83(C), pages 13-24.
    16. Sabar, Nasser R. & Ayob, Masri & Kendall, Graham & Qu, Rong, 2012. "A honey-bee mating optimization algorithm for educational timetabling problems," European Journal of Operational Research, Elsevier, vol. 216(3), pages 533-543.
    17. Yu Lei & Jiao Shi, 2017. "A NNIA Scheme for Timetabling Problems," Journal of Optimization, Hindawi, vol. 2017, pages 1-11, May.
    18. 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.
    19. Nelishia Pillay & Ender Özcan, 2019. "Automated generation of constructive ordering heuristics for educational timetabling," Annals of Operations Research, Springer, vol. 275(1), pages 181-208, April.
    20. 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.

    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:180:y:2010:i:1:p:145-164:10.1007/s10479-008-0491-2. 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.