Job shop scheduling with unit processing times

N. Bansal; T. Kimbrel; M. Sviridenko

doi:10.1287/moor.1060.0189

Job shop scheduling with unit processing times

N. Bansal, T. Kimbrel, M. Sviridenko

Research output: Contribution to journal › Article › Academic › peer-review

15 Citations (Scopus)

1 Downloads (Pure)

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	https://doi.org/10.1287/moor.1060.0189
Publication status	Published - 2006

Access to Document

10.1287/moor.1060.0189

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

Cite this

@article{37bd4ae0fd5243a3be75caa31d3c64f2,

title = "Job shop scheduling with unit processing times",

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.",

author = "N. Bansal and T. Kimbrel and M. Sviridenko",

year = "2006",

doi = "10.1287/moor.1060.0189",

language = "English",

volume = "31",

pages = "381--389",

journal = "Mathematics of Operations Research",

issn = "0364-765X",

publisher = "INFORMS Institute for Operations Research and the Management Sciences",

number = "2",

}

TY - JOUR

T1 - Job shop scheduling with unit processing times

AU - Bansal, N.

AU - Kimbrel, T.

AU - Sviridenko, M.

PY - 2006

Y1 - 2006

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

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

U2 - 10.1287/moor.1060.0189

DO - 10.1287/moor.1060.0189

M3 - Article

VL - 31

SP - 381

EP - 389

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

SN - 0364-765X

IS - 2

ER -