Discrete Artificial Algae Algorithm for solving Job-Shop Scheduling Problems

The Job-Shop Scheduling Problem (JSSP) is an NP-hard problem and can be solved with both exact methods and heuristic algorithms. When the dimensionality is increased, exact methods cannot produce proper solutions, but heuristic algorithms can produce optimal or near-optimal results for high-dimensional JSSPs in a reasonable time. In this work, novel versions of the Artificial Algae Algorithm (AAA) have been proposed to solve discrete optimization problems. Three encoding schemes (Random-Key (RK), Smallest Position Value (SPV), and Ranked-Over Value (ROV) Encoding Schemes) were integrated with AAA to solve JSSPs. In addition, the comparison of these three encoding schemes was carried out for the first time in this study. In the experiments, 48 JSSP problems that have 36 to 300 dimensions were solved with 24 different approaches obtained by integrating 3 different coding schemes into 8 state-of-the-art algorithms. As a result of the comparative and detailed analysis, the best results in terms of makespan value were obtained by integrating the SPV coding scheme into the AAA method. (c) 2022 Elsevier B.V. All rights reserved.

Automated summary

The Job-Shop Scheduling Problem is a complex optimization problem that can be solved using heuristic algorithms. This study proposes a new version of the Artificial Algae Algorithm and integrates three different encoding schemes with this algorithm to solve high-dimensional Job-Shop Scheduling Problems. Through comparison and analysis, it is found that integrating the Smallest Position Value encoding scheme into the Artificial Algae Algorithm produces the best makespan value results.