Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

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
121Kb
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