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

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.