<![CDATA[ABSTRAK. Masalah penugasan yang diperumum merupakan perumumandari masalah penugasan klasik. Pada masalah penugasan yang diperumum,satu agen dapat dipasangkan dengan lebih dari satu tugas dan terdapatkendala berupa pembatasan sumber daya yang diberikan kepada setiapagen dalam melakukan tugasnya. Berbasis algoritma branch-and-bound,penelitian ini mengembangkan algoritma tersebut untuk menyelesaikanmasalah penugasan yang diperumum. Yaitu algoritma branch-and-boundyang direvisi yang dibahas dalam penelitian ini. Algoritma ini bekerjadengan cara menyelesaikan serangkaian masalah knapsack biner untukmemperbaiki nilai batas bawah dari setiap node, sehingga diperolehpercabangan yang lebih sedikit dibandingkan dengan algoritma branchand-boundbiasa. Akibatnya solusi optimal diperoleh dengan waktu yanglebih cepat.Kata Kunci: Masalah penugasan yang diperumum, algoritma branch-andboundyang direvisi, masalah knapsack biner.ABSTRACT. Generalized assignment problem is a generalization of theclassical assignment problem. In the generalized assignment problem, theagent can be assigned with more than one task and there are constraint thatis restrictions on the resources provided to each agent for handle the task.Based on branch-and-bound algorithm, this research develops thealgorithm for solving the generalized assignment problem. That is revisedbranch-and-bound algorithm that used in this research. The algorithmworks by solving a series of binary knapsack problems to improve thelower bounds of each node. So that we obtain branches less than thebranches obtained by the classical branch-and-bound algorithm. Hence theoptimal solution obtained in more efficiently.Keywords: Generalized assignment problem, revised branch-and-boundalgorithm, binary knapsack problem.]]>
Copyrights © 2017
