Solving an Integrated Job-Shop – Mobile Robot Scheduling Problem in Flexible Manufacturing System using Enhanced Genetic Algorithm Structure with Local Search Method
Keywords:
Flexible manufacturing system, Genetic algorithm, Hybrid optimization, Job-shop, Scheduling, Tabu search.Abstract
In a highly automated Flexible Manufacturing System (FMS), optimal utilization and scheduling of resources and equipment are paramount. This necessity underpins the full utilization of automation capabilities, leading to increased productivity and minimized downtime. Efficient resource allocation and scheduling also contribute to better overall performance, allowing the FMS to meet production demands effectively while maintaining a high level of operational efficiency. In this paper, the job-shop production scheduling problem is studied which involve with the concurrent scheduling of jobs processing and mobile robot assignment for job transportation within FMS environment. The hybrid Genetic Algorithm and Tabu Search algorithm is proposed to solve the combinatorial NP-hard job-shop and mobile robot scheduling problem. The primary objective is to search for the best scheduling plan that includes job allocation and mobile robot assignment, aiming to minimize the overall time necessary to complete all tasks, also known as makespan, to the minimum as possible. The developed algorithm has been evaluated and compared with the classical (or standard) genetic algorithm and other hybrid GA (with Simulated Annealing (SA) algorithm) using two job datasets spanning from small to large-scale problems adopted from renowned benchmark job instances. The results of computer experiments substantiate the effectiveness of the proposed hybrid algorithm, showcasing superior-quality solutions with an approximate up to 2.86% and 3.55% improvements compared to the hybrid GA – SA and standard algorithm, respectively. The developed algorithm has been run and tested in the Matlab software environment.References
M. H. F. Bin Md Fauadi and T. Murata, Makespan minimization of machines and automated guided vehicles schedule using binary particle swarm optimization, Proceedings of the International MultiConference of Engineers and Computer Scientists. Hong Kong, 2010, 1897-1902.
S. M. Homayouni and D. B. M. M. Fontes, Production and transport scheduling in flexible job shop manufacturing systems, Journal of Global Optimization, 79 (2), 2021, 463-502.
G. A. Chang, Modeling and analysis of flexible manufacturing systems: A simulation study, ASEE Annual Conference & Exposition, Seattle, Washington, 2015, 12726.
Y. M. Mejthab and K. M. Al-aubidy, Design and implementation of real-time scheduling algorithms for flexible manufacturing systems, International Journal of Advanced Mechatronic Systems, 7(4), 2017, 202-212.
L. Zaidi, B. Bettayeb, and M. Sahnoun, Optimisation and simulation of transportation tasks in flexible job shop with muti-robot systems, 1st International Conference on Cyber Management and Engineering (CyMaEn), Tunisia, 2021, 1-6.
P. Kostal and K. Velisek, Flexible manufacturing system, World Academy of Science, Engineering and Technology, 77, 2011, 825-829.
S. Gopi and S. A. Chandra, Solving distributed FMS scheduling problems with/ without breakdowns: Simulation optimization approach, Materials Today: Proceedings, 47(14), 2021, 4879-4884.
X. Wen, Y. Fu, W. Yang, H. Wang, Y. Zhang and C. Sun, An effective hybrid algorithm for joint scheduling of machines and AGVs in flexible job shop, Measurement and Control, 56(9-10), 2023, 1582-1598.
W. Li, D. Han, L. Gao, X. Li, and Y. Li, Integrated production and transportation scheduling method in hybrid flow shop, Chinese Journal of Mechanical Engineering, 35(1), 2022, 12.
P. Bharti and S. Jain, Hybrid frameworks for flexible job shop scheduling, The International Journal of Advanced Manufacturing Technology, 108(5-6), 2020, 1563-1585.
Q. V. Dang and L. Nguyen, A Heuristic approach to schedule mobile robots in flexible manufacturing environments, Procedia CIRP, 40, 2016, 390-395.
S. Kumar, V. Manjrekar, V. Singh and B. Kumar, Integrated yet distributed operations planning approach: A next generation manufacturing planning system, Journal of Manufacturing Systems, 54, 2020, 103-122.
S. Chakrabarti and H. N. Saha, Simultaneous Scheduling of machines and automated guided vehicles utilizing heuristic search algorithm, IEEE 8th Annual Computing and Communication Workshop and Conference (CCWC), Las Vegas, USA, 2018, 54-59.
B. Vaisi, A review of optimization models and applications in robotic manufacturing systems: Industry 4.0 and beyond, Decision Analytics Journal, 2, 2022, 100031.
P. Brucker, E. K. Burke and S. Groenemeyer, A branch and bound algorithm for the cyclic job-shop problem with transportation, Computers & Operations Research, 39(12), 2012, 3200-3214.
A. Caumond, P. Lacomme, A. Moukrim and N. Tchernev, An MILP for scheduling problems in an FMS with one vehicle, European Journal of Operational Research, 199(3), 2009, 706-722.
L. L. Fu, M. A. Aloulou and C. Triki, Integrated production scheduling and vehicle routing problem with job splitting and delivery time windows, International Journal of Production Research, 55(20), 2017, 5942-5957.
Q. Zhang, H. Manier and M. -A. Manier, Metaheuristics for job shop scheduling with transportation, Metaheuristics for Production Scheduling (eds B. Jarboui, P. Siarry and J. Teghem), 2013, 465-493.
Z. Zhang, B. Pi and Z. Wang, Scheduling mobile robots in flexible manufacturing system by an adaptive large neighborhood search, Proceedings of 6th International Conference on Computing and Data Engineering, 2020, 232-236.
Q. V. Dang and I. Nielsen, Simultaneous scheduling of machines and mobile robots, Communications in Computer and Information Science, 365, 2013, 118-128.
D. S. Sanches, J. da Silva Rocha, M. F. Castoldi, O. Morandin and E. R. R. Kato, An adaptive genetic algorithm for production scheduling on manufacturing systems with simultaneous use of machines and AGVs, Journal of Control Automation and Electrical Systems, 26(3), 2015, 225-234.
A. Elmi and S. Topaloglu, Cyclic job shop robotic cell scheduling problem: Ant colony optimization, Computers & Industrial Engineering, 111, 2017, 417-432.
M. Petrović, N. Vuković, M. Mitić and Z. Miljković, Integration of process planning and scheduling using chaotic particle swarm optimization algorithm, Expert Systems with Applications, 64, 2016, 569-588.
W. Q. Zou, Q. K. Pan, and M. F. Tasgetiren, An effective discrete artificial bee colony algorithm for scheduling an automatic-guided-vehicle in a linear manufacturing workshop, IEEE Access, 8, 2020, 35063-35076.
U. Bilge and G. Ulusoy, Time window approach to simultaneous scheduling of machines and material handling system in an FMS, Operations Research, 43(6), 1995, 1058-1070.
G. Ulusoy and U. Bilge, Simultaneous scheduling of machines and automated guided vehicles, International Journal of Production Research, 31(12), 1993, 2857-2873.
L. Deroussi and S. Norre, Simultaneous scheduling of machines and vehicles for the flexible job shop problem solution approach: Basic ideas, International Conference on Metaheuristics and Nature Inspired Computing, 2010, 2-3.
J. Hurink and S. Knust, Tabu search algorithms for job-shop problems with a single transport robot, European Journal of Operational Research, 162, 2005, 99-111.
Q. Zhang, H. Manier and M. Manier, A modified shifting bottleneck heuristic and disjunctive graph for job shop scheduling problems with transportation constraints, International Journal of Production Research, 52(4), 2014, 37-41.
D. Sharma, V. Singh and C. Sharma, GA based scheduling of FMS using roulette wheel selection process, Proceedings of the International Conference on Soft Computing for Problem Solving (SocProS), Springer, 2011, 931-940.
I. Nielsen, Q. D. Grzegorz, and B. Zbigniew, A methodology for implementation of mobile robot in adaptive manufacturing environments, Journal of Intelligent Manufacturing, 28, 2017, 1171-1188.
I. Nielsen, N. A. Dung Do, Z. A. Banaszak and M. N. Janardhanan, Material supply scheduling in a ubiquitous manufacturing system, Robotics and Computer-Integrated Manufacturing, 45, 2017, 21-33.
G. Zhang, J. Sun, X. Liu, G. Wang and Y. Yang, Solving flexible job shop scheduling problems with transportation time based on improved genetic algorithm, Mathematical Biosciences and Engineering, 16(3), 2019, 1334-1347.
H. Qiu, W. Zhou and H. Wang, A genetic algorithm-based approach to flexible job-shop scheduling problem, Fifth International Conference on Natural Computation (ICNC), 4, 2009, 81-85.
L. Gao, F. Lu, Y. Ge and D. Feng, A fuzzy adaptive genetic algorithms for global optimization problems, Chinese Control and Decision Conference (CCDC), 2010, 914-919.
A. P. Rifai, S. Z. M. Dawal, A. Zuhdi, H. Aoyama and K. Case, Reentrant FMS scheduling in loop layout with consideration of multi loading-unloading stations and shortcuts, The International Journal of Advanced Manufacturing Technology, 82(9-12), 2016, 1527-1545.
N. F. Fauziah and Y. H. Putra, Scheduling regular classrooms using heuristic genetic and tabu search algorithms, IOP Conference Series: Materials Science and Engineering, 407, 2018, 012116.
M. S. Umam, M. Mustafid and S. Suryono, A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem, Journal of King Saud University - Computer and Information Sciences, 34(9), 2021, 7459-7467.
M. P. A. Sonawane, Hybrid genetic algorithm and tabu search algorithm to solve class time table scheduling problem, International Journal of Research Studies in Computer Science and Engineering, 4840(4), 2014, 19-26.
Y. Ge, A. Wang, Z. Zhao, and J. Ye, A tabu-genetic hybrid search algorithm for job-shop scheduling problem, E3S Web of Conferences, 95, 2019, 3-6.
A. A. Abayomi-alli, F. O. Uzedu, S. Misra, O. O. Abayomi-alli and O. T. Arogundade, Hybrid Model of genetic algorithms and tabu search memory for nurse scheduling systems, International Journal of Service Science, Management, Engineering, and Technology, 13(1), 2022, 1-20.
S. Meeran and M. S. Morshed, A hybrid genetic tabu search algorithm for solving job shop scheduling problems: A case study, Journal of Intelligent Manufacturing, 23(4), 2012, 1063-1078.
J. J. Palacios, M. A. González, C. R. Vela, I. González-Rodríguez and J. Puente, Genetic tabu search for the fuzzy flexible job shop problem, Computers & Operations Research, 54, 2015, 74-89.
L. Zhang, L. Gao and X. Li, A hybrid genetic algorithm and tabu search for a multi-objective dynamic job shop scheduling problem, International Journal of Production Research, 51(12), 2013, 3516-3531.
X. Li and L. Gao, An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem, International Journal of Production Economics, 174, 2016, 93-110.
J. Xie, X. Li, L. Gao and L. Gui, A hybrid genetic tabu search algorithm for distributed flexible job shop scheduling problems, Journal of Manufacturing Systems, 71, 2023, pp. 82-94.
F. Xhafa, J. A. Gonzalez, K. P. Dahal and A. Abraham, A GA(TS) hybrid algorithm for scheduling in computational grids, Hybrid Artificial Intelligence Systems, Springer, Berlin, 2009.
M. Qiu, Z. Fu, R. Eglese and Q. Tang, A tabu search algorithm for the vehicle routing problem with discrete split deliveries and pickups, Computers & Operations Research, 100, 2018, 102-116.
Y. Qawqzeh, M. T. Alharbi, A. Jaradat and K. N. A. Sattar, A review of swarm intelligence algorithms deployment for scheduling and optimization in cloud computing environments, PeerJ Computer Science, 7, 2021, 1-17.
M. Wan, X. Xu and J. Nan, Flexible job-shop scheduling with integrated genetic algorithm, Proceedings of 4th International Workshop on Advanced Computational Intelligence (IWACI), Wuhan, China, 2011, 13-16.
M. V. S. Kumar, R. Janardhana and C. S. P. Rao, Simultaneous scheduling of machines and vehicles in an FMS environment with alternative routing, The International Journal of Advanced Manufacturing Technology, 53, 2011, 339-351.
M. Gen and L. Lin, Multiobjective evolutionary algorithm for manufacturing scheduling problems: State-of-the-art survey, Journal of Intellingent Manufacturing, 25(5), 2014, 849-866.
B. S. P. Reddy and C. S. P. Rao, A hybrid multi-objective GA for simultaneous scheduling of machines and AGVs in FMS, The International Journal of Advanced Manufacturing Technology, 31(5-6), 2006, 602-613.
B. S. P. Reddy and B. S. P. Rao, Flexible manufacturing systems modelling and performance evaluation using automod, International Journal of Simulation model, 10(2), 2011, 78-90.
S. Lawrence, Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques, Technical Report, Graduate School of Industrial Administration. Carnegie-Mellon University, 1984.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:Authors hold and retain copyright, and grant the journal right of first publication, with the work after publication simultaneously licensed under a Creative Commons Attribution 4.0 License CC BY that permits any use, reproduction and distribution of the work and article without further permission provided that the original work is properly cited.
Authors are permitted and encouraged to post their work online in institutional repositories, website and other social media before and after publication, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
