Involvement of Various Selection Methods for Genetic Algorithms in Determining the Optimal Production Schedule Problem

Rizki Muliono - Universitas Medan Area, Jl. Kolam No. 1, Medan Estate, 20223, Indonesia
Nukhe Silviana - Universitas Medan Area, Jl. Kolam No. 1, Medan Estate, 20223, Indonesia
Nanda Novita - Universitas Medan Area, Jl. Kolam No. 1, Medan Estate, 20223, Indonesia


Citation Format:



DOI: http://dx.doi.org/10.62527/joiv.8.4.2632

Abstract


This research investigates using genetic algorithms (GA) to optimize production scheduling in Medan's shoe industry. The study compares traditional manual and First Come First Serve (FCFS) methods against a GA approach, incorporating selection variations such as Boltzmann, Fitness Uniform Selection Scheme (FUSS), Exponential Rank Selection, and Roulette Wheel Selection. The optimal production order is derived from the chromosome with the highest fitness. Results indicate that GA with FUSS selection significantly reduces production time from 73,630 minutes to 45,650 minutes, achieving a 35% improvement in efficiency. This optimization is attributed to FUSS’s ability to maintain a diverse population, preventing premature convergence and ensuring a broader solution for space exploration. Additionally, it was found that using a smaller population size relative to the number of generations yields better optimization results. The study also demonstrates that while Roulette Wheel Selection shows more variability, it achieves higher optimization over time than FCFS. The practical implications of these findings are substantial for the shoe industry, including faster production cycles, better resource allocation, and an enhanced ability to meet customer demands. These benefits are exemplified by implementing the SISPROMA application, an innovative production scheduling information system that leverages machine learning to optimize scheduling in the manufacturing industry. This study provides valuable insights into applying genetic algorithms for production scheduling, highlighting their potential to enhance operational efficiency and reduce costs. Future research should explore additional optimization techniques and real-world applications to validate and extend these findings, ensuring broader applicability and continuous improvements in manufacturing efficiency.


Keywords


FCFS Method; Genetic Algorithm; Scheduling Optimization; Production Scheduling; Optimization of Production Time

Full Text:

PDF

References


L. Wang, Z. Pan, and J. Wang, “A Review of Reinforcement Learning Based Intelligent Optimization for Manufacturing Scheduling,” Complex System Modeling and Simulation, vol. 1, no. 4, 2021, doi: 10.23919/CSMS.2021.0027.

G. A. Süer, A. Subramanian, and J. Huang, “Heuristic procedures and mathematical models for cell loading and scheduling in a shoe manufacturing company,” Comput Ind Eng, vol. 56, no. 2, 2009, doi: 10.1016/j.cie.2008.10.008.

P. Barredo and J. Puente, “Precise makespan optimization via hybrid genetic algorithm for scientific workflow scheduling problem,” Nat Comput, vol. 22, no. 4, 2023, doi: 10.1007/s11047-023-09950-5.

J. Bastos, J. Voeten, S. Stuijk, R. Schiffelers, and H. Corporaal, “Taming the State-space Explosion in the Makespan Optimization of Flexible Manufacturing Systems,” ACM Transactions on Cyber-Physical Systems, vol. 5, no. 2, 2021, doi: 10.1145/3426194.

S. Mohammadi, A. Cheraghalikhani, and R. Ramezanian, “A joint scheduling of production and distribution operations in a flow shop manufacturing system,” Scientia Iranica, vol. 25, no. 2E, 2018, doi: 10.24200/sci.2017.4437.

C. T. Yeh, Y. K. Lin, L. C. L. Yeng, and Y. L. Chao, “Hybrid flow-shop manufacturing network reliability optimization using genetic algorithm and absorbing Markov chain,” Appl Math Model, vol. 120, 2023, doi: 10.1016/j.apm.2023.04.005.

A. S. Bhongade, P. M. Khodke, A. U. Rehman, M. D. Nikam, P. D. Patil, and P. Suryavanshi, “Managing Disruptions in a Flow-Shop Manufacturing System,” Mathematics, vol. 11, no. 7, 2023, doi: 10.3390/math11071731.

N. Y. Hidayah, M. Syafrizal, and M. Darmawan, “Analysis of textile dye production scheduling using FCFS, CDS and Heuristic Pour methods,” in IOP Conference Series: Materials Science and Engineering, 2020. doi: 10.1088/1757-899X/847/1/012006.

I. Siregar, I. Rizkya, R. M. Sari, and K. Syahputri, “Minimization of Makespan Using FCFS Method and Genetic Algorithm Method Comparison in Aluminum Industry,” in 2019 3rd International Conference on Electrical, Telecommunication and Computer Engineering, ELTICOM 2019 - Proceedings, 2019. doi: 10.1109/ELTICOM47379.2019.8943914.

N. Sutrisno, H. Aldriany Prasetyo, and S. Utami, “Comparison of FCFS, SPT, LPT, and EDD Methods at the Utility Level and Production Scheduling of Huller Machines,” International Journal of Research and Review, vol. 10, no. 9, 2023, doi: 10.52403/ijrr.20230920.

W. Boutegrabet, O. Piot, D. Guenot, and C. Gobinet, “Unsupervised Feature Selection by a Genetic Algorithm for Mid-Infrared Spectral Data,” Anal Chem, vol. 94, no. 46, 2022, doi: 10.1021/acs.analchem.2c03118.

Z. Banković, S. Bojanić, O. Nieto, and A. Badii, “Unsupervised genetic algorithm deployed for intrusion detection,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2008. doi: 10.1007/978-3-540-87656-4_17.

Z. Ali, K. N. Qureshi, A. S. Al-Shamayleh, A. Akhunzada, A. Raza, and M. F. U. Butt, “Delay Optimization in LoRaWAN by Employing Adaptive Scheduling Algorithm with Unsupervised Learning,” IEEE Access, vol. 11, 2023, doi: 10.1109/ACCESS.2023.3234188.

C. Y. Cheng, P. Pourhejazy, K. C. Ying, and C. F. Lin, “Unsupervised Learning-based Artificial Bee Colony for minimizing non-value-adding operations,” Appl Soft Comput, vol. 105, 2021, doi: 10.1016/j.asoc.2021.107280.

K. P. Sinaga and M. S. Yang, “Unsupervised K-means clustering algorithm,” IEEE Access, vol. 8, 2020, doi: 10.1109/ACCESS.2020.2988796.

A. M. Ikotun, A. E. Ezugwu, L. Abualigah, B. Abuhaija, and J. Heming, “K-means clustering algorithms: A comprehensive review, variants analysis, and advances in the era of big data,” Inf Sci (N Y), vol. 622, 2023, doi: 10.1016/j.ins.2022.11.139.

R. Barreto, P. Faria, and Z. Vale, “Determination of the typical load profile of industry tasks using fuzzy C-Means,” Energy Reports, vol. 6, 2020, doi: 10.1016/j.egyr.2020.11.094.

A. Kumar, P. P. Singh, D. Sharma, and P. Joshi, “Grid computing model to solve job shop scheduling and flow shop scheduling by fuzzy C-mean algorithm,” Int J Eng Adv Technol, vol. 9, no. 1, 2019, doi: 10.35940/ijeat.A1107.109119.

P. Ulum and D. Fitriani, “IMPLEMENTATION OF GENETIC ALGORITHM IN THE CURRENT SCHEDULING SYSTEM,” Jurnal Riset Informatika, vol. 3, no. 2, 2021, doi: 10.34288/jri.v3i2.167.

S. Castillo-Rivera, J. de Antón, R. Del Olmo, J. Pajares, and A. López-Paredes, “Genetic algorithms for the scheduling in additive manufacturing,” International Journal of Production Management and Engineering, vol. 8, no. 2, 2020, doi: 10.4995/ijpme.2020.12173.

G. Rivera, L. Cisneros, P. Sánchez-Solís, N. Rangel-Valdez, and J. Rodas-Osollo, “Genetic algorithm for scheduling optimization considering heterogeneous containers: A real-world case study,” Axioms, vol. 9, no. 1, 2020, doi: 10.3390/axioms9010027.

D. Nasien and A. Andi, “Optimization of Genetic Algorithm in Courses Scheduling,” IT Journal Research and Development, 2022, doi: 10.25299/itjrd.2022.7896.

H. M. Pandey, “Performance Evaluation of Selection Methods of Genetic Algorithm and Network Security Concerns,” in Physics Procedia, 2016. doi: 10.1016/j.procs.2016.02.004.

F. Amini and G. Hu, “A two-layer feature selection method using Genetic Algorithm and Elastic Net,” Expert Syst Appl, vol. 166, 2021, doi: 10.1016/j.eswa.2020.114072.

A. Brandwajn and T. Begin, “First-come-first-served queues with multiple servers and customer classes,” Performance Evaluation, vol. 130, 2019, doi: 10.1016/j.peva.2018.11.001.

A. Chraibi, S. Ben Alla, and A. Ezzati, “An efficient cloudlet scheduling via bin packing in cloud computing,” International Journal of Electrical and Computer Engineering, vol. 12, no. 3, 2022, doi: 10.11591/ijece.v12i3.pp3226-3237.

G. Zhou, W. Tian, and R. Buyya, “Multi-search-routes-based methods for minimizing makespan of homogeneous and heterogeneous resources in Cloud computing,” Future Generation Computer Systems, vol. 141, 2023, doi: 10.1016/j.future.2022.11.031.

J. A. Abdor-Sierra, E. A. Merchán-Cruz, R. G. Rodríguez-Cañizo, and D. Pavlyuk, “A comparison of first-come-first-served and multidimensional heuristic approaches for asset allocation of floor cleaning machines,” Results in Engineering, vol. 18, 2023, doi: 10.1016/j.rineng.2023.101074.

W. Guo, Q. Lei, Y. Song, and X. Lyu, “A learning interactive genetic algorithm based on edge selection encoding for assembly job shop scheduling problem,” Comput Ind Eng, vol. 159, 2021, doi: 10.1016/j.cie.2021.107455.

L. R. Abreu, J. O. Cunha, B. A. Prata, and J. M. Framinan, “A genetic algorithm for scheduling open shops with sequence-dependent setup times,” Comput Oper Res, vol. 113, 2020, doi: 10.1016/j.cor.2019.104793.

M. N. Gurcan, B. Sahiner, H. P. Chan, L. Hadjiiski, and N. Petrick, “Selection of an optimal neural network architecture for computer-aided detection of microcalcifications - Comparison of automated optimization techniques,” Med Phys, vol. 28, no. 9, 2001, doi: 10.1118/1.1395036.

N. Gulayeva and A. Ustilov, “Analysis of Selection Methods Used in Genetic Algorithms,” NaUKMA Research Papers. Computer Science, vol. 4, 2021, doi: 10.18523/2617-3808.2021.4.29-43.

I. Jannoud, Y. Jaradat, M. Z. Masoud, A. Manasrah, and M. Alia, “The role of genetic algorithm selection operators in extending wsn stability period: A comparative study,” Electronics (Switzerland), vol. 11, no. 1, 2022, doi: 10.3390/electronics11010028.

M. A. Al-Betar, M. A. Awadallah, H. Faris, X. S. Yang, A. Tajudin Khader, and O. A. Alomari, “Bat-inspired algorithms with natural selection mechanisms for global optimization,” Neurocomputing, vol. 273, 2018, doi: 10.1016/j.neucom.2017.07.039.

R. Kumar and Jyotishree, “Blending Roulette Wheel Selection & Rank Selection in Genetic Algorithms,” Int J Mach Learn Comput, 2012, doi: 10.7763/ijmlc.2012.v2.146.

H. Herman, L. Syafie, I. Irawati, L. N. Hayati, and H. Harlinda, “SCHEDULING USING GENETIC ALGORITHM AND ROULETTE WHEEL SELECTION METHOD CONSIDERING LECTURER TIME,” Journal of Information Technology and Its Utilization, vol. 2, no. 1, 2019, doi: 10.30818/jitu.2.1.2243.

T. X. Ying, A. M. Kassim, and N. A. Abdullah, “A Genetic Algorithm-based Group Formation to Assign Student with Academic Advisor: A Study on User Acceptance Using UTAUT,” International Journal on Informatics Visualization, vol. 7, no. 3, 2023, doi: 10.30630/joiv.7.3.1667.

Y. Widhiyasana, M. Harika, F. F. N. Hakim, F. Diani, K. S. Komariah, and D. R. Ramdania, “Genetic Algorithm for Artificial Neural Networks in Real-Time Strategy Games,” International Journal on Informatics Visualization, vol. 6, no. 2, 2022, doi: 10.30630/joiv.6.2.832.

K. Albeladi and S. Abdullah, “Application of genetic algorithm and personal informatics in stock market,” International Journal on Informatics Visualization, vol. 2, no. 2, 2018, doi: 10.30630/joiv.2.2.115.

F. M. Putra, F. K. Surado, and G. I. Sampurno, “Feature selection techniques for selecting proteins that influence mouse down syndrome using genetic algorithms and random forests,” International Journal on Informatics Visualization, vol. 4, no. 3, 2020, doi: 10.30630/joiv.4.3.375.