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

Wenchang Luo, Lin Chen, Guochuan Zhang

Research output: Contribution to journalArticlepeer-review

29 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 languageEnglish
Pages (from-to)229-239
Number of pages11
JournalJournal of Combinatorial Optimization
Volume24
Issue number3
DOIs
StatePublished - Oct 2012

Keywords

  • Approximation scheme
  • Flow shop
  • Scheduling with two agents

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