Presenter: Kyle M. Tarplee

Collaborator: Ryan Friese

Collaborator: Anthony A. Maciejewski

Collaborator: Howard Jay Siegel

- 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

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

- 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$ —
__e__stimated__t__ime to__c__ompute 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$

- 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

$$ \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 |

- 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

- 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}$

- 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

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

- 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

- 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

- 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

/