### Abstract

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

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

Place of Publication | Berlin |

Publisher | Springer Verlag |

Pages | 67-74 |

Number of pages | 8 |

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

DOIs | |

State | Published - Feb 2008 |

Event | 5th International Workshop on Approximation and Online Algorithms 2007 - Eilat, Israel |

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

### Fingerprint

### Keywords

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

### Cite this

*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 Verlag. DOI: 10.1007/978-3-540-77918-6_6

}

*5th International Workshop on Approximation and Online Algorithms, WAOA 2007.*, 10.1007/978-3-540-77918-6_6, Lecture Notes in Computer Science, vol. 4927, Springer Verlag, Berlin, pp. 67-74, 5th International Workshop on Approximation and Online Algorithms 2007, Eilat, Israel, 11-12 October. DOI: 10.1007/978-3-540-77918-6_6

**Online algorithm for parallel job scheduling and strip packing.** / Hurink, Johann L.; Paulus, J.J.

Research output: Scientific - peer-review › Conference contribution

TY - CHAP

T1 - Online algorithm for parallel job scheduling and strip packing

AU - Hurink,Johann L.

AU - Paulus,J.J.

N1 - 10.1007/978-3-540-77918-6_6

PY - 2008/2

Y1 - 2008/2

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

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

KW - METIS-250883

KW - EWI-12000

KW - IR-62190

U2 - 10.1007/978-3-540-77918-6_6

DO - 10.1007/978-3-540-77918-6_6

M3 - Conference contribution

SN - 978-3-540-77917-9

T3 - Lecture Notes in Computer Science

SP - 67

EP - 74

BT - 5th International Workshop on Approximation and Online Algorithms, WAOA 2007

PB - Springer Verlag

ER -