Computationally Efficient Energy/Makespan Scheduling

Presenter: Kyle M. Tarplee
Collaborator: Ryan Friese
Collaborator: Anthony A. Maciejewski
Collaborator: Howard Jay Siegel

Problem Statement

static scheduling

single bag-of-tasks
task assigned to only one machine
machine runs one task at a time

heterogeneous tasks and machines
desire to reduce energy consumption (operating cost) and makespan
to aid decision makers

find high quality schedules for both energy and makespan
desire computationally efficient algorithms to compute Pareto fronts

Outline

linear programming lower bound
recovering a feasible allocation to form an upper bound
Pareto front generation techniques
comparison with NSGA-II
complexity and scalability

Linear Programming Lower Bound

Preliminaries

$$ \newcommand{\ETC}{\mathit{ETC}_{ij}} \newcommand{\APC}{\mathit{APC}_{ij}} \newcommand{\APCIdle}{\mathit{APC}_{\emptyset j}} \newcommand{\MSLB}{\mathit{MS}_\mathit{LB}} \newcommand{\ELB}{E_\mathit{LB}} $$

simplifying approximation: tasks are divisible among machines
$T_i$ — number of tasks of type $i$
$M_j$ — number of machines of type $j$
$x_{ij}$ — number of tasks of type $i$ assigned to machine type (group) $j$
$\ETC$ — estimated time to compute for a task of type $i$ running on a machine of type $j$
finishing time of machine group $j$ is (lower bound) $$F_j = \frac{1}{M_j} \sum_i x_{ij} \ETC$$
$\APC$ — average power consumption for a task of type $i$ running on a machine of type $j$
$\APCIdle$ — idle power consumption for a machine of type $j$

Linear Programming Lower Bound

Objective Functions

makespan (lower bound): $$\MSLB = \underset{j}{\max}{F_j}$$
energy consumed by the bag-of-tasks (lower bound): $$\begin{split} \ELB = {} & \text{execution energy} + \text{idle energy} \\ = {} & \sum_i \sum_j x_{ij} \APC \ETC + \sum_j M_j \APCIdle (\MSLB - F_j)\\ = {} & \sum_i \sum_j x_{ij} \ETC \left( \APC - \APCIdle \right) + \sum_j M_j \APCIdle \MSLB \end{split}$$
note that energy is a function of makespan when we have non-zero idle power consumption

Linear Programming Lower Bound

Bi-Objective Problem

$$ \underset{x_{ij},\,\MSLB}{\text{minimize}} \quad \begin{pmatrix} \ELB\\ \MSLB \end{pmatrix} $$ subject to:

$$\forall i$$	$$\sum_j x_{ij} = T_i$$	task constraint
$$\forall j$$	$$F_j \le \MSLB$$	makespan constraint or machine constraint
$$\forall i,j$$	$$x_{ij} \ge 0$$	assignments must be non-negative

Linear Programming Lower Bound

Lower Bound Generation

solve for $x_{ij} \in \mathbb{R}$ to obtain a lower bound

generally infeasible solution to the actual scheduling problem
a lower bound for each objective function (tight in practice)

solve for $x_{ij} \in \mathbb{Z}$ to obtain a tighter lower bound

requires branch and bound (or similar)

typically this is computationally prohibitive

still making the assumption that tasks are divisible among machines

Recovering a Feasible Allocation

Phase 1: Round Near

find $\hat{x}_{ij} \in \mathbb{Z}$ that is "near" to $x_{ij}$ while maintaining the task assignment constraint
"Near" means (for a given $i$) minimize $\parallel \hat{x}_{ij} - x_{ij} \parallel_1 = \sum_j \left| \hat{x}_{ij} - x_{ij} \right| $

for each task type (row $i$ in $\boldsymbol{x}$) do:

let $n = T_i - \sum_j \lfloor x_{ij} \rfloor$
let $f_j = x_{ij} - \lfloor x_{ij} \rfloor$ be the fractional part of $x_{ij}$
let set $K$ be the indices of the $n$ largest $f_j$
$\hat{x}_{ij} = \begin{cases} \lceil x_{ij} \rceil, & j \in K\\ \lfloor x_{ij} \rfloor, & \text{otherwise} \end{cases}$

$$ \begin{pmatrix} 3 & 0 & 9 & 11 & 0 & 0 \\ 3 & 0 & \mathbf{9.6} & 11.4 & 0 & 0 \\ 3 & 15.3 & 9.3 & \mathbf{11.4} & 0 & 0 \\ 3 & 15.2 & \textbf{9.9} & \mathbf{11.4} & 2.3 & 4.2 \end{pmatrix} \rightarrow \begin{pmatrix} 3 & 0 & 9 & 11 & 0 & 0 \\ 3 & 0 & 10 & 11 & 0 & 0 \\ 3 & 15 & 9 & 12 & 0 & 0 \\ 3 & 15 & 10 & 12 & 2 & 4 \end{pmatrix} $$

Recovering a Feasible Allocation

Phase 2: Local Assignment

given integer number of tasks for each machine type
assign tasks to actual machines within a homogeneous machine group via a greedy algorithm

for each machine group (column $j$ in $\boldsymbol{\hat{x}})$ do
longest processing time algorithm

while any tasks are unassigned:

assign longest task (irrevocably) to machine that has the earliest finish time
update machine finish time

Pareto Front Generation Procedure

step 1 weighted sum scalarization

step 1.1 find the utopia (ideal) and nadir (non-ideal) points
step 1.2 sweep $\alpha$ between 0 and 1.
- at each step solve the scalar LP problem: $$\text{min} \frac{\alpha}{\Delta \ELB} \ELB + \frac{1 - \alpha}{\Delta \MSLB} \MSLB$$
step 1.3 Remove duplicates

linear objective functions and convex constraints

convex, lower bound Pareto front

step 2 round each solution
step 3 remove duplicates
step 4 locally assign each solution
remove duplicates and dominated solutions
full allocation is an upper bound on the true Pareto front

Simulation Results

simulation setup

ETC matric derived from actual systems
9 machine types, 36 machines, 4 machines per type
30 task types, 1100 tasks, 11-75 tasks per type

Non-dominated Sorting Genetic Algorithm II

NSGA-II is another algorithm for finding the Pareto front
an adaptation of classical genetic algorithms
basic seed

min energy, min-min completion time, and random

full allocation seed

all solutions from upper bound Pareto front

Pareto Fronts

Zoomed into the knee

Lower Bound to Full Allocation

No idle power

Lower Bound to Full Allocation

10% idle power

Effect of Idle Power

Complexity

let the ETC matrix be $T \times M$
linear programming lower bound
- $T+M$ constraints
- $TM + 1$ variables
- average complexity of simplex algorithm is then $(T+M)^2 (TM+1)$
rounding step: $T (M \log M)$
local assignment step:

number of tasks to scheduler for machine group $j$ is $n_j = \sum_i x_{ij}$
worst cast complexity is $M \, \underset{j}{\max} \left(n_j \log n_j + n_j \log M_j \right)$