Quality of Move-Optimal Schedules for Minimizing the Vector Norm of the Workloads

T. Brueggemann, Johann L. Hurink

Research output: Book/ReportReportProfessional

17 Downloads (Pure)

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 languageUndefined
Place of PublicationEnschede
PublisherToegepaste Wiskunde
Number of pages14
Publication statusPublished - 2006

Publication series

NameApplied Mathematics Memoranda
PublisherDepartment 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.