Hybrid-discrete multi-objective particle swarm optimization for multi-objective job-shop scheduling

Many real-world production scheduling problems involve the simultaneous optimization of multiple conflicting objectives that are challenging to solve without the aid of powerful optimization techniques. This includes the multi-objective Job-shop Scheduling Problem (JSP), which is among the most difficult to solve owing to the existence of an intractably large, highly complex solution space. Particle Swarm Optimization (PSO) is a population-based metaheuristic that possesses many advantages compared to other metaheuristics in solving scheduling problems. However, due to the complex nature of the multi-objective JSP, a single approach like PSO is not sufficient to explore the search space effectively owing to its shortcoming such as the tendency to become trapped in local optima. Besides, since PSO operates in the continuous domain, it cannot be applied directly to solve a discrete problem like the JSP efficiently. This research first proposes an improved continuous MOPSO to address the rapid clustering problem that exists in the basic PSO algorithm using three improvement strategies: re-initialization of particles, systematic switch of best solutions and mutation on global best selection. In order to establish an efficient mapping between the particle’s position in the continuous MOPSO and the scheduling solution in the JSP, this research proposes the JSP to be adopted within a discrete MOPSO through a modified solution representation using the permutation-based representation and a modified setup of the particle’s position and velocity. The discrete MOPSO also includes the modified maximin fitness function to promote solution diversity in the selection of global best solutions. In order to accomplish better performance by improving the search quality and efficiency of the discrete MOPSO, this research proposes a hybrid with the Diversification Generation Method in Scatter Search, the non-dominated sorting mechanism in non-dominated sorting Genetic Algorithm II (NSGA-II) and the local search mechanism in Tabu Search. The experimentations of the proposed algorithm are conducted using existing benchmark instances and a published case study on an energy-efficient job-shop model. The computational results are evaluated against other optimization techniques published in the literature. From the results, it is found that the proposed improved algorithm is effective in solving the benchmark instances compared to when no improvement is implemented and with a reasonable increase in computational costs. It is also discovered that the hybrid-discrete MOPSO (HD-MOPSO) algorithm manages to obtain higher values in the performance metrics consisting of non-dominance ratio and hypervolume compared to the competing algorithms. For the non-dominance ratio, HD-MOPSO is able to contribute 89% to 100% of solutions to the reference Pareto front. For the hypervolume values, HD-MOPSO manages to obtain a minimum of 1.0172 to 1.2862 out of the optimum value of 1.44. As higher values of metrics indicate better performance, HD-MOPSO thus outperforms the competing algorithms in solving the benchmark instances and the published case study. For these types of problems, the proposed algorithm is demonstrated to be capable of producing higher percentages of solutions in the overall non-dominated set with better quality in terms of convergence and diversity than those obtained by the competing algorithms