Layanan Tesis dan Disertasi S3 Kedokteran, hubungi Meruya Statistik 0812 1944 9060: 2014

PENJADWALAN FLOWSHOP

DENGAN METODE HEURISTIK MULTIPLE OBJECTIVE TERBOBOTI

Dyah Herawatie, Eto Wuryanto

Departemen Matematika, Fak. Sains dan Teknologi Universitas Airlangga

Email : dyah_hera@fst.unair.ac.id, eto-w@fst.unair.ac.id

Abstrak

Penelitian ini merupakan pengembangan dari penelitian yang telah dilakukan Rajendran (1995), yang telah mengembangkan algoritma CDS (Cambell, Dudek, Smith) untuk penjadwalan flowshop dengan menggunakan multiple objective. Penelitian ini memodifikasi fungsi tujuannya dengan memberi bobot, berdasarkan derajat kepentingannya. Disamping itu juga akan dikembangkan algoritma baru, yang merupakan pengembangan dari algoritma RA (Rapid Acess). Menurut Sahu (2009), algoritma RA yang merupakan modifikasi dengan menggabungkan keuntungan dari Palmer’s slope index dan CDS lebih efisien jika dibandingkan dengan algoritma lain.

Dari penelitian ini, dapat diambil kesimpulan antara lain : dari beberapa data yang digunakan, algoritma RA tidak selalu menghasilkan jadwal yang lebih baik dari algoritma CDS. Selain itu dengan bobot yang ditambahkan pada fungsi relativitas, akan bisa menghasilkan jadwal yang lebih baik lagi. Dalam penelitian ini ditunjukkan dengan semakin kecilnya nilai makespan, total flow time, dan total idle time. Hal ini terjadi pada data 3 (10X5), data 4 (10X10), dan data 5 (10X8). Jika data yang digunakan berukuran kecil (jumlah job X banyaknya mesin), maka penambahan bobot kurang mempengaruhi solusi yang diperoleh. Hal ini ditunjukan pada data 1 (5X3) dan data 2 (5X5).

Kata kunci : Penjadwalan flowshop, algoritma CDS, algoritma RA, multiple objectives.

Abstract

Rajendran (1995) has developed an algorithm CDS (Cambell, Dudek, Smith) for flowshop scheduling using multiple objective. This research was added on the Rajendran’s function of the goal with weighting based on the degree of importance. Besides, it was also made a new algorithm with weighted multiple objective that is the development of algorithm RA (Rapid Acess). RA algorithm is a modified version by combining the advantages of Palmer's slope index and CDS. This algorithm is more efficient than other algorithms (Sahu, 2009).

The results of this research are: The RA algorithm does not always produce a better scheduling than CDS algorithm. The weighted function of relativity will be able to obtain a best scheduling. This is shown by the data 3 (10 jobs X 5 machines), data 4 (10 X 10), and data 5 (10 X 8). In case of small data (data 1 (5 X 3) and data 2 (5 X 5)), the additional weight not affect to the gained solution.

Key word : Flowshop scheduling, CDS algorithm, RA algorithm, multiple objectives.

PENDAHULUAN

Latar Belakang

Penjadwalan merupakan salah satu bagian penting dalam bidang industri, terutama di bagian manufaktur dan produksi. Permasalahan penjadwalan di bidang produksi meliputi pengaturan job-job yang akan diproses pada serangkaian mesin dengan

urutan job yang sama berlaku untuk setiap mesin dan setiap mesin hanya memproses sebuah job pada saat yang sama. Masalah ini dikenal dengan istilah flowshop. Permasalahan utama pada flowshop adalah menentukan urutan job yang akan dipertahankan di sepanjang sistem yang memenuhi fungsi tujuan.

Permasalahan penjadwalan flow shop diperkenalkan oleh S.M Johnson pada tahun

1954 dengan permasalahan yang dikemukakan berupa permasalahan penjadwalan flow shop 2-mesin dengan fungsi tujuan meminimumkan makespan. Beberapa algoritma yang bisa digunakan untuk menyelesaikan permasalahan penjadwalan flow shop m-mesin, antara lain algoritma Palmer, Gupta, CDS (Cambell, Dudek, Smith), dan algoritma heuristik RA (Rapid Acess). Algoritma ini mempunyai fungsi tujuan meminimumkan makespan.

Selain makespan, fungsi tujuan yang sering digunakan sebagai ukuran efektifitas untuk permasalahan penjadwalan permutation flowshop antara lain total flow time, idle time mesin, dan tardiness (keterlambatan dalam proses produksi).

Rajendran (1995) mengemukakan sebuah algoritma heuristik untuk permasalahan penjadwalan permutation flowshop m-mesin dengan multiple objectives atau fungsi tujuan lebih dari satu. Dalam algoritma ini, jadwal awal diperoleh dari algoritma CDS. Setelah jadwal awal melalui beberapa iterasi terbentuklah sebuah jadwal baru. Dari tiap jadwal yang didapat kemudian dibandingkan efektivitas kedua jadwal dengan cara membandingkan nilai relativitas multiple objectives jadwal awal dengan nilai relativitas multiple objectives jadwal baru. Jadwal dengan nilai relativitas paling minimum akan diiterasi lagi hingga didapatkan nilai multiple objectives paling minimum. Jadwal dengan nilai multiple objectives paling minimum menjadi solusi dari penjadwalan permutation flow shop m-mesin.

Sahu (2009) dalam tesisnya melakukan survey terhadap metode-metode dalam penjadwalan flowshop dengan membanding-kan keefektifan algoritma Palmer, Gupta, CDS (Cambell, Dudek, Smith), dan algoritma heuristik RA. Ukuran efektivitas yang digunakan dalam survey tersebut adalah makespan. Dari hasil survey ini diperoleh kesimpulan bahwa algoritma RA memberikan hasil yang paling efisien.

Berdasarkan latar belakang permasalahan tersebut, maka perlu dilakukan penelitian yang lebih mendalam tentang penjadwalan flowshop dengan multiple objective. Dalam penelitian ini akan dikembangkan algoritma yang telah dikemukakan oleh Rajendran (1995), yaitu dengan menambahkan bobot dalam fungsi obyektifnya. Tujuan digunakannya bobot dalam fungsi obyektifnya adalah untuk memberikan kepentingan relatif di antara

fungsi–fungsi tujuan yang digunakan. Selain itu akan dikembangkan algoritma baru dengan jadwal awal menggunakan algoritma RA, dan menggunakan multiple objective terboboti. Dan selanjutnya akan dilakukan perbandingan terhadap kedua algoritma tersebut.

Tujuan

Penelitian ini bertujuan :

1. Mengembangkan algoritma CDS yang telah dilakukan Rajendran (1995) dengan menggunakan multiple objective terboboti.

2. Menyusun algoritma penjadwalan

flowshop baru dengan jadwal awal menggunakan algoritma RA menggunakan multiple objective terboboti.

3. Mengimplementasikan algoritma tersebut ke dalam program JAVA.

4. Membandingkan keefektifan kedua algoritma tersebut dengan menggunakan data sekunder.

STUDI PUSTAKA

Penjadwalan Flowshop

Seperti dijelaskan oleh Sahu (2009), penjadwalan flowshop sejenis dengan masalah kombinatorial. Penjadwalan flowshop merupakan sebuah permasalahan perencanaan produksi dengan n-job (item, tugas, dan lain-lain) yang harus diproses dalam urutan yang sama pada setiap m-mesin.. Masing-masing job mempunyai processing time yang berbeda untuk mesin yang berbeda. Beberapa karakteristik dari penjadwalan flowshop, antara lain :

1. Terdapat m mesin dan n job

2. Masing-masing job terdiri dari m operasi dan masing-masing operasi membutuhkan mesin yang berbeda

3. Ke-n job diproses dalam urutan yang sama pada m mesin

4. waktu pemrosesan dari job ke-i pada mesin ke-j dinotasikan dengan tij (i = 1,

2, ...n, dan j = 1, 2, ... m)

5. Disusun sebuah jadwal berupa urutan job, yang akan memenuhi tujuan tertentu. Tujuan yang sering digunakan adalah meminimumkan makespan.

Dalam penjadwalan flowshop digunakan asumsi antara lain :

1. Setiap job diproses pada semua mesin berdasarkan urutan tertentu

2. Setiap mesin hanya memproses satu job pada suatu waktu

3. Setiap job diproses pada satu mesin pada suatu waktu

4. Operasi tidak pre-emptif

5. Waktu set-up untuk sebuah operasi adalah sequence-independent dan tidak termasuk dalam waktu pemrosesan.

Untuk menyelesaian permasalahan penjadwalan flowshop, dikenal beberapa metode penjadwalan, antara lain (Sahu (2009))

1. Masalah flowshop 2 mesin :

a. Algoritma Johnson

b. Algoritma Kusiak

2. Metode heuristik untuk masalah penjadwalan n-job m-mesin :

a. Algoritma heuristik Palmer

b. Algoritma heuristik Gupta

c. Algoritma heuristik CDS

d. Algoritma heuristik RA

Ukuran efektivitas

Dalam penjadwalan digunakan beberapa ukuran efektifitas. Ukuran ini digunakan untuk mengukur efektivitas dari sebuah jadwal. Dalam Sahu (2009), disebutkan beberapa ukuran efektivitas yang digunakan dalam penjadwalan flowshop antara lain :

a. Rata-rata waktu penyelesaian pekerjaan

b. Rata-rata lamanya waktu pekerjaan

c. Lateness

d. Rata-rata lamanya waktu suatu job akan terlambat (due-date)

e. Makespan (waktu yang dibutuhkan oleh job terakhir untuk keluar dari sistem)

f. Total flow time merupakan jumlahan dari flow time (waktu yang dibutuhkan oleh job j untuk keluar dari sistem)

Sedangkan dalam Heizer & Render (2008), beberapa kriteria yang digunakan untuk mengevaluasi kinerja penjadwalan antara lain :

a. Meminimalkan waktu penyelesaian. Kriteria ini dievaluasi dengan mnentukan waktu penyelesaian rata-rata untuk setiap pekerjaan.

b. Memaksimalkan utlisasi. Kriteria ini dievaluasi dngan menghitung persentase waktu suatu fasilitas digunakan.

c. Meminimalkan persediaan barang

setengah jadi (work in process-WIP). Kriteria ini dievaluasi dengan menentukan jumlah pekerjaan rata-rata dalam sistem. Hubungan antara benyaknya pekerjaan dalam sistem da persediaan WIP akan tinggi. Oleh karen itu, jika terdapat lebih sedikit pekerjaan dalam sistem, maka persediaan yang ada lebih rendah.

d. Meminimalkan waktu tunggu pelanggan. Kriteria ini dievaluasi dengan menentukan keterlambatan pekerjaan rata-rata.

Algoritma CDS (Campbell, Dudek, Smith)

Algoritma CDS merupakan salah satu algoritma umum yang digunakan untuk menjadwalkan urutan job pada permasalahan flowshop dengan lebih dari 2 mesin guna mendapatkan sebuah waktu penyelesaian atau makespan yang mendekati minimum. Algoritma ini merupakan pengembangan dari algoritma Johnson. Langkah-langkah dalam algoritma CDS (Cambell, et al 1970 dan Hong et al., 2001) :

1. Set variabel i = 0.

2. Set variable i = i + 1 ,

a. Untuk j = 1 sampai m-1 hitung

ti′1 = ti′1 +t′

b. Untuk j = m sampai 2 hitung

ti′2 = ti′2 + t′ij

3. Hitung U = {j t1 j < t2j } dan V = { j t1j ≥ t2j }

4. Urutkan job dalam U dengan urutan non-decreasing dari ti′1

5. Urutkan job dalam V dengan urutan non-increasing dari ti′2

6. Sequence yang optimal diperoleh sebagai jadwal S didapat dengan menggabungkan job yang telah diurutkan dalam himpunan U diikuti dengan urutan job yang telah diurutkan dalam himpunan V dengan makespan yang minimum.

7. Kembali ke langkah 2 hingga i = n.

Algoritma RA (Rapid Acess)

Algoritma RA dikembangkan oleh Dannenbring yang berusaha menggabungkan keuntungan dari Slope index Palmer dan prosedur CDS. Dalam Sahu (2009), dijelaskan langkah-langkah dari algoritma heuristik RA :

1. Set variabel i = 0.

2. Set variable i = i + 1 ,

Untuk j = 1 sampai m-1 hitung wj1 =m−(j−1), wj 2 = j

ti1 ′= f m j1 wj 1 tij dan ti 2

′ = m j 1 wj2tij

= =

Dengan pembobotnya didefinisikan sebagai berikut :

W = wj j =

1 { 1 1,2, ... } { , 1, ...2,1}

m = m m −

W {wj j

= =1,2, ... m } { m m}

= 1,2, ... , 1,

−

2 2

3. Hitung U = { j t1′j < t′2j } dan

V = {j t′1j ≥t′2j }

4. Urutkan job dalam U dengan urutan non-decreasing dari ti′1

5. Urutkan job dalam V dengan urutan non-increasing dari ti′2

6. Sequance yang optimal diperoleh sebagai

jadwal S didapatkan dengan

menggabungkan job yang telah diurutkan dalam himpunan U diikuti dengan urutan job yang telah diurutkan dalam himpunan

V dengan makespan yang minimum.

7. Kembali ke langkah 2 hingga i = n.

Pengembangan Algoritma Heuristic CDS dengan Multiple Objective

Pengembangan algoritma heuristic CDS dengan multiple objective dikemukakan oleh Chandrasekharan Rajendran. Dalam algortima ini, digunakan tiga fungsi tujuan, yaitu meminimumkan makespan, total flow time, dan total idle-time mesin.

Makespan dari jadwal parsial óá dirumuskan

dengan M = q(σα, m)

Total flow time dari job-job dalam óá dirumuskan dengan Fóá = Fó + q(óá, m)

Sedangkan total idle time dari mesin-mesin, hasil dari jadwal parsial óá dirumuskan dengan

I = Ió +E[max(q(óá, j −1)− q(ó, j)}0]

j=2

dengan : ó

q(σ, j) : Himpunan (set) jadwal dari total

n job

: completion time dari jadwal

partial ó pada mesin ke-j

Secara garis besar, langkah-langkah dari algoritma ini adalah sebagai berikut (Rajendran, 1995):

1. Dapatkan jadwal awal dengan

menggunakan algoritma CDS. Dapatkan jadwal utama S dari iterasi job yang dilakukan dengan cara penukaran job berpasangan dari jadwal awal dengan tujuan utama mendapatkan makespan minimum.

2. Hitung D[r ] dan D′r[] dari jadwal utama S, dengan rumus:

m m

D r

[ ] = i 1 t i r

= [ ] − (1)

i i r

= [ + ]

1 t 1

D [ ′ ] = = { −+1}t[r] −m1{m−i+1}t[r+1]

(2)

D[r ] merupakan hasil pengurangan flow

time job di posisi ke-r dengan flow time job di posisi ke r+1.

3. Bentuk ranked list untuk D[r] ≥ 0.

4. Jika ranked list null maka STOP. Jika ranked list tidak null, tukar posisikan job di jadwal S berdasarkan job yang berada di ranked list, maka akan didapatkan jadwal baru S′.

5. Urutkan job yang berada dalam ranked list

dengan urutan D[r ] yang menurun. Jika ada dua atau lebih job dengan nilai D[r ]

yang sama di ranked list, maka job diurutkan berdasarkan nilai D′[r] yang

menurun.

6. Misalkan, dari jadwal S, job pertama di ranked list adalah job [q], posisi job ke-q ditukarkan dengan posisi job ke-q+1, dan sebaliknya. Terbentuk jadwal baru, yang dinotasikan dengan S’.

7. Bandingkan relativitas kenaikan pada nilai multiple objectives jadwal S′ terhadap jadwal S.

M' min( ', )

− M M F' min( ', )

− F F

Rs = +

' min(M', M) min(F',F)

+ I'−min(I',I) (3)

min( ', )

I I

M − min( ', )

M M F − min( ', )

F F

Rs = + min(M', M) min(F',F)

+ I − min(I', I) (4)

min( ', )

I I

8. Jika Rs ' < Rs , maka set S = S′, F = F’, M = M’, I = I’, dan ulangi langkah 2. Jika tidak, lanjutkan ke langkah 9.

9. Job [q] dihapus dari ranked list. Setelah penghapusan, jika ranked list tidak null maka ulangi langkah 6. Jika ranked list null maka lanjutkan ke langkah 10.

10. Jadwal S merupakan solusi dari permasalahan. STOP.

METODE PENELITIAN

Langkah-langkah yang dilakukan untuk mendapatkan penyelesaian dari masalah penjadwalan flowshop dengan multiple objective terboboti adalah sebagai berikut :

1. Melakukan penelusuran, penelahaan literatur, serta diskusi yang intensif, yang membahas tentang penjadwalan flowshop yang berhubungan antara lain dengan algoritma heuristik CDS, pengembangan algoritma CDS dengan multiple objectives, serta algoritma heuristik RA.

2. Menyusun pengembangan algoritma Rajendran dengan multiple objectives terboboti.

3. Menyusun pengembangan algoritma RA dengan multiple objectives terboboti.

4. Mengimplementasikan kedua

algoritma tersebut (algoritma CDS dengan multiple objectives terboboti dan algoritma RA dengan multiple objectives terboboti) ke dalam program bahasa JAVA.

5. Membandingkan keefektifan algoritma dengan menggunakan data sekunder.

HASIL DAN PEMBAHASAN

Pengembangan Algoritma Rajendran dengan Mutiple Objective Terboboti

Pengembangan algoritma heuristik CDS dengan multiple objective dikemukakan oleh Chandrasekharan Rajendran (Rajendran, 995). Pada dasarnya, relativitas yang harus dihitung pada langkah 7 pada algoritma ini, bisa ditulis dengan :

G − min( ', )

G G G − min( ' , )

G G

1 1 1 2 2 2

Rs = + min(G1', G1) min(G2', G2)

G3− min(G3 ', G3 )

Dengan Gi adalah tujuan yang dikehendaki. Dalam algoritma Rajendran, digunakan tiga tujuan, yaitu meminimumkan makespan, total flow time, dan total idle-time mesin.

Secara umum, jika digunakan n tujuan dan ditambahkan bobot dalam fungsi obyektifnya, rumus relativitasnya menjadi :

G G G G − min( ', )

G G

1 − min( ', )

1 1 2 2 2

R w

= + w

s 1 2

min( ', )

G G min( ', )

G G

1 1 2 2

G − min(Gn ', Gn )

+ +

... w (6)

nmin(Gn', Gn )

Modifikasi ini menghasilkan perubahan mulai pada langkah ke-7 dari algoritma Rajendran sebagai berikut :

7. Bandingkan relativitas kenaikan pada nilai multiple objectives jadwal S′ terhadap jadwal S.

G1'− min(G1 ', G1) G2'−min(G2', G2)

+ w 2

min( ', )

G G min( ', )

G G

1 1 2 2

G ' min( ', ) − G G

n min( ' , )

G G

n n

G − min( ', )

G G G min( ', )

1 G G

1 1 2 − 2 2

R w

= + w

s 1 2

min( ', )

G G min( ', )

G G

1 1 2 2

G − min( ' , )

G G

n n n

+ +

... w (8)

n min( ' , )

G G

n n

Dengan 0 ≤ wi ≤ 1, dan w1+w2+...+wn =1

8. Jika Rs ' < Rs , maka set S = S′, G1 = G1', G2 = G2' , ... Gn = Gn' , dan

ulangi langkah 2. Jika tidak, lanjutkan ke langkah 9.

9. Job [q] dihapus dari ranked list. Setelah penghapusan, jika ranked list tidak null maka ulangi langkah 6. Jika ranked list null maka lanjutkan ke langkah 10.

10. Jadwal S merupakan solusi dari permasalahan. STOP.

Pengembangan Algoritma RA dengan Mutiple Objective Terboboti

Dalam penelitian ini dikembangkan algoritma baru, dengan melakukan modifikasi algoritma yang dikembangkan oleh Rajendran (1995). Jika pada algoritma Rajendran, jadwal awal diperoleh dari algoritma CDS. Maka dalam penelitian ini digunakan algoritma RA.

Modifikasi algoritma ini dapat dituliskan sebagai berikut :

1. Dapatkan jadwal awal dengan menggunakan algoritma RA. Dapatkan jadwal utama S dari iterasi job yang dilakukan dengan cara penukaran job berpasangan dari jadwal awal dengan tujuan utama mendapatkan makespan minimum.

2. Hitung D[r ] dan D′r[] dari jadwal

utama S, dengan rumus:

mti[r] −~m i 1 ti[r+1] (9)

m m

D = { } [ ] = { } [ + ]

[ ]

′ = m i t

− + − m i t

− + 1

r i 1 i r i 1 i r 1

(10)

D[r ] merupakan hasil pengurangan

flow time job di posisi ke-r dengan

flow time job di posisi ke r+1.

3. Bentuk ranked list untuk D[r] ≥ 0.

4. Jika ranked list null maka STOP. Jika ranked list tidak null, tukar posisikan job di jadwal S berdasarkan job yang berada di ranked list, maka didapat jadwal baru S′ .

5. Urutkan job yang berada dalam ranked list dengan urutan D[r ] yang menurun.

Jika ada dua atau lebih job dengan nilai D[r ] yang sama di ranked list, maka

job diurutkan berdasarkan nilai D′r[]

yang menurun.

6. Misalkan, dari jadwal S, job pertama di ranked list adalah job [q], posisi job ke-q ditukarkan dengan posisi job ke¬q+1, dan sebaliknya. Terbentuk jadwal baru, yang dinotasikan dengan S’.

7. Bandingkan relativitas kenaikan pada nilai multiple objectives jadwal S′ terhadap jadwal S.

G ' min( ' , )

G G G ' min( ' , )

− G G

1 − 1 1 2 2 2

R w

= + w

s ' 1 min(G1' , G1) 2 min(G2' , G2)

G ' min( ' , )

− G G

n n n

+ +

... w (11)

n min(Gn' , Gn )

G − min( ' , )

G G G − min( ' , )

G G

1 1 1 2 2 2

R w

= + w

s 1 min(G1 ' , G1) 2 min(G2 ' , G2)

+...+w Gn −min(Gn',Gn) (12)

n min(Gn',Gn)

Dengan 0≤ wi ≤ 1, dan

w1+w2+...+wn =1

8. Jika Rs ' < Rs, maka set S = S′, G1 = G1', G2 = G2' , ... Gn = Gn' , dan

ulangi langkah 2. Jika tidak, lanjutkan ke langkah 9.

9. Job [q] dihapus dari ranked list. Setelah penghapusan, jika ranked list tidak null maka ulangi langkah 6. Jika ranked list null maka lanjutkan ke langkah 10.

10. Jadwal S merupakan solusi dari permasalahan. STOP.

Perbandingan Hasil Penjadwalan dan Analisis

Untuk tujuan perbandingan, dalam penelitian ini digunakan 6 data, yang diambil dari beberapa sumber, antara lain :

a. Data 5 job 3 mesin dari Rajendran (1995)

b. Data 5 job 5 mesin dari Ravindran (2005)

c. Data 10 job 5 mesin dari Kattan (2003)

d. Data 10 job 10 mesin dari Sahu (2009)

e. Data 10 job 8 mesin dari Sahu (2009).

Dengan keenam data ini, akan dibuat jadwal dengan menggunakan enam algoritma, antara lain :

1. CDS

2. RA

3. Pengembangan CDS dengan Mutiple

Objective (Rajendran atau CDS MO)

4. Pengembangan RA dengan Mutiple Objective (RA MO)

5. Pengembangan CDS dengan Mutiple Objective Terboboti (CDS MOT)

6. Pengembangan RA dengan Mutiple Objective Terboboti (RA MOT)

Bobot yang digunakan pada algoritma CDS dengan Mutiple Objective Terboboti, dan RA dengan Mutiple Objective Terboboti

mempunyai syarat 0<_ wi <_ 1, dan

w1 + w2+... + wn =1. Dalam penelitian ini,

bobot yang digunakan wi = 0, 0.1, 0.2, 0.3, 0,4, 0,5 ... , 1. Sebagai ukuran efektivitas, dalam penelitian ini akan digunakan makespan, total flow time, dan total idle time.

Data 5 job 3 mesin dari Rajendran, 1995 Dengan menggunakan data pada tabel 1, dan menggunakan keenam algoritma diperoleh hasil penjadwalan seperti pada tabel 2, dengan

M = makespan, F = total flow time, dan I = total idle time. Algoritma CDS dan RA bertujuan sama, yaitu mendapatkan jadwal dengan makespan minimum. Pada data 2, dengan menggunakan algoritma CDS dan RA, diperoleh makespan 51. Meskipun kedua algoritma menghasilkan makespan yang sama, tetapi RA menghasilkan jadwal dengan total flow time dan total idle-time mesin yang lebih kecil.

Tabel 1. Data (5X3) dari Rajendran (1995)

M1 M2 M3

J1 5 10 9

J2 2 3 7

J3 7 9 3

J4 3 2 18

J5 4 3 9

Tabel 2. Hasil Penjadwalan Data (5X3)

Algoritma Jadwal M F I

CDS 2-4-5-1-3 51 180 56

RA 2-5-4-1-3 51 171 46

CDS MO 2-5-3-4-1 52 153 22

RA MO 2-5-3-4-1 52 153 22

CDS MOT 2-5-4-3-1 51 165 38

2-5-3-4-1 52 153 22

RA MOT 2-5-4-3-1 51 165 38

2-5-3-4-1 52 153 22

Jika menggunakan algoritma CDS dengan Mutiple Objective dan RA dengan Mutiple Objective diperoleh jadwal yang sama, sehingga menghasilkan makespan, total flow time dan total idle-time yang sama, yaitu 52, 153, dan 22.. Jika menggunakan algoritma CDS dengan Mutiple Objective Terboboti dan RA dengan Mutiple Objective Terboboti juga diperoleh jadwal yang sama. Ada dua alternatif jadwal yang diberikan. Satu jadwal sama dengan jadwal yang dihasilkan oleh algoritma CDS dengan Mutiple Objective dan RA dengan Mutiple Objective, dan jadwal yang lain mempunyai nilai makespan yang lebh kecil (51). Jika dibandingkan dengan total flow time dan total idle-time yang nilainya lebih besar (yaitu 165 dan 38), penurunan nilai makespan ini menjadi tidak signifikan. Sehingga jadwal terbaik untuk kedua algoritma ini sama dengan apabila tidak dilakukan pembobotan.

Data 5 job 5 mesin dari Ravindran (2005)

Dari data Ravindran (2005) seperti pada tabel 3, dan dengan menggunakan keenam algoritma diperoleh hasil penjadwalan seperti pada tabel 4.

Tabel 3. Data (5X5) dari Ravindran (2005)

M1 M2 M3 M4 M5

J1 10 11 20 22 5

J2 3 21 19 13 12

J3 45 30 9 15 17

J4 1 40 32 24 28

J5 35 4 26 16 25

Algoritma CDS dan RA menghaslkan makespan yang sama dengan jadwal dengan urutan yang berbeda. Jika dibandingkan jadwal yang dihasilkan keduanya, RA menghasilkan jadwal yang relatif lebih baik daripada CDS. Meskipun total flowtime-nya lebih besar (790) tetapi jadwal ini menghasilkan total idle time yang jauh lebih kecil (88). Dengan menggunakan keenam algoritma, jadwal terbaik dihasilkan dari algoritma CDS dengan Mutiple Objective dan dengan Mutiple Objective Terboboti.

Tabel 4. Hasil penjadwalan Data (5X5)

Algoritma Jadwal M F I

CDS 4-2-5-3-1 184 787 176

RA 4-3-5-1-2 184 790 88

tujuan mempunyai nilai yang lebih kecil. Jika digunakan bobot, menghasilkan yang lebih baik lagi, yaitu (93, 732, 126). Bobot yang digunakan w1, w2, w3 berturut-turut (0, 0, 1)

Kesimpulan yang sama juga diperoleh jika algoritma RA dibandingkan dengan algoritma RA dengan Mutiple Objective. Pada algoritma RA dengan multiple objective terboboti, diperoleh nilai idle yang terkecil, yaitu senilai 119 unit. Tetapi dua tujuan yang lain yaitu makespan dan total flow time lebih besar dibandingkan dengan hasil algoritma CDS dengan Mutiple Objective terboboti.

Tabel 8. Hasil Penjadwalan Data (10X10)

Algoritma Jadwal M F I

CDS 3-1-10-5-9-

6-8-2-7-4 95 765 154

RA 3-10-1-5-9-

8-6-2-7-4 97 766 154

CDS MO 3-1-5-10-9-

6-8-4-2-6 93 755 137

RA MO 3-1-10-5-8-

9-4-2-6-7 96 749 130

3-1-6-5-10- 93 732 126

9-2-4-7-8

3-1-5-10-9- 93 748 139

2-6-8-4-7

3-1-5-10-9- 93 751 127

CDS MOT 4-6-8-2-7

3-1-5-10-9- 93 755 137

6-8-4-2-7

3-1-5-10-4- 95 745 125

9-2-6-8-7

3-1-5-10-4- 96 750 126

9-6-8-2-7

3-1-10-5-8- 95 756 140

9-6-4-2-7

3-1-10-5-8- 95 755 144

9-6-2-4-7

3-1-10-5-8- 95 752 132

9-4-6-2-7

RA MOT 3-1-10-5-8-

9-4-2-6-7 96 749 130

3-1-10-5-8- 96 748 141

6-9-2-4-7

3-1-10-5-8- 96 749 137

6-9-4-2-7

3-1-4-10-5- 98 741 119

8-6-9-2-7

Data 10 job 8 mesin dari Sahu (2009)

Jika keenam algoritma diterapkan pada data 10 job 8 mesin dari Sahu (2009) (tabel 9), diperoleh hasil seperti pada tabel 10.

Tabel 9. Data (10X8) dari Sahu (2009)

M1 M2 M3 M4 M5 M6 M7 M8

J1 6 5 1 7 9 3 4 2

J2 3 9 5 7 2 5 6 1

J3 8 1 6 4 3 9 5 9

J4 4 6 3 1 5 6 7 7

J5 9 8 2 9 2 5 9 6

J6 3 2 4 3 7 2 3 5

J7 5 9 4 2 4 8 6 6

J8 2 8 9 1 6 3 4 8

J9 1 4 6 2 5 4 3 9

J10 6 3 5 5 2 7 1 9

Tabel 10. Hasil Penjadwalan Data (10X8)

Algoritma Jadwal M F I

CDS 6-9-4-3-8-7-

5-10-1-2 90 658 77

RA 6-9-4-10-8-

3-7-5-2-1 92 665 93

CDS MO 6-9-4-3-8-7-

1-5-2-10 93 645 70

RA MO 6-9-10-4-8-

7-3-5-1-2 91 650 76

CDS

MOT 6-9-10-4-3-

8-7-1-5-2 89 648 68

6-9-4-3-8-7-

1-10-5-2 90 650 75

6-9-4-3-8-7-

5-10-1-2 90 658 77

6-9-4-3-8-7-

1-5-10-2 91 650 72

6-9-4-3-8-7-

1-5-2-10 93 645 70

RA MOT 6-9-4-10-8-

7-1-3-5-2 90 650 83

6-9-10-4-8-

7-3-1-5-2 91 649 78

6-9-10-4-8-

7-3-5-1-2 91 650 76

6-9-10-4-8-

7-1-3-5-2 92 648 79

6-9-10-4-8-

7-3-1-2-5 96 646 81

Dibandingkan dengan RA, algoritma CDS menghasilkan jadwal yang lebih baik. Jika jadwal RA menghasilkan makespan, total flow time dan total idle time berturut-turut (92, 665, 93), maka CDS menghasilkan makespan, total

flow time dan total idle time (90, 658, 77). Dengan menggunakan CDS multiple objective, terjadi peningkatan nilai makespan, tetapi total flow time dan total idle timenya menurun, yaitu (93, 645, 70). Jika digunakan CDS multiple objective terboboti, dengan bobot w1, w2, w3 berturut-turut (1, 0, 0), diperoleh jadwal yang lebih baik lagi, yaitu (89, 648, 68).

KESIMPULAN

Dari memodifikasi algpritma yang telah dikembangkan oleh Rajendran (1995), dengan memberi bobot pada fungsi relativitasnya, dan mengubah jadwal awal dengan menggunakan algoritma RA, serta melakukan perbandingan dengan menggunakan data sekunder dapat diambil kesimpulan antara lain :

1. Dari beberapa data yang digunakan, algoritma RA yang merupakan modifikasi dari dengan menggabungkan keuntungan dari Palmer’s slope index dan CDS, tidak selalu menghasilkan jadwal yang lebih baik algoritma CDS.

2. Dengan Bobot yang ditambahkan pada fungsi relativitas, akan bisa menghasilkan jadwal yang lebih baik lagi. Dalam penelitian ini ditunjukkan dengan semakin kecilnya nilai makespan, total flow time, dan total idle time. Hal ini terjadi pada data 3 (10X5), data 4 (10X10), dan data 5

(10X8). Jika data yang digunakan

berukuran kecil (jumlah job X banyaknya mesin), maka penambahan bobot kurang mempengaruhi solusi yang diperoleh. Hal ini ditunjukan pada data 1 (5X3) dan data 2 (5X5).

DAFTAR PUSTAKA

[1] Rajendran, Chandrasekharan. Heuristic for Scheduling in Flowshop with Multiple Objectives, European Journal of Operational Research, Vol.82, p 540-555, 1995.

[2] Sahu, Atul Kumar, Efficient Heuristics for Scheduling Tasks on A Flow Shop Environment to Optimize Makespan, Thesis, Departemen of Mechanical Engineering, National Institute of Technology, Rourkela, 2009.

[3] Heizer, Jay & Barry Render. Operations Management.. Upper Saddle River, New Jersey. Pearson Education, Inc, 2008.

[4] Champbell, H.G., Dudek, R.A, and Smith, M.L. A Heuristic Algorithm for the n-job,

m-machine sequencing problem,

Managemen Science 16, p. B630-B637, 1970.

[5] Hong, T. P., T. T., Wang, S. L., Wang. A Fuzzy CDS-based Scheduling Algorithm for More Than Two Machine Centers, Journal of Advanced Computational Intelligence, Vol.5, No.4., 2001.

[6] Ravindran, D., Haq, A. Noorul, Selvakuar, S.J., Sivaraman, R.. Flow Shop Scheduling With Multiple Objective of Minimizing Makespan and Total Flow Time, Int J Adv Manuf Technol, Vol. 25, p 1007-1012, 2005.

[7] Kattan, Ibrahim, Mikolajczak, Boleslaw, Kattan, Khalid, Alqassar, Bassam. Minimizing Cycle Time and Group Scheduling, Using Petri Nets A Study of Heuristic Methods, Journal of Intelligent Manufacturing, Vol. 14, p 107-121, 2003.

Sabtu, 19 Juli 2014