Minimizing tardiness and makespan for distributed heterogeneous unrelated parallel machine scheduling by knowledge and Pareto-based memetic algorithm

This work aims to deal with the distributed heterogeneous unrelated parallel machine scheduling prob-lem (DHUPMSP) with minimizing total tardiness (TDD) and makespan. To solve this complex combina-torial optimization problem, this work proposed a knowledge and Pareto-based memetic algorithm (KPMA) which contains the following features: 1) four heuristic rules are designed including the shortest processing time rule, the minimum factory workload rule, the minimum machine finish time rule, and the earliest due date rule. Meanwhile, a hybrid heuristic initialization is developed to construct a popu-lation with great convergence and diversity; 2) four problem feature-based heuristic neighborhood struc-tures are designed to increase the success rate of local search; and 3) a simple elite strategy is developed to enhance the usage of historical elite solutions. Finally, to evaluate the performance of KMPA, it is com-pared to five state-of-art and run on 20 instances with different scales. The results of numerical experi-ments show that the proposed hybrid heuristic initialization can efficiently save computation resources to improve the initialized convergence. In addition, the knowledge-based neighborhood structures can vastly accelerate exploration. Moreover, the elite strategy can efficiently improve the diversity of the final non-dominated solutions set. The proposed KPMA has better performance than the state-of-art and has a strong ability to solve DHUPMSP.(c) 2023 THE AUTHORS. Published by Elsevier BV on behalf of Faculty of Computers and Artificial Intel-ligence, Cairo University. This is an open access article under the CC BY-NC-ND license (http://creative-commons.org/licenses/by-nc-nd/4.0/).

Automated summary

This work aims to solve the distributed heterogeneous unrelated parallel machine scheduling problem with minimizing total tardiness and makespan. A knowledge and Pareto-based memetic algorithm (KPMA) is proposed, which includes heuristic rules, heuristic neighborhood structures, and an elite strategy. Numerical experiments show that KPMA has better performance and a strong ability to solve DHUPMSP compared to other state-of-art methods.