Penyelesaian Matching Problem dengan menggunakan Algoritma arus maksimal pada sebuah network

ABRORI, Muchammad, Drs. Retantyo Wardoyo, MSc.,PhD

2007 | Tesis | S2 Ilmu Komputer

Sebuah matching merupakan masalah mengenai mengawankan elemenelemen dalam sebuah himpunan dengan elemen-elemen dalam himpunan yang lain. Contoh aplikasi dari matching ini adalah dalam hal penempatan karyawan baru agar masing-masing karyawan mendapat pekerjaan sesuai dengan kualifikasinya masing-masing, pemberian tugas mengajar dosen agar sesuai dengan keahlian yang dimiliki masing-masing, pada perjodohan supaya setiap laki-laki dapat menikahi wanita yang sesuai dan lain-lain. Situasinya dapat dimodelkan dengan menggunakan graf. Matching direpresentasikan sebagai arus dalam suatu model network transportasi (yang selanjutnya disebut sebagai network). Apabila arus maksimal maka matching adalah maksimal. Sehingga permasalahannya bagaimana menyelesaikan matching problem dengan menggunakan algoritma arus maksimal dalam sebuah network. Hasil penelitian antara lain bahwa a) Matching Problem adalah kejadian khusus dari pencarian arus maksimal dimana kapasitas setiap edge-nya adalah satu; b) dalam matching problem tidak ada edge yang mempunyai sifat improperly oriented; c) algoritma arus maksimal mampu membantu para manajer dalam suatu perusahaan atau institusi dalam mengambil keputusan terutama menyangkut pemberian pekerjaan, penempatan posisi karyawan, pengiriman delegasi dan sebagainya

another set. Examples of matching application are new employee placement in order to fit with their qualifications, lecturer’s teaching schedule in order to fit with their major, on marriage suppose each man can marry a compatible woman, etc. The situations can be modeled by graphs. A matching is represented as a flow in a transportation network model. If a flow is maximal then a matching is maximal. So the problem is how to solve matching problem with maximal flow algorithm on a network The result among other things: a) Matching Problem is a special case from finding maximal flow algorithm on a network; b) in matching problem there isn’t an edge which is improperly oriented; c) maximal flow algorithm is able to help manager in a firm or institution to decide something especially about giving jobs, positioning employees, choosing delegation, etc.

Kata Kunci : Algoritma Arus,Network,Matching, mapping, transportation networks, capacity