### Abstract

We study the problem of minimizing the vector norm $||\cdot||_p$ of the workloads. We examine move-optimal assignments and prove a performance guarantee of
$\frac{2^p-1}{p} \cdot \left(\frac{p-1}{2^p-2}\right)^{\frac{p-1}{p}},$
for any integer $p>1$ and moreover, we show that this guarantee is tight.
Additionally, we consider assignments obtained by applying the LPT-heuristic of Graham (1969). We prove that an LPT-assignment has a performance guarantee of
$\frac{3^p-2^p}{p} \cdot \left(\frac{p-1}{2 \cdot 3^p - 3 \cdot 2^p}\right)^{\frac{p-1}{p}},$
which reproves a result of Chandra and Wong (1975).

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | Toegepaste Wiskunde |

Number of pages | 14 |

Publication status | Published - 2006 |

### Publication series

Name | Applied Mathematics Memoranda |
---|---|

Publisher | Department of Applied Mathematics, University of Twente |

No. | 1808 |

ISSN (Print) | 0169-2690 |

### Keywords

- EWI-7596
- METIS-238242
- IR-66527
- MSC-90B35

## Cite this

Brueggemann, T., & Hurink, J. L. (2006).

*Quality of Move-Optimal Schedules for Minimizing the Vector Norm of the Workloads*. (Applied Mathematics Memoranda; No. 1808). Enschede: Toegepaste Wiskunde.