Application of TSGA, a hybrid meta-heuristic model, to solve a real size problem of flow shop scheduling with changeover times in operations

Abstract

Flow shop scheduling (FSS) problems are NP-hard combinatorial optimization problems. It’s quite difficult to achieve an optimal solution for real size problems with mathematical modeling approach because of its NP-hard structure. Meta-heuristic algorithms, like Tabu Search (TS) and genetic algorithm (GA), play a major role in searching for near-optimal solutions for NP-hard optimization problems. In the case study, the current scheduling method is ineffective, and the total tardiness time of orders is still quite high. This paper develops a Tabu Search and Genetic Algorithm (TSGA) model for solving the real FSS problem, with the objective of dispatching orders more effectively than the current dispatching method. The TSGA model is a hybrid meta-heuristic model, combining TS and GA. In the model, TS is used as the platform for local search, and GA is used to support TS in global search. The performance of the model is compared with the traditional heuristic being used. The result indicates that the model is a good approach for FSS problems. However, the factors of the model are only selected empirically; therefore, the results are not particularly satisfactory. The future research is to use experimental design (DOE) to determine the model parameters to get better suboptimal results.