PENGGUNAAN METODE BRANCH AND BOUND UNTUK MENYELESAIKAN MASALAH PENUGASAN PADA KASUS PENYUSUNAN JARINGAN KOMUNIKASI

Abstract

Assignment problem is how to match exactly only one agent for one task, the aim is to get
maximum advantage or minimum cost. One of assignment problem case is arranging
communication network, that how to make order formation of sending Short Massage Service
(SMS) from someone to another one in a group. Each one in that group has to send one SMS to the
other member. The last stage in this process is the SMS was sent by the first sender will comeback
to the first sender again as indication that all of member of a group was received SMS.
Arranging communication network is done by using branch and bound method by distributing
the big scale problem to the small until it can be solved. Distributing is done recursive until formed
tree structure. The objective of this research is how to find optimal solution for solving assignment
problem in arranging communication network by using branch and bound method.
This research is done with literature study method that is by collecting and studying from
supporter reference related to assignment problem and branch and bound method. Procedure in
this research that is forming cost matrix, reducing rows and columns, counting up all rows and
columns reducer as bound of 0 node. 0 node have branch that called first level, node’s bound of
first level finding by using formula Cs = Cr + Ci,j + r. optimum bound of first level make as E-node
that will branched and resulting second level, etc. 

The result of research is finding one of communication network that below: Simpati  As
Halo Matrix Mentari starOne Im3Flexi Fren XL Simpati with minimum cost
Rp 1.298.