The strong NP-hardness of two-stage flowshop scheduling with a common second-stage machine

Miao-Tsong Lin*

*Corresponding author for this work

Research output: Contribution to journalArticle

21 Scopus citations

Abstract

The problem of interest is to schedule two types of jobs on a two-stage flowshop with a common second-stage machine so as to minimize the makespan. This problem was previously known to be NP-hard in the ordinary sense. In this note, we give a proof for the strong NP-hardness. Scope and purpose Two different products are to be processed on two different machines but they must be then processed by a common machine, say for final testing. Given two sets of jobs, the goal is to find a production schedule achieving the shortest completion time. In this note, we establish the inherent intractability of the problem.

Original languageEnglish
Pages (from-to)695-698
Number of pages4
JournalComputers and Operations Research
Volume26
Issue number7
DOIs
StatePublished - 1 Jul 1999

Fingerprint Dive into the research topics of 'The strong NP-hardness of two-stage flowshop scheduling with a common second-stage machine'. Together they form a unique fingerprint.

  • Cite this