PENJADWALAN DUA MESIN FLOW SHOP UNTUK MEMINIMASI TOTAL TARDINESS DENGAN MEMPERHATIKAN KETIDAKTERSEDIAAN PADA KEDUA MESIN Rr.Orifia Pitrasari, Stefanus Eko Wiratno, Patdono Suwignjo Jurusan Teknik Industri Institut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email:
[email protected] ;
[email protected];
[email protected]
ABSTRAK Penelitian ini membahas permasalahan penjadwalan dua mesin flow shop yang mengakomodasi ketidaktersediaan pada kedua mesin dengan kondisi non-resumable. Sebuah model matematis dan algoritma heuristik dirancang untuk mendapatkan urutan job yang dapat meminimasi total tardiness. Model matematis diselesaikan dengan bantuan Lingo, sedangkan algoritma heuristik dirancang dengan menggunakan 3 prioritas pengurutan yaitu earliness due date, slack dan earliness D/P. Hasil penelitian mengkonfirmasikan bahwa model matematis dapat menghasilkan solusi yang lebih baik dibanding algoritma heuristik, namun membutuhkan waktu yang sangat lama untuk menyelesaikan permasalahan dengan jumlah job yang banyak. Sedangkan untuk algoritma heuristik dengan prioritas pengurutan earliness due date dapat menghasilkan solusi yang lebih baik dibandingkan dengan slack dan earliness D/P. Selain itu, model matematis dan heuristik yang telah dirancang tidak selalu dapat menghasilkan solusi yang optimal. Kata Kunci : Flow Shop, ketidaktersediaan, model matematis, dan Heuristik
ABSTRACT This research discussed about two machines flow shop scheduling problem that accommodate non-availability of two machines in non-resumable condition. A mathematic model and heuristic algorithm is established to get job sequence to minimize total tardiness. Mathematic model is solved by using lingo software, whereas the heuristic algorithm that established to solve mathematic model is using three dispatching priority there are earliness due date, slack, and earliness D/P. The result is confirm that mathematic model can get better solution than heuristic algorithm, however need much time to solve a big problem. Whereas for heuristic algorithm that using earliness due date priority can get solution better than slack and earliness D/P. In addition, mathematic model and heuristic that have been established not always can get optimal solution. Key word: Flow Shop, Non-availability, Mathematic Model, Heuristic
1.
Pendahuluan Beberapa penelitian dilakukan untuk mengatasi masalah penjadwalan pada sistem flow shop antara lain adalah penelitian Pan et al. (2002) membuat model penjadwalan dua mesin dengan kriteria performansi minimasi total tardiness dan mengasumsikan mesin dalam keadaan tersedia. Selain itu, ada penelitian yang mengasumsikan bahwa mesin tidak selalu tersedia saat akan digunakan dalam penjadwalan deterministik. Penelitian tersebut antara lain penelitian yang dilakukan oleh Lee (1997) model tersebut mengasumsikan kondisi ketidaktersediaan mesin yang resumable serta non-resumable dan ketidaktersediaan hanya terjadi pada satu mesin dengan kriteria
minimasi makespan. Lee (1999) mengembangkan model penjadwalan untuk kondisi semi-resumable. Arlianto (2001) dalam Berhitu (2008) mengembangkan model penjadwalan Lee (1999) menjadi model penjadwalan flow shop m mesin n job dengan kendala ketidaktersediaan pada salah satu mesin. Kubiak et al. (2002) membuat model penjadwalan untuk kondisi resumable, dengan interval ketidaktersediaan pada beberapa mesin, dengan kriteria minimasi makespan. Setiawati (2003) dalam Berhitu (2008) mengembangkan model Arlianto (2001) dengan mempertimbangkan ketidaktersediaan mesin yang dapat terjadi pada lebih dari satu mesin dan terletak pada posisi manapun untuk kondisi
non resumable dengan kriteria minimasi mean Earliness. Berhitu (2008) membuat model penjadwalan m mesin dengan kondisi nonresumable, semi resumable dan resumble untuk tujuan minimasi makespan. Kusuma (2008) membuat model penjadwalan dua mesin dimana ketidaktersediaan terjadi terbatas hanya pada salah satu mesin untuk kondisi non-resumable dengan kriteria minimasi total tardiness. Pengembangan model dalam penelitian ini mengacu pada penelitian Kusuma (2008). Penelitian ini membuat suatu model penjadwalan dua mesin untuk meminimasi total keterlambatan (total tardiness) dengan memperhatikan ketidaktersediaan yang terjadi pada kedua mesin kondisi non-resumable. Dalam penelitian ini, proses pengerjaan job bersifat non-resumable yang berarti jika terdapat job yang proses pengerjaannya terpotong oleh ketidaktersediaan mesin, ketika mesin tersedia kembali, job tersebut harus diulang prosesnya dari awal. Menurut Morton and Pentico (1993) apabila memasukkan kendala due date dalam menjadwalkan suatu job, maka fungsi tujuan yang sesuai adalah minimasi total tardiness. Minimasi Total tardiness terjadi karena besarnya penalty yang diberikan oleh konsumen proportional terhadap jumlah job yang terlambat serta tidak ada reward apabila job selesai dikerjakan sebelum due date. Hasil penelitian diharapkan dapat menjadi alternatif bagi pemecahan masalah penjadwalan flow shop untuk meminimasi total tardiness yang mempertimbangkan ketidaktersediaan kedua mesin yang proses jobnya bersifat nonresumable. 2.
Studi Literatur
Penjadwalan Penjadwalan Menurut (Blazewicz et.al, 2007) terdiri dari 3 karakteristik, yaitu sejumlah T = {T1, T2,.., Tn} dimana n adalah tugas/job, sejumlah P = {P1,P2,..,Pm} dimana m merupakan mesin, dan sejumlah R = {R1,R2,.., Rs} dimana s merupakan sumberdaya lainnya. Atau dengan kata lain, penjadwalan berarti penugasan sejumlah job untuk diproses disejumlah mesin dengan sumberdaya yang ada serta dengan batasan yang ditentukan.
Faktor-Faktor yang menggambarkan karakteristik penjadwalan produksi adalah : 1. Jumlah pekerjaan (job) yang dijadwalkan, yaitu jumlah job yang akan diproses, waktu yang diperlukan untuk tiap proses, dan jenis mesin yang diperlukan. 2. Jumlah mesin dan atau operasi pada workshop. 3. Pola fasilitas manufaktur : flow shop, jobshop, openshop. 4. Production environment : deterministic (waktu proses dan hal lain yang berhubungan dengan penjadwalan sudah diketahui) dan Stochastic (tidak diketahui secara pasti secara pasti waktu yang ada). Klasifikasi penjadwalan Beberapa machine environment yang mungkin terbentuk adalah sebagai berikut : a. Mesin Tunggal (Single Machine) Hanya ada satu mesin untuk memproses sejumlah n job. b. Mesin Paralel (Parallel Machine) Terdapat m mesin identik yang disusun secara paralel. Sehingga job j dapat dilayani oleh mesin mana saja. c. Flow Shop Terdapat m mesin, dimana job memerlukan operasi di masing-masing mesin. Semua job memiliki routing yang sama. Biasanya semua antriannya diasumsikan beroperasi secara First in First Out. d. Job Shop Dalam penjadwalan job shop ini routing tiap mesin tetap, namun urutan proses tidak sama untuk setiap job. e. Open Shop Terdapat m mesin, dimana masing-masing job melewati mesin yang sama lebih dari satu kali. Job yang berbeda bisa memiliki routing berbeda. Penjadwalan flow shop Ada beberapa macam pola flow shop menurut Morton and Pentico(1993) : 1. Pure Flow shop Semua job memerlukan satu operasi pada setiap mesin dan karena tiap job memerlukan jumlah mesin dan urutan
2
yang sama. Gambar 2.2 menunjukkan pola pure flow shop. 1
2
m
Gambar 2.2 Pola Pure Flow shop
2. Skip Flow shop Gambar 2.3 menunjukkan pola skip flow shop atau pola melompat, dimana mesinmesin tertentu dapat dilompati oleh jobjob tertentu. 1
2
3
4
5
6
Gambar 2.3 Pola Skip Flow shop
3. Reentrant Flow shop Dalam reentrant flow shop, beberapa mesin dapat dilalui lebih dari sekali. 2.4 menunjukkan pola reentrant flow shop R
R 1
2
3
2
R 4
2
Gambar 2.4 Pola Reentrant Flow shop
4. Compound Flow shop Dalam compound flow shop, satu mesin dalam set mesin dapat digantikan oleh sekelompok mesin. Kelompok mesin tersebut umumnya adalah mesin-mesin parallel atau jalur batch yang diikuti oleh mesin-mesin parallel. Gambar 2.5 menunjukkan pola compound flow shop.
Gambar 2.5 Pola Compound Flow shop
Availability dalam Penjadwalan Menurut Strusevich et al. (2009) kondisi ketidaktersediaan mesin dapat dibedakan menjadi tiga macam, antara lain : Resumable Pada kondisi ini job yang belum selesai diproses tersebut bisa dilanjutkan kembali setelah mesin tersedia tanpa mengulang proses
tersebut dari awal. Contoh kondisi ini adalah pada proses welding (mengelas), Semi-Resumable Bagian proses yang telah dikerjakan sebelum terjadi ketidaktersediaan maka setelah mesin tersedia, ada bagian proses yang harus diulang. Contoh kondisi semi-resumable yaitu pada proses drilling (mengebor). Non-Resumable Kondisi dimana jika terdapat job yang proses pengerjaannya terpotong oleh ketidaktersediaan mesin, ketika mesin tersedia kembali, job tersebut harus diulang prosesnya dari awal. Contoh adalah pengecoran. Model Penjadwalan Kusuma Model yang digunakan dalam penjadwalan Kusuma(2008) adalah : Z = f(Tk) = Fungsi Tujuan Z adalah minimasi Total tardiness i = nomor job i = 1,2,..,n j = nomor mesin j = 1,2 k = urutan job k = 1,2,..,n pi,j = waktu proses job-i pada mesin-j aj = saat mulai interval ketidaktersediaan mesin pada mesin ke-j bj = saat selesai interval ketidaktersediaan mesin pada mesin ke-i di = due date job i = 1,2..,n Variabel Keputusan yang digunakan adalah : Zik = indeks job i dijadwalkan pada posisi ke-k. Zik = 1 jika job i dijadwalkan pada posisi ke-k, jika tidak, maka Zi,k = 0. Auxiliary Variable : Pkj = processing job urutan ke-k di mesin j dk = due date job urutan ke-k Sk,1 = starting time job urutan ke-k pada mesin pertama, k = 1,2,..,n Xk = idle time untuk job urutan urutan kek, yaitu waktu antara selesainya job urutan ke-k pada mesin pertama dengan mulainya job urutan ke-k pada mesin kedua, k =1,2,..,n hkj = indeks mesin ke-j tersedia saat job urutan ke-k, hkj = 1, bila mesin ke-j tidak tersedia saat job urutan ke-k; hkj = 0, jika mesin ke-j tersedia saat job urutan ke-k. Ckj = completion time untuk job urutan ke-k pada mesin ke-j. Bila Ketidaktersediaan Terjadi Pada Mesin Pertama
3
Berikut adalah model matematis bila terdapat ketidaktersediaan pada mesin pertama. Fungsi Tujuan : (1) MinZ Tk Subject To : n
Zi,k
1
i 1
Untuk k =1,2,..,n ; i = 1,2,..,n
(2)
n
p kj
( Z i ,k x
pij )
Untuk j = 1,2; k = 1,2,..,n
1, j
A j dan
A j atau Ckj ( k
Untuk k = 1,2,..,n
(17)
Pk
1,1
S k , 2 S k ,1
(4)
dk }
Untuk k = 1,2,..,n
1,1
Pk
(18)
Xk
1,1
hk , 2 x(b2
Untuk k = 1,2,..n
1, 2
(19)
Untuk Completion time:
C k , 2 Ck ,1
(6)
Pk , 2
hk , 2 x{b2
Pk , 2
Xk
Untuk k = 1 Untuk Starting time:
C k , 2 Ck ,1
S 1,1 h1,1 xb1 xPk
1,1
{hk ,1 x(b1
Ck
1,1
(8)
n
C kj S kj
( Z i ,k x
pij )
i 1
Untuk j = 1; k=1,2,..,n
(9)
P1, 2
C k , 2 Ck ,1
Xk}
hk , j
0 jika
C kj ( k , j
1)
Ck , j
Pkj ( k , j )
Pk , 2
Xk (11)
1
k 1
Untuk j=1; k=1,2,..,n
(12)
hk , j {0,1} Untuk j = 1,2; k = 1,2,..,n
(13)
Z j ,k {0,1} Untuk i = 1,2,..n; k = 1,2,..n
Untuk i = 1 dan j = 1
A j dan
A j atau Ckj ( k , j
hk , j
0 jika
C kj ( k , j
1)
(22)
Ck , j
Pkj ( k , j )
Bj
1)
1
Xk
A j dan A j atau C kj ( k , j
1)
Bj
(23)
3.
n
P1,1
1
(10)
Untuk k = 2,3,..,n
0 jika
)}
Untuk k =2,3,..n; j =2
Untuk j = 2 dan k = 1
hk , j
Ck ,1
(21)
Untuk k =1 ; j =2
Untuk Completion time:
hi ,k
(20)
(7)
Untuk k = 2,3,..n
C 1, 2 C1,1
Ck ,1}
hk , 2 x{b2
Untuk k = 2,3,..,n
Untuk k = 1 1,1
Ck ,1 )
(5)
Ck ,1 }
Untuk j=1; k= 1,2,..,n
S k ,1 S k
Bj
1, j )
Untuk k = 2,3,..n dan j = 1 (16) Bila Ketidaktersediaan Terjadi Pada Mesin Kedua Adapun batasan untuk ketidaktersediaan yang terjadi pada mesin ke-2 adalah sebagai berikut Untuk Starting time :
Untuk k = 2,3,..,n
i 1
X k max{0, Ck
Pkj ( k , j )
1, j )
S k ,1 S k
( Z i , k x di ) max{0, Ck , 2
Ck
Untuk k = 1
(3)
n
Tk
C kj ( k
0 jika
S 1,1 0
i 1
dk
hk , j
(14)
Aj (15)
Formulasi Masalah Pengembangan model dilakukan pada sistem flow shop dua mesin dengan asumsi bahwa posisi ketidaktersediaan untuk masingmasing mesin diketahui pada saat penjadwalan akan dilakukan, tidak ada mesin yang dapat memproses lebih dari satu operasi dalam waktu yang bersamaan, waktu proses untuk masingmasing job telah diketahui serta waktu set up sudah termasuk dalam waktu proses. Model yang dikembangkan ini dimodifikasi dari model Kusuma (2008). Modifikasi tersebut adalah : Modifikasi 1 : Pembuatan model eksak dalam penelitian ini nilai indeks
4
interval ketidaktersediaan mesin ditinjau dari waktu awal proses (starting time). Sedangkan Kusuma (2008) meninjau dari waktu selesainya job (completion time). Modifikasi 2 : Penggabungan parameter saat mulai (a1) dan saat selesai (b1) ketidaktersediaan pada mesin pertama dan saat mulai (a2) dan saat selesai (b2) ketidaktersediaan pada mesin kedua dalam starting time maupun completion time. Penjabaran komponen-komponen model untuk penyusunan formulasi model matematis seperti dibawah ini. i nomor job j nomor mesin
i = 1,2,..,n j = 1,2
job urutan ke-k ; hkj = 0 jika mesin ke-j tersedia saat job urutan ke-k Model matematis ditunjukkan oleh persamaan 1 sampai dengan 21 Fungsi Tujuan :
MinZ
Tk
Untuk k = 1,2,..,n
(1)
Subject to : n
Z i ,k
1
i 1
Untuk k =1,2,..,n;
(2)
n
Z i ,k
1
k 1
Untuk i = 1,2,..,n
(3)
n
p k, j
( Z i ,k x
k urutan job setelah di jadwalkan
pij )
i 1
Untuk j=1,2; k=1,2,..,n k = 1,2,..,n L urutan job setelah di jadwalkan
(4)
n
dk
( Z i , k x di ) i 1
(5)
pij waktu proses job i pada mesin ke-j
Untuk k = 1,2,..,n Tk max{0, Ck , 2 d k }
aj saat mulai interval ketidaktersediaan mesin pada mesin ke-j.
Untuk k = 1,2,..,n X k max{0, Ck 1, 2
(6)
bj saat selesai interval ketidaktersediaan mesin pada mesin ke-j
Untuk j=1; k = 1,2,..,n
L = 1,2,..,n
di due date job i = 1,2,..,n Variabel Keputusan : Zik indeks job i dijadwalkan pada posisi kek. Zik = 1 jika job i dijadwalkan pada posisi ke-k, jika tidak maka Zik = 0 Sk1 Starting time job urutan ke-k pada mesin pertama. k = 1,2,..,n Ckj Completion time untuk job urutan ke-k pada mesin ke-j. Parameter yang digunakan: Pkj Processing time job urutan ke-k dimesin ke-j dk due date job urutan ke-k Xk idle time untuk job urutan ke-k, yaitu waktu antara selesainya job urutan ke-k pada mesin pertama dengan mulainya job urutan ke-k pada mesin kedua, k = 1,2,..,n hkj indeks mesin ke-j tersedia saat job urutan ke-k, hkj = 1 bila mesin ke-j tidak tersedia saat
Ck ,1 }
(7)
n
hi ,k
1
k 1
Untuk j = 1,2; k = 1,2,..,n
(8)
Berikut ini pembuatan model matematis dari hasil modifikasi seperti yang disebutkan dalam penjabaran model, yaitu : Modifikasi 1 Pada modifikasi 1, persamaan (15), (16) dan (22),(23) menjadi persamaan (9), (10),(11) dan (12) dibawah ini
hk , j
0 jika
P1,1
Untuk k = 1; j = 1
Aj
(9)
5
hk , j
0 jika S k Sk
pk
1, j
hk , j {0,1}
B j , dan
1, j
pk , j
1, j
Untuk j = 1,2; k =1,2,..,n Aj
Z j ,k {0,1}
Untuk i = 1,2..,n; k = 1,2,...,n(21)
Untuk k = 2,3,..,n; j = 1 (10) hk , j
0 jika S k , j
pk , j
1
Untuk k = 1; j = 2
pk , j
1
(20)
Aj
Konstrain meminimasi tardiness)
(11)
(1)
memastikan total
job.
fungsi
tujuan
keterlambatan
(total
Konstrain
(2)
dan
(3)
memastikan bahwa hanya terdapat satu job yang
hk , j
0 jika S k Sk, j
pk , j
1
B j , dan
1, j
pk , j
1
Untuk k = 2,3,..,n; j = 2
dapat dijadwalkan pada posisi ke-k. Konstrain (4) memastikan waktu proses (processing time)
Aj
(12)
Modifikasi 2 untuk starting time: Pada model modifikasi 2, persamaan (7), (8), dan (17),(18) ,(19) menjadi persamaan (13), (14), (15) dan (16) dibawah ini
S 1,1 h1,1 xb1
Untuk k = 1 ; j = 1 (13) S k ,1 S k 1,1 Pk 1,1 {hk ,1 x(b1 Ck
1,1
)}
Untuk k = 2,3,..,n (14) S k , 2 S k ,1 Pk ,1 {hk , 2 x max( 0, b2 Ck ,1 )} Untuk k = 1; j = 2 S k , 2 S k ,1 Pk ,1 X k
(15) {hk , 2 x max( 0, b2
Untuk k = 2,3,..,n; j = 2
Ck ,1 )}
(16)
Modifikasi 2 untuk completion time: persamaan (9), (10) dan (11) serta (20) dan (21) menjadi (18) dan (19) dibawah ini : n
C k, j Sk, j
( Z i ,k x
pij )
i 1
Untuk j = 1; k dan i = 1,2,..,n(17) C 1, 2 C1,1
P1, 2 {hk , 2 x max( 0, b2
Untuk k = 1; j = 2 C k , 2 Ck ,1
Pk , 2
Xk
C1,1 )}
(18) {hk , 2 x{max( 0, b2
Untuk k =2,3,..,n; j = 2
(19)
Ck ,1 )}
job urutan ke-k di mesin ke-j. Konstrain (5) memastikan tenggat waktu (due date) job untuk job urutan ke-k. Konstrain (6) memastikan bahwa jika (Ck,2 – dk) bernilai positif, maka job terlambat. Jika nilainya negatif, maka tidak ada keterlambatan. Konstrain (7) memastikan idle time job terjadi jika waktu selesainya proses job urutan ke (k-1) pada mesin kedua lebih besar dari waktu selesainya proses job urutan ke-k dimesin pertama. Bila tidak terjadi idle time job, maka Xk = 0. Konstrain (8) memastikan bahwa selama penjadwalan dilakukan, ketidaktersediaan hanya terjadi sekali. Konstrain (9) sampai (12) memastikan jika proses job ke-k dimesin ke-j tidak terpotong oleh interval ketidaktersediaan, maka mesin tersedia ( hk , j 0 ). Konstrain (13) sampai dengan (16) memastikan starting time job di mesin ke-j terjadi sebelum mesin tidak tersedia atau setelah mesin tersedia serta setelah job sebelumnya selesai diproses di mesin ke-j. Konstrain (17) sampai dengan (18) memastikan bahwa completion time job terjadi pada saat awal mesin mulai tidaktersedia atau terjadi saat mesin telah tersedia. Konstrain (4.19) dan (4.20) memastikan indeks interval ketidaktersediaan mesin dan urutan job berupa binary. Model matematis yang dibuat diselesaikan dengan Lingo.8 dan juga diselesaikan dengan Algoritma heuristik. Algoritma Heuristik Algoritma yang dikembangkan dalam penelitian ini menggunakan 3 prioritas pengurutan job, yaitu aturan EDD, Slack, dan Earliness D/P disertai dengan adanya switch job
6
pada mesin pertama. Langkah-langkah algoritma yang dibuat adalah : Langkah 1 : tentukan posisi mesin beserta panjang interval ketidaktersediaan di mesin 1 (a1,b1) dan mesin 2 (a2,b2). Lanjutkan ke langkah 2. Langkah 2 : masukkan data tentang Pi1, Pi2, jumlah job (n), Due date masing-masing job (di), A sebagai urutan job yang belum terjadwal, B sebagai urutan job yang telah terjadwal. Langkah 3 : tentukan prioritas pengurutan dan urutkan job berdasarkan prioritas pengurutan. Langkah 4 : Set L = 1,2,..,n ; j = 1 dan L = 1 Langkah 5 : periksa apakah masih belum ada job yang telah dischedule kan ( B=0 ), jika memenuhi lanjutkan ke langkah 6. Jika tidak memenuhi yang berarti telah ada job yang terjadwalkan, lanjutkan ke langkah 8 Langkah 6 : periksa apakah keadaan B=0 berada pada mesin pertama (mesin ke-1),. Jika memenuhi, maka job tersebut diproses dimesin ke-1 urutan ke-1 dimana starting time-nya = 0 dan lanjutkan ke langkah 11. Jika tidak memenuhi, berarti job urutan ke L tersebut tidak diproses di mesin ke-1, sehingga dipastikan dia diproses di mesin ke-2 dan lanjutkan ke langkah 7. Langkah 7 : hitung starting time job urutan ke-L = 1 dimesin ke dua. Dimana Starting time job urutan ke L dimesin ke 2 merupakan Completion time job urutan ke-L di mesin ke-1 (SL,2= SL,1 + PL,1). Selanjutnya ke langkah 11 Langkah 8 : periksa apakah job yang akan terjadwalkan tersebut akan di proses pada mesin pertama. Jika memenuhi, lanjutkan ke langkah 9. Jika tidak memenuhi
Langkah 9 :
Langkah 10 :
Langkah 11 :
Langkah 12 :
Langkah 13 :
Langkah 14 :
yang berarti job tersebut di jadwalkan pada mesin selanjutnya, yaitu mesin ke-2, maka lanjutkan ke langkah 10 hitung starting time job urutan ke-L dimesin ke satu, dimana Starting time job urutan ke-L di mesin 1 merupakan Completion time job sebelumnya yang telah terjadwalkan di mesin ke-1 (SL,1= SL-1,1 + PL-1,1). Kemudian lanjutkan ke langkah 11. hitung starting time job urutan ke-L di mesin ke-2 setelah ada beberapa job yang terjadwal. Starting time job urutan ke-L dimesin ke-2 ini merupakan completion time job urutan ke-L di mesin ke-1 ditambah dengan idle job. Selanjutnya ke langkah 11. hitung completion time job urutan ke-L yang akan dijadwalkan baik pada mesin 1 maupun mesin ke-2. Dimana completion time job urutan ke-L yang diproses di mesin ke-J merupakan penambahan dari starting time job urutan ke-L di mesin ke-J dengan processing time job urutan ke-L di mesin ke-J. Lanjutkan ke langkah 12. periksa apakah job ke-L diproses di mesin ke-1. Jika memenuhi, lanjutkan ke langkah 13. Jika tidak memenuhi ke langkah 21 periksa apakah job urutan ke-L bisa dijadwalkan pada mesin ke-J sebelum waktu ketidaktersediaan mesin. Gunakan syarat CL,J ≤ aJ apabila syarat tersebut terpenuhi, maka lanjutkan ke langkah 14. Jika syarat tersebut tidak terpenuhi, maka lanjutkan ke langkah 15. Jadwalkan job urutan ke-L setelah job urutan ke-L-1 selesai. Set k = L, dimana k merupakan urutan pengerjaan job yang telah terjadwal (B). Lanjutkan ke langkah 19.
7
Langkah 15 :
Langkah 16 :
Langkah 17 :
Langkah 18 :
Langkah 19 :
Langkah 20 :
Langkah 21 :
periksa apakah job urutan ke-L bisa dijadwalkan pada mesin ke-J sebelum waktu ketidaktersediaan mesin. Gunakan syarat SL,J ≤ aJ apabila syarat tersebut terpenuhi, maka ke langkah Jika syarat tersebut tidak terpenuhi, maka lanjutkan ke langkah 17. Periksa apakah ada job pengganti dibelakang job urutan ke-L dengan syarat CL,J ≤ aJ. Apabila syarat tersebut terpenuhi, maka Tukar posisi job pengganti dan urutkan job menurut di terkecil hingga terbesar dan kembali ke langkah 14. Jika syarat tersebut tidak terpenuhi, Lanjutkan ke langkah 17. periksa apakah SL,J ≤ bJ. Jika syarat tersebut terpenuhi, lanjutkan ke langkah 18. Jika syarat tersebut tidak terpenuhi, maka kembali ke langkah 14. job merupakan cross over job, yaitu job tersebut terpotong oleh interval ketidaktersediaan mesin, sehingga set SL,J = b1, kemudian hitung CL,J = SL,J + PL,J. Dan kembali ke langkah 14. set L = L+1. Jika L = n, maka output dari mesin ke-1 yang berupa urutan job yang telah terjadwal (B) akan menjadi input di mesin ke-2 (A). Sehingga untuk diproses di mesin ke-2, maka set B di mesin ke-1= 0. Lanjutkan ke langkah 20. Jika L < = n, maka kembali ke langkah 5. set J = J+1. Jika J > jumlah mesin (M), maka lanjutkan ke langkah 27 . Jika tidak maka kembali ke langkah 4. periksa apakah job urutan ke-L bisa dijadwalkan pada mesin ke-J sebelum waktu ketidaktersediaan mesin. Gunakan syarat CL,J ≤ aJ apabila
Langkah 22 :
Langkah 23 :
Langkah 24 :
Langkah 25 :
Langkah 26 :
Langkah 27 :
syarat tersebut terpenuhi, maka lanjutkan ke langkah 14. Jika syarat tersebut tidak terpenuhi, maka lanjutkan ke langkah 22. periksa apakah job urutan ke-L bisa dijadwalkan pada mesin ke-J sebelum waktu ketidaktersediaan mesin. Gunakan syarat SL,J ≤ aJ apabila syarat tersebut terpenuhi, maka ke langkah 23. Jika syarat tersebut tidak terpenuhi, maka lanjutkan ke langkah 24. Periksa apakah ada job pengganti dibelakang job urutan ke-L dengan syarat CL,J ≤ aJ. Apabila syarat tersebut terpenuhi, maka Tukar posisi job pengganti dan urutkan job menurut di terkecil hingga terbesar dan kembali ke langkah 14. Jika syarat tersebut tidak terpenuhi, Lanjutkan ke langkah 24. periksa apakah SL,J ≤ bJ. Jika syarat tersebut terpenuhi, lanjutkan ke langkah 25. Jika syarat tersebut tidak terpenuhi, maka lanjutkan ke langkah 14. job merupakan cross over job, yaitu job tersebut terpotong oleh interval ketidaktersediaan mesin, sehingga set SL,J = b1, kemudian hitung CL,J = SL,J + PL,J. Dan kembali ke langkah 14. hitung total tardiness dari semua job yang telah dijadwalkan , dimana Σ(Tk) = Σmax(0, Ck-dk). Lanjutkan ke langkah 27. Algoritma selesai
4.
Contoh Numerik dan Analisis Hasil Contoh numerik dilakukan terhadap teknik penyelesaian, yaitu enumerasi, eksak dan heuristik dengan mengambil sampel jumlah job sebanyak n = 5 (data dari penelitian sebelumnya, Schaller (2005)) sehingga menghasilkan total tardiness. Kemudian, total tardiness tersebut digunakan untuk mengukur
8
kemampuan masing-masing teknik penyelesaian dalam menyelesaikan problem penjadwalan. Problem penjadwalan dengan jumlah job n = 5 salah satunya dilakukan dengan enumerasi karena dipastikan memberikan solusi optimal. Dengan enumerasi semua alternatif penjadwalan dihitung total tardinessnya dan masing-masing n job diuji dengan beberapa interval ketidaktersediaan mesin. Perhitungan enumerasi memerlukan waktu yang cukup lama apabila dilakukan secara manual, Oleh karena itu untuk memudahkan dalam perhitungan, enumerasi yang dilakukan disini untuk mempermudah perhitungan menggunakan bantuan pemrograman Java. Dari rekapan enumerasi, diketahui hubungan antara ketidaktersediaan yang terjadi di kedua mesin dalam mempengaruhi total keterlambatan, yaitu keterlambatan terbesar terjadi apabila ketidaktersediaan mesin terjadi di awal untuk mesin pertama dan terjadi di tengah untuk mesin ke dua. Selain diselesaikan dengan enumerasi model matematis diselesaikan dengan Algoritma Heuristik dan Lingo.8. Untuk mempermudah melakukan perhitungan, Algoritma heuristik menggunakan alat bantu Java dengan mengikuti Langkah 1 sampai dengan Langkah 27 seperti yang dijelaskan diatas. Dari hasil heuristik diketahui bahwa prioritas pengurutan dengan menggunakan EDD menghasilkan total keterlambatan yang paling kecil dibandingkan dengan Slack dan Earliness D/P. Hal ini dikarenakan dalam EDD, due date merupakan pertimbangan utama dalam permulaan pengerjaan job. Dimana job dengan due date terkecil diproses terlebih dahulu. Untuk mengetahui performansi penyelesaian masalah penjadwalan dengan Lingo.8, maka akan diujikan sejumlah job (n) dengan n = 6 sampai dengan n = 12. Setelah model matematis dirunning dengan Lingo.8, dari n = 6 sampai dengan n = 8, tidak dibutuhkan adanya penyesuaian konstrain. Namun ketika n = 9 sampai dengan n = 12, dibutuhkan adanya penyesuaian konstrain. Kemudian dibandingkan performansi antara ketiga teknik penyelesaian (enumerasi, eksak dan heuristik) dalam menyelesaikan kasus penjadwalan yang memperhatikan ketidaktersediaan mesin, maka dilakukan suatu perbandingan terhadap masing-masing posisi
ketidaktersediaan mesin. Dalam penelitian ini, terdapat 9 kombinasi posisi ketidaktersediaan mesin. Dan hasilnya ditunjukkan oleh Gambar 1 dibawah ini.
Gambar 1. Perbandingan Performansi Enumerasi, Eksak dan Heuristik
Dari gambar 1 diatas, kemudian dibuat suatu persentase perbedaan total tardiness yang dapat dilihat pada persamaan 22 dan 23 berikut ini. Perbedaan total tardiness antara solusi eksak terhadap enumerasi: 71 69 x100% 3% 69 (22) Perbedaan total tardiness antara solusi heuristik terhadap enumerasi :
72 69 x100% 5% 69
(23) Persentase perbedaan pada persamaan 22 dan 23 menunjukkan bahwa semakin kecil perbedaan terhadap solusi enumerasi (solusi optimal) maka semakin baik performansi eksak maupun heuristik 5. Kesimpulan Model matematis yang dikembangkan merupakan model Integer Non-Linear Programming, maka dalam pencapaian solusinya, menghasilkan solusi yang local optimum. Dalam penyelesaiannya model matematis di running dalam Lingo.8, dimana dalam menyelesaikan problem penjadwalan, untuk beberapa jumlah job model matematis masih membutuhkan adanya penyesuaian konstrain. Pembuatan model matematis ini sangatlah rumit dan membutuhkan ketelitian serta waktu yang cukup lama. Selain pembuatan model matematis yang sangat rumit, penyelesaian kasus penjadwalan dengan jumlah
9
job yang banyak akan membutuhkan waktu yang lama dalam memperoleh hasil keputusan. Untuk mengatasi hal tersebut, model matematis diselesaikan dengan pendekatan Heuristik. Algoritma heuristik yang dibuat mampu menyelesaikan kasus penjadwalan flow shop dua mesin dengan kriteria performansi minimasi total tardiness dengan mempertimbangkan kendala ketidaktersediaan pada kedua mesin kondisi non-resumble dalam waktu singkat tanpa adanya penyesuaian konstrain. Dimana algoritma heuristik dengan prioritas pengurutan EDD disertai adanya pertukaran job (switch job) dimesin pertama menghasilkan penjadwalan yang cukup baik, yaitu total tardiness paling minimum dibandingkan dengan slack dan juga earliness D/P. Namun, prioritas pengurutan EDD untuk fungsi tujuan total tardiness tidak selalu memperoleh hasil yang optimal. Performansi antara metode eksak (dengan merun dalam Lingo.8) dan heuristik (dengan merun dalam Java) terhadap enumerasi (hasil optimal), diketahui bahwa metode eksak menghasilkan nilai total tardiness yang lebih kecil dibandingkan dengan Algoritma heuristik sehingga dikatakan metode eksak lebih baik dari segi hasil, yaitu menghasilkan job dengan urutan yang nilai keterlambatannya lebih kecil dibandingkan dengan algoritma heuristik. Dengan persentase perbedaan antara enumerasi dan eksak sebesar 3% dan persentase perbedaan antara enumerasi dan heuristik sebasar 5%. Namun dalam kasus tertentu, Algoritma heuristik lebih disarankan digunakan dari pada eksak karena dalam memperoleh hasil keputusan dengan jumlah job yang sangat besar, penyelesaian dengan heuristik membutuhkan waktu yang cukup singkat. Dalam penelitian selanjutnya untuk melengkapi dan menyempurnakan penelitian ini perlu diperhatikan hal-hal sebagai berikut : 1. Interval ketidaktersediaan menggunakan lebih dari sekali untuk masing-masing mesin. 2. Modifikasi model matematik untuk permasalahan dengan jumlah job yang banyak sehingga tidak perlu melakukan penyesuaian model matematik ketika dirunning dengan software Lingo 3. Urutan job di mesin kedua dapat dibuat berbeda dengan urutan job di mesin kesatu.
4. Prioritas pengurutan job dalam heuristik perlu disempurnakan agar dapat menghasilkan solusi yang optimal dan/atau lebih baik. 5. Posisi ketidaktersediaan mesin bersifat probabilistik. 6. Daftar Pustaka Allaoui, H., Artiba, A., Elmaghraby, S.E., Riane, F. 2006. Scheduling of TwoMachine Flow Shop With Availability Constraints On The First Machine. International Journal of Production Economics, Vol. 99, pp. 16-27. Baker, K. R. 1974. Introduction to Scheduling. Canada : John Wiley & Sons, Inc. Berhitu, Jefikz. 2008. Model Penjadwalan Flow Shop n Job m Mesin untuk Meminimasi Makespan dengan Kendala Ketidaktersediaan Mesin dengan Due Date. Thesis Jurusan Teknik Industri ITS. Blazewicz J., Ecker K., Pesch E., Schmidt G., Weglarz J. 2007. International Handbooks Scheduling Computer and Manufacturing Process. Berlin : Springer Chantaravarapan, Samarn, B.E., M.S.I.E. 2002. Heuristic For The Family Scheduling Problems To Minimize Total Tardiness. A Dissertation in Industrial Engineering of Texas. Kubiak, Weislaw, Blazewicz J., Formanowicz P.,Breit J.,Schmidt G. 2002. Two-Machine Flow Shop with Limited Machine Availability. European Journal Of Operation Research, Vol. 136, pp. 528-540. Kusuma, Budiyanti. 2008. Penjadwalan Dua Mesin Flow Shop Untuk Meminimasi Total Tardiness berdasarkan Ketidaktersediaan Mesin. Tugas Akhir Jurusan Teknik Industri ITS. Lee, C. Y. 1997. Minimizing the Makespan in The Two Flow Shop Scheduling
10
Problem With Unavaibility Constraints. Operation Research Letter, Vol.20, pp.129-139.
Availability Constraints. Computers & Operation Research, Vol. 36, pp. 379390.
Lee, C.Y. 1999. Two Machine Flow Shop Scheduling with Avaibility Constraints. European Journal Of Operation Research, Vol.114, pp. 420-129. Liao, L.M and Tsai, C.H. 2008. Heuristic Algorithm for Two Machine Flow Shop with Avaibility Constraints. Computer & Industrial Engineering, Vol. Xxx, pp. xxx-xxx Morton, Thomas E and Pentico, David W. 1993. Heuristic Scheduling Systems. Canada : John Wiley & Sons, Inc. Pan, J.C.H., Chen, J.S., and Chao, C.M. 2002. Minimizing Tardiness in A Two Machine Flowshop. Computers & Operation Research, Vol. 29, pp. 869885. Pinedo, Michael. 2002. Scheduling Theory, Algorithms, and System, Third Edition. New York : Prentice Hall, Inc. Pinedo, Michael. 2008. Scheduling Theory, Algorithms, and System, Second Edition. New Jersey : Prentice Hall, Inc. Riggs, James L. 1976. Production Systems : Planning, Analysis and Control, Third Edition. Canada : John Wiley & Sons, Inc. Schaller, Jefrey. 2005. Note on Minimizing Total Tardiness on A Two-Machine Flowshop. Computers & Operation Research, Vol. 32, pp. 3273-3281. Sipper, D and Bulfin, Robert L., Jr. 1997. Production : Planning, Control, and Integration. New York : The MacGraw Hill, Inc. Strusevich, Vitaly A., Potts, Chris N., And Kubzin, Mikhail A. 2009. Approximation Result for Flow Shop Scheduling Problems with Machine
11
