PENYELESAIAN MASALAH PENUGASAN YANG DIPERUMUM DENGAN METODE BRANCH AND PRICE - Deni Septian, - (2021)
Masalah penugasan yang diperumum adalah peluasan dari masalah penugasan klasik, dimana satu tugas dipasangkan dengan tepat satu agen, tetapi satu agen dapat mengerjakan lebih dari satu tugas tergantung bobot tugas dan kapasitas agen. Tujuan penyelesaian masalah penugasan yang diperumum adalah untuk menentukan penugasan optimal, yaitu penugasan yang menghasilkan keuntungan yang besar atau meminimalkan biaya. Penelitian ini meterapkan metode Branch and Price (B&P) untuk menyelesaikan masalah penugasan yang diperumum. Metode B&P merupakan gabungan dari teknik Column Generation dan Branch and Bound (B&B). Metode B&B menyempurnakan teknik column generation, yang tidak menjamin dapat memberikan solusi berupa bilangan bulat, dengan menggabungkannya dengan metode B&B. Hasil implementasi model penugasan yang diperumum dengan metode B&P pada masalah penugasan penjahit pada salah satu perusahaan konveksi di Kota Bandung menunjukkan bahwa metode B&P dapat menyelesaikan model penugasan yang diperumum dan mampu memberikan penugasan yang optimal. The generalized assignment problem is an extension of the classical assignment problem, where each task is paired with exactly one agent, but each agent can be assigned to more than one task depending on the weight of the task and the capacity of the agent. The generalized assignment problem is solved to determine the optimal assignment, that is the assigment with the largest profit or the lowest cost. In this study, the Branch and Price (B&P) method was applied to solve generalized assignment problems. The B&P method is a combination of the Column Generation techniques and Branch and Bound (B&B). Using the column generation technique, the optimal solution does not guarantee as integer solutions. Therefore the B&P method enhances the column generation technique by combining the B&B method in order to obtain integer solutions. The results show that the generalized assignment model using the B&P method can be applied to solve the tailor's assignment at a convection company in Bandung, and it can provide optimal assignments.