MODEL PENJADWALAN BATCH PADA JOB SHOP DENGAN KELOMPOK MESIN HETEROGEN UNTUK MEMINIMASI TOTAL WAKTU TINGGAL AKTUAL
Draft Tesis Karya tulis sebagai salah satu syarat Untuk memperoleh gelar Magister dari Institut Teknologi Bandung
Oleh Fedo Rizviyatmaja Sarian 23405003
Program Studi Teknik dan Manajemen Industri Institut Teknologi Bandung 2008
Pedoman Penggunaan Tesis
Tesis S2 yang tidak dipublikasikan terdaftar dan tersedia di perpustakaan Institut Teknologi Bandung dan terbuka untuk umum dengan ketentuan bahwa hak cipta ada pada pengarang dengan mengikuti aturan HaKI yang berlaku di Institut Teknologi Bandung. Referensi kepustakaan diperkenan dicatat, tetapi pengutipan atau peringkasan hanya dapat dilakukan sezin pengarang dan harus disertai dengn kebiasaan ilmiah untuk menyebutkan sumbernya. Memperbanyak atau menerbitkan sebagai atau seluruh tesis haruslah seizin Direktur Program Pasca Sarjana, Institut Teknologi Bandung.
iv
Abstrak Model Penjadwalan Batch pada Job Shop dengan Kelompok Mesin Heterogen untuk Meminimasi Waktu Tinggal Aktual Oleh Fedo Rizviyatmaja Sarian 23405003 Penelitian ini mengembangkan model penjadwalan batch yang diproses pada job shop dengan kelompok mesin heterogen. Sejumlah mesin dinyatakan heterogen jika mesinmesin tersebut memiliki kemampuan untuk menghasilkan output yang sama tetapi paling tidak satu mesin diantaranya memiliki karakteristik operasi, waktu setup atau waktu proses, yang berbeda dari karakteristik operasi mesin- mesin yang lain.
Kriteria untuk model penjadwalan yang dikembangkan adalah minimasi total waktu tinggal aktual yang mempertimbangkan due date di dalamnya. Variabel keputusan dalam penelitian ini adalah jumlah dan ukuran batch serta urutan pemrosesan batch yang dihasilkan. Untuk memperoleh solusi model, diusulkan 2 buah algoritma yaitu Algoritma Penjadwalan Batch Optimal dan Algoritma Penjadwalan Batch Sub-Optimal.
Hasil pengujian memperlihatkan bahwa model mampu menyelesaikan pemasalahan penjadwalan batch dengan kelompok mesin heterogen. Berdasarkan hasil yang diperoleh terlihat bahwa batch dengan jenis part yang sama tidak harus dijadwalkan secara berurutan dan ukuran batch yang dihasilkan tidak harus sama.
Kata kunci: penjadwalan batch, job shop, kelompok mesin heterogen, total waktu tinggal aktual
v
Abstract Batch Scheduling Model in Job Shop with Heterogeneous Group Machine to Minimizing Actual Flow Time By Fedo Rizviyatmaja Sarian 23405003 This Research develop batch scheduling model in Job Shop with heterogeneous group machine. A group of machine called heterogeneous if machines can produce same output, but at least one machine have different specification, like: operation, setup time or processing time.
The criteria for developed batch scheduling model is minimizing total actual flow time, which defined as the time the job spent in shop from the starting time of the processing until due date. Decision variables in this research are total batch, size batch, and batch sequence. There are 2 Algorithm that suggested getting the solution of model, Optimal Batch Scheduling Algorithm and Sub-Optimal Batch Scheduling Algorithm.
The output of experiment indicates that model can resolve batch scheduling problem with heterogeneous group machine. From the output show that batch with same part not always scheduled in succession and the size of batch not always equal.
Keyword: batch scheduling, job shop, heterogeneous group machine, total actual flow time.
vi
Daftar Isi Lembar Pengesahan .............................................................................................
ii
Lembar Persembahan ...........................................................................................
iii
Pedoman Penggunaan Tesis .................................................................................
iv
Abstrak .................................................................................................................
v
Abstract ................................................................................................................
vi
Kata Pengantar .....................................................................................................
vii
Daftar isi ...............................................................................................................
viii
Daftar Gambar ......................................................................................................
x
Daftar Tabel .......................................................................................................... xi Daftar Simbol dan Notasi ...................................................................................... xii Bab I. Pendahuluan ................................................................................................ 1 1.1 Latar Belakang ..................................................................................... 1 1.2 Perumusan Masalah ............................................................................... 3 1.3 Tujuan Penelitian ................................................................................. 3 1.4 Batasan Masalah .................................................................................. 3 1.5 Asumsi ................................................................................................. 3 1.6 Sistematika Penulisan .......................................................................... 4 Bab II. Tinjauan Pustaka ....................................................................................... 6 2.1 Penjadwalan ........................................................................................ 6 2.2 Penjadwalan Job Shop ........................................................................ 7 2.2.1 Definisi ................................................................................. 7 2.2.2 Model Analitik untuk Penjadwalan Job Shop ...................... 8 2.2.3 Jadwal Semi Aktif, Aktif, Non Delay dan Optimal ………. 9 2.3 Penjadwalan dengan Pendekatan Mundur …………………………... 11 2.4 Waktu Tinggal Aktual ………………………………………………. 11 2.5 Teorema-teorema dalam Penjadwalan Batch ………………………… 13 Bab III. Metodologi Penelitian …………………………………………………… 15 3.1 Metodologi Peneltian …………………………………………………. 15 3.1.1 Studi Literatur ………...…………………………………….. 15 viii
3.1.2 Perumusan Masalah dan Tujuan Penelitian ........................... 15 3.1.3 Pengembangan Model ……………………………………… 15 3.1.4 Pengujian dan Analisis ……………………………………... 17 3.1.5 Penarikan Kesimpulan dan Saran …………………………... 17 3.2 Pengembangan Model …………………………………………………17 3.2.1 Deskripsi Permasalahan ……………………………………. 17 3.2.2 Kriteria Kinerja dan Variabel Keputusan ………………….. 19 3.2.3 Parameter dan Variabel Keputusan ....................................... 19 3.2.4 Formulasi Model .................................................................... 20 3.3 Pencarian Solusi Model ......................................................................... 22 3.3.1 Contoh Perhitungan ................................................................ 26 3.4 Pengembangan Algoritma Penjadwalan Batch Semi Optimal ............... 27 Bab IV Pengujian dan Analisis Model ................................................................... 30 4.1 Pengujian Model …………………………………………………….. 30 4.2 Hasil Pengujian Model ……………..………………………………… 30 4.2.1
Algoritma Penjadwalan Optimal ………………………… 30
4.2.2
Algoritma Penjadwalan Batch Semi Optimal ……………. 33
4.3 Perbandingan Kinerja Algoritma Penjadwalan Batch Optimal dan Algoritma Penjadwalan Batch Sub-Optimal ……………………. 34 4.3.1
Perbandingan Kinerja Menggunakan Data Contoh Perhitungan ………………………………........... 34
4.3.2
Perbandingan Kinerja Menggunakan Data 16 Kasus ………………………….………………………. 36
Bab V Kesimpulan dan Saran …………………………………………………… 47 5.1 Kesimpulan ………………………………………………………….. 47 5.2 Saran ………………………………………………………………… 49 Daftar Pustaka …………………………………………………………………… 50
ix
Daftar Gambar
Gambar 2.1 Pendekatan dalam Penyusunan Jadwal ............................................... 12 Gambar 3.1 Tahapan-tahapan Penelitian ................................................................ 18 Gambar 3.2 Gannt Chart Jadwal Akhir untuk N = 3 ..........……………………… 29 Gambar 4.1 Gannt Chart Jadwal terbaik Algoritma Penjadwalan Batch Optimal ………………………………………... 32 Gambar 4.2 Gannt Chart Jadwal terbaik Algoritma Penjadwalan Batch Sub-Optimal …………………………………... 35
x
Daftar Tabel
Tabel 3.1 Posisi Penelitian ……………………………………………………….. 16 Tabel 3.2 Data Routing ..............................……………………………….............. 26 Tabel 3.3 Data Waktu Proses ……………………………………………….......... 27 Tabel 4.1 Data Routing ......................................................................................…. 30 Tabel 4.2 Data Waktu Proses ………………………………………………...…. 30 Tabel 4.3 Nilai Actual Flow Time menggunakan Algoritma Penjadwalan Optimal ................................................................31 Tabel 4.4 Computational Time pada Sub Algoritma Penjadwalan Batch pada Job Shop dengan Mesin Heterogen …….……………………………. 33 Tabel 4.5 Banyaknya Alternatif Nilai Q dan Jadwal ……………………………... 33 Tabel 4.6 Perubahan-Perubahan Parameter ............................................................. 37 Tabel 4.7 Waktu Proses Kasus 1…………...……………………………………… 37 Tabel 4.8 Waktu Proses Kasus 2…………...……………………………………… 38 Tabel 4.9 Waktu Proses Kasus 3…………...……………………………………… 38 Tabel 4.10 Waktu Proses Kasus 4………...……………………………………… 39 Tabel 4.11 Waktu Proses Kasus 5……….....……………………………………… 39 Tabel 4.12 Waktu Proses Kasus 6…………....…………………………………… 40 Tabel 4.13 Waktu Proses Kasus 7…………...…………………………………… 40 Tabel 4.14 Waktu Proses Kasus 8………...……………………………………… 40 Tabel 4.15 Waktu Proses Kasus 9………...……………………………………… 41 Tabel 4.16 Waktu Proses Kasus 10………...……………………………………… 41 Tabel 4.17 Waktu Proses Kasus 11………...……………………………………… 42 Tabel 4.18 Waktu Proses Kasus 12………...……………………………………… 42 Tabel 4.19 Waktu Proses Kasus 13………...……………………………………… 43 Tabel 4.20 Waktu Proses Kasus 14………...……………………………………… 43 Tabel 4.21 Waktu Proses Kasus 15………...……………………………………… 44 Tabel 4.22 Waktu Proses Kasus 16………...……………………………………… 44 Tabel 4.23 Hasil Pengujian 16 Kasus ....................................................................... 45 Tabel 4.24 Computational Time dengan Data 16 Kasus .......................................... 46
xi
Daftar Simbol dan Notasi
Bijkm[u ] : waktu mulai part i operasi j dimesin m dari stasiun kerja k batch urutan ke-u
d
: batas waktu penyerahan semua part (common due date)
i dan g : indeks jenis part dari 1 sampai I j
: indeks urutan proses dari 1 sampai Ji atau Jg
k dan h : indeks stasiun kerja dari 1 sampai K m dan l : indeks mesin dari suatu stasiun kerja dari 1 sampai Mk atau Mh N
: jumlah batch
ni
: jumlah permintaan part i
Q i[ u ]
: ukuran batch part i yang diproses pada urutan ke-u
ri[ u]
: variabel biner pemilihan part i pada batch urutan ke-u
s
: waktu setup
t ijkm
: waktu proses part i operasi j dimesin m stasiun kerja k
TFa
: total waktu tinggal aktual
u dan v : indeks urutan batch dari 1 sampai N X jkm[u ] : variabel biner pemilihan mesin m dari stasiun kerja k operasi j batch urutan ke-u
Zkm
: nilai saat selesai suatu batch bila pada stasiun kerja dan mesin yang sama terdapat batch lain yang dijadwalkan
xii
