Abstract
In this paper we study the time complexities of some two- and three-stage no-wait flowshop makespan scheduling problems where, in some stage, all the jobs require a constant processing time and the stage may consist of parallel identical machines. Polynomial time algorithms are presented for certain problems, while several others are proved to be strongly NP-complete.
Original language | English |
---|---|
Pages (from-to) | 367-378 |
Number of pages | 12 |
Journal | Production and Operations Management |
Volume | 9 |
Issue number | 4 |
Publication status | Published - 1 Jan 2000 |
Externally published | Yes |
Keywords
- Algorithms
- Complexity
- Flowshop scheduling
- Makespan minimization
ASJC Scopus subject areas
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Management of Technology and Innovation