PEMODELAN MASALAH PENUGASAN (ASSIGNMENT PROBLEM) DENGAN KOEFISIEN ONGKOS KABUR

Nomor I/Tahun XXII

Majalah I1miah Matematika dan Komputer, April 2006 ISSN 0216-4728

PEMODELAN MASALAH PENUGASAN (ASSIGNMENT PROBLEM) DENGAN KOEFISIEN ONGKOS KABUR Sani Susanto' Dedy Suryadi ' 1,2Jurusan Teknik Industri, Fakultas Teknologi Industri,Universitas Katolik Parahyangan J1. Ciurnbuleuit 94, Bandung - 40141. Tlp/Fax: (022) 232700 [email protected], [email protected] ABSTRAK

Masalah penugasan (MP, assignment problem) sebagai bentuk khusus dari masalah pemrograman linier telah banyak dibahas. Namun demikian, sebagian besar pembahasannya masih didasarkan pada asumsi bahwa besamya ongkos/waktu pengerjaan tugas bersifat tertentu. Tulisan ini membahas MP dalam hal asumsi ini terlanggar, artinya, ongkos/waktu pengerjaan suatu tugas tidak berupa bilangan tunggal , melainkan berupa nilai yang berada padasuatu interval tertentu. Kata kunci: Masalah Penugasan (Assignment Problem) , bilangan kabur.

PENDAHULUAN

Pada masalah

penugasan

(MP, assignment

problem) diberikan sejumlah sumber daya yang

dapat mengerjakan sejumlah pekerjaan dengan ongkos total pengerjaan yang diketahui secara pasti/tepat . Setiap sumber daya hanya mengerjakan satu pekerjaan, demikian pula sebaliknya. Tujuan dari pemecahan MP adalah menentukan satu pekerjaan manakah (dari sejumlah pekerjaan yang ada) yang harus dikerjakan oleh seorang pekerja (dari sejumlah pekerja yang ada), dan sebaliknya, agar ongkos total pengerj aan menjadi serendah mungkin. Dalam hal ini, besaran ongkos pengerjaan dapat digantikan dengan waktu pengerjaan . Berdasarkan klasifikasi modellpermasalahan pada penelitian operasional, MP merupakan bentuk khusus masalah transportasi (MT). Adapun MT dapat dimodelkan sebagai masalah pemrograman linier bilangan bulat (MPLBB). Dengan demikian, MP dapat didekati melalui MPLBB, khususnya MPLBB 0-1 . MP yang banyak dibahas dalam literatur didasarkan pada asumsi bahwa koefisien ongkos pengerjaan diketahu i dengan pasti/tepat. Artinya setiap koefisien ini cukup dinyatakan cukup dengan sebuah bilangan saja. Pada kenyataannya , mungkin sekali terjadi kekaburan (juzzyness) pada koefisien-

koefisien tersebut. Artinya, besar kemungkinan bahwa koefisien-koefisien ongkos itu tidak mengambil nilai berupa sebuah bilangan saja, melainkan nilainya berada pada suatu interval. Jadi, diperlukan suatu pemoC:elan MP yang dapat mengakomodasi kekaburan koefisien ongkos, agar pembahasan MP menjadi lebih realistis. Pemodelan MP biasa menjadi MP dengan koefisien ongkos yang kabur dapat dilakukan dengan memodelkan MP ke dalam masalah pemrograman linier dengan koefisien fungsi objektif kabur (MPLKFOK) 0-1 . Model yang dihasilkan merepresentasikan pemodelan masalah penugasan kabur (MPK). TINJAUAN PUSTAKA

Pada perumusan model MPLKFOK 0-1 untuk MPK terdapat beberapa teori yang melandasinya. Teori-teori tersebut meliputi perumusan MP dalam bentuk masalah pemrograman linier (MPL) bersifat crisp, dan konsep bilangan kabur. Masalah Penugasan. MP terbentuk dari adanya hal-hal berikut: terdapat m-buah sumber daya dan n buah pekerjaan , setiap sumber daya dapat mengerjakan semua jenis pekerjaan yang tersedia dan setiap pekerjaan boleh dikerjakan oleh semua sumber daya yang ada, ongkos yang timbul sebagai akibat penugasan sumber daya ke-i untuk

Matematika dan Komputer

14 SUSANTO & SURY AD!

mengerjakan pekerjaan ke-) adalah sebesar ci) satuan, harus ditentukan penugasan dengan total ongkos terendah sehingga sebuah pekerjaan hanya dikerjakan oleh sebuah sumber daya, dan sebaliknya. MP tersebut dapat dirumuskan ke dalam MPLBB 0-1 sebagai berikut: i em j;n

minimasi LLcijxi) j;)

(2.1)

j;l

dengan kendala (2.2) (2.3) X i}

=0

a/au 1

(2.4)

dimana: Cij, disebut koefisien jungsi objektif (KFO) atau koefisien ongkos yang menyatakan ongkos atau waktu untuk menugaskan sumber daya-i mengerjakan pekerjaan-), Xij bemilai 1 bila sumber daya-i ditugaskan untuk mengerjakan pekerjaan-j i;:; m j;n

dan bemilai 0 bila tidak demikian , L L ci)xi) i ;1

j;l

merupakan fungsi objektif dari MP yang menyatakan ongkos total penugasan setiap sumber daya untuk mengerjakan setiap pekerjaan, satu orang pekerja tertentu hanya mengerjakan satu jenis pekerjaan j =n

tertentu atau

L xij = 1,

satu pekerjaan tertentu

j; l

hanya dikerjakan oleh satu orang pekerja tertentu i=m

atau LXi)

= I, i = 1,2,.. .,m

(m = jumlah pekerja)

;;)

danj =1,2,...,n (n = jumlah pekerjaan). Rumusan MP dengan fungsi objektif (2.1) dibuat berdasarkan asumsi bahwa KFO cij bernilai tentu, yaitu berupa sebuah bilangan tunggal. Pada kenyataannya, seringkali nilai KFO tidak berupa bilangan tunggal, melainkan berada pada sebuah interval. Kenyataan tersebut dapat diakomodasi dengan membangun sebuah model yang baru bagi MP. Model baru itu mengizinkan pelanggaran Cij dengan asumsi ketertentuan KFO membolehkannya mengambil nilai pada suatu interval. Untuk itu, diperlukan konsep bilangan kabur yang akan dibahas pada bagian berikutnya.

Konsep Bilangan Kabur (Susanto dan Adianto, 2005). Konsep bilangan kabur muncul karena sering tidak mungkin digunakan frase tepat sekian, melainkan harus menggunakan frase yang menggambarkan ketidaktepatan, seperti: sekitar sekian, kira-kira sekian, hampir sekian atau kurang lebih sekian. Contohnya, seorang operator dapat menyelesaikan pekerjaan memasang satu kancing baju dalam waktu kurang lebih 15 detik. Pada Matematika terdapat konsep yang mengakomodasi situasi ketidaktepatan. Konsep tersebut dibangun oleh Lotti Zadeh pada tahun 1965 (Wang, 1997). Nama konsep itu bervariasi, ada yang menyebutnya Fuzzy Logic, Fuzzy Sets, Fuzzy Mathematics. Istilah fuzzy belum mendapatkan keseragaman terjemahan. Beberapa terjemahan tersebut adalah : kabur, tidak tegas, halus . Dalam tulisan ini dipilih padanan kabur untuk kata fuzzy , dan konsep yang akan digunakan, adalah konsep bilangan kabur ataufuzzy number.

Tinjau A, himpunan bilangan yang sarna dengan 3, jadi A= {3}. Himpunan ini hanya memiliki sebuah anggota , yaitu 3. Himpunan ini dicirikan oleh fungsi berikut, yang disebutfungsi karakteristik dari himpunan A, atau JlA (x) yang persamaannya adalah: I , jika x = 3 ~ A (x) = { 0, Jliika x « 3 Fungsi ini memberikan derajat keanggotaan pada setiap unsur di himpunan semesta. Misalnya, 3 memiliki derajat keanggotaan penuh, yaitu 1, terhadap A. Bilangan 5, 4,2,1 tak memiliki derajat keanggotaan , atau derajat keanggotaannya O. Bilangan 3.1; 3.01; 3.001; 2.999;2.99;2 .9 nilainya cukup dekat terhadap 3, namun terhadap himpunan A bilangan ini berderajat keanggotaan O. Himpunan yang hanya mengenal dua jenis relasi (anggota atau bukan anggota) antara suatu unsur dengan suatu himpunan disebut himpunan tegas (crisp set) . Himpunan ini, hanya mengenal dua macam derajat keanggotaan, yaitu keanggotaan penuh (full membership) dengan n i lai fungsi karakteristik sebesar 1, serta ketidakanggotaan sarna sekali (full nonmembership). Berbeda dengan himpunan tegas, himpunan kabur (fuzzy set) , mengenal konsep keanggotaan sebagian (partial membership). Contohnya, bilangan 3.1 atau 2.9 masih mendapat semacam pengakuan


Nomor I, 2006

sebagai anggota A, misalnya, masing-masing dengan derajat keanggotaan 0.9. Bila himpunan nilai derajat keanggotaan himpunan tegas adalah himpunan biner {O;I}, maka himpunan nilai derajat keanggotaan himpunan kabur adalah interval tertutup [0,1]. Himpunan bilangan yang nilainya sekitar (kira kira, hampir, kurang lebih) 3 adalah contoh himpunan kabur, disebut bilangan kabul' 3. Ada dua jenis bilangan kabur yang biasa digunakan : bilangan

15

kabul' segitiga (triangular fuzzy number) dan bilangan kabul' trapesium (trapezoidal fuzzy number) (Wang, 1997). Tulisan ini membahas jenis pertama. Bilangan kabul' segitiga c ij' ditulis Cj , dengan batas bawah cijdan batas atas C~ didefinisikan oleh

fungsi keanggotaan segitiga berikut:

(X-Cij)/(b-Ci),jikacij :S;x
= (c,j -xy(c,j -Cjj),j ik£Cjj s x :S;C~ {

(2.5)

O,jikax>c,j ataux
Bilangan kabur segitiga Cj pada (2.5) sering dilambangkan dengan

Cj

=

(2.6)

(Cij'Cij'C j;)

Sebagai contoh bilangan kabur segitiga 3, atau 3 ,secara subjektif, dapat didefinisikan melalui fungsi keanggotaan: 2(X- 2.5),jika 2.5:S; x < 3} 3

= 113(x;2.5,3 ,4) =

-(4 -x), jika Ls x < 4 {

= (3- ,3,3+) =(2.5, 3, 4)

O,jika x> 4 atau x < 2.5

Pada himpunan bilangan kabur segitiga 3, atau 3 , derajat keanggotaan beberapa anggotanya disajikan pada Tabel-l. Tabell . Beb--

-.- ilai deraiat k ---

dari

--- -00-----. - -- - h' ----- -.-- --_ . bit ------0--- -----. --0-- -0-

3

2.5

2.6

2.7

2.8

2.9

3

3.2

3.4

3.6

3.8

4

fi 3 (x;2.5,3,4)

0

0.2

0.4

0.6

0.8

1

0.8

0.6

0.4

0.2

0

METODE PENELITIAN Tinjau Masalah Penugasan (2.1 )-(2.4). Misalkan KFO c ij pada (2.1) tidak berupa bilangan tunggal yang tegas (crisp) melainkan berbentuk bilangan kabur (fuzzy), khususnya berbentuk bilangan kabur segitiga Cj , seperti didefinisikan pada persamaan (2.5). Untuk itu perlu ditetapkan batas bawah dan

batas atas bagi

kab

X

cij '

misalkan saja cjj dan c~. Jadi

bilangan kabur segitiga Cj dapat didefinisikan oleh fungsi keanggotaan (2.5). Berikut ini adalah bahasan selengkapnya dari pemodelan MPK serta usulan solusinya .

Pemodelan Masalah Penugasan Kabur. Pengembangan model (2.1)-(2.4) menjadi MPKFOK dapat didekati dengan MPLKFOK 0 1. Perumusan MPLKFOK, dapat dilihat pada (Susanto dan Adianto, 2005), sehingga



Langkah-1: Tentukan MP yang akan diubah kedalam MPKFOK (yaitu, (2.1)-(2.4)) Langkah-Z: Tentukan jenis bilangan kabur bagi KFO (yaitu, (3.1))

penugasan satu unit sumber daya-i untuk mengerjakan tugas ke-). Langkah-4: Rumuskan pemrograman linier bertujuan majemuk berfungsi objektif meminimumkan nilai bilangan kabur segitiga sebagai berikut:

Langkah-3: Tentukan :

minimasiz = (cx.cx,c "x)

penerapannya bagi perumusan MPKFOK adalah sebagai berikut:

a) e=(cll' ..cln;c21 ...c2n;· ...; cil ...cin; ....;cml ...cmn)' . yaitu vektor KFO, dengan

Cij

ongkos yang "the most possible" bagi penugasan satu unit sumber daya-i untuk mengerjakan tugas ke:i, b)

c" =(C~I ...c~;c;I ...c;n;""; Ci~ .. .ci~ ;,,,,;C;I ...c;n)' yaitu vektor batas bawah KFO, dengan

cij

menyatakan batas bawah ongkos penugasan satu unit sumber daya-i untuk mengerjakan tugas ke j, C)

dengankendala

menyatakan

(3.2)

AXiO=,j'h

xi~ Usulan Solusi Masalah Penugasan Kabur. Dalam hal KFO

«,

pada MP (2.1)-(2.4) merupakan

bilangan kabur segitiga, maka masalah ini dapat dirumuskan menjadi masalah optimasi (3 .2). Berikut ini adalah langkah-langkah penyelesaian masalah optimasi (3.2) : Langkah-S: Untuk memecahkan (3.2) ubah masalah

+-(+ + . + + .. + + . . + +) e - cll .. .cln'c21.. .c2n' ....' cil'..cin ' ....'cml ...cmn ,

tersebut menjadi:

yaitu vektor batas bawah KFO, dengan c; menyatakan

batas

atas

max

ongkos

pengiriman

= (e - c)», min Z2 = cx.rnin z , = (c ' - e)x

ZI

dengan kendala Ax

(3.:)

~,= , 2:b

x ..I) = 0, 1 Langkah-6: Untuk memecahkan masalah (3.3) ditempuh sub-langkah berikut ini: Sub-langkah 6-1: Tentukan nilai-nilai berikut ini: min Zl

=

Z~a x

=

• nun

I

2

min

Z 2

z~ax

e-e -) X

(3.4)

(c cjx

(3.5)

ex

(3 .6)

ex

(3.7)

(c ' - e)x

(3 .8)

(e+- e) X

(3 .9)

max

xO;< ={x IAXI~,2:

zmax

(

xQ ;<={xIAX i ~ . > b ,x lj = O,I }

=

v

b ,x lj =O,I)

max

XEX=\xIAX S .= ,2: b ,x lj=O ,11

=

.

min xeX=(x IAxs,=,2: b ,x lj= O,11

=

,max xO ;< =(X IAXi ~ , 2: b,X ij=O,I }

min

Z 3

=

. rrun xG;<={ xlAx jlJ= ,2:b , Xlj =O,I }

Sub-langkah 6-2: Definisikan ketiga fungsi keanggotaan berikut:


Nomor I, 2006

o , jika (e-e-)x~Z~in (e - e-)x - Zmin . fl (x)=~ . 1 jika zmm ~(e-e-)x~zmax ZJ 1 max mm' 1 1 Zl

flZl (x)

=

=

(3.10)

-Zl

1

fl Z1 (x)

17

, j ika (e-e-)x;:::

z~ax

o , jika ex;:::z~ax max Z2 -ex jika zmin ~ cx s z?" max mm ' 2 2 Z2 -Z2

, jika cx s; z~in

(3,11)

o , jika (c" -e)x;:::z~ax zmax - (e+ - e)x . 3 . jika zmm ~(e+ _ e)x~zmax max mm' 3 3 Z3

(3.12)

- Z3

,jika (c' -e)x~ Z~in Sub-langkah 6-3: Definisikan masalah PL berikut ini:

max min{flz (x), flz (x),f.l. z (x)} xeX={xIAx 5 b.x=O,I ) J 1 1

(3.13)

dan definisikan pula

a =min{flz (X),flz, (x) ,flz (x)} 1

(3.14)

l

Sub-langkah 6-4 : Dapatkan masalah berikut (yang ekivalen dengan masalah Sub-langkah 2-3): max o; (3.15) dengan kendala

f.l.z (xj >o; atau (e-e- )x- cx(z~ax _z~in);::: z~ in

(3 .16)

f.l. z1(x j >« atau ex + cx(z~ ax - z;in) ~ z~ax

(3.17)

f.l. z1 (x);:::cx atau (c' -e)x+cx(z ~ax _z~in )~z~ax

(3.18)

Ax~ ,=,;:::b

(3.19)

1

os e s i x i)

= 0 atau 1

HASIL DAN PEMBAHASAN Untuk memperjelas langkah-Iangkah pembentukan dan penyelesaian Masalah Penugasan dengan Koefisien Fungsi Objektif Kabur (MPKFOK), berikut ini diberikan ilustrasi numeriknya yang berasal dari masalah Machineco (Winston, 2003) sebagai contohnya. Masalah Machineco adalah masalah penugasan dengan KFO berupa waktu yang diperlukan oleh sebuah sumber daya untuk mengerjakan pekerjaan tertentu. KFO ini sifatnya crisp, atau berupa bilangan yang nilainya

(3.20) (3.21)

tunggal. Masalah ini akan dikembangkan menjadi MPKFOK dalam hal waktu pengerjaan yang tidak lagi berupa bilangan bernilai tunggaJ , melainkan mengambil nilai pada suatu interval. Machineco memiliki empat mesin dan empat pekerjaan yang harus disel esaikan . Setiap mesin akan ditu gaskan untuk menyelesaikan sebuah pekerjaan dan sebaliknya. Harus ditentukan penuga san dari setiap mesin yang dimiliki Machin eco, agar total waktu setup yang dibutuhkan untuk menyelesaikan semua pekerjaan menjadi minimum. Waktu setup pada tiap mesin dalam



menyelesaikan setiapjenis pekerjaan seperti tertera

pada Tabel-2 berikut.

. untu k Tirap Pek erjaan . Tb12 a e Tb1Wk a e atu Setup T rap M esin Waktu Setup (menit) Mesin Pekerjaan-l Pekerjaan-2 Pekerjaan-J Pekerjaan-4 Mesin-l 480 840 300 420 Mesin-2 720 120 360 300 Mesin-3 420 480 180 540 Mesin-4 120 240 600 360 min z

= 14xII + 5xI2 + 8x\3 + 7XI4 + 2X21 + 12xn + 6X23 + 5x24 +

7X31 + 8X32 + 3X33 + 9X34 + 2X41 + 4X42 + 6X43 + lOXM

dengan kendala

XII+ XI2+ X\3+ Xl4 = 1

X21+ xn+ X23+ X24 = 1

X31+ X32+ X33+ X34 = 1

X41+ X42+ X43+ X44 = 1

X11+ X2I+ X31+ X41 = 1

X12+ xn+ X32+ X42 = 1

X\3+ X23+ X33+ X43 = 1

X14+ X24+ X34+ X44 = 1

Xij = 0 atau 1

(x - 800)/40, jika 800 ::; x < 840

Gil

= )lCII (x;800,840 ,920) =

(920 - x)/80 , jika 840 ;,; x ::; 920

{

O,jika x > 920 atau x < 800 (x -270)/30,jika 270::; x < 300

GI2

= )lCI! (x;270,300 ,360) =

(360 - x)/60 , jika 300 ::; x ::; 360 {

O,jika x > 360 atau x < 270 (x - 450)/30, jika 450::; x < 480

G\3

= !lcli (x ;450,480,540)

(540 - x)/60, jika 480 ::; x ::; 540

=

{

O,jika x> 540 atau x < 450 (x - 390)/30, j ika 390 ::; x < 420

GI 4 =)l C, (x;390,420,480)

1

= (4800 - x)/60, j ika 420 ::; x s 480 {

0, jika x > 480 atau x < 390

(x -100)/20,jika 100::; x < 120 G21

=!l c21 (x;100,120,140)

(140 - x)/20, jika 120 ::; x ::; 140

=

{

O,jika x » 140 atau x < 100 (x - 680)/40, jika 680

Gn

= !lcn (x ;680,nO,800) = (800 - x)/80, jika no {

x < no

::; x ::; 800

0, jika x > 800 atau x < 680 (x - 330)/30, jika 330

G 23 =

s

s

x < 360

/lcn (x;330,360,390) = (390 - x)/30, jika 360 ::; x ::; 390 {

0, jika x > 390 atau x < 330


Nomor 1, 2006

s

(x - 270)/30 , jika 270 C 24

= Il

(x;270,300,330)

, C2

=

(330 - x)/30, jika 300 {

s

x < 300

x ::; 330

0, jika x > 330 atau x < 270 (x - 390)/30, jika 390 ::; x < 420

C

31 = Il

C3 1

(x ;390,420,450)

=

(450 - x)/30, jika 420 ::; x {

~

450

0, jika x > 450 atau x < 390

(x - 450 )/30, jika 450::; x < 480

c 32

= Il

CJ 2

(x;450,480,540)

=

(540 - x)/60, jika 480::; x::; 540

{

0, jika x> 540 atau x < 450

(x - 160)/20, j ika 160 s x < 180

c n = llc (x;160,180,200) = (200 - x)/20, jika 180 ::; x ::; 200

JJ { O,jika x > 200 atau x < 160

(x - 520)/20, jika 520 s x < 540

C 34

= llc (x;520,540,600) = J'

(600 - x)/60, jika 540 ::; x {

~

600

0, j ika x > 600 atau x < 540

(x -100)/20,jika 100 s x < 120 C

41 = Ilc,t (x ;100,120,140) =

(140 - x)!20,jika 120::; x ~ 140

{

0,jikax>140 atau x
C 42

= llc

"

(x ;21 0,240,270)

=

(270 - x)/30 , jika 240 {

~

x ::; 270

0,jika x>270 atau x <210 (x - 330)/30 , jika 330::; x < 360

C 43

= llc (x ;330,360,390) = (390 - x)/30,jika 360 ~ x ~ 390

u { 0, j ika x > 390 atau x < 360

(x - 580)/20, jika 580::; x < 600

C 44

= ll c (x ;580,600,660) =

"

(660 - x)/60 , jika 600::; x {

~

660

O,jika x > 660 atau x < 580

Langkah-3 : Untuk kasus Machineco didapatkan vektor-vektor berikut: -- -- -- C==(C 11 CI2 Cu CI4 C21 cn C 23 C 24 C31 c 32 c n C 34 C41 C 42 C 43 - -- -- -- == (S40 300 4S0 420 120 720 360 300 420 4S0 ISO 540 120 240 360 600) -

-

-

-

CII = 840 = (840-

CI2 = 300 = (300c 13 = 480 = (480-

-

-

-

-

-

840 840+)= (800 840 920)= (C~I C0II C;I) 300 300+)= (270 300 330)=(C~2 c 012 C;2) 480 480+)= (450 480 540)= (C~3 C0I3 C;3)

CI4 = 420 = (420420 420+)=(390 420 480)= (C~4 C0I4 C;4 ) C21 = 120 = (120- 120 120+)= (l00 120 140)= (C;I C021 C;I)

C22 = 720 = (720c n = 360 = (360-

720 720+) = (680 720 800) = (C;2

c 0n

C;2 )

360 360+)= (330 360 390)= (C;3

c 0B

C;3 )

C 44 )

19


20 SUSANTO & SURYADI

-

-

C24 = 300 = (300C31 = 420 = (420-

-

-

-

-

300 420

300+)= (270 420+)= (390

300

0

330)= (C;4

C24

450)= (C~l

0

420

C;4 )

C31 C;I)

0 c 32 = 480 = (480- 480 480+)=(450 480 540)= (C~2 c 32 C;2 ) 0 c 33 = 180 = (180- 180 180+)= (160 180 200)=(C~3 C33 C;3 ) 0 C34 = 540 = (540- 540 540+)= (520 540 600)= (C~4 C34 C;4 ) 0 C41 = 120 = (120- 120 120+)= (100 120 140)= (C;l C41 C;I) C42 = 240 = (240240 240+)= (210 240 270)= (C;2 C042 C;2) C43 = 360 = (360- 360 360+)= (330 360 390)= (C;3 C043 C;3 )

C44 = 600 = (600C-

=(C;I

C;2

C;3

600

600+)= (580

C;4 C;I

C;2

C;3

600 C;4 C;I

660)= (C;4 C;2

C;3

0

C44

C;4 )

C;4 C~ I

=(800 270 450 390 100 680 330 270 390 450 160 520 100 210 330 0 0 o 0 0 0 0 0 0 0 0 0 0 CI2 C13 C14 C2\ C22 C23 C24 C31 C32 C33 C34 C41 C o = (CII =(840 300 480 420 120 720 360 300 420 480 180 540 120 240 360 + + + + + + + + C + = (+ CII CI2 Cl3 C;4 C;I Cn C;3 C24 C31 C32 C;3 C34 C41 =(920 360 540 480 140 800 390 330 450 540 200 600 140 270 390

C~2

C~ 3

C~4 )

580) C42 C43 C~4 ) 600) C+ 42 C;3 C;4 ) 660) 0

0

Langkah-A: Untuk kasus Machineco didapatkan masalah berikut: minimasi z = 800XII + 270XI2 + 450Xl3 + 390XI4 + 100X21 + 680xn + 330X23+ 270X24 + 390X31+ 450x32 + 160x33+ 520x34 + 100~1 -t 210~2 + 330~ 3 + 580~4, 840XII + 300x12 + 480x13 + 420XI4 + 120x21 + nOxn + 360X23 + 300X24 + 420X31 + 480X32 + 180x33 + 540x34 + 120~1 + 240~2 + 360~3 + 600~4, 920XII + 360x12 + 540X13 + 480XI4 + 140X21 + 800X22 + 390X23 + 330X24+ 450X31 + 540x32 + 200X33 + 600X34 + 140~1 + 270~2 + 390~3 + 560~4' dengan kendala:

Xll+ X12+ XI3+ XI4 = 1

X21+ X22+ X23+ X24 = 1

X31+ X32+ X33+ X34 = 1

~I+ ~2+ ~3+ ~4 = 1

XII+ X21+ X31+ ~I = 1

X12+ X22+ X32+ ~2 = 1

X13+ X23+ X33+ ~3 = 1

X14+ X24+ X34+ ~4 = 1

Xij = 0 atau Xij = I

Langkah-Iangkah Penyelesaian MPLKFOK Langkah-S: Untuk Machineco didapatkan:

max ZI = 40Xl1 + 30XI2 + 30x13 + 30X14 + 20X2\ + 40X22 + 30X23 + 30X24 + 30X31 + 30X32 + 20X33 + 20X34 + 20~1

+ 30~2 + 30~3 + 20~4 min Z2 = 840xII + 300XI2 + 480x13 + 420Xl4 + 120x21 + nOxn + 360X23 + 300X24 + 420X31 + 480xn + 180x33 + 540x34 + 120~1 + 240~2 + 360~3 + 600~4

min Z3 = 80XII + 60XI2 + 60XI3 + 60XI4 + 20X21 + 80X22 + 30X23 + 30X24 + 30X31 + 60xn + 20X33 + 60X34 + 20~1

+ 30~2 + 30~3 + 60X44

dengan kendala


Nomor 1, 2006

= 1

= 1

X31+ X32+ X33+ X34 = 1

X41 + X42+ X43+ X44 = 1

XII+ X21+ X31+ X41 = 1

XII+ X12+ XI3+ XI4

X21+ X22+ X23+ X24

X12+ X22+ X32+ X42 =

1

= 1

X14+ X24+ X34+ X44 = 1

X13+ X23+ X33+ X43 Xij

=

0 atau 1

Langkah-6:

Sub-langkah 6-1:

Untuk kasus Machineco, didapatkan nilai-nilai berikut ini:

z~ ax

=

max

(cv cjx

l O?:={l IAxjU;o,;, b , xij= O,I }

max

=

( 40xl 1 +3 0x12 +30xl3 + 30x14 +20x21 +40x22 +30x23 + 30x 24 + 30x3 1 +30x32 +

xOl'=lll AXj (}" ,;' b ,x;J= O,1l

20x3 3 +20x34 +20x4 1 + 30x42 +30x43 +20x 44) =1 30

z ~ jn

=

(c c)»

min

v

xO?:= [x IAXj(}",> b , xij = O,I }

min

=

(40x l 1 +30x 12 + 30x 13 +30x14 +20 x21 + 40x 22 +30x23 + 30x 24 + 30x31 +3 0x32 +

xO?:={xIAX jU;o,;, b,xij=O ,1l

20x33 +20x34 + 20x4 1 +30x4 2 +30"'43 + 20X44 )= 2 0 z min 2

min

CX

xeX ={xIAX$, =,;' b ,x 'j = O, I }

min

=

(840xI I +300x 12 +480x 13 +420x 14 + 120x21 + 720x 22 +360x 23 +

l Ol'=lx lAx jU;o ,? b , Xij= O, I}

300, 24 + 420, 3 I + 480x 32 + 180x33 + 540, 34 + 120x 4 1 + 240x42 + 360x 43 + 600, 44 ) = 900

z ~ax

= max

cx

xeX =! xij =O,l }

max

= _

x..Jl'=[x!Ax ,l.k',;' b,x=O,l)

(S 40x l l + 300x 12 +4S0xl3 +420x 14 + 120x2 1 + 720 x 22 +360x23 +

300x24 +420x 3 1 + 4sox32 +l s ox 33 + S40x 34 +120x 4 1 + 240x 42 +360x 43 +600x44 )= 2 4 60 = 24 60 zmin 3

= =

.

min

(c + - c) X

min

(sox i l +60x 12 +60x 13 +60x 14 +20x 2 1 +sox22 + 30x2 3 + 30x 24 +

xOl'=lx lAx i ~= , ;'b , x JJ = O .11

xOl' ={xlAx ,l.k',;' b , l JJ = O,I }

30x 3 1 +60x32 +20x 33 +60x 34 + 20x 4 1 +3 0x42 +30x43 + 60x4 4)=130

z max 3

=

max

(c ' - c)x

max

(soxl 1 +60x 12 +60x 13 +60x14 +20x2 1 +so x22 + 30x 23 + 30x24 + 30x3 1 +

~ xOl' ={xIAXjl.k',;' b,x IJ=O,1l

= .

xOl'=!x IAx ,l.k',;' b ,x IJ = O,I )

60x 32 +20 x33 +60x34 + 20x 41 + 30x 4 2 +30x43 +60x44) = 2 5 0

Sub-langkah 6-2:

21



Untuk kasus Machineco didapatkan: , jika (c - c- )x~20

0

Jl (x)= (c-c-)x-20 ,jika 20~(c-c-)x~130

z, 110

1 ,jika (c - c- )x~ 130

1

, jika cx~1500

0

Jlz (x)= 2460-cx ,jika 900~cx~2460

2 { 1560

1 , jika cx s 900 0 , jika (c+ -c)x~130 250 - c" - C x Jlz (x) = ( ) ,jika 130 ~(c+ - c)x~250 J 120 1 , jika (c' -c)x~ 130

Sub-langkah 6-3:

1

Definisikan MPL berikut ini: I

e X={I

I AI

max

~,=, ~ b,

I II

= 0, I}

mm {J.L

z,

(x), Jl Z 2 (x), Jl ZJ (x) J

dan

Sub-langkah 6-4: Untuk kasus Machineco didapatkan masalah: maxa

dengan kendala: (40x 11 +30X 11 +30x 13 +30X 14 +20x 21 +40X 22 +30X 23 +30X 24 + 30x 31 +30 X32 +20X 33 +20X 34 +20x 41 +30X 42 +30X 43 + 20 x44)-110a~20 (S40x II + 300X12 + 4S0XI3 + 420X I4 + 120x 21 + nOX n + 360X 23 + 300 X24 + 420x 31 +4S0 X32 + lSOx 33 +540X34 +120x 41 + 240X42 + 360 X43 +600x44)+1560a~2460 (SOX11 +60X 12 +60x 13 +60X 14 +20 x 21 +SOX n +30X 23 +30X 24 + 30x 31 +60X 32 +20X 33 +60X 34 +20x 41 +30X 42 +30X 43 +60X 44)+ O~a

120a~250

s1

XII+ X1 2+ X1 3+ XI4 = X21 + Xn+ X23+ X24 = X31+ X32+ X33+ X34 = X41+ X42+ X43+ X44 = X11+ X21+ X3 1+ X4 1 = X1 2+ X22+ X32+ X42 = X\3+ X23+ X33+ X43 = X14+ X24+ X34+ X44 = Xij = 0,1

I

1

1

1

1

1

1

1

Interpretasi Penyelesaian MPLKFOK. Dengan bantuan perangkat lunak WinQSB didapatkan solusi terhadap MPLKFOK pada sub-Iangkah 6-4 pada Bab 4.2 sebagai berikut: ex = 0.n73 XII = 0, XI 2 = I, X\3 =0, XI 4 =0


Nomor 1,2006

23

X21 =0, X22 =0, X23 =0, X24 =1, X31 =0, X32 =0, X33 = 1, X34= X4\ = I, X42 =0, X43 =0, X44= 0,

°

Artinya Machineco disarankan untuk melakukan penugasan kerja mengikuti Tabel-3 berikut.

Mesin Mesin-I Mesin-2 Mesin-3 Mesin-4

Tabel-3 SPekeriaan-I

°° ° I

_.~-

-p ----0----- K' - -- -

Pekeriaan-Z I

°° °

k Mach'---- - Pekeriaan-J Pekeriaan-4

_.~---

°° ° I

° °° I

Jadi, Machineco disarankan untuk menugaskan Mesin-I,2,3 dan 4 untuk, berturut-turut, mengerjakan Pekerjaan 2,4,3 dan I. Bila saran ini diikuti oleh Machineco, maka dari Sub-Iangkah 6-2 didapatkan: Ilz1(x) = Ilz1 (15,0,0,20,17.5,2.5,30,0,12.5,17.5,0, I0,45,20,30,30) = 0.7273 Il Z2 (x) = Ilz2 (15,0,0,20,17.5,2.5,30,0,12.5,17.5,0, I0,45,20,30,30) = 0.9167 Il z1 (x) = Il z1 (15,0,0,20,17.5,2.5,30,0,12.5,17.5,0, I0,45,20,30,30) = 1 sehingga dari definisi pada Sub-Iangkah 6-3 didapatkan nilai a=min{llz l (x),llz 2 (x),llz 1 (x)}= min{0.7273,0.9167,1} = 0.7273 Interpretasi terhadap nilai a diberikan setelah pembahasan hal berikut ini. Selanjutnya dari Langkah-5 akan didapatkan nilai-nilai: max Zl = 40Xll + 30X12 + 30X\3 + 30Xl4 + 20X21 + 40X22 + 30X23 + 30X24 + 30X31 + 30X32 + 20X33 + 20X34 + 20X41 + 30X42 + 30X43 + 20X44 = 100 menit min Z2 = 840XII + 300X\2 + 480X13 + 420X14 + 120X21 + 720X22 + 360X23 + 300X24 + 420X31 + 480X32 + 180X33 + 540X34 + 120X41 + 240X42 + 360X43 + 600X44 = 1030 menit min Z3 = 80XII + 60XI2 + 60X13 + 60Xl4 + 20X21 + 80X22 + 30X23 + 30X24 + 30X31 + 60X32 + 20X33 + 60X34 + 20X41 + 30X42 + 30X-<3 + 60X44 =130 menit Artinya, bila saran seperti tertera pada Tabel-3 diikuti oleh Machineco, maka di tengah ketidakmenentuan waktu setup mesin, waktu setup maksimum yang dihabiskan Machineco dijamin akan berkisar antara: batas bawah = Z2 - ZI = 1030 - 100 = 930 menit batas atas = Z2 + Z3 = 1030 + 130 = 1160 menit. Meski demikian, waktu setup maksimum yang bersifat paling boleh jadi (the most possible, the most likely) adalah sebesar-besamya 1030 menit. Di atas telah didapatkan nilai a = 0.7273, nilai ini berkaitan dengan nilai waktu setup maksimum sebesar 1030 menit. Artinya "derajat keboleh-jadian" terhadap perolehan solusi yang berkaitan dengan waktu setup maksimum ini adalah 0.7273. Sebagai perbandingan, "derajat kebolehjadian" bagi tercapainya skenario waktu setup terburuk (the worst case) sebesar 1160 menit, adalah 0. Sementara, "derajat kebolehjadian" bagi tercapainya skenario

waktu setup terbaik (the best case) sebesar 930 menit, adalah I. PENUTUP Berdasarkan pembicaraan sebelumnya, berikut ini dapat disampaikan beberapa butir kesimpulan dan saran, terutama saran yang berkaitan dengan potensi penelitian selanjutnya. Simpulan. Langkah-langkah Pemodelan dan Penyelesaian Masalah Penugasan dengan Koefisien Ongkos berbentuk Bilangan Kabur Segitiga telah diuraikan pada Bab 3.1-3.2. Langkah-Iangkah tersebut merumuskan Masalah Penugasan kedalam MPLBB 0-1, kemudian adanya koefisien ongkos yang kabur menjadikan terbentuknya MPLKFOK 0 I. Pencarian solusi dilakukan dengan cara mengubah MPLKFOK 0-1 menjadi MPLBB biasa.

24 SUSANTO & SURYAD!

Masalah Penugasan Kabur memiliki keunggulan atas Masalah Penugasan biasa. Keunggulan itu terletak pada kemampuannya untuk mengakomodasi kasus koefisien ongkos tidak lagi berupa bilangan tunggal melainkan mengambil nilai pada suatu interval. Kemampuan mengakomodasi kasus ini menjadi penting, karena seringkali pada realitanya koefisien ini dinyatakan dalam frase-frase yang bersifat subjektif, seperti "sekitar", "kira-kira", "hampir" atau "kurang lebih". Saran. Tulisan ini membahas pemodelan dan penyelesaian Masalah Penugasan dengan Koefisien Objektif berbentuk Bilangan Kabur Segitiga. Dari bahasan ini dapat disampaikan beberapa butir saran penelitian lebih lanjut berikut ini: Pemodelan dan Penyelesaian masalah serupa untuk kasus koefisien ongkos berupa bilangan kabur jenis lain, seperti bilangan kabur trapesium, bilangan kabur bahu kiri,


bilangan kabur bahu kanan dan lain-lain; Penyusunan analisis sensitivitas serta bentuk dual dan analisis lebih lanjut dari Model Penugasan Kabur.

DAFTAR PUSTAKA Susanto S dan Adianto H. Pemodelan dan Penyelesaian Pemrograman Linier dengan Koefisien Fungsi Objektif Berbentuk Bilangan Kabur Segitiga. Jurnal Ekonomi dan Komputer. Lembaga Penelitian Universitas Gunadarma. Nomor 2/Tahun XIII. hal 85-93 .2005 . Wang L X. A Course in Fuzzy Systems and Control. Prentice Hall International. London. 1997. Winston W L. 2003. Operations Research: Applications and Algorithms. Ed ke-4. International Thomson Publishing. California. 2003.

PEMODELAN MASALAH PENUGASAN (ASSIGNMENT PROBLEM) DENGAN KOEFISIEN ONGKOS KABUR

Recommend Documents