Online Algorithms for Parallel Job Scheduling and Strip Packing

Share/Save/Bookmark

Hurink, J.L. and Paulus, J.J. (2007) Online Algorithms for Parallel Job Scheduling and Strip Packing. [Report]

[img] PDF
Restricted to UT campus only

124kB
Abstract:We consider the online scheduling problem of parallel jobs on parallel machines, $P|online{−}list,m_j |C_{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 problem 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 these problems assume bounded job length, the presented algorithm is the first with a constant competitive ratio.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/61849
Publisher URL:http://beta.ieis.tue.nl/node/1205
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 241784