Approximation schemes for two-machine flow shop scheduling with two agents

Wenchang Luo; Lin Chen; Guochuan Zhang

doi:10.1007/s10878-011-9378-2

Approximation schemes for two-machine flow shop scheduling with two agents

Wenchang Luo, Lin Chen, Guochuan Zhang

Computer Science

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

27 Scopus citations

Abstract

In this paper we consider two-machine flow shop scheduling with two agents. Two models are investigated. One is the weighted-sum optimization model and the other is the constrained optimization model. For the former, we show that it is weakly NP-hard and propose a fully polynomial time approximation scheme. For the latter, we also show the problem is weakly NP-hard.With violating the constraint a factor of ε a fully polynomial time approximation scheme is provided.

Original language	English
Pages (from-to)	229-239
Number of pages	11
Journal	Journal of Combinatorial Optimization
Volume	24
Issue number	3
DOIs	https://doi.org/10.1007/s10878-011-9378-2
State	Published - Oct 2012

Keywords

Approximation scheme
Flow shop
Scheduling with two agents

Access to Document

10.1007/s10878-011-9378-2

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Approximation schemes for two-machine flow shop scheduling with two agents'. Together they form a unique fingerprint.

Cite this

@article{0768f334134b40ac9e0fa81ec26675a1,

title = "Approximation schemes for two-machine flow shop scheduling with two agents",

abstract = "In this paper we consider two-machine flow shop scheduling with two agents. Two models are investigated. One is the weighted-sum optimization model and the other is the constrained optimization model. For the former, we show that it is weakly NP-hard and propose a fully polynomial time approximation scheme. For the latter, we also show the problem is weakly NP-hard.With violating the constraint a factor of ε a fully polynomial time approximation scheme is provided.",

keywords = "Approximation scheme, Flow shop, Scheduling with two agents",

author = "Wenchang Luo and Lin Chen and Guochuan Zhang",

year = "2012",

month = oct,

doi = "10.1007/s10878-011-9378-2",

language = "English",

volume = "24",

pages = "229--239",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

number = "3",

}

TY - JOUR

T1 - Approximation schemes for two-machine flow shop scheduling with two agents

AU - Luo, Wenchang

AU - Chen, Lin

AU - Zhang, Guochuan

PY - 2012/10

Y1 - 2012/10

N2 - In this paper we consider two-machine flow shop scheduling with two agents. Two models are investigated. One is the weighted-sum optimization model and the other is the constrained optimization model. For the former, we show that it is weakly NP-hard and propose a fully polynomial time approximation scheme. For the latter, we also show the problem is weakly NP-hard.With violating the constraint a factor of ε a fully polynomial time approximation scheme is provided.

AB - In this paper we consider two-machine flow shop scheduling with two agents. Two models are investigated. One is the weighted-sum optimization model and the other is the constrained optimization model. For the former, we show that it is weakly NP-hard and propose a fully polynomial time approximation scheme. For the latter, we also show the problem is weakly NP-hard.With violating the constraint a factor of ε a fully polynomial time approximation scheme is provided.

KW - Approximation scheme

KW - Flow shop

KW - Scheduling with two agents

UR - http://www.scopus.com/inward/record.url?scp=84867097831&partnerID=8YFLogxK

U2 - 10.1007/s10878-011-9378-2

DO - 10.1007/s10878-011-9378-2

M3 - Article

AN - SCOPUS:84867097831

VL - 24

SP - 229

EP - 239

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 3

ER -