Impact of varying levels of setup time on the performance of algorithms for scheduling a flow shop with sequence dependent setup time

摘要

This paper presents a comparative study of two algorithms for the flow shop scheduling problem with sequence dependent setup time. The objective is to investigate the effect of setup time on makespan criterion under varying proportions of setup time. The two constructive algorithms used in the study involve a completely different approach in constructing the sequence. The first algorithm is processing time-based and the second algorithm setup time-based. Taillard benchmark flow shop problems are used for the development of benchmark problems for flow shop scheduling with sequence dependent setup time. Eight different levels of setup time matrices are developed for each problem size. The two algorithms are tested for the 960 problem instances developed. The results are analysed graphically and statistically for the varying levels of setup time. The analysis reveals that the setup time-based algorithm improves its performance when the setup time increases as a percentage of processing time. The results of statistical analysis validate the variability in performance of the two algorithms considered at different levels of setup time.