2019/09/29 by Antonios P. Antoniadis, Antoniadis, Antonios, Naveen Garg +5
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1909.13345
openalex publication_date 2019/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given n jobs with release dates, deadlines and processing times we consider the problem of scheduling them on m parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires Q units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem.