TY - JOUR
T1 - Approximation schemes for two-machine flow shop scheduling with two agents
AU - Luo, Wenchang
AU - Chen, Lin
AU - Zhang, Guochuan
N1 - Funding Information:
Research supported in part by NSFC (10971192).
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 -