We address a no-wait flowshop scheduling problem where the setup times are treated as separate and uncertain. The objective is to minimize maximum lateness which is one of the most essential performance measures for customer satisfaction and loss of goodwill. The considered problem is common in manufacturing environments like metal, food and pharmaceutical industries where some of the operations must not be interrupted. In many cases, setup time, the time required to setup a resource, is either ignored or assumed to be constant. However, these assumptions might lead to inefficient planning. Therefore, we relax these assumptions and consider uncertain but bounded setup times. The problem has been addressed in the scheduling literature where dominance relations were presented. In the current paper, we propose new dominance relations and show that the newly proposed dominance relations are around 100% more efficient than the existing. One of the main strengths of the newly proposed dominance relations is that their performances get better as the uncertainty in setup time increases. These dominance relations can also be used for initial sequence generation or improving the final solution as well as finding the optimal solutions for small size problems. Moreover, we also propose new and efficient heuristics as potential solutions for the problem and also for similar problems. Based on extensive computational experiments, we show that our new heuristics are around 90% more efficient than the existing ones in the literature under the same computational time.

Keywords
Heuristics, Flowshop scheduling, Dominance relations, Setup times and maximum lateness.