An estimation of distribution algorithm based on the Dirichlet distribution for the flexible job shop scheduling problem

Abstract

This article proposes a novel Estimation of Distribution Algorithm (EDA), named DEDA, which leverages the Dirichlet distribution to address the Flexible Job Shop Scheduling Problem (FJSSP). The FJSSP is a complex combinatorial optimization problem in which jobs consist of multiple operations processed on various feasible machines under sequence constraints. Complexity of FJSSP motivates the development of efficient algorithms. This research outlines the problem, provides a comprehensive review of diverse methods applied to the FJSSP, and offers an in-depth discussion of solution representations, local search strategies, dynamic environment handling, and multi-objective approaches. Evaluation metrics and benchmarking datasets used in the literature are also summarized. The study introduces the DEDA method, detailing solution representation, population generation, offspring creation using the Dirichlet distribution, fitness evaluation, and population replacement. The manuscript discusses the concept of EDAs, their advantages in building probabilistic models to generate improved offspring, and various modeling approaches, including Bayesian networks, ranking models, and radial distributions. It highlights a gap in the literature regarding EDAs that utilize Dirichlet distributions to enhance offspring quality for combinatorial problems such as the FJSSP. DEDA is tested and compared on standard benchmark datasets against prominent EDAs and metaheuristics, showing statistically significant superior performance in multiple tests. The article concludes that DEDA offers a promising approach for the FJSSP and can be extended to other scheduling and combinatorial optimization problems.