Energy Aware Scheduling for Unrelated Parallel Machines
Authors:
- Eric AngelEAEric Angel
- Evripidis BampisEBEvripidis Bampis
- Fadi KacemFKFadi Kacem
- 1 November 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 533-540
Abstract
We consider the problem of energy aware scheduling of a set of jobs on a set of unrelated parallel machines with the average weighted completion time plus energy objective. The processing time and the energy consumption of the jobs are machine and speed dependent. Also, every job is subject to a machine-dependent release date. Firstly, we aim to find a non-preemptive schedule of the jobs minimizing the average weighted completion time plus energy, and we propose a randomized approximation algorithm that we derandomize obtaining a deterministic approximation algorithm. We then consider the budget variant of the problem where the objective is to minimize the average completion time while the total energy consumption does not exceed a given budget.Keywords
This publication has 32 references indexed in Scilit:
- Optimizing throughput and energy in online deadline schedulingACM Transactions on Algorithms, 2009
- Deterministic load balancing in computer networks2002
- Scheduling Unrelated Machines by Randomized RoundingSIAM Journal on Discrete Mathematics, 2002
- A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines2001
- Convex quadratic and semidefinite programming relaxations in schedulingJournal of the ACM, 2001
- A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machinesJournal of Scheduling, 1999
- A Review of Machine Scheduling: Complexity, Algorithms and Approximability1998
- An approximation algorithm for the generalized assignment problemMathematical Programming, 1993
- Randomized rounding: A technique for provably good algorithms and algorithmic proofsCombinatorica, 1987
- Scheduling independent tasks to reduce mean finishing timeCommunications of the ACM, 1974