PENYELESAIAN MASALAH PENUGASAN YANG DIPERUMUM DENGAN MENGGUNAKAN ALGORITMA BRANCH-AND-BOUND YANG DIREVISI

Abstract

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.
Kata Kunci: Masalah penugasan yang diperumum, algoritma branch-andbound
yang direvisi, masalah knapsack biner.
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.
Keywords: Generalized assignment problem, revised branch-and-bound
algorithm, binary knapsack problem.