IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v21y2018i5d10.1007_s10951-017-0552-y.html
   My bibliography  Save this article

Models and algorithms for energy-efficient scheduling with immediate start of jobs

Author

Listed:
  • Akiyoshi Shioura

    (School of Engineering, Tokyo Institute of Technology)

  • Natalia V. Shakhlevich

    (School of Computing, University of Leeds)

  • Vitaly A. Strusevich

    (University of Greenwich, Old Royal Naval College)

  • Bernhard Primas

    (School of Computing, University of Leeds)

Abstract

We study a scheduling model with speed scaling for machines and the immediate start requirement for jobs. Speed scaling improves the system performance, but incurs the energy cost. The immediate start condition implies that each job should be started exactly at its release time. Such a condition is typical for modern Cloud computing systems with abundant resources. We consider two cost functions, one that represents the quality of service and the other that corresponds to the cost of running. We demonstrate that the basic scheduling model to minimize the aggregated cost function with n jobs is solvable in $$O(n\log n)$$ O ( n log n ) time in the single-machine case and in $$O(n^{2}m)$$ O ( n 2 m ) time in the case of m parallel machines. We also address additional features, e.g., the cost of job rejection or the cost of initiating a machine. In the case of a single machine, we present algorithms for minimizing one of the cost functions subject to an upper bound on the value of the other, as well as for finding a Pareto-optimal solution.

Suggested Citation

  • Akiyoshi Shioura & Natalia V. Shakhlevich & Vitaly A. Strusevich & Bernhard Primas, 2018. "Models and algorithms for energy-efficient scheduling with immediate start of jobs," Journal of Scheduling, Springer, vol. 21(5), pages 505-516, October.
    • Handle: RePEc:spr:jsched:v:21:y:2018:i:5:d:10.1007_s10951-017-0552-y
    DOI: 10.1007/s10951-017-0552-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-017-0552-y
    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/s10951-017-0552-y?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. Yaron Leyvand & Dvir Shabtay & George Steiner & Liron Yedidsion, 2010. "Just-in-time scheduling with controllable processing times on parallel machines," Journal of Combinatorial Optimization, Springer, vol. 19(3), pages 347-368, April.
    2. Bekki, Özgün BarIs & Azizoglu, Meral, 2008. "Operational fixed interval scheduling problem on uniform parallel machines," International Journal of Production Economics, Elsevier, vol. 112(2), pages 756-768, April.
    3. Kenji Kushida & Jonathan Murray & John Zysman, 2015. "Cloud Computing: From Scarcity to Abundance," Journal of Industry, Competition and Trade, Springer, vol. 15(1), pages 5-19, March.
    4. Patriksson, Michael, 2008. "A survey on the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 185(1), pages 1-46, February.
    5. Marco E. T. Gerards & Johann L. Hurink & Philip K. F. Hölzenspies, 2016. "A survey of offline algorithms for energy minimization under deadline constraints," Journal of Scheduling, Springer, vol. 19(1), pages 3-19, February.
    6. Kovalyov, Mikhail Y. & Ng, C.T. & Cheng, T.C. Edwin, 2007. "Fixed interval scheduling: Models, applications, computational complexity and algorithms," European Journal of Operational Research, Elsevier, vol. 178(2), pages 331-342, April.
    7. Antoon W.J. Kolen & Jan Karel Lenstra & Christos H. Papadimitriou & Frits C.R. Spieksma, 2007. "Interval scheduling: A survey," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(5), pages 530-543, August.
    8. Shabtay, Dvir & Bensoussan, Yaron & Kaspi, Moshe, 2012. "A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system," International Journal of Production Economics, Elsevier, vol. 136(1), pages 67-74.
    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. Yunqiang Yin & T. C. E. Cheng & Du-Juan Wang & Chin-Chia Wu, 2017. "Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs," Journal of Scheduling, Springer, vol. 20(4), pages 313-335, August.
    2. Slotnick, Susan A., 2011. "Order acceptance and scheduling: A taxonomy and review," European Journal of Operational Research, Elsevier, vol. 212(1), pages 1-11, July.
    3. Yin, Yunqiang & Cheng, Shuenn-Ren & Cheng, T.C.E. & Wang, Du-Juan & Wu, Chin-Chia, 2016. "Just-in-time scheduling with two competing agents on unrelated parallel machines," Omega, Elsevier, vol. 63(C), pages 41-47.
    4. Ons Sassi & Ammar Oulamara, 2017. "Electric vehicle scheduling and optimal charging problem: complexity, exact and heuristic approaches," International Journal of Production Research, Taylor & Francis Journals, vol. 55(2), pages 519-535, January.
    5. Diefenbach, Heiko & Emde, Simon & Glock, Christoph H., 2023. "Multi-depot electric vehicle scheduling in in-plant production logistics considering non-linear charging models," European Journal of Operational Research, Elsevier, vol. 306(2), pages 828-848.
    6. Di Martinelly, Christine & Meskens, Nadine, 2017. "A bi-objective integrated approach to building surgical teams and nurse schedule rosters to maximise surgical team affinities and minimise nurses' idle time," International Journal of Production Economics, Elsevier, vol. 191(C), pages 323-334.
    7. Arne Herzel & Michael Hopf & Clemens Thielen, 2019. "Multistage interval scheduling games," Journal of Scheduling, Springer, vol. 22(3), pages 359-377, June.
    8. Türsel Eliiyi, Deniz & Azizoglu, Meral, 2011. "Heuristics for operational fixed job scheduling problems with working and spread time constraints," International Journal of Production Economics, Elsevier, vol. 132(1), pages 107-121, July.
    9. Yim, Seho & Hong, Sung-Pil & Park, Myoung-Ju & Chung, Yerim, 2022. "Inverse interval scheduling via reduction on a single machine," European Journal of Operational Research, Elsevier, vol. 303(2), pages 541-549.
    10. Eliiyi, Deniz Türsel & Ornek, Arslan & Karakütük, SadIk Serhat, 2009. "A vehicle scheduling problem with fixed trips and time limitations," International Journal of Production Economics, Elsevier, vol. 117(1), pages 150-161, January.
    11. Juha Puttonen & Andrei Lobov & Maria A. Cavia Soto & José L. Martinez Lastra, 2019. "Cloud computing as a facilitator for web service composition in factory automation," Journal of Intelligent Manufacturing, Springer, vol. 30(2), pages 687-700, February.
    12. Thijs Klauw & Marco E. T. Gerards & Johann L. Hurink, 2017. "Resource allocation problems in decentralized energy management," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(3), pages 749-773, July.
    13. Ge Yu & Sheldon H. Jacobson, 2020. "Primal-dual analysis for online interval scheduling problems," Journal of Global Optimization, Springer, vol. 77(3), pages 575-602, July.
    14. Jungho Park & Hadi El-Amine & Nevin Mutlu, 2021. "An Exact Algorithm for Large-Scale Continuous Nonlinear Resource Allocation Problems with Minimax Regret Objectives," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1213-1228, July.
    15. Kenneth David Strang, 2012. "Man versus math: Behaviorist exploration of post-crisis non-banking asset management," Journal of Asset Management, Palgrave Macmillan, vol. 13(5), pages 348-367, October.
    16. Pajarinen, Mika & Rouvinen, Petri & Ekeland, Anders, 2015. "Computerization Threatens One-Third of Finnish and Norwegian Employment," ETLA Brief 34, The Research Institute of the Finnish Economy.
    17. Shabtay, Dvir, 2022. "Single-machine scheduling with machine unavailability periods and resource dependent processing times," European Journal of Operational Research, Elsevier, vol. 296(2), pages 423-439.
    18. David Byrne & Carol Corrado & Daniel Sichel, 2020. "The Rise of Cloud Computing: Minding Your Ps, Qs and Ks," NBER Chapters, in: Measuring and Accounting for Innovation in the Twenty-First Century, pages 519-551, National Bureau of Economic Research, Inc.
    19. Wei Dai & Kam Yu, 2019. "Contestability in the Digital Music Player Market," Journal of Industry, Competition and Trade, Springer, vol. 19(2), pages 293-311, June.
    20. Lee, Soonhui & Turner, Jonathan & Daskin, Mark S. & Homem-de-Mello, Tito & Smilowitz, Karen, 2012. "Improving fleet utilization for carriers by interval scheduling," European Journal of Operational Research, Elsevier, vol. 218(1), pages 261-269.

    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:jsched:v:21:y:2018:i:5:d:10.1007_s10951-017-0552-y. 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.