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

• DOI: 10.1007/s10878-011-9378-2
• Publication Date: 2011-01-18T13:24:57Z
• Authors: Wenchang Luo; Lin Chen; Guochuan Zhang
• Keywords: 0211 other engineering and technologies; 02 engineering and technology

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.