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

Authors: Rajesh Vanchipura; R. Sridharan

Addresses: Government Engineering College, Thrissur, Kerala – 680 009, India ' National Institute of Technology Calicut, Kerala – 673 601, India

Abstract: 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.

Keywords: operations management; flow shop scheduling; sequence dependent setup times; SDST; constructive algorithm; setup time proportion.

DOI: 10.1504/IJSOM.2013.052837

International Journal of Services and Operations Management, 2013 Vol.14 No.4, pp.421 - 444

Published online: 30 Aug 2013 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article