This paper examines a two-machine flowshop scheduling problem with the objective of minimizing total tardiness in an environment where setup times are treated separately from processing times and are subject to uncertainty. Setup times are modeled as interval parameters, where only their lower and upper bounds are known, reflecting practical manufacturing conditions in which setup durations may vary due to operational factors. The total tardiness performance measure is of particular importance in manufacturing systems because it is closely associated with due-date adherence and customer satisfaction. This problem has been previously studied in the literature, and several algorithms have been proposed. Building on these studies, the present paper addresses the same problem and introduces a new algorithm that explicitly incorporates bounded setup-time information into the sequencing decision. Extensive computational experiments are conducted over a wide range of problem sizes and parameter settings, and the results demonstrate that the proposed algorithm consistently outperforms the best-known existing algorithm for this problem. On average, the new approach achieves a meaningful reduction in total tardiness, and therefore the algorithm proposed in this paper is recommended for two-machine flowshop scheduling problems with uncertain setup times.

Keywords

Flowshop, total tardiness, uncertain setup times, algorithm