### 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.

Original language | Undefined |
---|---|

Title of host publication | 5th International Workshop on Approximation and Online Algorithms, WAOA 2007 |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 67-74 |

Number of pages | 8 |

ISBN (Print) | 978-3-540-77917-9 |

DOIs | |

Publication status | Published - Feb 2008 |

Event | 5th International Workshop on Approximation and Online Algorithms 2007 - Eilat, Israel Duration: 11 Oct 2007 → 12 Oct 2007 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Volume | 4927 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 5th International Workshop on Approximation and Online Algorithms 2007 |
---|---|

Abbreviated title | WAOA 2007 |

Country | Israel |

City | Eilat |

Period | 11/10/07 → 12/10/07 |

### Keywords

- METIS-250883
- EWI-12000
- IR-62190

## Cite this

Hurink, J. L., & Paulus, J. J. (2008). Online algorithm for parallel job scheduling and strip packing. In

*5th International Workshop on Approximation and Online Algorithms, WAOA 2007*(pp. 67-74). [10.1007/978-3-540-77918-6_6] (Lecture Notes in Computer Science; Vol. 4927). Berlin: Springer. https://doi.org/10.1007/978-3-540-77918-6_6