A multi-machine bicriteria flow shop scheduling with sequence dependent setup time

Bicriteria flow shop scheduling problem with sequence dependent setup time (BPFSSP/SDST) is addressed in this paper. The objective of scheduling problem is to minimise weighted sum of makespan and system utilisation time, when both criteria are equal weighted. To solve the referred scheduling problem in small size machine-job environment, a mixed-integer programming model is developed and implemented. Since permutation flow shop scheduling problem with SDST is NP-complete in nature, therefore, the heuristic approach based on Nawaz, Enscore, Ham (NEH) neighbourhood structure and metaheuristic approach of hybrid iterated greedy algorithm with delay time, are proposed and implemented to optimise aforementioned scheduling bicriteria. The computation experiment is carried out to evaluate the performance of all developed heuristics and metaheuristics on varying size job-machine environment. The comparative analysis reported with response variable average relative percentage deviation (ARPD) verifies the effectiveness of proposed computation techniques over existing one's in solving the referred scheduling problem.