Research on multi-agent genetic algorithm based on tabu search for the job shop scheduling problem

Chong Peng; Guanglin Wu; T Warren Liao; Hedong Wang

doi:10.1371/journal.pone.0223182

Research on multi-agent genetic algorithm based on tabu search for the job shop scheduling problem

PLoS One. 2019 Sep 27;14(9):e0223182. doi: 10.1371/journal.pone.0223182. eCollection 2019.

Authors

Chong Peng¹, Guanglin Wu¹, T Warren Liao², Hedong Wang¹

Affiliations

¹ School of Mechanical Engineering and Automation, Beihang University, Beijing, China.
² Department of Mechanical and Industrial Engineering, Louisiana State University, Baton Rouge, LA, United States of America.

Abstract

The solution to the job shop scheduling problem (JSSP) is of great significance for improving resource utilization and production efficiency of enterprises. In this paper, in view of its non-deterministic polynomial properties, a multi-agent genetic algorithm based on tabu search (MAGATS) is proposed to solve JSSPs under makespan constraints. Firstly, a multi-agent genetic algorithm (MAGA) is proposed. During the process, a multi-agent grid environment is constructed based on characteristics of multi-agent systems and genetic algorithm (GA), and a corresponding neighbor interaction operator, a mutation operator based on neighborhood structure and a self-learning operator are designed. Then, combining tabu search algorithm with a MAGA, the algorithm MAGATS are presented. Finally, 43 benchmark instances are tested with the new algorithm. Compared with four other algorithms, the optimization performance of it is analyzed based on obtained test results. Effectiveness of the new algorithm is verified by analysis results.

Publication types

Research Support, Non-U.S. Gov't

MeSH terms

Algorithms*
Computer Simulation*
Efficiency, Organizational
Job Application*
Models, Organizational*

Grants and funding

The research was supported by National Natural Science Foundation of China (Grant No. 51875029) and was supported by the National Science and Technology Major Project “High-Grade CNC Machine Tools and Basic Manufacturing Equipments” (Grant No. 2016ZX04004006) to CP.