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

Authors
Lin, BMT
Citation
Bmt. Lin, The strong NP-hardness of two-stage flowshop scheduling with a common second-stage machine, COMPUT OPER, 26(7), 1999, pp. 695-698
Citations number
3
Categorie Soggetti
Engineering Management /General
Journal title
COMPUTERS & OPERATIONS RESEARCH
ISSN journal
03050548 → ACNP
Volume
26
Issue
7
Year of publication
1999
Pages
695 - 698
Database
ISI
SICI code
0305-0548(199906)26:7<695:TSNOTF>2.0.ZU;2-2
Abstract
The problem of interest is to schedule two types of jobs on a two-stage flo wshop with a common second-stage machine so as to minimize the makespan. Th is problem was previously known to be NP-hard in the ordinary sense. In thi s note, we give a proof for the strong NP-hardness. (C) 1999 Elsevier Scien ce Ltd. All rights reserved.