Sequence-dependent flow shop scheduling problem minimising the number of tardy jobs

Abstract

Flow shop scheduling problems with sequence-dependent setup times and minimising the number of tardy jobs as the criterion (F_m |prmu, S_ijk |ΣU_j ) are considered in this research. A mixed-integer linear programming model is developed for the research problem. Since the proposed research problem has been proven to be NP-hard, several meta-heuristic algorithms based on tabu search (TS) and the imperialist competitive algorithm (ICA) are proposed to heuristically solve the problem. In order to find the best meta-heuristic algorithm, random test problems, ranging in size from small, medium, to large, are generated and solved by the meta-heuristic algorithms. Then, a detailed statistical experiment based on the split-plot design is performed to find the best meta-heuristic algorithm. The results of the experiment show that the performance of ICA is worse than the other algorithms for small- and medium-sized problems. The hybrid of ICA and the TS algorithm provides better performance than the other proposed algorithms for large-sized problems.

Keywords:

• flow shop
• mathematical modelling
• sequence dependent setup time
• tabu search
• minimising the number of tardy jobs
• imperialist competitive