Minimization of weighted earliness and tardiness for no-wait sequence-dependent setup times flowshop scheduling problem

In this research, the no-wait flowshop sequence-dependent setup time scheduling problem with minimization of weighted earliness and tardiness penalties as the criterion, typically classified as Fm|nwt,Sijk|∑wj′Ej+wj″Tj, is investigated. A mixed integer linear programming model for the research problem is proposed. As the problem is shown to be strongly NP-hard, several metaheuristic algorithms based on tabu search (TS) and particle swarm optimization (PSO) algorithms are developed to heuristically solve the problem. A timing algorithm is generated to find the optimal schedule and calculate the objective function value of a given sequence. In order to compare the performance of the proposed algorithms, random test problems are generated and solved by all metaheuristic algorithms. Computational results show that the PSO algorithm has better performance than TS algorithm especially for the large sized problems.

► Approach the Fm|nwt,Sijk|∑wj′Ej+wj″Tj problem for the first time. ► Propose a mixed integer linear programming model for the proposed research problem. ► Propose several metaheuristic algorithms based on tabu search and particle swarm optimization for the proposed research problem. ► Propose a timing algorithm to find the optimal schedule for any sequence for the proposed research problem.