A new hybrid multi-objective Pareto archive PSO algorithm for a bi-objective job shop scheduling problem

This paper presents a new mathematical model for a bi-objective job shop scheduling problem with sequence-dependent setup times and ready times that minimizes the weighted mean flow time (F¯w) and total penalties of tardiness and earliness (E/T). Obtaining an optimal solution for this complex problem especially in large-sized problem instances within reasonable computational time is cumbersome. Thus, we propose a new multi-objective Pareto archive particle swarm optimization (PSO) algorithm combined with genetic operators as variable neighborhood search (VNS). Furthermore, we use a character of scatter search (SS) to select new swarm in each iteration in order to find Pareto optimal solutions for the given problem. Some test problems are examined to validate the performance of the proposed Pareto archive PSO in terms of the solution quality and diversity level. In addition, the efficiency of the proposed Pareto archive PSO, based on various metrics, is compared with two prominent multi-objective evolutionary algorithms, namely NSGA-II and SPEA-II. Our computational results show the superiority of our proposed algorithm to the foregoing algorithms, especially for the large-sized problems.

Research highlights► Presenting a novel mathematical model for a bi-objective job shop scheduling problem with sequence-dependent setup times and ready times. ► Proposing a new multi-objective Pareto archive particle swarm optimization (PSO) algorithm combined with genetic operators as variable neighborhood search (VNS). ► Comparing the proposed Pareto archive PSO with two we-known multi-objective evolutionary algorithms, namely NSGA-II and SPEA-II. ► Using three comparison metrics, namely Quality metric, Spacing metric and Diversification metric in order to validate the efficiency of the proposed PSO.