UET-scheduling with chain-type precedence constraints

K. Jansen; G.J. Woeginger; Zhongliang Yu

doi:10.1016/0305-0548(94)00084-L

UET-scheduling with chain-type precedence constraints

K. Jansen, G.J. Woeginger, Zhongliang Yu

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

5 Citations (Scopus)

1 Downloads (Pure)

Abstract

We consider a special case of the precedence constrained scheduling problem of n unit execution time jobs on two parallel machines without preemption: the precedence constraints are chain-type and each job can be processed on only one of the two machines. We show that this problem is NP-complete in general, and we derive an approximation algorithm with constant worst case guarantee.

Original language	English
Pages (from-to)	915-920
Number of pages	6
Journal	Computers & Operations Research
Volume	22
Issue number	9
DOIs	https://doi.org/10.1016/0305-0548(94)00084-L
Publication status	Published - 1995

Access to Document

10.1016/0305-0548(94)00084-L

Cite this

@article{32da6f7840294481a8ebd3762b52d86d,

title = "UET-scheduling with chain-type precedence constraints",

abstract = "We consider a special case of the precedence constrained scheduling problem of n unit execution time jobs on two parallel machines without preemption: the precedence constraints are chain-type and each job can be processed on only one of the two machines. We show that this problem is NP-complete in general, and we derive an approximation algorithm with constant worst case guarantee.",

author = "K. Jansen and G.J. Woeginger and Zhongliang Yu",

year = "1995",

doi = "10.1016/0305-0548(94)00084-L",

language = "English",

volume = "22",

pages = "915--920",

journal = "Computers & Operations Research",

issn = "0305-0548",

publisher = "Elsevier",

number = "9",

}

TY - JOUR

T1 - UET-scheduling with chain-type precedence constraints

AU - Jansen, K.

AU - Woeginger, G.J.

AU - Yu, Zhongliang

PY - 1995

Y1 - 1995

N2 - We consider a special case of the precedence constrained scheduling problem of n unit execution time jobs on two parallel machines without preemption: the precedence constraints are chain-type and each job can be processed on only one of the two machines. We show that this problem is NP-complete in general, and we derive an approximation algorithm with constant worst case guarantee.

AB - We consider a special case of the precedence constrained scheduling problem of n unit execution time jobs on two parallel machines without preemption: the precedence constraints are chain-type and each job can be processed on only one of the two machines. We show that this problem is NP-complete in general, and we derive an approximation algorithm with constant worst case guarantee.

U2 - 10.1016/0305-0548(94)00084-L

DO - 10.1016/0305-0548(94)00084-L

M3 - Article

SN - 0305-0548

VL - 22

SP - 915

EP - 920

JO - Computers & Operations Research

JF - Computers & Operations Research

IS - 9

ER -

UET-scheduling with chain-type precedence constraints

Abstract

Access to Document

Fingerprint

Cite this