Penerapan Algoritma Genetika pada Persoalan Pemotongan Stok Satu Dimensi

Lisa Harianto, M. Imran, M. D. H. Gamal

Abstract


Cutting stock into several parts with specific lengths requested by customers is crucial for a company. Often, during the stock-cutting process, waste known as *trim loss* occurs due to inaccurate selection of cutting patterns. This process of determining the stock cutting pattern is referred to as the Cutting Stock Problem (CSP). In the context of advancements in computer science to address problem-solving, alternative solutions can be achieved through a metaheuristic approach, specifically the Genetic Algorithm (GA). This algorithm is inspired by the genetic processes in living organisms, where generations in a population naturally evolve over time following the principle of natural selection—survival of the fittest. This article presents a one-dimensional CSP aiming to find an optimal cutting pattern by minimizing trim loss, which is equivalent to minimizing the amount of stock used. Subsequently, the GA approach is applied using MATLAB R2021a to solve the one-dimensional CSP. The research results show a solution with the minimum use of standard-size stock to meet customer demands. After 20 trials, the best fitness value achieved was 1.000000, with a trim loss percentage of 0%.


Keywords


Cutting Stock Problem, Fitness Value, Genetic Algorithm, Metaheuristics

Full Text:

PDF

References


P. B. J. Bangun, S. Octarina, L. Hanum, R. Sawitri, and E. S. Cahyono, “Column generation model in capacitated multi-periods cutting stock problem with pattern set-up cost,” Sci. Technol. Indones., vol. 6, no. 1, pp. 8–13, Jan. 2021.

S. Octarina, D. Septimiranti, and E. Yuliza, “Implementation of arc flow model incapacitated multi-period cutting stock problem with the pattern set up cost to minimize the trim loss,” J. Phys. Conf. Ser., pp. 1–6, July 23-24, 2021.

S. Octarina, D. G. Juita, N. Eliyati, and P. B. J. Bangun, “Set covering model in solving multiple cutting stock problem,” Sci. Technol. Indones., vol. 5, no. 4, pp. 121–130, Oct. 2020.

J. Fang, Y. Rao, Q. Luo, and J. Xu, “Solving one-dimensional cutting stock problems with the deep reinforcement learning,” Mathematics, vol. 11, no. 4, pp. 1–16, Feb. 2023.

P. C. Gilmore and R. E. Gomory, “A linear programming approach to the cutting-stock problem,” Inst. Oper. Res. Manag. Sci., vol. 9, no. 6, pp. 849–859, Jan. 1961.

W. L. Winston, Operations Research Applications and Algotihms, Fourth Edition. USA: Thomson Learning, 2004.

B. P. Silalahi, F. Hanum, F. Setyawan and P. T. Supriyo, “One dimensional cutting stock problem that minimizes the number of different patterns,” Barekeng: Journal of Mathematics and Its Application., vol. 16, no. 3, pp. 805–814, Sept. 2022.

J. Bagherinejad and M. Shoeib, “Dynamic capacitated maximal covering location problem by considering dynamic capacity,” Int. J. Ind. Eng. Comput., vol. 9, no. 2, pp. 249–264, March 2018.

M. Herda, “Parallel genetic algorithm for capacitated p-median problem,” Procedia Eng., pp. 313–317, May 31-June 2, 2017.

A. I. Kusuma, A. W. Widodo and M.A. Fauzi, “optimasi sisa bahan baku pada industri mebel menggunakan algoritma genetika,”Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer, vol. 2, no. 3, pp. 1119–1125, March 2018.

B. Santoso and H. Haerudin, “Genetic algorithm approach for cutting stock problems in construction industries,” Int. J. Integr. Sci., vol. 2, no. 7, pp. 957–970, July 2023.

E. K. Burke and G. Kendall, Introduction Tutorials in Optimization and Decision Support Techniques. New York: Springer, 2005.

S. Kartolo and C. Natalia, “Website design optimization of cutting stock problem on 1 and 2 dimentions by using genetic algorithm,” Jurnal IPTEK Media Komunikasi Teknologi, vol. 24, no. 2, pp. 85–94, Dec. 2020.

H. A. Taha, Operations Research an Introduction , Tenth Edition. Harlow: Pearson Education Hall, Newark, 2017.

A. Kusnadi and D. S. Santoso, “Implementasi algoritma genetika pada penempatan tugas asisten laboratorium berbasis web (studi kasus: LAB ICT universitas multimedia nusantara),” ULTIMACS, vol. 7, no. 2, pp. 139–147, 2015.

D. E. Goldberg, Genetic Algorithms in Search, Optimization & Machine Learning. Canada: Addison-Wesley Publishing Company, INC, 1989.

A. Mehdary, A. Chehri, A. Jakimi, and R. Saadane, “Hyperparameter optimization with genetic algorithms and xgboost: a step forward in smart grid fraud detection,” Sensors, vol. 24, no. 4, pp. 1–24, Feb. 2024.

T. F. D. Aditama and Azhari. SN, “Determining community structure and modularity in social network using genetic algorithm,” IJCCS (Indonesian J. Comput. Cybern. Syst., vol. 14, no. 3, pp. 219–230, July 2020.

G. Valerian, T. Sutrisno and D. E. Herwindianti, “Image clustering using genetic algorithm with tournament selection and uniform crossover,” IOP Conferences Series: Materials Science and Engineering, 852 (2020), 012043.

Z. Michalewicz, Genetic algorithms + Data Structures = Evolution Programs, Third Edition. New York: Springer, 1995.

M. Devilawanti, S. H. Sitorus and Ilhamsyah, “Sistem seleksi calon pejabat tinggi pratama dengan menggunakan algoritma genetika,” Coding Jurnal Komputer dan Aplikasi, vol. 07, no. 03, pp. 75–84, Dec. 2019.

A. Tohari and Y. P. Astuti, “Penerapan algoritma genetika dalam menentukan rute terpendek pt. pos cabang lamongan,” MATH UNESA Jurnal Ilmiah Matematika, vol. 11, no. 03, pp. 458–467, 2023.

N. W. S. Saraswati, I. D. M. D. Dwiastuti and I. G. A. A. D. Indradewi, “Modified genetic algorithm for employee work shifts schedulling optimization”, Journal of Physics: Conferences Series, 1810 (2021),012014.

A. Syarif, Aristoteles, A. Dwiastuti and R. Malinda, “Performance evaluation of various genetic algorithm approaches for knapsack problem”, ARPN Journal of Engineering and Applied Scinces, 11 (2016), 4713 - 4719.

M. Affenzeller, S. Winkler, S. Wagner and A. Beham, Genetic Algorithms and Genetic Programming Modern Concepts and Practical Applications, CRC Press, New York, 2009.

R. L. Haupt and S. E. Haupt, Practical Genetic Algoritms, Second Edition, A john Willey & Sons, INC., Publicarion, Canada, 2004.




DOI: https://doi.org/10.15548/jostech.v5i1.10183

Refbacks

  • There are currently no refbacks.


Copyright (c) 2025 JOSTECH Journal of Science and Technology

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.