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

[img] PDF
Restricted to UT campus only
: Request a copy
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
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page