SOLVABLE CASES OF THE NO-WAIT FLOWSHOP SCHEDULING PROBLEM

The no-wait flow-shop scheduling problem (NWFSSP) with a makespan objective function is considered. As is well known, this problem is NP-hard for three or more machines. Therefore, it is interesting to consider special cases, i.e. special structured processing time matrices, that allow polynomial time solution algorithms. Furthermore, it is well known that the NWFSSP with a makespan objective function can be formulated as a travelling salesman problem (TSP). It is observed that special structured processing time matrices for the NWFSSP lead to special structured distance matrices for which the TSP is polynomially solvable. Using this observation, it is shown that some NWFSSPs with fixed processing times on all except two machines are well solvable while the others are conjectured to be NP-hard. Also, it is shown that NWFSSPs with a mean completion time objective function restricted to semi-ordered processing time matrices are easily solvable.