Improved online algorithms for parallel job scheduling and strip packing

Share/Save/Bookmark

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

[img] PDF
Restricted to UT campus only
: Request a copy
347kB
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:
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

 

Repository Staff Only: item control page