Online algorithm for parallel job scheduling and strip packing

Hurink, J.L. and Paulus, J.J. (2008) Online algorithm for parallel job scheduling and strip packing. In: 5th International Workshop on Approximation and Online Algorithms, WAOA 2007, 11-12 Oct, 2007, Eilat, Israel.

PDF
Restricted to UT campus only: Request a copy
451Kb

Abstract:	We consider the online scheduling problem of parallel jobs on parallel machines, $P\|\mathrm{online − list},m_j \|C_{\mathrm{max}}$ . For this problem we present a 6.6623-competitive algorithm. This improves the best known 7- competitive algorithm for this problem. The presented algorithm also applies to the special case where machines are ordered on a line and only adjacent machines can be assigned to a job and, therefore, also to online orthogonal strip packing. Since previous results for online orthogonal strip packing assume bounded rectangles, the presented algorithm is the first with a constant competitive ratio.
Item Type:	Conference or Workshop Item
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/62190
Official URL:	http://dx.doi.org/10.1007/978-3-540-77918-6_6
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 250883