Riset Operasi (masalah Penugasan)

V. Masalah Penugasan (Assignment Problem)
Masalah penugasan terjadi dalam berbagai varian proses pembuatan keputusan;
umumnya masalah penugasan melibatkan penunjukkan seseorang untuk mengoperasikan
mesin tertentu, pelaksanaan penjualan di satu wilayah, pelaksanaan riset dan sebagainya.
Salah satu sifat khusus dari masalah penugasan adalah seorang personil ditunjuk untuk
melaksanakan satu dan hanya satu tugas. Tujuannya adalah meminimumkan biaya, atau
waktu ataupun untuk memaksimumkan keuntungan.
Ilustrasi:
Sebuah lembaga konsultan mendapatkan tawaran untuk melaksanakan riset pemasaran
dari tiga perusahaan yang merupakan klien baru mereka. Lembaga konsultan tersebut
menghadapai masalah menentukan siapa dari tiga orang stafnya yang harus bertindak
sebagai pimpinan proyek untuk masing-masing studi tersebut karena tiga orang tersebut
memiliki keahlian dan pengalaman riset yang berbeda sedangkan ketiga studi tersebut
memiliki prioritas yang sama. Lembaga tersebut bermaksud meminimumkan waktu
pengerjaan untuk dapat menyiapkan diri menghadapi pesanan dari klien berikutnya. Jika
seorang pimpinan proyek hanya mengerjakan satu tugas riset, bagaimanakah penugasan
yang dilakukan dalam arti siapa mengerjakan riset yang mana ?
Untuk menyelesaikan masalah penugasan maka lembaga konsultan tersebut harus
mempertimbangkan semua kemungkinan penugasan dan mengestimasi waktu pengerjaan
yang diperlukan. Dengan tiga orang pimpinan proyek (pimpro) dan tiga klien maka
terdapat sembilan alternatif penugasan yang mungkin dilakukan. Alternatif penugasan
dan estimasi waktu penyelesaian (minggu) disajikan pada tabel berikut:
Klien
Pimpinan proyek 1 2 3
1. Dea 18 15 13
2. Ahza 16 14 9
3. Bayang 15 12 7
Dari data di atas terlihat bahwa Dea memerlukan waktu 18 minggu untuk menyelesaikan
riset klien 1 sementara Bayang membutuhkan 15 minggu untuk proyek yang sama.
Ilustrai masalah penugasan tersebut ditampilkan juga pada gambar berikut dimana
lingkaran (nodes) berhubungan dengan pimpinan proyek dan klien sedangkan garis lurus
bertanda panah berhubungan dengan kemungkinan penugasan yang mungkin dilakukan.
Penawaran (supply) dan permintaan (demand) untuk masing-masing node adalah 1;
sedangkan biaya berasosiasi dengan waktu yang diperlukan untuk menyelesaikan riset
tersebut.
1
1
1
Oleh karena terdapat sembilan kemungkinan alternatif penugasan maka berarti ada
sembilan variabel keputusan (decision variables) pada fungsi tujuan. Dengan
menggunakan double-scripted decision variables, maka X11 berarti penugasan untuk
pimpinan proyek 1 (Dea) mengerjakan proyek dari klien 1; X12 berarti penugasan untuk
pimpinan proyek 1 (Dea) mengerjakan proyek dari klien 2 dan sebagainya. Dengan
demikian variabel keputusan dari masalah tersebut secara umum adalah:
Klien
(destination nodes)
Pimpinan
Proyek
( i i d )
7
14
9
13
16
Klien
3
12
15
1
Dea
2
Ahza
Klien
1
18
15
Klien
2
3
Bayang
Supplies Kemungkinan Penugasan Demands
1
1
1
Xij =
1
0


sehingga Xij =1 berarti pimpinan proyek i ditugaskan untuk mengerjakan proyek klien j,
sedangkan bila Xij = 0 berarti sebaliknya (tidak ditugaskan); i = 1, 2, 3 dan j = 1, 2, 3
Dengan demikian X21= 1 dan X31= 0 berarti pimpinan proyek 2 (Ahza) ditugaskan untuk
mengerjakan riset klien 1 sedangkan pimpinan proyek 3 (Bayang) tidak ditugaskan untuk
riset klien 1.
Dengan menggunakan notasi ini dan data estimasi penyelesaian tugas pada tabel atau
gambar di atas maka kita dapat merumuskan fungsi tujuan dari persoalan penugasan
seperti disajikan pada persamaan berikut:
Jumlah minggu yang diperlukan oleh
Dea untuk menyelesaikan riset = 18 X11 + 15 X12 + 13 X13
Jumlah minggu yang diperlukan oleh
Ahza untuk menyelesaikan riset = 16 X21 + 14 X22 + 9 X23
Jumlah minggu yang diperlukan oleh
Bayang untuk menyelesaikan riset = 15 X31 + 12 X32 + 7 X33
Total dari jumlah minggu yang dibutuhkan oleh ketiga pimpinan proyek tersebut
menghasilkan total minggu yang diperlukan untuk menyelesaikan ketiga pekerjaan
tersebut. Dengan demikian fungsi tujuan dituliskan sebagai:
Min 18X11 + 15X12 + 13X13 + 6X21 + 14X22 + 9X23 + 15X31 + 12X32 + 7X33
Pembatas dari masalah penugasan tersebut mencerminkan kondisi yang harus dipenuhi
yaitu satu pimpinan proyek paling banyak mengerjakan satu tugas riset dari klien dan
satu klien hanya dilayani oleh satu pimpinan proyek. Fungsi pembatas tersebut adalah:
X11 + X12 + X13 ≤ 1 Dea
X21 + X22 + X23 ≤ 1 Ahza
X31 + X32 + X33 ≤ 1 Bayang
X11 + X21 + X31 = 1 Klien 1
X12 + X22 + X32 = 1 Klien 2
X13 + X23 + X33 = 1 Klien 3
Dengan menggabungkan fungsi tujuan dan fungsi pembatas kedalam satu model maka
diperoleh model linear dari lembaga konsultan tersebut, yaitu:
Min 18X11 + 15X12 + 13X13 + 6X21 + 14X22 + 9X23 + 15X31 + 12X32 + 7X33
s.t.
X11 + X12 + X13 ≤ 1
X21 + X22 + X23 ≤ 1
X31 + X32 + X33 ≤ 1
X11 + X21 + X31 = 1
X12 + X22 + X32 = 1
X13 + X23 + X33 = 1
Xij ≥ 0 untuk i = 1, 2, 3 dan j = 1, 2, 3
Tabel berikut menyajikan solusi komputer dengan menggunakan program LINDO/PC
dari persoalan penugasan tersebut. Hasilnya, Dea mengerjakan proyek klien 2 (X12 = 1),
Ahza bertanggung jawab untuk proyek klien 1 (X21 = 1) dan Bayang ditugaskan untuk
mengerjakan proyek klien 3 (X33 = 1). Total waktu kerja yang diperlukan untuk
menyelesaikan proyek tersebut adalah 38 minggu kerja orang (MKO).
LP OPTIMUM FOUND AT STEP 5
OBJECTIVE FUNCTION VALUE
1) 38.000000
VARIABLE VALUE REDUCED COST
X11 .000000 1.000000
X12 1.000000 .000000
X13 .000000 3.000000
X21 1.000000 .000000
X22 .000000 .000000
X23 .000000 .000000
X31 .000000 1.000000
X32 .000000 .000000
X33 1.000000 .000000
Ringkasan penggunaan waktu penyelesaian tugas disajikan pada tabel berikut:
Pimpinan proyek Klien Penyelesaian
Dea 2 15
Ahza 1 16
Bayang 3 7
Total 38