PENYELESAIAN MASALAH CUTTING STOCK DENGAN PENGELASAN MENGGUNAKAN MODEL ARC-FLOW DAN ALGORITMA PATTERN GENERATION

Masalah cutting stock dengan pengelasan adalah masalah penentuan pola pemotongan dan pengelasan bahan baku untuk memenuhi permintaan dengan bahan baku yang sedikit mungkin. Penelitian ini menggunakan model Arc-Flow dan algoritma Pattern Generation untuk menyelesaikan permasalahan pemotongan pipa. Model Arc-Flow merepresentasikan permasalahan cutting stock dengan pengelasan dalam bentuk graf berarah asiklik. Model ini bertujuan untuk menentukan aliran minimum (flow) dari simpul awal ke simpul akhir pada graf. Sedangkan, algoritma Pattern Generation menghasilkan pola-pola pemotongan yang feasible dengan menggunakan pohon pencarian. Pola pemotongan yang telah diperoleh dapat dipilih kembali agar diperoleh pola pemotongan optimal. Hasil implementasi menunjukan bahwa model Arc-Flow dan algoritma Pattern Generation dapat menyelesaikan masalah cutting stock dengan pengelasan. Berdasarkan hasil pengujian diperoleh bahwa solusi yang dihasilkan model Arc-Flow lebih optimal jika dibandingkan dengan solusi hasil implementasi algoritma Pattern Generation. Cutting stock with welding problem is a problem to find the patterns of cutting and welding raw materials to meet demand with as few raw materials as possible. In this research, we use Arc-Flow model and Pattern Generation algorithm to solve the problem. The Arc-Flow Model represents the problem using acyclic directed graphs. Then, we should determine the minimum flowfrom the initial node to the end node on the graph. On the other hands, the Pattern Generation algorithm produces feasible cutting patterns using a search tree. The cutting patterns that have been obtained can be reselected to an optimal level. Then, we should choose the optimal patterns. The computational results show that the Arc-Flow model and Pattern Generation algorithm can be implemented to solve the cutting stock with welding problem. According to the test data, we can conclude that the solutions of the Arc-Flow model are more optimal than the solutions of the Pattern Generation algorithm