# Computationally Efficient Energy/Makespan Scheduling

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

## Problem Statement

• static scheduling
• task assigned to only one machine
• machine runs one task at a time
• 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

• 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
• 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

## 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)$
• complexity of all steps is dominated by either
• linear programming solver
• local assignment
• complexity of LP is independent of the number tasks and machines
• depends only on the number of task types and machine types

## Contributions:

• algorithms to compute
• tight lower bounds on the energy and makespan
• quickly recovers near optimal feasible solutions
• high quality bi-objective Pareto fronts
• evaluation of the scaling properties of the proposed algorithms
• addition of idle power consumption to the formulation of the energy/makespan problem

## Conclusions

• linear programming approach to Pareto front generation is efficient, accurate, and practical
• bound is tight when:
• a small percentage of tasks are divided
• a large number of tasks assigned to each machine group and individual machine
• asymptotic solution quality and runtime are very reasonable

/