Usulan Penerapan Penjadwalan dengan Menggunakan Metode Tabu Search di PT Gistex Textile Division The Proposal of Scheduling Implementation Using Tabu Search Method at PT Gistex Textile Division Arifin Suandy, Santoso, Rainisa Maini Heryanto Jurusan Teknik Industri – Universitas Kristen Maranatha E-mail:
[email protected],
[email protected],
[email protected]
Abstrak PT Gistex Textile Division adalah sebuah perusahaan yang bergerak di bidang textile yang mengolah polyester (bahan baku) menjadi kain. Perusahaan memproduksi barang sesuai dengan pesanan konsumen (job order). Dalam melakukan penjadwalan, kriteria yang digunakan perusahaan saat itu untuk menentukan pesanan yang akan diproduksi terlebih dahulu adalah keuntungan terbesar, kesulitan pengerjaan, dan berlangganan. Dengan menerapkan metode ini, terjadi delay yang tinggi pada tiap mesinnya, sehingga utilisasi mesin menjadi rendah dan makespan menjadi besar. Untuk dapat meminimasi makespan dan delay pada tiap mesin, diusulkan metode penjadwalan metaheuristik, yaitu metode Tabu Search. Dalam menerapkan metode Tabu Search dibantu dengan menggunakan software. Penggunaan software bertujuan untuk mempermudah perhitungan dan menghemat waktu untuk mencari solusi yang dihasilkan. Dengan menggunakan data pesanan yang diproduksi pada bulan Desember 2012, untuk metode perusahaan saat ini, dengan menggunakan mesin preset 1 buah didapat makespan sebesar 99.690 menit. Namun dengan menggunakan metode Tabu Search juga didapat hasil yang sama, yaitu sebesar 99.690 menit. Dari hasil penjadwalan metode perusahaan dengan menggunakan 2 mesin Preset, didapat makespan sebesar 72.645 menit, sedangkan dengan menggunakan metode Tabu Search didapat makespan sebesar 71.915 menit dari 300 iterasi, dimana semakin besar iterasi yang dilakukan, maka kemungkinan untuk mendapatkan solusi yang mendekati optimal akan semakin besar. Dengan menggunakan metode Tabu Search, diperoleh penurunan makespan sebesar 1% (12,17 jam) dari metode perusahaan dan peningkatan rata-rata utilisasi mesin sebesar 0,32%. Kata kunci: tabu search, makespan, delay, utilisasi Abstract PT Gistex Textile Division is a company engaged in textile that processing polyester (raw material) into fabric. The company produces fabric according to consumer order (job order). In scheduling, the criteria used by a company to determine order that should be produced first, are the biggest profit, difficulty processing, and customer. By applying this method, high delay occurs at each machine so that the machine utilization is low and the makespan becomes high. In order to minimize the makespan and delay on each machine, the proposed metaheuristic scheduling method is Tabu Search. In applying Tabu Search method is assisted by using the software. The use of software aims to simplify calculations and save the time for searching generate solutions. By using the order data produced in December 2012, the current company method, using one preset machine, makespan obtained for 99,690 minutes. However, by using Tabu Search also obtained the same result, which is 99,690 minutes. From the results of the company method by using two preset machines, makespan obtained for 72,645 minutes, while using Tabu Search 103
JURNAL INTEGRA VOL. 3, NO. 2, DESEMBER 2013: 103-120 method, makespan obtained for 71,915 minutes of 300 iterations, where the greater number of iteration is done, then it is likely to get a near optimal solution will be greater. By using Tabu Search, obtained makespan decrease of 1% (12.17 hours) of the company method and an average increase of 0.32% machine utilization. Keywords: tabu search, makespan, delay, utilization
1. Pendahuluan 1.1 Latar Belakang PT Gistex Textile Division adalah sebuah perusahaan yang bergerak di bidang textile yang mengolah polyester (bahan baku) menjadi kain. Perusahaan memproduksi barang sesuai dengan pesanan konsumen (job order). Masalah yang sedang dihadapi perusahaan saat ini adalah adanya delay pada bagian produksinya. Hal ini menyebabkan utilisasi mesin akan berkurang dan makespan akan meningkat. Investasi mesin yang mahal, menyebabkan perusahaan seharusnya memanfaatkan mesin sebaik mungkin dengan tidak membiarkan mesin delay agar utilisasi mesin meningkat. Dengan meningkatnya utilisasi mesin, maka makespan akan dapat diminimasi. Perusahaan mengalami kesulitan dalam melakukan penjadwalan yang dikarenakan banyaknya job dengan routing mesin yang panjang. Hal ini membuat perusahaan belum memperhatikan delay pada mesin, sehingga utilisasi rendah dan makespan yang dihasilkan cukup besar. Saat ini metode yang digunakan perusahaan untuk mempermudah dalam melakukan penjadwalan adalah dengan melihat kriteria sebagai berikut: 1. Keuntungan terbesar 2. Kesulitan pengerjaan 3. Berlangganan Untuk memperbaiki performansi tersebut maka akan diusulkan suatu metode penjadwalan yang dapat meningkatkan utilisasi mesin dan meminimasi makespan.
2. Landasan Teori 2.1 Job Shop Masalah penjadwalan job shop merupakan masalah penjadwalan yang memiliki karakteristik sebagai berikut: 1. Penjadwalan job shop memiliki sejumlah job yang harus diselesaikan, direpresentasikan sebagai J = {J1, J2, …, Jn} 2. Penjadwalan job shop memiliki sejumlah resource yang digunakan untuk menyelesaikan setiap operasi, direpresentasikan sebagai R = {R1, R2,…,Rm}. Resource biasa disebut juga dengan machine. 3. Setiap job memiliki sejumlah operasi yang harus diselesaikan pada tenggat waktu, mulai dari ready time (rt) sampai due date (dt). 4. Setiap operasi memiliki waktu proses yang berbeda-beda, direpresentasikan dengan t = {t1, t2,…,tj}. Secara fisik, tata letak peralatan yang bertipe job shop ditandai dengan pengelompokkan peralatan yang memiliki fungsi yang sama di area yang sama (Fogarty, 1991). Dalam penjadwalan job shop, jika ada n job yang akan diproses dalam m mesin maka ada (n!)m set jadwal, namun tidak semua jadwal tersebut layak digunakan. Sebuah jadwal dikatakan layak jika memenuhi kriteria sebagai berikut (Fogarty, 1991): 1. Urutan pengerjaan operasi (routing) dalam suatu job tidak dilanggar. 2. Tidak terjadi overlap waktu pengerjaan operasi.
104
PENJADWALAN MENGGUNAKAN METODE TABU SEARCH (Arifin S., et al.)
Pada penjadwalan job shop, karakteristik pekerjaan yang harus diselesaikan harus melewati beberapa mesin (routing) dan tiap rute yang ditempuh masing-masing pekerjaan berlainan/berbeda. Karena tiap job memiliki routing yang berlainan, maka notasi untuk penjadwalan job shop ialah: (Elsayed, 1985) dimana i menyetakan nomor pekerjaan, j menyatakan nomor operasi, dan k menyatakan nomor mesin. Terdapat beberapa definisi yang harus dipahami sebelumnya: 1. Jadwal Feasible Suatu jadwal dikatakan feasible jika seluruh operasi dari semua job telah ditugaskan dan ketentuan routing operasi telah dipenuhi (atau dengan kata lain tidak ada overlap antar operasi). 2. Jadwal Semi Aktif (SA) Kumpulan jadwal feasible dimana tidak satu pun operasi dapat dikerjakan lebih awal tanpa mengubah susunan beberapa operasi mesin. 3. Jadwal Aktif (A) Kumpulan jadwal feasible dimana tidak satu pun operasi dapat dipindahkan lebih awal tanpa menunda operasi lain. 4. Jadwal Non Delay (ND) Kumpulan jadwal feasiblel dimana tidak satu pun mesin dibiarkan menganggur jika pada saat yang sama terdapat operasi yang membutuhkan mesin tersebut. 2.2 Algoritma Tabu Search Berdasarkan informasi yang diambil dari Glover & Laguna (1998), kata “tabu” berasal dari sebuah bahasa Polynesia, yaitu Tongan, yang digunakan oleh suku aborigin pulau Tonga untuk menandakan suatu hal yang tidak dapat disentuh karena hal tersebut keramat. Menurut kamus Webster, kata “tabu” sekarang juga berarti larangan yang muncul akibat kebiasaan atau adat istiadat yang bersifat melindungi. Status “tabu” suatu hal biasanya bergantung kepada ingatan sosial yang selalu termodifikasi seiring dengan berjalannya waktu. Hal ini yang menjadi dasar pengertian “tabu” pada umumnya dengan “tabu” pada Tabu Search. Tabu Search merupakan algoritma yang setingkat lebih baik dibandingkan dengan beberapa algoritma lainnya, seperti Simulated Annealing, untuk melakukan pencarian dengan efisien dan mencegah terjebaknya solusi dalam optimum lokal (Heragu, 2006). Optimum lokal merupakan solusi yang menjadi terbaik di antara solusi-solusi yang berada di sekitarnya, atau yang biasa disebut neighbourhood. Dalam tabu search, dilakukan eksplorasi responsif yang membantu pencegahan terjebaknya solusi dalam optimum lokal dengan mengeksploitasi solusi yang sudah dihasilkan dengan baik, sekaligus daerah solusi di sekitar solusi baik tersebut. Walaupun simulated annealiing juga memiliki mekanisme yang memperbolehkan proses pencarian untuk keluar dari optimum lokal, namun karena simulated annealing merupakan prosedur yang tidak menyimpan informasi mengenai solusi-solusi yang tellah dicek sebelumnya, maka bisa saja memeriksa solusi yang sebelumnya telah dicek, sehingga menyia-nyiakan waktu komputansi dan membuatnya menjadi lebih lama. Pemeriksaan ulang ini biasa disebut dengan cycling. Metode pencarian tabu berprinsip pada penggunaan memori sebagai elemen esensial dalam pencariannya, karena pencarian Tabu tidak hanya menyimpan nilai sebuah solusi terbaik seperti kebanyakan metode pencarian, namun juga menyimpan informasi selama pencarian melalui solusi terakhir yang dikunjungi. Sebuah informasi akan digunakan sebagai petunjuk untuk bergerak dari i ke solusi selanjutnya dalam N(i). Penggunaan memori sebagai pembatas dalam pemilihan beberapa subset dari N(i) dengan mencegah pergerakan ke beberapa solusi tetangga. Untuk mengaplikasikan algoritma Tabu Search ke dalam masalah penjadwalan job shop, perlu didefinisikan enam hal berikut secara tepat, yaitu: (Glover, 1990) 1. Tahap pembuatan solusi (jadwal) awal. Solusi awal untuk algoritma Tabu Search dapat dibuat secara acak atau dengan menggunakan metode heuristik tertentu. Pembuatan solusi job shop secara acak dapat membuka peluang lebih
105
JURNAL INTEGRA VOL. 3, NO. 2, DESEMBER 2013: 103-120
besar untuk dihasilkannya graph jadwal job shop yang mengandung cycle terutama pada kasus uji berukuran besar, sehingga proses pembuatan jadwal awal perlu diulang beberapa kali. 2. Tahap evaluasi fungsi biaya dan penentuan lintasan kritis. Setelah diperoleh sebuah graph untuk jadwal awal, dihitung nilai ES dan LS dari setiap operasi dalam graph dengan menggunakan critical path method. Makespan jadwal adalah nilai ES atau LS dari operasi (operasi dummy N+1). Pada proses komputasi ini juga sekaligus dilakukan identifikasi apakah terdapat cycle dalam graph.jika dalam graph terdapat cycle, maka jadwal tersebut ditolak dan dibuat jadwal baru. Setelah menghitung makespan jadwal, diidentifikasi lintasan kritis dalam graph, yaitu himpunan busur-busur dari vertex pertama menuju vertex terakhir yang memenuhi syarat berikut: - Nilai ES dan LS dari setiap vertex yang dihubungkan oleh busur-busur tersebut harus sama. - Untuk busur u → v, hasil penjumlahan start time dan waktu pengerjaan dari operasi u harus sama dengan start time dari operasi v. 3. Tahap pembuatan neighbour baru. Neighbourhood dari sebuah jadwal adalah himpunan jadwal baru yang dapat diperoleh dengan menerapkan fungsi transisi terhadap jadwal tersebut. Fungsi transisi dalam kasus penjadwalan job shop memilih vertex v dan w sedemikian rupa sehingga: - v dan w adalah dua operasi berurutan sembarang yang dikerjakan pada mesin k. - busur (v,w) Є Ei adalah sebuah busur kritis, atau (v, w) berada pada lintasan kritis dari graph. Fungsi transisi akan memilih satu solusi feasible secara acak dari himpunan neighborhood yang berisi semua kemungkinan solusi yang dapat diperoleh dengan penukaran urutan terhadap operasi-operasi semesin yang posisinya bersebelahan pada lintasan kritis. Sebuah neighborhood dari suatu jadwal dibuat dengan cara mempertukarkan urutan pengerjaan operasi v dan w pada mesin k atau membalikkan arah busur (v,w). Struktur neighbourhood ini didasarkan dua fakta bahwa: - Pembalikan sebuah busur kritis dalam graph Di tidak akan menghasilkan graph Dj yang cyclic. - Jika pembalikan sebuah busur non kritis dalam Di menghasilkan graph acyclic Dj, maka lintasan kritis q dalam Dj tidak mungkin lebih pendek dari lintasan kritis p dalam Di karena Dj masih memuat lintasan p. Dengan cara ini, dapat dihindari pemilihan jadwal yang tidak menghasilkan penurunan makespan dan jadwal yang mengakibatkan terjadinya cyclic graph. Struktur neighbourhood ini memungkinkan model TS hanya meninjau graph-graph yang mewakili solusi yang feasible. Jadi, transisi ini menyebabkan pembalikan busur yang menghubungkan v dan w (v,w) menjadi (w,v) dan penggantian busur (u,v) dan (w,x) dengan busur (u,w) dan (v,x), dimana u adalah operasi sebelum v pada mesin k dan x adalah operasi setelah w pada mesin k. 4. Tahap pengelolaan tabu list. Tabu List memiliki ukuran yang terbatas dan dikelola menggunakan metode FIFO (First In First Out), dimana setiap kali solusi baru dibuat, algoritma TS menyimpan atribut move yang membentuk solusi baru tersebut dan menghapus atribut move yang lama dari list. Kinerja algoritma TS sangat bergantung kepada cara penentuan panjang tabu list secara tepat. Secara empirik, ukuran tabu list untuk menghasilkan kualitas solusi yang baik akan bertambah seiring dengan membesarnya ukuran masalah. Hal ini disebabkan ukuran list yang tepat sebenarnya tergantung pada ketatnya kriteria tabu yang diterapkan; kriteria tabu yang semakin ketat akan mengurangi panjang tabu list yang dibutuhkan. Ukuran tabu list yang terlalu pendek akan mengakibatkan sering terjadinya cycling dalam daerah pencarian yang menyebabkan 106
PENJADWALAN MENGGUNAKAN METODE TABU SEARCH (Arifin S., et al.)
pencarian terjebak dalam solusi optimum lokal, sedangkan ukuran yang terlalu panjang akan mengakibatkan memburuknya kualitas solusi karena terlalu banyak move yang dilarang. 5. Tahap pendefinisian kriteria aspirasi. Pada suatu kondisi tertentu, tabu search dapat melarang sebuah move yang sebenarnya dapat menuntun proses pencarian bergerak ke daerah solusi yang belum dikunjungi, yang mungkin dapat memberikan solusi yang baik, maka diperlukan suatu metode untuk dapat membatalkan efek dari tabu list, yang disebut kriteria aspirasi. Kriteria aspirasi diperkenalkan dalam tabu search untuk menentukan kapan forbidden move tetap dapat digunakan, atau merupakan bagian dari tabu search yang berfungsi untuk membatalkan efek dari tabu list untuk beberapa move pada beberapa kondisi tertentu. Aturan dasar yang dapat digunakan sebagai kriteria aspirasi adalah untuk tiap kandidat move yang merupakan anggota dari tabu list dihitung panjang lintasan kritis dari solusi yang dihasilkannya. Jika panjang lintasan kritis (yang mewakili nilai makespan untuk solusi baru tersebut) lebih kecil dari solusi terbaik yang telah ditemukan sebelumnya, maka status tabu dari move tersebut dihapuskan dan move itu digunakan untuk membuat solusi berikutnya. 6. Tahap penentuan kriteria terminasi. Terdapat beberapa kondisi yang dapat digunakan sebagai kriteria terminasi dalam algoritma TS, di antaranya: - Ditemukannya sebuah solusi optimal. - N(s,k+1) = Ø, artinya tidak ada lagi solusi baru yang dapat dibangkitkan dari neighbourhood solusi sekarang, karena semua move dalam neighbourhood tersebut terdapat di dalam tabu list. - Jumlah iterasi k sudah melebihi jumlah iterasi maksimum yang ditetapkan di awal. - Jumlah iterasi yang dilakukan setelah memperoleh solusi terbaik yang terbaru sudah melebihi batas maksimum iterasi non-improving yang ditetapkan di awal.
107
JURNAL INTEGRA VOL. 3, NO. 2, DESEMBER 2013: 103-120 Mulai Data awal yang dibutuhkan: 1. Jumlah job 2. Kuantitas tiap job 3. Routing tiap job 4. Jenis dan jumlah mesin 5. Waktu proses 6. Peta Proses Operasi Penentuan Parameter: Maximum Iterasi (kmax) Buat jadwal awal job shop Buat graph awal Definisikan busur disjunctive Penentuan lintasan kritis (Perhitungan nilai makespan )
Lintasan Kritis >1
Ya
Prioritaskan mesin paling depan
Tidak Set k = 0 Penentuan matrix solusi awal Penentuan nilai GlobalMin Pembuatan Tabu List Set k = k+1
Penentuan BestSoFar Penentuan lintasan kritis Pencarian solusi tetangga
Lintasan Kritis >1
Ya
Tidak
Definisikan busur disjunctive & lintasan kritis Hitung nilai makespan (Fcost)
B
C
A
Gambar 1. Flowchart Tabu Search
108
Prioritaskan mesin paling depan Simpan sisa lintasan kritis pada list
PENJADWALAN MENGGUNAKAN METODE TABU SEARCH (Arifin S., et al.)
B
A
C
Pilih Fcost terkecil Set solusi tetangga i=1
Set solusi tetangga i= i+1
Tidak
Ya
Tidak
Apakah i > I max
Ya
Fcost terpilih< BestSoFar?
Ya Ya
Lintasan Kritis = TL
Apakah ada sisa lintasan kritis?
BestSoFar = BestSoFar lama
Ya Fcost terpilih = BestSoFar
Tidak Penentuan BestMove (S)
Pilih solusi dari Fcost terkecil berikutnya
Tambahkan solusi tetangga ke Tabu List
BestSoFar < GlobalMin?
Tidak
GlobalMin=GlobalMin lama
Ya BestSoFar = GlobalMin
Penentuan Best
Hapus list
Tidak
k = kmax?
Ya Solusi akhir terbaik telah diperoleh
Selesai
Gambar 1. Flowchart Tabu Search (Lanjutan)
3. Pembahasan 3.1 Perhitungan Metode Perusahaan Penjadwalan dengan metode perusahaan ditunjukkan dalam tabel 1. 109
110
FB
FB
FB
FB
Reg
Reg
Reg
Reg
Reg
Reg
Reg
FB
FB
Reg
Item 63
Item 95
Item 118
Item 51
Item 112
Item 134
Item 117
Item 58
Item 116
Item 137
Item 136
Item 90
Reg
Item 107
Item 2
FB
Item 127
Item 27
Reg
Item 67
FB
Reg
Item 24
Reg
Reg
Item 99
Item 91
Reg
Item 43
Reg
Reg
Item 72
Item 82
Reg
Item 145
Item 41
Reg
Item 98
Reg
Reg
Item 106
Item 12
Reg
Item 28
FB
FB
Item 6
FB
Reg
Item 18
Item 93
Reg
Item 126
Item 81
Reg
Item 60
FB
Reg
Item 150
Reg
Reg
Item 38
Item 131
Reg
Item 79
Item 128
Color
Job
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
$
1,65
1,45
1,55
2,20
3,67
2,92
2,10
1,65
3,75
2,24
2,08
2,95
3,10
1,78
3,60
2,60
3,85
1,45
2,65
3,20
1,95
2,50
2,50
2,10
1,51
3,20
3,70
1,55
3,30
4,30
2,40
3,60
3,50
2,75
1,50
3,50
3,55
1,47
1,46
2,55
Price $/Yd
2.000
2.800
2.800
1.500
700
1.500
2.000
1.800
1.000
2.000
1.200
900
1.200
2.000
600
800
900
2.800
1.000
1.000
1.100
1.300
1.000
1.100
2.400
1.400
1.000
2.800
800
900
1.100
900
800
800
1.600
900
900
1.800
2.200
1.000
Batch (yard)
1.850
5.000
5.000
5.000
3.000
5.000
7.500
10.000
7.655
13.800
20.000
15.300
15.000
30.000
15.600
22.000
15.000
45.000
25.000
22.000
65.100
54.681
54.681
74.681
110.000
55.000
51.400
130.000
61.242
53.124
95.927
68.755
75.459
97.745
179.353
105.096
115.976
315.000
386.965
319.212
Permintaan Desember (yard)
153
364
388
550
551
730
788
825
1.435
1.546
2.080
2.257
2.325
2.670
2.808
2.860
2.888
3.263
3.313
3.520
6.347
6.835
6.835
7.841
8.305
8.800
9.509
10.075
10.105
11.422
11.511
12.376
13.205
13.440
13.451
18.392
20.586
23.153
28.248
40.699
keuntungan ($)
1
2
2
4
5
4
4
6
8
7
17
17
13
15
26
28
17
17
25
22
60
43
55
68
46
40
52
47
77
60
88
77
95
123
113
117
129
175
176
320
Jumlah batch
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
Re e ling Re laxing A Re laxing B Hydro (4) (6) (4) (3)
20
20
20
20
20
20
20
20
20
20
Softce r (1)
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
Unroll (3)
40
40
40
40
40
40
40
40
40
40
40
Pre Washing Drying (1) 40
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
Pre se t (1)
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
25
25
25
25
25
25
25
25
25
25
25
150
150
150
150
150
150
150
150
150
150
150
150
150
150
150
150
150
150
150
150
150
150
Hisaka Dye ing ST Tank (4) WR (3) colour (7)
Waktu/batch (menit)
Tabel 1. Penjadwalan Metode Perusahaan
150
150
150
150
150
150
150
150
150
150
150
150
150
150
150
150
150
Dye ing black (5)
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
FWD (2)
35
140
140
35
35
35
35
35
35
35
140
140
140
35
140
35
140
35
35
35
35
35
35
140
140
35
140
35
35
35
35
35
140
35
35
35
35
35
35
20
20
20
20
20
20
20
20
20
20
20
20
20
20
Final Se t He atcut (3) (2)
45
Folding (3)
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
Sablon (3)
JURNAL INTEGRA VOL. 3, NO. 2, DESEMBER 2013: 103-120
PENJADWALAN MENGGUNAKAN METODE TABU SEARCH (Arifin S., et al.)
Dari tabel 1, dapat dilihat job yang akan dijadwalkan dengan urutan mesin yang dibutuhkan dan waktu per batch untuk menyelesaikan job tersebut. Contoh baris pertama yaitu job item 79 dengan jumlah batch sebesar 320. Urutan proses pengerjaan job tersebut adalah mesin Relaxing B – Softcer – Unroll – Pre Washing Drying – Preset – ST Tank – Dyeing Colour – FWD – Final Set. Contoh membaca waktu per batch untuk mesin Relaxing B adalah 120 menit. Dengan menggunakan 1 buah mesin preset, makespan yang dihasilkan sebesar 99.690 menit, sedangkan dengan menggunakan 2 buah mesin preset, makespan yang dihasilkan sebesar 72.645 menit. Utilisasi tiap mesin dengan 2 buah mesin preset dapat dilihat pada Tabel 2. Tabel 2. Utilisasi dan Delay Mesin Metode Perusahaan Mesin
Reeling
Relaxing A
Relaxing B
Hydro Softcer Unroll Pre washing drying preset Hisaka WR
MesinKe Used Time % Utilisasi 1 2 3 4 1 2 3 4 5 6 1 2 3 4 1 2 3 1 1 2 3 1 1 2 1 2 3
5.075 5.050 5.050 5.050 16.200 16.200 16.200 16.200 16.200 16.080 41.760 41.760 41.760 41.760 9.450 9.450 9.415 17.480 19.550 16.550 18.925 31.160 49.545 49.500 49.320 49.320 49.200
6,99% 6,95% 6,95% 6,95% 22,30% 22,30% 22,30% 22,30% 22,30% 22,14% 57,49% 57,49% 57,49% 57,49% 13,01% 13,01% 12,96% 24,06% 26,91% 22,78% 26,05% 42,89% 68,20% 68,14% 67,89% 67,89% 67,73%
Mesin
% Delay 93,01% 93,05% 93,05% 93,05% 77,70% 77,70% 77,70% 77,70% 77,70% 77,86% 42,51% 42,51% 42,51% 42,51% 86,99% 86,99% 87,04% 75,94% 73,09% 77,22% 73,95% 57,11% 31,80% 31,86% 32,11% 32,11% 32,27%
MesinKe Used Time % Utilisasi 1 2 3 4 1 2 3 4 5 6 7 1 2 3 4 5 1 2 1 2 1 2 1 2 3 1 2 3
ST Tank
Dyeing colour
Dyeing black
FWD Final Set Heat cut Folding
Sablon
16.525 8.100 25 42.300 42.300 42.000 36.600 24.450 20.700 20.250 21.600 21.600 21.150 17.700 16.950 50.680 26.920 63.945 49.245 7.000 3.660 5.265 2.610 16.500 16.200 8.300
22,75% 11,15% 0,03% 0,00% 58,23% 58,23% 57,82% 50,38% 33,66% 28,49% 27,88% 29,73% 29,73% 29,11% 24,37% 23,33% 69,76% 37,06% 88,02% 67,79% 9,64% 5,04% 7,25% 3,59% 0,00% 22,71% 22,30% 11,43%
% Delay 77,25% 88,85% 99,97% 100,00% 41,77% 41,77% 42,18% 49,62% 66,34% 71,51% 72,12% 70,27% 70,27% 70,89% 75,63% 76,67% 30,24% 62,94% 11,98% 32,21% 90,36% 94,96% 92,75% 96,41% 100,00% 77,29% 77,70% 88,57%
3.2 Perhitungan Manual Metode Tabu Search Contoh Kasus Sederhana: Tabel 3. Urutan Penjadwalan Metode Perusahaan
M1 (3) Job 1 (5) Job 2 (4) Job 3 (3)
3 3
M2 (4) 4 4
M3 (2) 5 5
M4 (2) 5 5
Langkah 1: Penentuan Parameter MaksItr = Kmax = 1 Langkah 2: Pembuatan Jadwal Awal Notasi: i-j-k ( job - operasi - mesin) Metode: Semi Aktif
111
112
3
9
J22AM12
J21AM11
M1 a
J11AM21
M2 a
M1 b
J12AM22
M2 b
J23AM13
J13AM23
M2 c
M1 c
J14AM24
M2 d
6
J24AM11
J31AM12
6
8
J31BM22
J32BM23
J33AM11
J15AM21
J32AM13
4
4
4
4
10
9
9
J33BM21
J13BM31
13
14
19
J22BM31
Gambar 2. Gantt Chart
J15BM31
J11BM31
M3 a
4
J23BM32
J21BM32
J12BM32
M3 b J14BM32
J21CM41
M4 a
M4 b
24
24
J24BM31
J22CM41
J23CM42
29
29 J24CM41
J31CM42 34 J32CM41
J33CM42 39
JURNAL INTEGRA VOL. 3, NO. 2, DESEMBER 2013: 103-120
33
32
Job 31
24
23
22
Job 21
15
14
13
12
Job 11
X
0 0
Langkah 3:
J33 A M11
J24 A M11
J21 A M11
6 9
3 6
0 3
M11
J31 A M12
J22 A M12
3 6
0 3
M12
J32 A M13
J23 A M13
3 6
0 3
M13
Pembuatan Graph awal Job Shop
4 8
0 4
J33 9 B M21 13
J15 A M21
J11 A M21
M21
0 4
0 4
J32 6 B M23 10
J13 A M23
M23
Gambar 3. Graph awal
J31 6 B M22 10
J12 A M22
M22
J14 A M24
0 4
M24 4 9
J24 24 B M31 29
J22 19 B M31 24
J15 14 B M31 19
J13 9 B M31 14
J11 B M31
M31
4 9
J23 19 B M32 24
J21 14 B M32 19
J14 9 B M32 14
J12 B M32
M32
J32 34 C M41 39
J24 29 C M41 34
J22 24 C M41 29
J21 19 C M41 24
M41
J33 34 C M42 39
J31 29 C M42 34
J23 24 C M42 29
M42
Y
39 39
PENJADWALAN MENGGUNAKAN METODE TABU SEARCH (Arifin S., et al.)
113
114
33
32
Job 31
24
23
22
Job 21
15
14
13
12
Job 11
X
Langkah 4:
0 0
J33 A M11
J24 A M11
J21 A M11
6 9
3 6
0 3
M11
J31 A M12
J22 A M12
3 6
0 3
M12
J32 A M13
J23 A M13
3 6
0 3
M13
Definisikan busur disjunctive
4 8
0 4
0 4
J31 6 B M22 10
J12 A M22
M22
0 4
J32 6 B M23 10
J13 A M23
M23
J14 A M24
0 4
M24
Gambar 4. Busur Disjunctive
J33 9 B M21 13
J15 A M21
J11 A M21
M21 4 9
J24 24 B M31 29
J22 19 B M31 24
J15 14 B M31 19
J13 9 B M31 14
J11 B M31
M31
4 9
J23 19 B M32 24
J21 14 B M32 19
J14 9 B M32 14
J12 B M32
M32
J32 34 C M41 39
J24 29 C M41 34
J22 24 C M41 29
J21 19 C M41 24
M41
J33 34 C M42 39
J31 29 C M42 34
J23 24 C M42 29
M42
Y
39 39
JURNAL INTEGRA VOL. 3, NO. 2, DESEMBER 2013: 103-120
PENJADWALAN MENGGUNAKAN METODE TABU SEARCH (Arifin S., et al.)
Langkah 5: Tentukan Lintasan kritis J12AM22-J12BM32-J14BM32-J21BM32-J21CM41-J22CM41-J24CM41-J32CM41 1 2 3 4 5 6 7 8 Makespan = 39 Langkah 6: k=0
Set k = 0
Langkah 7: Penentuan matriks solusi awal S= [ 1 2 3 4 5 6 7 8] Langkah 8: Penentuan Global Minimun Global Minimum= Fcost = 39 Langkah 9: Pembuatan Tabu List TL= [J12AM22-J12BM32-J14BM32-J21BM32-J21CM41-J22CM41-J24CM41- J32CM41] Langkah 10: Set k =1 k=1 Langkah 11: Penentuan Best So Far Best So Far = Fcost = 39 Langkah 12: Pencarian solusi tetangga (Neighborhood) 2-1-3-4-5-6-7-8 =x 1-3-2-4-5-6-7-8 =x 1-2-5-4-3-6-7-8 =x 3-2-1-4-5-6-7-8 =x 1-4-3-2-5-6-7-8 =x 1-2-6-4-5-3-7-8 =x 4-2-3-1-5-6-7-8 =x 1-5-3-4-2-6-7-8 =x 1-2-7-4-5-6-3-8 =x 5-2-3-4-1-6-7-8 =x 1-6-3-4-5-2-7-8 =x 1-2-8-4-5-6-7-3 =x 6-2-3-4-5-1-7-8 =x 1-7-3-4-5-6-2-8 =x 1-2-3-5-4-6-7-8 =x 7-2-3-4-5-6-1-8 =x 1-8-3-4-5-6-7-2 =x 1-2-3-6-5-4-7-8 =x 8-2-3-4-5-6-7-1 =x 1-2-4-3-5-6-7-8 =? 1-2-3-7-5-6-4-8 =x
1-2-3-8-5-6-7-4=x 1-2-3-4-6-5-7-8=x 1-2-3-4-7-6-5-8=x 1-2-3-4-8-6-7-5=x 1-2-3-4-5-7-6-8=x 1-2-3-4-5-8-7-6=x 1-2-3-4-5-6-8-7=?
115
116
33
32
Job 31
24
23
22
Job 21
15
14
13
12
Job 11
X
0 0
J33 A M11
J24 A M11
J21 A M11
6 9
3 6
0 3
M11
J31 A M12
J22 A M12
3 6
0 3
M12
3 6
0 3
4 8
0 4
J33 9 B M21 13
J15 A M21
J11 A M21
M21
0 4
J31 6 B M22 10
J12 A M22
M22
0 4
J32 6 B M23 10
J13 A M23
M23
J14 A M24
0 4
M24 4 9
J24 24 B M31 29
J22 19 B M31 24
J15 14 B M31 19
J13 9 B M31 14
J11 B M31
M31
Gambar 5. Busur Disjunctive (1-2-4-3-5-6-7-8)
J32 A M13
J23 A M13
M13
Langkah 13: Definisikan Busur Disjunctive 1-2-4-3-5-6-7-8
4 9
J23 19 B M32 24
J21 9 B M32 14
J14 14 B M32 19
J12 B M32
M32
J32 34 C M41 39
J24 29 C M41 34
J22 24 C M41 29
J21 14 C M41 19
M41
J33 34 C M42 39
J31 29 C M42 34
J23 24 C M42 29
M42
Y
39 39
JURNAL INTEGRA VOL. 3, NO. 2, DESEMBER 2013: 103-120
33
32
Job 31
24
23
22
Job 21
15
14
13
12
Job 11
X
0 0
1-2-3-4-5-6-8-7
J33 A M11
J24 A M11
J21 A M11
6 9
3 6
0 3
M11
J31 A M12
J22 A M12
3 6
0 3
M12
J32 A M13
J23 A M13
4 8
0 4
J33 9 B M21 13
J15 A M21
J11 A M21
M21
0 4
J31 6 B M22 10
J12 A M22
M22
0 4
J32 6 B M23 10
J13 A M23
M23
J14 A M24
0 4
M24
Gambar 6. Busur Disjunctive (1-2-3-4-5-6-8-7)
3 6
0 3
M13 4 9
J24 24 B M31 29
J22 19 B M31 24
J15 14 B M31 19
J13 9 B M31 14
J11 B M31
M31
4 9
J23 19 B M32 24
J21 14 B M32 19
J14 9 B M32 14
J12 B M32
M32
J32 29 C M41 34
J24 34 C M41 39
J22 24 C M41 29
J21 19 C M41 24
M41
J33 34 C M42 39
J31 29 C M42 34
J23 24 C M42 29
M42
Y
39 39
PENJADWALAN MENGGUNAKAN METODE TABU SEARCH (Arifin S., et al.)
117
JURNAL INTEGRA VOL. 3, NO. 2, DESEMBER 2013: 103-120
Langkah 14: Hitung nilai makespan Alternatif 1: 39 Alternatif 2: 39 Best so far = 39 Langkah 15: Penentuan Best Move S = [ 1 2 4 3 5 6 7 8] Lintasan Kritis: [J11AM21 – J11BM31 – J13BM31 – J15BM31 – J22BM31 – J22CM41 – J24CM41 – J32CM41] Langkah 16:
Tambahkan solusi tetangga ke tabu list
TL= Global min = 39 Langkah 17: Penentuan Best Best = [ 1 2 3 4 5 6 7 8 ], dengan global min = 39 Lintasan Kritis = J12AM22-J12BM32-J14BM32-J21BM32-J21CM41-J22CM41-J24CM41J32CM41 3.3 Penjadwalan Kasus Perusahaan Menggunakan Metode Tabu Search Dari hasil penjadwalan metode Tabu Search, dengan menggunakan mesin preset 1 buah didapat makespan sebesar 99.690 menit, sedangkan dengan menggunakan 2 mesin preset didapat makespan sebesar 71.915 menit dengan 300 buah iterasi. Utilisasi tiap mesin dari skenario 2 dapat dilihat pada Tabel 4. Tabel 4. Utilisasi dan Delay tiap mesin metode Tabu Search Mesin
MesinKe Used Time % Utilisasi 1 5.075 7,06% 2 5.050 7,02% Reeling 3 5.050 7,02% 4 5.050 7,02% 1 16.200 22,53% 2 16.200 22,53% 3 16.200 22,53% Relaxing A 4 16.200 22,53% 5 16.200 22,53% 6 16.080 22,36% 1 41.760 58,07% 2 41.760 58,07% Relaxing B 3 41.760 58,07% 4 41.760 58,07% 1 9.450 13,14% Hydro 2 9.450 13,14% 3 9.415 13,09% Softcer 1 17.480 24,31% 1 19.550 27,18% Unroll 2 16.550 23,01% 3 18.925 26,32% Pre washing drying 1 31.160 43,33% 1 49.545 68,89% preset 2 49.500 68,83% 1 49.320 68,58% Hisaka WR 2 49.320 68,58% 3 49.200 68,41%
118
% Delay 92,94% 92,98% 92,98% 92,98% 77,47% 77,47% 77,47% 77,47% 77,47% 77,64% 41,93% 41,93% 41,93% 41,93% 86,86% 86,86% 86,91% 75,69% 72,82% 76,99% 73,68% 56,67% 31,11% 31,17% 31,42% 31,42% 31,59%
Mesin ST Tank
Dyeing colour
Dyeing black
FWD Final Set Heat cut Folding
Sablon
MesinKe Used Time 1 16.525 2 8.100 3 25 4 1 42.300 2 42.300 3 42.000 4 36.600 5 24.450 6 20.700 7 20.250 1 21.600 2 21.600 3 21.150 4 17.700 5 16.950 1 50.680 2 26.920 1 63.945 2 49.245 1 7.000 2 3.660 1 5.265 2 2.610 3 1 16.500 2 16.200 3 8.300
% Utilisasi % Delay 22,98% 77,02% 11,26% 88,74% 0,03% 99,97% 0,00% 100,00% 58,82% 41,18% 58,82% 41,18% 58,40% 41,60% 50,89% 49,11% 34,00% 66,00% 28,78% 71,22% 28,16% 71,84% 30,04% 69,96% 30,04% 69,96% 29,41% 70,59% 24,61% 75,39% 23,57% 76,43% 70,47% 29,53% 37,43% 62,57% 88,92% 11,08% 68,48% 31,52% 9,73% 90,27% 5,09% 94,91% 7,32% 92,68% 3,63% 96,37% 0,00% 100,00% 22,94% 77,06% 22,53% 77,47% 11,54% 88,46%
PENJADWALAN MENGGUNAKAN METODE TABU SEARCH (Arifin S., et al.)
4. Kesimpulan dan Saran 4.1 Kesimpulan Dari hasil pengolahan data dan analisis, dapat disimpulkan: 1. Penjadwalan Metode Perusahaan saat ini Dalam melakukan penjadwalan, saat ini perusahaan menggunakan kriteria untuk menentukan pesanan yang akan diproduksi terlebih dahulu. Adapaun kriteria tersebut sbb: (1) Keuntungan terbesar, (2) Kesulitan Pengerjaan, dan (3) Berlangganan. Dengan menggunakan kriteria tersebut, perusahaan lebih mudah dalam melakukan penjadwalannya. Namun, hal ini mengakibatkan perusahaan tidak begitu memperhatikan delay pada mesin, sehingga menyebabkan makespan yang lama, yaitu sebesar 99.690 menit untuk skenario 1, dimana terdapat 1 buah mesin Preset dan 72.645 menit untuk skenario 2, dimana terdapat 2 buah mesin Preset. 2. Usulan Penjadwalan untuk PT Gistex Textile Division Metode usulan yang tepat pada saat ini untuk penjadwalan perusahaan adalah dengan metode Tabu Search, karena metode ini dapat menghasilkan banyak solusi dan kemungkinan untuk mendapatkan solusi optimal pun cukup besar. Dari hasil perhitungan metode Tabu Search didapat makespan sebesar 99.690 menit untuk skenario 1, dimana pada skenario ini mesin Preset hanya 1 dan mesin Final Set 3 mesin. Untuk skenario 2, dimana menggunakan 2 Preset dan 2 Final Set didapat makespan sebesar 71.915 menit dengan jumlah iterasi 300 buah. Dengan menggunakan skenario 2, jika iterasi diperbanyak, maka kemungkinan untuk dapat meminimasi makespan lebih besar. 3. Manfaat yang Diperoleh Perusahaan dengan Metode Usulan Manfaat yang akan diperoleh perusahaan jika menerapkan metode Tabu Search adalah dapat meminimasi makespan hingga 1% (dengan 300 buah iterasi). Dengan meminimasi makespan, maka utilisasi tiap mesin akan meningkat dan delay tiap mesin akan berkurang. 4.2 Saran 1. Sebaiknya perusahaan menyelesaikan permasalahan pada proses operasi di mesin preset terlebih dahulu sebelum melakukan penjadwalan. 2. Jika metode Tabu Search akan diterapkan oleh perusahaan, perlu pelatihan untuk penggunaan software bagi karyawan bagian penjadwalan. Diperlukan juga hardware yang mendukung penggunaan software tersebut. 3. Perlunya penelitian untuk membandingkan performansi Tabu Search dengan metode metaheuristik yang lain.
5. Daftar Pustaka Baker, K. R. (1974), “Introduction to Sequencing and Scheduling”, John Wiley and Sons Inc., New York. Conway, R., et al. (1976), “Theory of Scheduling”, Addison Wesley Publishing Company, Massachusetts.
Elsayed, E. A. and Thomas O Boucher (1985), “Analysis and Control of Production Systems”, Prentice-Hall, New Jersey. Fogarty, D. W., John H. Blackstone, Thomas R. Hoffman (1991), “Production and Inventory Management”, 2nd Edition, South Western Publishing, Cincinnati. Glover, F. (1990), ”Tabu Search – Part II”, ORSA Journal on Computing. 119
JURNAL INTEGRA VOL. 3, NO. 2, DESEMBER 2013: 103-120
Glover, F. and Manuel Laguna (1998), “Tabu Search”, Article. Heragu, S. S. (2006), “Facilities Design”, Second Edition, iUniverse Inc., USA. Kusuma, Ir. H. (1992), “Perencanaan dan Pengendalian Produksi”, Penerbit Andi. Morton, T. E. and David W. Pentico (1993), “Heuristic Scheduling System”, John Wiley and Sons Inc., Canada. Parker, R. G. (1995), “Deterministic Scheduling Theory”, Chapman & Hall, London.
120
