Open Access iconOpen Access

ARTICLE

crossmark

A Strengthened Dominance Relation NSGA-III Algorithm Based on Differential Evolution to Solve Job Shop Scheduling Problem

Liang Zeng1,2, Junyang Shi1, Yanyan Li1, Shanshan Wang1,2,*, Weigang Li3

1 School of Electrical and Electronic Engineering, Hubei University of Technology, Wuhan, 430068, China
2 Hubei Key Laboratory for High-Efficiency Utilization of Solar Energy and Operation Control of Energy Storage System, Hubei University of Technology, Wuhan, 430068, China
3 School of Information Science and Engineering, Wuhan University of Science and Technology, Wuhan, 430081, China

* Corresponding Author: Shanshan Wang. Email: email

(This article belongs to this Special Issue: Intelligent Computing Techniques and Their Real Life Applications)

Computers, Materials & Continua 2024, 78(1), 375-392. https://doi.org/10.32604/cmc.2023.045803

Abstract

The job shop scheduling problem is a classical combinatorial optimization challenge frequently encountered in manufacturing systems. It involves determining the optimal execution sequences for a set of jobs on various machines to maximize production efficiency and meet multiple objectives. The Non-dominated Sorting Genetic Algorithm III (NSGA-III) is an effective approach for solving the multi-objective job shop scheduling problem. Nevertheless, it has some limitations in solving scheduling problems, including inadequate global search capability, susceptibility to premature convergence, and challenges in balancing convergence and diversity. To enhance its performance, this paper introduces a strengthened dominance relation NSGA-III algorithm based on differential evolution (NSGA-III-SD). By incorporating constrained differential evolution and simulated binary crossover genetic operators, this algorithm effectively improves NSGA-III’s global search capability while mitigating premature convergence issues. Furthermore, it introduces a reinforced dominance relation to address the trade-off between convergence and diversity in NSGA-III. Additionally, effective encoding and decoding methods for discrete job shop scheduling are proposed, which can improve the overall performance of the algorithm without complex computation. To validate the algorithm’s effectiveness, NSGA-III-SD is extensively compared with other advanced multi-objective optimization algorithms using 20 job shop scheduling test instances. The experimental results demonstrate that NSGA-III-SD achieves better solution quality and diversity, proving its effectiveness in solving the multi-objective job shop scheduling problem.

Keywords


Cite This Article

L. Zeng, J. Shi, Y. Li, S. Wang and W. Li, "A strengthened dominance relation nsga-iii algorithm based on differential evolution to solve job shop scheduling problem," Computers, Materials & Continua, vol. 78, no.1, pp. 375–392, 2024.



cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 114

    View

  • 64

    Download

  • 0

    Like

Share Link