Penyelesaian Masalah Penugasan yang Diperumum dengan Menggunakan Algoritma Branch-and-Bound yang Direvisi

Abstract

Generalized assignment problem is a generalization of the classical assignment problem. In the generalized assignment problem, the agent can be assigned with more than one task and there are constraint that is restrictions on the resources provided to each agent for handle the task. Based on branch-and-bound algorithm, this research develops the algorithm for solving the generalized assignment problem. That is revised branch-and-bound algorithm that used in this research. The algorithm works by solving a series of binary knapsack problems to improve the lower bounds of each node. So that we obtain branches less than the branches obtained by the classical branch-and-bound algorithm. Hence the optimal solution obtained in more efficiently.

ABSTRAK

Masalah penugasan yang diperumum merupakan perumuman dari masalah penugasan klasik. Pada masalah penugasan yang diperumum, satu agen dapat dipasangkan dengan lebih dari satu tugas dan terdapat kendala berupa pembatasan sumber daya yang diberikan kepada setiap agen dalam melakukan tugasnya. Berbasis algoritma branch-and-bound, penelitian ini mengembangkan algoritma tersebut untuk menyelesaikan masalah penugasan yang diperumum. Yaitu algoritma branch-and-bound yang direvisi yang dibahas dalam penelitian ini. Algoritma ini bekerja dengan cara menyelesaikan serangkaian masalah knapsack biner untuk memperbaiki nilai batas bawah dari setiap node, sehingga diperoleh percabangan yang lebih sedikit dibandingkan dengan algoritma branchand-bound biasa. Akibatnya solusi optimal diperoleh dengan waktu yang lebih cepat.