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

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 propose...

Full description

Saved in:
Bibliographic Details
Published in:PloS one 2019-09, Vol.14 (9), p.e0223182-e0223182
Main Authors: Peng, Chong, Wu, Guanglin, Liao, T Warren, Wang, Hedong
Format: Article
Language:English
Subjects:
Algorithms
Benchmarking
Biology and Life Sciences
Computer and Information Sciences
Computer science
Computer Simulation
Earth Sciences
Efficiency, Organizational
Engineering and Technology
Genetic algorithms
Job Application
Job shop scheduling
Job shops
Machine learning
Models, Organizational
Multiagent systems
Mutation
Optimization
Physical Sciences
Polynomials
Problems
Research and Analysis Methods
Resource utilization
Search algorithms
Social economy
Tabu search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1932-6203
1932-6203
DOI:10.1371/journal.pone.0223182