## Abstract

We study the problem of scheduling a set of jobs with release dates, deadlines and processing requirements (or works) on parallel speed scalable processors so as to minimize the total energy consumption. We consider that both preemptions and migrations of jobs are allowed. For this problem, there exists an optimal polynomial-time algorithm which uses as a black box an algorithm for linear programming. Here, we formulate the problem as a convex program and we propose a combinatorial polynomial-time algorithm which is based on finding maximum flows. Our algorithm runs in O(nf(n) log U) time, where n is the number of jobs, U is the range of all possible values of processors’ speeds divided by the desired accuracy and f(n) is the time needed for computing a maximum flow in a layered graph with O(n) vertices.

Original language | English |
---|---|

Pages (from-to) | 1266-1282 |

Number of pages | 17 |

Journal | JOURNAL OF COMBINATORIAL OPTIMIZATION |

Volume | 37 |

Issue number | 4 |

Early online date | 12 Oct 2018 |

DOIs | |

Publication status | Published - 1 May 2019 |

## Keywords

- Convex programming
- Energy efficient scheduling
- Network flows
- Speed scaling