Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)


In this article, we consider the concurrent open shop scheduling problem to minimize the total weighted completion time. When the number of machines is arbitrary, the problem has been shown to be inapproximable within a factor of 4/3 - Îμ for any Îμ > 0 if the unique games conjecture is true in the literature. We propose a polynomial time approximation scheme for the problem under the restriction that the number of machines is fixed. Naval Research Logistics, 2011
Original languageEnglish
Pages (from-to)763-770
Number of pages8
JournalNaval Research Logistics
Issue number8
Publication statusPublished - 1 Dec 2011


  • approximation scheme
  • concurrent open shop
  • scheduling

ASJC Scopus subject areas

  • Ocean Engineering
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this