PENJADWALAN FLOWSHOP UNTUK MEMINIMASI LOGOTOTAL TARDINESS DENGAN URUTAN JOB YANG SAMA DAN/ATAU BERBEDA DAN MEMPERHATIKAN KETIDAKTERSEDIAAN PADA MASING-MASING MESIN
OLEH : RULI ASTRI ANDRIANI (2506 100 143)
Jurusan Teknik Industri Fakultas Teknologi Industri Institut Teknologi Sepuluh Nopember Surabaya
LATAR BELAKANG Proses produksi membutuhkan mesin untuk memproses job. Mesin tidak selalu tersedia karena kendala ketidaktersediaan (preventive maintenance).
Pembuatan jadwal produksi harus mempertimbangkan ketidaktersediaan mesin.
LATAR BELAKANG Asumsi urutan job job--job pada masingmasing-masing mesin sama
Penjadwalan flowshop dengan memperhatikan ketidaktersediaan mesin Lee (1997)
Lee (1999)
Arlianto (2001)
Kubiak et al. (2002)
Setiawati (2003)
Berhitu (2008)
Budiyanti (2008)
Pitrasari (2009)
LATAR BELAKANG
Penjadwalan flowshop dengan urutan job pada masing-masing mesin sama
LATAR BELAKANG Penjadwalan flowshop dengan urutan job pada masing-masing mesin berbeda
Penelitian yang dilakukan: -Penjadwalan flowshop n job m mesin -Meminimasi total tardiness -Ketidaktersediaan pada masing-masing mesin -Urutan job dapat sama dan/atau berbeda -Pengerjaan job non resumable -Eksak, Heuristik, dan Enumerasi
PERUMUSAN MASALAH Penelitian yang akan dilakukan adalah merancang model penjadwalan m mesin flowshop dengan urutan job yang dapat sama dan atau berbeda dan mempertimbangkan ketidaktersediaan pada masingmasing mesin. Kriteria performansi yang digunakan pada penelitian ini yaitu meminimumkan total tardiness untuk kondisi job non resumable.
TUJUAN PENELITIAN Merancang algoritma heuristik yang mampu menyelesaikan permasalahan penjadwalan flowshop dengan kriteria performansi meminimumkan total tardiness.
Membandingkan antara solusi yang dihasilkan dari algoritma dengan solusi dari enumerasi.
Membandingkan antara solusi yang dihasilkan dalam penelitian ini dengan solusi pada penelitian-penelitian sebelumnya.
RUANG LINGKUP PENELITIAN Asumsi
Batasan Interval ketidaktersediaan mesin sebanyak satu kali pada masingmasing mesin.
Job sudah tersedia dan siap diproses pada waktu ke-0 Processing time dan due date diketahui Set up time mesin termasuk dalam processing time Posisi ketidaktersediaan mesin diketahui sebelum proses produksi dilakukan Urutan job yang diproses pada masingmasing mesin dapat sama dan/atau berbeda
MANFAAT PENELITIAN Memberikan solusi alternatif yang lebih baik dan riil untuk diimplementasikan pada suatu sistem manufakturing.
Mengetahui perbandingan antara solusi yang dihasilkan dari algoritma dengan solusi dari enumerasi.
Mengetahui perbandingan antara solusi yang dihasilkan dalam penelitian ini dengan solusi yang dihasilkan pada penelitianpenelitian sebelumnya.
METODOLOGI PENELITIAN
METODOLOGI PENELITIAN
MODEL KONSEPTUAL
ALGORITMA HEURISTIK Masukkan data dan parameter, yaitu panjang interval ketidaktersediaan mesin (aj, bj), jumlah job, processing time job di mesin j, dan due date. Urutkan job berdasarkan SPT (Shortest Processing Time). Urutan ini akan menjadi input bagi mesin 1. Proses job di mesin 1 berdasarkan urutan input. Lihat apakah processing time job urutan 1 pada input ≤ a1. Apabila benar maka proses job tersebut sebagai urutan 1 dengan starting time = 0. Apabila tidak memenuhi cari job urutan selanjutnya (urutan input) dimana processing time-nya ≤ a1 dan proses job tersebut dengan starting time = 0. Apabila semua job pada inputan tidak terdapat job yang memiliki processing time ≤ a1, maka proses job inputan urutan 1 dengan starting time = b1. Lihat apakah terdapat job inputan urutan sebelumnya yang belum diproses. Apabila ada, maka kembali ke job tersebut. Lihat apakah . Apabila memenuhi syarat tersebut, proses job tersebut sebagai urutan selanjutnya dengan starting time = . Kemudian proses job inputan urutan selanjutnya dengan cara yang sama. Apabila maka cari job inputan urutan selanjutnya yang memenuhi syarat . Apabila semua job inputan yang tersisa tidak terdapat yang memenuhi syarat maka pilih job inputan urutan paling awal dengan starting time = b1. Lakukan dengan cara yang sama untuk job-job urutan selanjutnya.
CONT’D Apabila semua job pada inputan sudah selesai diproses di mesin 1, catat completion time untuk masing-masing job. Urutan job-job yang selesai diproses dicatat sebagai urutan jobjob di mesin j dan menjadi inputan bagi mesin j+1. Proses job di mesin m+1 berdasarkan urutan input. Lihat job inputan urutan ((j+1)-1). Apabila maka proses job tersebut sebagai urutan 1 dengan . Apabila cari job urutan selanjutnya yang memenuhi syarat kemudian proses job tersebut sebagai urutan 1. Apabila semua job pada inputan tidak terdapat job yang memenuhi syarat maka proses job inputan urutan 1 dengan starting time = . Apabila terdapat lebih dari 1 job yang memenuhi syarat maka lihat apakah ini terjadi di mesin terakhir. Apabila terjadi di mesin terakhir maka pilih job dengan processing time terpendek untuk diproses terlebih dahulu. Apabila tidak terjadi di mesin terakhir (masih terdapat mesin selanjutnya) maka pilih job berdasarkan urutan paling awal untuk diproses terlebih dahulu.
CONT’D Lihat apakah terdapat job inputan urutan sebelumnya yang belum diproses. Apabila ada, maka kembali ke job tersebut. Apabila tidak maka lanjutkan untuk job selanjutnya. Bandingkan antara dan . Apabila lanjut ke langkah 9. Apabila lanjut ke langkah 10. Apabila maka lihat apakah . Apabila memenuhi syarat tersebut, proses job tersebut sebagai urutan selanjutnya dengan starting time = . Kemudian proses job inputan urutan selanjutnya dengan cara yang sama. Apabila maka cari job inputan urutan selanjutnya yang memenuhi syarat . Apabila semua job inputan yang tersisa tidak terdapat yang memenuhi syarat maka lihat apakah , apabila memenuhi maka pilih job inputan urutan paling awal. Bandingkan dengan . Apabila maka starting time = . Apabila maka starting time = Lakukan dengan cara yang sama untuk job-job urutan selanjutnya.
CONT’D Apabila maka lihat apakah . Apabila memenuhi syarat tersebut, proses job tersebut sebagai urutan selanjutnya dengan starting time = . Kemudian proses job inputan urutan selanjutnya dengan cara yang sama. Apabila maka cari job inputan urutan selanjutnya yang memenuhi syarat . Apabila semua job inputan yang tersisa tidak terdapat yang memenuhi syarat maka lihat apakah , apabila memenuhi maka pilih job inputan urutan paling awal dengan starting time = . Apabila maka pilih job inputan urutan paling awal dengan Lakukan dengan cara yang sama untuk job-job urutan selanjutnya. Apabila dalam kasus terdapat lebih dari 1 job yang sudah diselesaikan pada mesin j-1 sebelum job urutan sebelumnya (pada mesin j) diselesaikan maka lihat apakah ini terjadi di mesin terakhir (terdapat mesin selanjutnya atau tidak). Apabila terjadi di mesin terakhhir maka pilih job dengan processing time terkecil untuk diproses terlebih dahulu. Apabila tidak terjadi di mesin terakhir (terdapat mesin selanjutnya yang akan melakukan proses) maka pilih job berdasarkan urutan terkecil.
CONT’D Apabila semua job pada inputan sudah selesai diproses di mesin j, hitung completion time untuk masing-masing job. Lihat apakah terdapat mesin selanjutnya. Apabila masih terdapat mesin selanjutnya maka lanjut ke langkah 6. Apabila sudah tidak terdapat mesin selanjutnya maka lanjut ke langkah 13. Hitung nilai total tardiness dengan menggunakan persamaan
CONTOH NUMERIK Job 1 Pi,1 1 Pi,2 3 Pi,3 3 Pi,4 1 Pi,5 2 Pi,6 1 Pi,7 3 Pi,8 2 Pi,9 4 Pi,10 5 di 22
2 3 1 1 3 2 3 3 1 3 3 24
3 5 2 2 4 1 3 1 4 2 4 26
4 6 1 2 2 3 1 3 2 1 1 27
Data Processing time dan due date
5 4 3 3 1 2 2 2 3 4 2 28
INTERVAL KETIDAKTERSEDIAAN MESIN MESIN 1 (4,6) 3 MESIN MESIN 2 (5,7) MESIN 3 (3,5) MESIN 1 (4,6) MESIN 2 (5,7) 4 MESIN MESIN 3 (3,5) MESIN 4 (6,8) MESIN 1 (4,6) MESIN 2 (5,7) 5 MESIN MESIN 3 (3,5) MESIN 4 (6,8) MESIN 5 (8,10) MESIN 1 (4,6) MESIN 2 (5,7) MESIN 3 (3,5) 6 MESIN MESIN 4 (6,8) MESIN 5 (8,10) MESIN 6 (13,15) MESIN 1 (4,6) MESIN 2 (5,7) MESIN 3 (3,5) 7 MESIN MESIN 4 (6,8) MESIN 5 (8,10) MESIN 6 (13,15) MESIN 7 (19,21) MESIN 1 (4,6) MESIN 2 (5,7) MESIN 3 (3,5) MESIN 4 (6,8) 8 MESIN MESIN 5 (8,10) MESIN 6 (13,15) MESIN 7 (19,21) MESIN 8 (24,26) MESIN 1 (4,6) MESIN 2 (5,7) MESIN 3 (3,5) MESIN 4 (6,8) 9 MESIN MESIN 5 (8,10) MESIN 6 (13,15) MESIN 7 (19,21) MESIN 8 (24,26) MESIN 9 (17,19) MESIN 1 (4,6) MESIN 2 (5,7) MESIN 3 (3,5) MESIN 4 (6,8) MESIN 5 (8,10) 10 MESIN MESIN 6 (13,15) MESIN 7 (19,21) MESIN 8 (24,26) MESIN 9 (17,19) MESIN 10 (25,27)
Data Interval Ketidaktersediaan Mesin
ANALISIS PENGARUH JUMLAH MESIN TERHADAP SOLUSI ALGORITMA HEURISTIK
3 MESIN
4 MESIN
5 MESIN
6 MESIN
7 MESIN
8 MESIN
Interval Ketidaktersediaan Mesin Mesin 1 (4,6) Mesin 2 (5,7) Mesin 3 (3,5) Mesin 1 (4,6) Mesin 2 (5,7) Mesin 3 (3,5) Mesin 4 (6,8) Mesin 1 (4,6) Mesin 2 (5,7) Mesin 3 (3,5) Mesin 4 (6,8) Mesin 5 (8,10) Mesin 1 (4,6) Mesin 2 (5,7) Mesin 3 (3,5) Mesin 4 (6,8) Mesin 5 (8,10) Mesin 6 (13,15) Mesin 1 (4,6) Mesin 2 (5,7) Mesin 3 (3,5) Mesin 4 (6,8) Mesin 5 (8,10) Mesin 6 (13,15) Mesin 7 (19,21) Mesin 1 (4,6) Mesin 2 (5,7) Mesin 3 (3,5) Mesin 4 (6,8) Mesin 5 (8,10) Mesin 6 (13,15) Mesin 7 (19,21) Mesin 8 (24,26)
Enumerasi Urutan 1-2-5-3-4 1-2-5-3-4 2-1-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-5-2-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-5-2-3-4 1-2-5-3-4
Tardiness
36
40
31
42
34
53
Algoritma Heuristik Urutan 1-2-5-3-4 1-2-5-3-4 2-1-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-5-2-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4
Tardiness
Perbedaan (%)
36
0
40
0
31
0
SKENARIO
9 MESIN
10 MESIN
42
34
53
0
0
0
Interval Ketidaktersediaan Mesin Mesin 1 (4,6) Mesin 2 (5,7) Mesin 3 (3,5) Mesin 4 (6,8) Mesin 5 (8,10) Mesin 6 (13,15) Mesin 7 (19,21) Mesin 8 (24,26) Mesin 9 (17,19) Mesin 1 (4,6) Mesin 2 (5,7) Mesin 3 (3,5) Mesin 4 (6,8) Mesin 5 (8,10) Mesin 6 (13,15) Mesin 7 (19,21) Mesin 8 (24,26) Mesin 9 (17,19) Mesin 10 (25,27)
Enumerasi Urutan 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-5-2-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 2-1-5-3-4 2-1-5-3-4 2-1-5-3-4 1-2-5-3-4 1-5-2-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-4-3
Tardiness
43
57
Algoritma Heuristik Urutan 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4
Tardiness
Perbedaan (%)
43
0
60
0.052631579
Perbandingan Total Tardiness Berdasarkan Jumlah Mesin Total Tardiness
SKENARIO
80 60 40 20 0
Enumerasi Algoritma Heuristik
ANALISIS PENGARUH POSISI KETIDAKTERSEDIAAN MESIN TERHADAP TOTAL TARDINESS
Enumerasi Urutan Tardiness 1-2-5-3-4 36 1-2-5-3-4 2-1-5-3-4 1-3-2-5-4 39 1-3-2-5-4 1-3-2-5-4 1-2-5-3-4 32 1-2-5-3-4 2-1-5-3-4
Algoritma Heuristik Perbedaan (%) Urutan Tardiness 1-2-5-3-4 1-2-5-3-4 36 0 2-1-5-3-4 1-2-5-3-4 1-2-5-3-4 42 0.07692308 1-2-5-3-4 1-2-5-3-4 1-2-5-3-4 32 0 2-1-5-3-4
Perbandingan Total Tardiness Berdasarkan Posisi Ketidaktersediaan Mesin Total Tardiness
Interval Ketidaktersediaan Mesin 1 (4,6) Mesin 2 (5,7) Mesin 3 (3,5) Mesin 1 (11,13) Mesin 2 (11,13) Mesin 3 (11,13) Mesin 1 (19,21) Mesin 2 (11,13) Mesin 3 (4,6)
45 40 35 30 25 20 15 10 5 0
Enumerasi Algoritma
1
2
3
ANALISIS PENGARUH DUE DATE TERHADAP TOTAL TARDINESS SKENARIO Skenario 1 Skenario 2 Skenario 3 Skenario 4 Skenario 5
PENJELASAN Besarnya due date sebanding dengan besarnya processing time job di mesin 1 Besarnya due date sebanding dengan besarnya jumlah processing time job di semua mesin Besarnya due date berbanding terbalik dengan besarnya processing time job di mesin 1 Besarnya due date berbanding terbalik dengan jumlah processing time job di semua mesin Besarnya due date sama untuk semua job
HASIL Skenario
Enumerasi
Skenario 1 Skenario 2 Skenario 3 Skenario 4 Skenario 5
36 36 40 40 49
Perbandingan Hasil Algoritma Heuristik dan Enumerasi dengan Skenario Due Date 60 50 40 30 20 10 0 Skenario 1 Skenario 2 Skenario 3 Skenario 4 Skenario 5 Enumerasi
Algoritma Heuristik
Algoritma Perbedaan (%) Heuristik 0 36 0 36 0 40 0 40 0 49
ANALISIS PRIORITAS PENGURUTAN DALAM ALGORITMA HEURISTIK TERHADAP TOTAL TARDINESS Prioritas Pengurutan
SKENARIO
Enumerasi
3 MESIN 4 MESIN 5 MESIN 6 MESIN 7 MESIN 8 MESIN 9 MESIN 10 MESIN
36 40 31 42 34 53 43 57
SPT
EDD
36 40 31 42 34 53 43 60
39 43 34 45 36 54 44 59
Perbedaan (%) EDD dengan Enumerasi
EDD dengan SPT
0.083333333 0.083333333 0.075 0.075 0.096774194 0.096774194 0.071428571 0.071428571 0.058823529 0.058823529 0.018867925 0.018867925 0.023255814 0.023255814 0.035087719 -0.016666667
Prioritas Pengurutan SKENARIO
Enumerasi
3 MESIN 4 MESIN 5 MESIN 6 MESIN 7 MESIN 8 MESIN 9 MESIN 10 MESIN
36 40 31 42 34 53 43 57
Perbedaan (%)
Berbeda pada Berbeda pada II dengan II dengan I mesin terakhir (I) setiap mesin (II) Enumerasi 36 40 31 42 34 53 43 60
36 42 33 46 37 56 45 57
0 0.05 0.0645161 0.0952381 0.0882353 0.0566038 0.0465116 0
0 0.05 0.0645161 0.0952381 0.0882353 0.0566038 0.0465116 -0.05
Analisis Penerapan Algoritma Heuristik Untuk Permasalahan Penjadwalan Dua Mesin Flowshop Enumerasi Interval Skenario Ketidaktersediaan Mesin
Skenario Mesin 1 1 Mesin 2
Penelitian Terdahulu Model Eksak
Perbedaan (%)
Penelitian Saat ini
Algoritma heuristik Algoritma heuristik
Algoritma Algoritma dengan dengan Model Urutan Tardiness Urutan Tardiness Urutan Tardiness Urutan Tardiness Enumerasi Eksak
(0,4) 5-1-3-2-4 (0,4) 5-1-3-2-4
70
Skenario Mesin 1 (0,4) 5-1-4-3-2 2 Mesin 2 (16,20) 5-1-4-3-2
76
Skenario Mesin 1 (0,4) 5-1-3-4-2 3 Mesin 2 (27,31) 5-1-3-4-2
71
Skenario Mesin 1 (16,20) 5-3-4-1-2 4 Mesin 2 (0,4) 5-3-4-1-2
68
Skenario Mesin 1 (16,20) 5-1-4-3-2 5 Mesin 2 (16,20) 5-1-4-3-2
67
Skenario Mesin 1 (16,20) 5-3-2-1-4 6 Mesin 2 (27,31) 5-3-2-1-4
64
Skenario Mesin 1 (27,31) 5-1-3-2-4 7 Mesin 2 (0,4) 5-1-3-2-4
68
Skenario Mesin 1 (27,31) 5-1-4-2-3 8 Mesin 2 (16,20) 5-1-4-2-3
68
Skenario Mesin 1 (27,31) 5-1-3-2-4 9 Mesin 2 (27,31) 5-1-3-2-4
64
5-1-3-2-4 5-1-3-2-4 5-1-2-3-4 5-1-2-3-4 5-1-3-4-2 5-1-3-4-2 1-3-5-4-2 1-3-5-4-2
5-3-4-1-2 5-3-4-1-2 5-3-2-4-1 5-3-2-4-1 5-1-2-3-4 5-1-2-3-4 5-3-4-1-2 5-3-4-1-2 5-1-3-4-2 5-1-3-4-2
70 78 71 82
68 71 70 72 64
5-3-4-1-2 5-3-4-1-2 5-3-4-1-2 5-3-4-1-2 5-3-4-1-2 5-3-4-1-2 5-3-4-1-2 5-3-4-1-2
5-3-4-1-2 5-3-4-1-2 5-3-4-1-2 5-3-4-1-2 5-3-4-1-2 5-3-4-1-2 5-3-4-1-2 5-3-4-1-2 5-3-4-1-2 5-3-4-1-2
76 93 76 68
68 64 71 72 67
5-1-3-2-4 5-1-3-2-4 5-1-3-2-4 5-1-3-2-4 5-1-3-2-4 5-1-3-2-4 5-1-3-2-4 5-1-3-2-4
5-1-3-2-4 5-1-3-2-4 5-1-3-2-4 5-1-3-2-4 5-1-3-2-4 5-1-3-2-4 5-1-3-2-4 5-1-3-2-4 5-1-3-2-4 5-1-3-2-4
Algoritma dengan Algoritma terdahulu
70
0
0
-0.078947368
78
0.02631579
0
-0.161290323
83
0.16901408 0.169014085 0.092105263
74
0.08823529 -0.09756098 0.088235294
79
0.17910448 0.161764706 0.161764706
73
0.140625
68
0
80 64
0.028169014
0.140625
-0.02857143 -0.042253521
0.17647059 0.111111111 0.111111111 0
0
-0.044776119
KESIMPULAN Algoritma heuristik yang dibuat mampu menyelesaikan permasalahan penjadwalan m mesin flowshop dengan urutan job pada masing-masing mesin sama dan/atau berbeda dengan memperhatikan ketidaktersediaan mesin. Namun algoritma heuristik tidak selalu dapat memberikan solusi optimal terutama apabila diterapkan pada permasalahan dua mesin flowshop. Total tardiness yang dihasilkan algoritma heuristik masih sedikit lebih jelek apabila dibandingkan dengan metode enumerasi. Akan tetapi, dari waktu yang dibutuhkan untuk menyelesaikan permasalahan lebih baik daripada metode enumerasi. Pada permasalahan penjadwalan dua mesin, algoritma yang dihasilkan tidak menunjukkan hasil yang konsisten untuk menghasilkan tardiness minimum. Apabila dibandingkan dengan hasil penelitian Pitrasari (2009), tardiness yang dihasilkan masih lebih jelek daripada tardiness yang dihasilkan oleh Pitrasari (2009). Hasil analisis mengkonfirmasikan bahwa untuk urutan berbeda pada mesin terakhir menghasilkan tardiness minimal untuk jumlah mesin 3 sampai 9 mesin. Hal ini disebabkan karena pemilihan job yang menyebabkan terjadinya perbedaan urutan pada mesin terakhir tidak akan berpengaruh pada mesin-mesin yang lain.
SARAN Pengembangan dan perbaikan model matematis untuk permasalahan m mesin flowshop dengan memperhatikan ketidaktersediaan mesin dimana urutan job-job pada masing-masing mesin dapat sama atau berbeda. Pengembangan model matematis dan algoritma heuristik dimana posisi ketidaktersediaan mesin bersifat probabilistik.
