• Energy-efficient scheduling: classification, bounds, and algorithms

    • Fulltext

       

        Click here to view fulltext PDF


      Permanent link:
      https://www.ias.ac.in/article/fulltext/sadh/046/0046

    • Keywords

       

      Scheduling; energy efficiency; approximation algorithms; distributed systems; computational complexity.

    • Abstract

       

      The problem of attaining energy efficiency in distributed systems is of importance, but a general, non-domain-specific theory of energy-minimal scheduling is far from developed. In this paper, we classify the problems of energy-minimal scheduling and present theoretical foundations of the same. We derive results concerning energy-minimal scheduling of independent jobs in a distributed system with functionally similar machines with different working and idle power ratings. The machines considered in our system can have identical as well as different speeds. If the jobs can be divided into arbitrary parts, we show that the minimum-energy schedule can be generated in linear time and give exact scheduling algorithms. For the cases where jobs are non-divisible, we prove that the scheduling problems are NP-hard and also give approximation algorithmsfor the same along with their bounds.

    • Graphical Abstract

       

    • Author Affiliations

       

      PRAGATI AGRAWAL1 SHRISHA RAO2

      1. Department of Computer Science and Engineering, Maulana Azad National Institute of Technology, Bhopal, India
      2. International Institute of Information Technology Bangalore, Bangalore, India
    • Dates

       
  • Sadhana | News

    • Editorial Note on Continuous Article Publication

      Posted on July 25, 2019

      Click here for Editorial Note on CAP Mode

© 2021-2022 Indian Academy of Sciences, Bengaluru.