Solvable Cases of the No-Wait Flow-Shop Scheduling Problem

Abstract

The no-wait flow-shop scheduling problem (NWFSSP) with a makespan objective function is considered. As is well known, this problem is 𝒩𝒫-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 𝒩𝒫-hard. Also, it is shown that NWFSSPs with a mean completion time objective function restricted to semi-ordered processing time matrices are easily solvable.

Keywords:

• Optimization
• Scheduling
• Travelling Salesman