Job shop scheduling with unit processing times

N. Bansal, T. Kimbrel, M. Sviridenko

    Research output: Contribution to journalArticleAcademicpeer-review

    15 Citations (Scopus)
    1 Downloads (Pure)


    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 languageEnglish
    Pages (from-to)381-389
    JournalMathematics of Operations Research
    Issue number2
    Publication statusPublished - 2006


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

    Cite this