Research on multi-agent genetic algorithm based on tabu search for the job shop scheduling problem
Autoři:
Chong Peng aff001; Guanglin Wu aff001; T. Warren Liao aff002; Hedong Wang aff001
Působiště autorů:
School of Mechanical Engineering and Automation, Beihang University, Beijing, China
aff001; Department of Mechanical and Industrial Engineering, Louisiana State University, Baton Rouge, LA, United States of America
aff002
Vyšlo v časopise:
PLoS ONE 14(9)
Kategorie:
Research Article
prolekare.web.journal.doi_sk:
https://doi.org/10.1371/journal.pone.0223182
Souhrn
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.
Klíčová slova:
Evolutionary genetics – Algorithms – Optimization – Islands – Built structures – Agent-based modeling – Genetic algorithms – Insertion mutation
Zdroje
1. Garey MR, Johnson DS, Sethi R. The Complexity of Flowshop and Jobshop Scheduling. Math Oper Res. 1976;1(2):117–129.
2. Manne A. On the Job Shop Scheduling Problem. Cowles Foundation, Yale University, Cowles Foundation Discussion Papers. 1959;8.
3. Balas E. Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm. Oper Res. 1969;17(6):941–957.
4. Calis B, Bulkan S. A research survey: review of AI solution strategies of job shop scheduling problem. J Intell Manuf. 2015;26(5):961–973.
5. Chen D. Research on Traffic Flow Prediction in the Big Data Environment Based on the Improved RBF Neural Network. IEEE T Ind Inform. 2017;13(4):2000–2008.
6. Liu Y, Liu Z, Jia R. Deep PF: A deep learning based architecture for metro passenger flow prediction. Transport Res C-Emer. 2019;101:18–34.
7. Holland J. Adoption in Natural and Artificial System. The University of Michigan Press, Ann Arbor. 1975.
8. Xu XD, Li CX. Research on immune genetic algorithm for solving the job-shop scheduling problem. Int J Adv Manuf Technol. 2007;34(7–8):783–789.
9. Kurdi M. An effective new island model genetic algorithm for job shop scheduling problem. Comput Oper Res. 2016;67(C):132–142.
10. Chang HC, Liu TK. Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms. J Intell Manuf. 2015;28(8):1–14.
11. Liu J, Jing H, Tang YY. Multi-agent oriented constraint satisfaction. Artif Intell. 2002;136(1):101–44.
12. Chen W, Li J, Ma W. Hybrid flow shop rescheduling algorithm for perishable products subject to a due date with random invalidity to the operational unit. Int J Adv Manuf Technol. 2017;93(1):225–239.
13. Tsujimura Y. A tutorial survey of job-shop scheduling problems using genetic algorithms—I. representation. Comput Ind Eng. 1996;30(4):983–997.
14. Knopp S, Dauzère-Pérès S, Yugma C. A batch-oblivious approach for Complex Job-Shop scheduling problems. Eur J Oper Res. 2017;263(1):50–61.
15. Bean JC. Genetic Algorithms and Random Keys for Sequencing and Optimization. Orsa J Comput. 2017;6:154–160.
16. Zambrano Rey G, Bekrar A, Trentesaux D, Zhou B-H. Solving the flexible job-shop just-in-time scheduling problem with quadratic earliness and tardiness costs. Int J Adv Manuf Technol. 2015;81(9):1871–1891.
17. Kuhpfahl J, Bierwirth C. A Study on Local Search Neighborhoods for the Job Shop Scheduling Problem with Total Weighted Tardiness Objective. Comput Oper Res. 2015;66:44–57.
18. Engin O, Güçlü A. A new hybrid ant colony optimization algorithm for solving the no-wait flow shop scheduling problems. Appl Soft Comput. 2018;72:166–176.
19. Gao L, Li X, Wen X, Lu C, Wen F. A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem. Comput Ind Eng. 2015;88:417–429.
20. Selsa V, Vanhouckeabc M. A hybrid single and dual population search procedure for the job shop scheduling problem. Eur J Oper Res. 2011;215(3):512–523.
21. Zhang C, Rao Y, Li P. An effective hybrid genetic algorithm for the job shop scheduling problem. Int J Adv Manuf Technol. 2008;39(9–10):965–974.
22. Laarhoven PJMV, Aarts EHL, Lenstra JK. Job shop scheduling by simulated annealing. Oper Res. 1992;40(1):113–125.
23. Dell'Amico M, Trubian M. Applying tabu search to the job-shop scheduling problem. Ann Oper Res. 1993;41(3):231–252.
24. Nowicki E, Smutnicki C. A Fast Taboo Search Algorithm for the Job Shop Problem. Manag Sci. 1996;42(6):797–813.
25. Balas E, Vazacopoulos A. Guided Local Search with Shifting Bottleneck for Job Shop Scheduling. Manag Sci. 1998;44:262–275.
26. Matsuo H, Suh C, Sullivan R. A Controlled Search Simulated Annealing Method for the General Job-Shop Scheduling Problem. 1988.
27. Zhang CY, Li PG, Guan ZL, Rao YQ. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Comput Oper Res. 2007;34(11):3229–3242.
28. Fisher H., & Thompson G. L. Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules. Industrial Scheduling. Englewood Cliffs, New Jersey: Prentice-Hall. 1963:225–251.
29. Lawrence S. Supplement to Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques. Graduate School of Industrial Administration, Carnegie-Mellon University. 1984;4(7):4411–4417.
30. Asadzadeh L. A local search genetic algorithm for the job shop scheduling problem with intelligent agents. Comput Ind Eng. 2015;85(C):376–383.
31. Lin C, Zhang Q, Fei T, Ni K, Yang C. A novel search algorithm based on waterweeds reproduction principle for job shop scheduling problem. Int J Adv Manuf Technol. 2016;84(1–4):405–424.
32. Pezzella F, Merelli E. A tabu search method guided by shifting bottleneck for the job shop scheduling problem. Eur J Oper Res. 2000;120(2):297–310.
Článok vyšiel v časopise
PLOS One
2019 Číslo 9
- Metamizol jako analgetikum první volby: kdy, pro koho, jak a proč?
- Nejasný stín na plicích – kazuistika
- Masturbační chování žen v ČR − dotazníková studie
- Je Fuchsova endotelová dystrofie rohovky neurodegenerativní onemocnění?
- Fixní kombinace paracetamol/kodein nabízí synergické analgetické účinky
Najčítanejšie v tomto čísle
- Graviola (Annona muricata) attenuates behavioural alterations and testicular oxidative stress induced by streptozotocin in diabetic rats
- CH(II), a cerebroprotein hydrolysate, exhibits potential neuro-protective effect on Alzheimer’s disease
- Comparison between Aptima Assays (Hologic) and the Allplex STI Essential Assay (Seegene) for the diagnosis of Sexually transmitted infections
- Assessment of glucose-6-phosphate dehydrogenase activity using CareStart G6PD rapid diagnostic test and associated genetic variants in Plasmodium vivax malaria endemic setting in Mauritania