Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

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

Share/Save/Bookmark

Brueggemann, T. and Hurink, J.L. (2006) Quality of Move-Optimal Schedules for Minimizing the Vector Norm of the Workloads. [Report]

[img]
Preview
PDF
197Kb
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).
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/66527
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 238242