Improved online algorithms for parallel job scheduling and strip packing

Hurink, J.L. and Paulus, J.J. (2011) Improved online algorithms for parallel job scheduling and strip packing. Theoretical Computer Science, 412 (7). pp. 583-593. ISSN 0304-3975

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

Abstract:	In this paper we consider the online scheduling of jobs which require processing on a number of machines simultaneously. These jobs are presented to a decision maker one by one, where the next job becomes known as soon as the current job is scheduled. The objective is to minimize the makespan (P\|online - list,m_j\|C_max). We present a 6.6623-competitive algorithm for this online problem, improving the best known algorithm, which is 7-competitive. The presented algorithm also applies to the online orthogonal strip packing problem. Since the previous results for this problem assume bounded rectangles, the presented algorithm is the first with a constant competitive ratio for the general online orthogonal strip packing problem. Furthermore, for the special case with 3 machines we give a 2.8-competitive algorithm, improving upon the 3-competitive greedy algorithm.
Item Type:	Article
Copyright:	© 2011 Elsevier
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/76016
Official URL:	http://dx.doi.org/10.1016/j.tcs.2009.05.033
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page