@inproceedings{42df28972dca4dafad010c88e798883f,

title = "Online algorithm for parallel job scheduling and strip packing",

abstract = "We consider the online scheduling problem of parallel jobs on parallel machines, $P|\mathrm{online − list},m_j |C_{\mathrm{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 special case 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 online orthogonal strip packing assume bounded rectangles, the presented algorithm is the first with a constant competitive ratio.",

keywords = "METIS-250883, EWI-12000, IR-62190",

author = "Hurink, {Johann L.} and J.J. Paulus",

note = "10.1007/978-3-540-77918-6_6 ; null ; Conference date: 11-10-2007 Through 12-10-2007",

year = "2008",

month = feb,

doi = "10.1007/978-3-540-77918-6_6",

language = "Undefined",

isbn = "978-3-540-77917-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "67--74",

booktitle = "5th International Workshop on Approximation and Online Algorithms, WAOA 2007",

}