Makespan minimization in preemptive two machine job shops

S.V. Sevastianov; G.J. Woeginger

doi:10.1007/BF02684330

Makespan minimization in preemptive two machine job shops

S.V. Sevastianov, G.J. Woeginger

Stochastic Operations Research

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

11 Citations (Scopus)

1 Downloads (Pure)

Abstract

In this note we investigate the NP-complete problem of minimizing the makespan in a preemptive two machine job shop. We present a polynomial time approximation algorithm with worst case ratio 3/2 for this problem, and we also argue that this is the best possible result that can be derived via our line of approach.

Original language	English
Pages (from-to)	73-79
Number of pages	7
Journal	Computing
Volume	60
Issue number	1
DOIs	https://doi.org/10.1007/BF02684330
Publication status	Published - 1998

Access to Document

10.1007/BF02684330

Cite this

@article{e52d6d93032044b5b975b7c92f52fb60,

title = "Makespan minimization in preemptive two machine job shops",

abstract = "In this note we investigate the NP-complete problem of minimizing the makespan in a preemptive two machine job shop. We present a polynomial time approximation algorithm with worst case ratio 3/2 for this problem, and we also argue that this is the best possible result that can be derived via our line of approach.",

author = "S.V. Sevastianov and G.J. Woeginger",

year = "1998",

doi = "10.1007/BF02684330",

language = "English",

volume = "60",

pages = "73--79",

journal = "Computing",

issn = "0010-485X",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Makespan minimization in preemptive two machine job shops

AU - Sevastianov, S.V.

AU - Woeginger, G.J.

PY - 1998

Y1 - 1998

N2 - In this note we investigate the NP-complete problem of minimizing the makespan in a preemptive two machine job shop. We present a polynomial time approximation algorithm with worst case ratio 3/2 for this problem, and we also argue that this is the best possible result that can be derived via our line of approach.

AB - In this note we investigate the NP-complete problem of minimizing the makespan in a preemptive two machine job shop. We present a polynomial time approximation algorithm with worst case ratio 3/2 for this problem, and we also argue that this is the best possible result that can be derived via our line of approach.

U2 - 10.1007/BF02684330

DO - 10.1007/BF02684330

M3 - Article

SN - 0010-485X

VL - 60

SP - 73

EP - 79

JO - Computing

JF - Computing

IS - 1

ER -

Makespan minimization in preemptive two machine job shops

Abstract

Access to Document

Fingerprint

Cite this