# Online Algorithms for Parallel Job Scheduling and Strip Packing

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

PDF
Restricted to UT campus only 124kB |

Abstract: | We consider the online scheduling problem of parallel jobs on parallel machines, . 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