Parallel Scheduling using Genetic Algorithm and Knowledge Based Approach
DOI:
https://doi.org/10.32734/jsti.v27i2.19099Keywords:
Scheduling, Genetic Algorithm, Makespan, Lateness, Flow ShopAbstract
Production scheduling are very important considering the complexity of the production system. This study aims to solve parallel machine scheduling to get the best job sequence and minimize lateness. Genetic algorithm is optimization algorithms by implementing evolution process and eliminating bad solutions. Knowledge based approach (KBA) solve problems by creating a computing system to imitates human intelligent behavior. Genetic algorithm and KBA are combined with the earliest due date (EDD) rule to produce an inference engine to build more adaptive population initialization. The results of the proposed scheduling show that the rules successfully guide the search process more adaptively. The genetic operation increasing the fitness value when the job is overload or underload. When the job is underload fitness increases by 3.56%, there is no lateness and load capacity ratio (LCR) increase by 4.67%. When the overload fitness increases by 1%, lateness decreases by 4.57%, and LCR decreases by 7.56%. The increase of fitness value shows better results of the proposed job sequence with minimum lateness. The implementation of integration genetic algorithms and KBA using VB.Net language requires a reasonable computing time, which is an average of 32 seconds when running.
Downloads
References
[2] R. Fitas, H. J. Schaffrath, and S. Schabel, “A Review of Optimization for Corrugated Boards,” Nov. 01, 2023, Multidisciplinary Digital Publishing Institute (MDPI). doi: 10.3390/su152115588.
[3] R. Ojstersek, M. Brezocnik, and B. Buchmeister, “Multi-objective optimization of production scheduling with evolutionary computation: A review,” 2020, Growing Science. doi: 10.5267/j.ijiec.2020.1.003.
[4] R. Ginting, Penjadwalan Mesin: Sistem, Algoritma, Pemecahan Masalah dan Penerapan. Medan: USU Press, 2022.
[5] S. Sinulingga, Perencanaan & Pengendalian Produksi. Medan: USU Press, 2021.
[6] P. Perez-Gonzalez and J. M. Framinan, “A review and classification on distributed permutation flowshop scheduling problems,” Jan. 01, 2024, Elsevier B.V. doi: 10.1016/j.ejor.2023.02.001.
[7] A. Allahverdi, “A new heuristic for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness,” Comput. Oper. Res., vol. 31, no. 2, pp. 157–180, Feb. 2004, doi: 10.1016/S0305-0548(02)00143-0.
[8] E. Özdöl, “A Genetic Algorithm for a Flexible Job Shop Scheduling Problem with Sequence Dependent Setup Times,” Dokuz Eylül University, Ontario, 2011.
[9] P. Kianpour, D. Gupta, K. Krishnan, and B. Gopalakrishnan, “DOE-based Enhanced Genetic Algorithm for Unrelated Parallel Machine Scheduling to Minimize Earliness and Tardiness Costs,” J. Optim. Ind. Eng., vol. 16, no. 2, pp. 99–114, Jun. 2023, doi: 10.22094/JOIE.2023.1967925.1992.
[10] F. Abderrabi et al., “Flexible Job Shop Scheduling Problem with Sequence Dependent Setup Time and Job Splitting: Hospital Catering Case Study,” Appl. Sci., vol. 11, no. 4, pp. 1–27, Feb. 2021, doi: 10.3390/app11041504.
[11] D. Rooyani and F. M. Defersha, “An efficient two-stage genetic algorithm for flexible job-shop scheduling,” in IFAC-PapersOnLine, Elsevier B.V., Sep. 2019, pp. 2519–2524. doi: 10.1016/j.ifacol.2019.11.585.
[12] F. M. Defersha and D. Rooyani, “An efficient two-stage genetic algorithm for a flexible job-shop scheduling problem with sequence dependent attached/detached setup, machine release date and lag-time,” Comput. Ind. Eng., vol. 147, Sep. 2020, doi: 10.1016/j.cie.2020.106605.
[13] L. Meng et al., “Constraint programing for solving four complex flexible shop scheduling problems,” IET Collab. Intell. Manuf., vol. 3, no. 2, pp. 147–160, 2021, doi: 10.1049/cim2.12005.
[14] N. Xie and N. Chen, “Flexible job shop scheduling problem with interval grey processing time,” Appl. Soft Comput. J., vol. 70, 2018, doi: 10.1016/j.asoc.2018.06.004.
[15] L. Cheng, Q. Tang, L. Zhang, and C. Yu, “Scheduling flexible manufacturing cell with no-idle flow-lines and job-shop via Q-learning-based genetic algorithm,” Comput. Ind. Eng., vol. 169, Jul. 2022, doi: 10.1016/j.cie.2022.108293.
[16] J. Fan, C. Zhang, Q. Liu, W. Shen, and L. Gao, “An improved genetic algorithm for flexible job shop scheduling problem considering reconfigurable machine tools with limited auxiliary modules,” J. Manuf. Syst., vol. 62, pp. 650–667, Jan. 2022, doi: 10.1016/j.jmsy.2022.01.014.
[17] B. Rolf, T. Reggelin, A. Nahhas, S. Lang, and M. Müller, “Assigning dispatching rules using a genetic algorithm to solve a hybrid flow shop scheduling problem,” Procedia Manuf., vol. 42, no. 2019, pp. 442–449, 2020, doi: 10.1016/j.promfg.2020.02.051.
[18] S. Yuan, T. Li, and B. Wang, “A co-evolutionary genetic algorithm for the two-machine flow shop group scheduling problem with job-related blocking and transportation times,” Expert Syst. Appl., vol. 152, p. 113360, 2020, doi: 10.1016/j.eswa.2020.113360.
[19] M. S. Umam, M. Mustafid, and S. Suryono, “A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem,” J. King Saud Univ. - Comput. Inf. Sci., vol. 34, no. 9, pp. 7459–7467, 2021, doi: 10.1016/j.jksuci.2021.08.025.
[20] P. D. Kusuma, “Multi-objective Batch Scheduling in Collaborative Multi-product Flow Shop System by using Non-dominated Sorting Genetic Algorithm,” Int. J. Adv. Comput. Sci. Appl., vol. 12, no. 9, pp. 349–357, 2021, doi: 10.14569/IJACSA.2021.0120939.
[21] E. Rashidi, M. Jahandar, and M. Zandieh, “An improved hybrid multi-objective parallel genetic algorithm for hybrid flow shop scheduling with unrelated parallel machines,” Int. J. Adv. Manuf. Technol., vol. 49, no. 9–12, pp. 1129–1139, Aug. 2010, doi: 10.1007/s00170-009-2475-z.
[22] M. Aufenanger, N. Lipka, B. Klopper, and W. Dangelmaier, A Knowledge-Based Giffler-Thompson Heuristic for Rescheduling Job Shops. IEEE, 2009.
[23] Z. Pan, D. Lei, and L. Wang, “A Knowledge-Based Two-Population Optimization Algorithm for Distributed Energy-Efficient Parallel Machines Scheduling,” IEEE Trans. Cybern., vol. 52, no. 6, pp. 5051–5063, Jun. 2020, doi: 10.1109/TCYB.2020.3026571.
[24] H. Wang, R. Li, and W. Gong, “Minimizing tardiness and makespan for distributed heterogeneous unrelated parallel machine scheduling by knowledge and Pareto-based memetic algorithm,” Egypt. Informatics J., vol. 24, no. 3, Sep. 2023, doi: 10.1016/j.eij.2023.05.008.
[25] Z. Qin and Y. Lu, “Manufacturing Letters A Knowledge Graph-based knowledge representation for adaptive manufacturing control under mass personalization-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0) Peer-review under responsibility of the Scientific Committee of the NAMRI/SME,” 2023, [Online]. Available: www.sciencedirect.com
[26] S. P. Leo Kumar, “Knowledge-based expert system in manufacturing planning: state-of-the-art review,” 2019, Taylor and Francis Ltd. doi: 10.1080/00207543.2018.1424372.
[27] A. Kusiak, “KBSS: A Knowledge-Based System for Scheduling in Automated Manufacturing,” 1990.
[28] H. Sirait, E. U. Simanihuruk, R. Tambun, A. Parbina Nusantara, and P. Siantar, “Elemen Dasar dan Kharakteristik Membangun Sistem Pakar,” J. BisantaraInformatika, vol. 7, no. 1, 2023.
[29] Z. Zukhri, Algoritma Genetika, Metode Komputasi Evolusioner untuk Menyelesaikan Masalah Optimasi. Yogyakarta: Andi, 2014.
[30] T. Weise, Global Optimization Algorithms – Theory and Application –. 2009. Accessed: Sep. 10, 2024. [Online]. Available: http://www2.fiit.stuba.sk/~kvasnicka/Free books/Weisse_Global Optimization Algorithms - Theory and Application.pdf
[31] M. L. Pinedo, “Scheduling: Theory, Algorithms, and Systems,” 2002.
[32] W. J. Stevenson, Operations Management, 13th ed. New York: McGraw-Hill Education, 2018.
[33] A. Syarif, Algoritma Genetika, Teori dan Aplikasi, Kedua. Bandar Lampung: Graha Ilmu, 2014.
[34] K. Deb, “Multi-Objective Optimization Using Evolutionary Algorithms,” 2001.
[35] M. Tonggiroh, V. B. A. Pardosi, Basiroh, and F. Nugroho, Rekayasa Perangkat Lunak, 1st ed. Solok: PT Mafy Media Literasi Indonesia, 2024.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 TALENTA Publisher Universitas Sumatera Utara
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
The Authors submitting a manuscript do so on the understanding that if accepted for publication, the copyright of the article shall be assigned to TALENTA Publisher Universitas Sumatera Utara as the publisher of the journal.
Copyright encompasses the rights to reproduce and deliver the article in all forms and media. The reproduction of any part of this journal, its storage in databases, and its transmission by any form or medium will be allowed.
