### Abstract

We consider randomized algorithms for the preemptive job shop problem, or equivalently, the case in which all operations have unit length. We give an a-approximation for the case of two machines where alpha <1.45, an improved approximation ratio of O(log m/log log m) for an arbitrary number m of machines, and the first (2 + epsilon) -approximation for a constant number of machines. The first result is via an approximation algorithm for a string matching problem that is of independent interest.

Original language | English |
---|---|

Pages (from-to) | 381-389 |

Journal | Mathematics of Operations Research |

Volume | 31 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2006 |

## Fingerprint Dive into the research topics of 'Job shop scheduling with unit processing times'. Together they form a unique fingerprint.

## Cite this

Bansal, N., Kimbrel, T., & Sviridenko, M. (2006). Job shop scheduling with unit processing times.

*Mathematics of Operations Research*,*31*(2), 381-389. https://doi.org/10.1287/moor.1060.0189