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

Abstract

This work aims to deal with the distributed heterogeneous unrelated parallel machine scheduling problem (DHUPMSP) with minimizing total tardiness (TDD) and makespan. To solve this complex combinatorial 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 population with great convergence and diversity; 2) four problem feature-based heuristic neighborhood structures 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 compared to five state-of-art and run on 20 instances with different scales. The results of numerical experiments 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.

Keywords

• Distributed heterogeneous factory
• Unrelated parallel machine scheduling
• Memetic algorithm
• Knowledge-based heuristic strategies
• Multi-objective optimization