PENDEKATAN CROSS ENTROPY UNTUK MINIMASI BIKRITERIA MAKESPAN DAN TOTAL TARDINESS PADA PENJADWALAN PRODUKSI FLOWSHOP DENGAN MESIN PARALEL Sayid Basori dan Suparno Jurusan Teknik Industri Institut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email:
[email protected] ;
[email protected]
Abstrak Permasalahan penjadwalan produksi hampir ditemui disetiap perusahaan manufaktur, baik perusahaan yang menggunakan sistem produksi make to order, make to stock ataupun sistem yang lain. Penjadwalan produksi yang baik akan meningkatkan efisiensi dan performa perusahaan serta dapat meningkatkan pelayanan perusahaan kepada konsumennya, karena dengan penjadwalan produksi yang baik maka perusahaan dapat memenuhi order dari konsumen dengan tepat waktu, serta dapat mengurangi permasalahan inventory karena kelebihan ataupun kekurangan stock. Ada beberapa cara untuk mengoptimalkan penjadwalan produksi agar tidak terjadi banyak tardy job. Pada penelitian ini akan dikembangkan sebuah konsep pendekatan metaheuristik dengan menggunakan tools Cross Entropy untuk menyelesaikan permasalahan penjadwalan produksi yang menggunakan sistem flowshop dengan mesin paralel. Penggunaan pendekatan metode cross entropy ini digunakan untuk menyelesaikan multiobjective function yaitu minimize total tardinesss dan minimize makespan. Penelitian ini menggunakan software MATLAB untuk menyelesaikan model yang disusun. Model ini diaplikasikan untuk 3 sekenario permasalahan, permasalahan yang pertama memprioritaskan makespan untuk diminimasi, sekenario kedua memprioritaskan total tardiness untuk diminimasi dan sekenario yang ketiga menempatkan bobot yang sama untuk masing – masing fungsi tujuan. Dari hasil eksperimen didapatkan hasil perbaikan untuk total tardinesss dan makespan produksi, dari sekenario I didapatkan perbaikan masing – masing 8%, sedangkan untuk sekenario II didapatkan perbaikan 24 % untuk total tardiness dan 8% untuk makespan, sedangkan pada sekenario III didapatkan perbaikan sebesar 24% untuk total tardinesss dan 8% untuk makespan. Kata Kunci: penjadwalan produksi, cross entropy, flowshop, parallel machine, total tardiness, makespan
1. Pendahuluan Globalisasi pasar dan persaingan dunia manufaktur sudah memasuki babak baru. Selain persaingan dari segi harga dan kualitas keunggulan kompetitif perusahaan dalam memenuhi order tepat waktu menjadi perhatian utama perusahaan manufaktur akhir – akhir ini. Kecenderungan konsumen untuk memperoleh barang kebutuhan secepat mungkin menjadi voice of customer yang paling diperhatikan para penyedia produk – produk customer needs. Performansi dan daya saing perusahaan akan sangat dipengaruhi oleh ketepatan perusahaan dalam menyelesaikan order. Untuk bisa memenuhi order dengan tepat waktu maka perusahaan harus mempunyai perencanaan
penjadwalan produksi yang baik. Sehingga dalam hal ini permasalahan penjadwalan produksi menjadi hal yang sangat penting untuk diperhatikan. Kebijakan inventory spare part merupakan salah satu strategi perusahaan yang digunakakan untuk mempermudah proses produksi perusahaan. Kebijakan spare part harus menjadi perhatian di dalam perusahaan karena berpengaruh langsung terhadap sistem produksi yang dimiliki. Terdapat beberapa kemungkinan mengenai strategi perusahaan dalam pengadaan spare part antara lain kebijakan untuk melakukan pembelian ke luar (order) dan kebijakan memproduksi sendiri spare part yang dibutuhkan. Bagi perusahaan
yang sangat mementingka ketepatan waktu dan kontinuitas produksinya maka akan menetapkan kebijakan untuk memproduksi sendiri spare part yang dibutuhkan. Sehingga kerusakan mesin bisa segera diatasi tanpa menunggu order terlalu lama. Pada perusahaan dengan tipe seperti ini maka penjadwalan produksi dalam pengadaan spare part menjadi faktor penting yang mempengaruhi kelancaran proses produksi perusahaan. PT. Gudang Garam Tbk, merupakan perusahaan penghasil rokok yang memiliki strategi membuat spare part-nya sendiri. Mereka memproduksi berbagai macam spare part yang memenuhi semua kebutuhan perusahaan tiap harinya. Spare part ini diproduksi di Bengkel Umum Unit III. Job order yang diterima oleh bagian ini berasal dari semua bagian yang ada di dalam perusahaan, seperti dari bagian produksi rokok (mesin maupun tangan) serta bagian pengolahan bahan baku (tembakau, cengkeh, dll) . Di bengkel ini terdapat beberapa jenis mesin diantaranya mesin bubut, mesin frais, potong plat, mesin las, serta gerinda yang disusun secara paralel dengan masing-masing jenis mesin memiliki susunan jumlah yang berbeda pula, dengan tujuan untuk memproduksi order yang datang dengan jumlah dan spesifikasi yang bermacam-macam. Pada bagian ini sistem produksi yang dijalankan adalah berdasarkan pesanan (make to order) yang berasal dari dalam perusahaan sendiri, Sehingga tidak terdapat penalty maupun back order. Namun demikian proses pengerjaan order haruslah tetap berjalan baik, keterlambatan harus dapat diminimalkan. Karena dengan meminimalkan keterlambatan produksi maka penyediaan spare part pun akan tepat waktu sehingga proses perbaikan pada mesin-mesin produksi atau unit kerja tidak terjadi kendala. Jumlah pesanan yang datang pada bagian ini tiap waktunya sangat banyak baik variasi maupun jumlahnya sehingga diperlukan penjadwalan produksi yang mampu mengoptimalkan keterbatasan sumberdaya seperti mesin dan waktu. Sifat kebutuhan terhadap spare part di perusahaan adalah bersifat random dan berbanding lurus terhadap tingkat kerusakan mesin-mesin atau unit kerja yang dimiliki. Sehingga secara otomatis sistem produksi pada bagian pembuatan spare part ini
akan bersifat make to order yaitu akan berproduksi ketika ada kerusakan komponen mesin. Karena bersifat random maka order akan datang kapan pun sehingga disini dibutuhkan sistem penjadwalan secara optimal agar tingkat keterlambatan menjadi minimum, sebab jika terjadi keterlambatan maka hal yang mungkin terjadi adalah time to repaire mesin menjadi terhambat karena harus menunggu spare part terselesaikan dan sistem produksi tentunya akan terganggu. Selain itu dengan terlambatnya suatu order dimungkinkan akan mempengaruhi penjadwalan produksi order lainnya dan tentunya hal ini akan membuat performasi bagian ini menjadi tidak baik. Ada beberapa cara untuk mengoptimalkan penjadwalan produksi agar tidak terjadi banyak tardy job. Beberapa metode yang dapat digunakan untuk menyelesaikan permasalahan penjadwalan produksi antara lain metode integer programming, namun ada kelemahan dalam integer programming yaitu sulit diterapkan untuk permasalahan yang kompleks (NP-Hard Problem). Selain integer programming permasalahan ini dapat diselesaikan dengan pendekatan metaheuristik, dimana metode ini bisa digunakan untuk permasalahan yang sederhana maupun kompleks(NP-Hard Problem). Pada penelitian ini akan dikembangkan sebuah konsep pendekatan metaheuristic dengan menggunakan metode cross entropy untuk menyelesaikan permasalahan penjadwalan produksi yang menggunakan sistem make to order dengan mesin paralel. Penggunaan pendekatan metode cros entropy ini digunakan untuk menyelesaikan bicriteria objective function yaitu minimize total tardiness dan minimize makespan. 2. Metodologi Penelitian Pada bagian ini akan dijelaskan mengenai langkah-langkah yang digunakan dalam melakukan penelitian. Metodologi penelitian ini berguna sebagai acuan sehingga penelitian dapat berjalan secara sistematis, sesuai dengan framework penelitian. Secara umum terdapat tiga tahapan dalam metodologi penelitian kali ini yaitu tahap persiapan, tahap pengumpulan dan pengolahan data serta tahap pengambilan kesimpulan. Tahap persiapan ini bertujuan untuk mendapatkan permasalahan yang akan dibahas
dalam penelitian ini dan penentuan tujuan penelitian. Untuk dapat menghasilkan permasalahan dan tujuan yang cukup komprehensif maka dilakukan studi literatur dan studi lapangan mengenai permasalahan tersebut. Setelah tahap identifikasi dilakukan, maka tahapan selanjutnya adalah pengumpulan dan pengolahan data. Pada tahap ini dilakukan pengumpulan data Berupa pencarian data sekunder yang digunakan sebagai input model penelitian, data sekunder yang didapatkan yaitu berupa data – data job order yang terdiri dari jenis produk, spesifikasi produk, jumlah produk ready time dan due date, serta data mesin produksi yang meliputi jumlah blog mesin dan jumlah mesin tiap blok yang didapatkan dari data yang pernah diselesaikan dengan metode integer programming oleh peneliti sebelumnya. Kemudian dilakukan pembuatan model matematis dari permasalahan yang ada. Model yang dibuat adalah jenis model pemrograman integer dari jurnal yang sudah ada. Dari model matematis ini kemudian dikembangkan menjadi algoritma yang digunakan penyelesaian. Pada tahap ini akan dibuat algoritma pemrograman secara general dengan mengikuti diagram alir (flow chart) sesuai permasalahan yang ada. Adapun algoritma yang dikembangkan adalah algoritma CE (Cross Entropy) untuk menyelesaikan permasalahan tersebut. Dari algoritma ini kemudian diterjemahkan menjadi code bahasa pemrograman untuk software Matlab. Tahapan terakhir dari tahap pengumpulan dan pengolahan data adalah running code pada software untuk mendapatkan solusi dari permasalahan yang ada. Tahapan ini berupa penjalanan algoritma dengan menggunakan komputer dengan software matlab, dengan data input yang didapatkan dari pengumpulan data untuk mendapatkan jadwal optimal bagi masing-masing proses produksi, dengan diikuti penghitungan nilai total tardiness dan makespan minimal serta penghitungan objective function. Tahap terakhir dari penelitian ini yaitu tahap Analisis Hasil dan Pengambilan Kesimpulan. Pada tahap ini dilakukan evaluasi hasil yang ada serta pengambilan kesimpulan akhir dari hasil penelitian. Evaluasi delakukan dengan perbandingan hasil dengan kondisi existing, berupa pembandingan antara hasil total tardiness dan makespan minimal menggunakan
pendekatan algoritma cross entropy dengan hasil total tardiness dan makespan terbaik kondisi existingnya. Dan tahapan terakhir yaitu tahap penarikan kesimpulan. Tahap ini merupakan ringkasan dari seluruh aktivitas penelitian. Pada tahap ini juga ditambahkan saran – saran yang berguan untuk penelitian - penelitian sejenis selanjutnya. 3. Pengumpulan dan Pengolahan Data Tahap ini merupakan tahap penentuan set data yang akan diujikan terhadap algoritma Cross Entropy (CE), serta bagaimana pengujian model dilakukan dengan kerangka penelitian yang telah dibuat. 3.1 Pengumpulan Data
Pada tahap pengumpulan ini dilakukan pengumpulan data- data yang diperlukan dalam penelitian. Metode pengumpulan data dilakukan dengan cara pengumpulan data sekunder yaitu dari data yang sudah dikumpulkan oleh peneliti sebelumnya untuk dikembangkan pengolahan datanya dengan metode yang baru. Data-data yang dikumpulkan untuk penelitian ini diantaranya jumlah blok mesin dan jumlah mesin, data order pada bulan desember 2009, serta data waktu proses masing – masing order pada masing – masing blok mesin. Dari data – data tersebut kemudian di ubah menjadi data mesin, processing time, ready time, dan due date job dalam satuan jam dengan menggunakan jumlah jam kerja yang tersedia per hari untuk kemudian digunakan sebagai input program MATLAB. 3.2 Pemodelan Permasalahan Model untuk permasalahan Flowshop Paralel Machine Scheduling Problem (FPMSP) dapat dimodelkan dalam bentuk pemrograman integer seperti model yang diusulkan Sawik (2005), pada model tersebut dijelaskan permasalahan penjadwalan pada produksi make to order untuk meminimalkan total keterlambatan pada mesin paralel. Dan berikut merupakan
model yang dikembangkan oleh Sawik (2005): Indeks: g : order job, g ∈ G = {1,...,q} i : seksi (bagian) proses produksi, i ∈ I = {1,...,m} j : parallel mesin pada seksi ke-i, j ∈ Ji = {1,..., } t : periode perencanaan, t ∈ T = {1,...,h} Input Parameter: h : horizon perencanaan m : jumlah seksi (bagian) proses produksi : jumlah mesin yang tersusun parallel pada seksi i q : jumlah order job : periode kedatangan order g : ukuran portion terkecil dari order g yang harus diproses pada periode t : due date dari order g : jumlah order g : waktu proses order g pada seksi ke i : subset dari beberapa order yang harus diproses pada seksi (bagian) i : besarnya jam kerja pada stage i yang tersedia pada periode t : besarnya kapasitas mesin j pada stage i Variable Keputusan: ≥ 0 : jumlah lateness = 1 : jika order g dikerjakan pada periode t; jika tidak =0 : portion (bagian) dari order g yang diproses pada periode t : jika mesin j pada stage i ditugaskan pada periode t Fungsi tujuan untuk Meminimasi Total tardiness: Min T = ∑ ∈
Constrain: Constraint pembagian dan pengalokasian masing-masing job order diantara beberapa periode penjadwalan ∑ ∈ : = ; g ∈ G, + = + = … + = ≥ -1; g ∈ G, ∀ ∈ : ≤ ≤ ℎ ≥ -1 … ≥ -1 Constraint yang menjamin jika sebuah order pasti di proses pada sebuah periode perencanaan ≥ ; g ∈ G, t ∈ T : t > ≥ ≥
;
g ∈ G, t ∈ T : t >
≥ Constraint kapasitas mesin ∑ ∈ () ∑∈ ≤ ; i∈ I, t ∈ T ∑ ∈ () ∑∈ ≤ ; i ∈ I, t ∈ T ∑∈, ∈ ≤∑ ∈ : [ / ] ; i ∈ I, t ∈ T Constraint yang menunjukan keterlambatan order ≥ t - ; g ∈ G, ∀ ∈ : ≥ Constraint variable non-negative dan integrality ∈ {0,1}; g ∈ G, t ∈ T : t > ≥ 0; g ∈ G, t ∈ T : t > , ≥ 0; g ∈ G,
(21)
3.3 Pengembangan Model dan Algoritma
Dalam penelitian kali ini, permasalahan akan dikembangkan menjadi bicriteria yaitu dengan menambahkan fungsi tujuan minimize makespan, dengan rumus (Baker,1974): Indeks: C = Makespan Z = Objective function T = Total Tardiness Fungsi Tujuan Meminimasi Makespan ∑ Min C = max , [ ] Dengan constrain yang sama dengan yang dikemukakan oleh Sawik di atas. Sedangkan fungsi untuk meminimasi bicriteria total tardiness dan makespan seperti yang dikemukakan oleh Ruiz dan Alahverdy (2009), yaitu dengan membobotkan masing – masing fungsi tujuan menurut kepentingan yaitu sebagai berikut: Min Z = a*T + b*C Kemudian permasalahan ini akan diselesaikan dengan menggunakan metode Cross Entropy (CE). Secara umum alur algoritma CE yang digunakan sebagai metode penyelesaian permasalahan ini dapat dijelaskan sebagai berikut: 1. Pendefinisian output dan input Alur algoritma ini dimulai dengan menetapkan output yang ingin di dapatkan serta input yang diperlukan. Output: Nilai z Nilai Total tardiness Nilai Makespan Finishing time Jadwal optimal Input: Jumlah job (n) Matriks urutan job (Rij), job i dikerjakan pada mesin ke j Matriks waktu proses (Wij), waktu proses job ke i pada blok mesin ke j
Jumlah blok mesin (s) Jumlah mesin tiap blok Jumlah sampel pembangkitan (N) Parameter kejarangan (ρ) Koefisien penghalusan (α) Bobot fungsi objektif 1 (a) Bobot fungsi objektif 2 (b) Set data uji 2. Memasukkan nilai parameter awal dan stopping criteria Parameter-parameter yang dimasukkan (33) sebagai input, yakni N, ρ, α ditentukan sebagai tolok ukur performansi output yang dihasilkan. Dengan nilai parameter yang berbeda pastinya akan didapatkan hasil yang berbeda. Adapun aturan untuk pemberian parameter tersebut di atas adalah sebagai berikut: Untuk jumlah sampel pembangkitan N, tidak ada aturan khusus terkait dengan penentuan jumlah sampel pada optimasi kombinatorial, namun semakin besar jumlah job pastinya semakin besar sampel yang harusnya diambil. Pada algoritma digunakan jumlah sampel default 10000. Untuk parameter kejarangan ρ , biasanya digunakan nilai 1% - 10% (Kroese, 2009). Pada algoritma digunakan nilai default 1% Untuk koefisien penghalusan α , nilainya berada antara 0-1, namun secara empiris nilai 0,4 - 0,9 merupakan nilai yang paling optimal (de Boer, 2003). Pada algoritma digunakan nilai default 0,8. Untuk stopping kriteria adalah aturan yang digunakan untuk menghentikan iterasi ketika sudah mencapai kondisi tertentu, disini kan digunakan stopping kriteria dengan selisih antara hasil dengan iterasi sebelumnyaa adalah 0.005. 3. Pembangkitan sampel awal Sampel yang dibangkitkan di sini adalah merupakan urutan prioritas job yang terlebih dahulu dijadwalkan.
Pembangkitan sampel dilakukan dengan menggunakan teknik acak penuh (fully randomized). 4. Pengitungan Makespan Penghitungan makespan dilakukan dengan menghitung waktu terakhir mesin selesai mengerjakan semua job. 5. Pengitungan Total tardiness Penghitungan nilai total tardiness dilakukan dengan cara menjumlahkan semua keterlambatan dari setiap job. Yaitu nilai maksimal antara 0 dan completion time job tersebut dikurangi dengan due date dari job tersebut. Sehingga jika job selesai sebelum due date maka nilai tardiness adalah 0. 6. Penghitungan objective function Objective function dihitung dengan mengalikan a dengan Total tardiness dan b dengan nilai Makespan. 7. Mengurutkan hasil objective function Kemudian dari hasil objective function pada langkah 6 akan di urutkan mulai dari yang terkecil ke yang terbesar. 8. Tentukan sampel elit Sampel elite dipilih sebanyak ⌈ρ N⌉ dari jumlah sampel yang dibangkitkan berdasarkan nilai objective function-nya. 9. Smoothing parameter Kemudian dari sampel elite yang didapatkan maka di lakukan smoothing parameter dengan rumusan (18) = + (1 − ) 10. Cek stopping criteria Syarat pemberhentian pada penelitian ini adalah bahwa selisih antara parameter iterasi saat ini dan iterasi sebelumnya lebih kecil dari β . Jika syarat pemberhentian ini terpenuhi, maka hentikan iterasi dan lanjutkan ke langkah berikutnya. jika tidak memenuhi kembali ke langkah 3. 11. Penampilan hasil Langkah terakhir adalah menampilan hasil sesuai dengan output yang telah ditentukan di awal.
Secara umum algoritma di atas dapat digambarkan dalam flow chart algoritma seperti pada gambar 3.1 berikut ini
Gambar 3.1 Flowchart Algoritma CE 3.4 Aplikasi Algoritma pada permasalahan FPMSP Dalam pengujian Algoritma ini akan dibuat 3 skenario objective function yaitu untuk objective function yang memprioritaskan Makespan , memprioritaskan Total tardiness, dan seimbang. Ilustrasi dari 3 skenario tersebut seperti pada rumus di bawah ini:
Indeks: C = Makespan Z = Objective function T = Total Tardiness Rumus minimize bicriteria dengan memproiritaskan makespan: Min Z = 0.3*T + 0.7*C Rumus minimize bicriteria dengan memproiritaskan total tardiness: Min Z = 0.7*T + 0.3*C Rumus minimize bicriteria dengan bobot yang seimbang: Min Z = 0.5*T + 0.5*C Pengujian algoritma dilakukan dengan membuat kode program algoritma pada software Matlab (kode dilampirkan pada Lampiran 2). Langkah awal pengujian algoritma adalah dengan melakukan validasi algoritma yaitu dengan melakukan pengujian model sederhana dengan uji coba numerik (manual) dan di running dengan software. 3.5 Uji validasi Pada contoh ini, data yang di gunakan pada uji validasi berupa permasalahan penjadwalan produksi flow shop dengan mesin parallel, yang melibatkan 3 job, 2 blok mesin, blok mesin 1 terdiri dari 2 buah mesin, dan pada blok 2 terdiri dari 3 buah mesin Data waktu proses, ready time dan duedate diberikan seperti pada tabel 4.5 berikut:
makespan , total tardiness serta z minimum, untuk perhitungan kali ini di pakai a=0.3 dan b = 0.7. Penyelesaian dengan enumerasi Urutan proses penyelesaian permasalahan ini adalah sebagai berikut: Langkah 1 Generate kandidat solusi Pada tahap ini di generate semua kandidat solusi yang mungkin dari kombinasi job yang ada. Langkah 2 Jadwalkan pada mesin yang ada Dari kandidat solusi kemudian job dijadwalkan kedalam mesin yang tersedia dengan memperhatikan redy time dari job yang bersangkutan. Langkah 3 Hitung nilai makespan, total tardiness dan objective function. Setiap kandidat solusi di hitung nilai makespan, total tardiness dan objective functionnya Langkah 4 Pemilihan solusi terbaik dari kandidat solusi Pada tahapan ini dipilih dari kandidat solusi yang menghasilkan objective function paling kecil untuk dijadikan solusi terbaik. Permasalahan diatas dapat diselesaikan dengan metode pembuatan gantt chart dimulai dari generate kandidat solusi dengan kandidat solusi : 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1, kemudian dari kandidat solusi tersebut di plotting pada mesin yang tersedia seperti gantcahart. Contoh gantt chart untuk urutan 1-3-2 seperti berikut: Table 3.2 Gantt chart kandidat solusi 1-3-2
Table 3.1 Waktu proses, ready time dan due date contoh
Job M1 M2 Rt dd j1 2 5 1 8 j2 3 2 1 6 j3 4 8 1 13 Dari data di atas kemudian diselesaikan dengan metode enumerasi dan Cross Entropy untuk mendapatkan
Kemudian di hitung completion time, tardiness, total tardiness, makespan dan objective function-nya. Rekap hasil perhitungannya adalah sebagai berikut:
Table 3.3 Nilai total tardiness, makespan, dan objective function setiap kandidat solusi
Langkah 4 Penghitungan objective function Dari setiap urutan jadwal diatas di hitung z dengan rumus Z=a*T+b*C Maka di dapatkan nilai Z dari jadwal yang dibangkitkan seperti pada tabel 4.12 berikut: Tabel 3.5 Hasil objective function jadwal CE
Dari perhitungan diatas maka di pilih satu solusi terbaik dari kandidat solusi dengan z paling minimum yaitu z = 9.7 dengan jadwal optimum 1-3-2/3-1-2.
Metode Cross Entropy Dari problem di atas kemudian akan diselesaikan dengan metode cross entropy dengan langkah – langkah sebagai berikut: Langkah 1 Tahap inisialisai Pada tahap ini ditetapkan rho sebesar 0.01, alpha=0.8, toleransi 0.005, dengan sampel yang dibangkitkan sebanyak 1000. Langkah 2 tahap pembangkitan matriks transisi Pada tahap ini dibangkitkan matriks n x n dimana n adalah jumlah job dalam hal ini n = 3. Mekanisme pembangkitannya adalah dengan node placement sebagai berikut: Pij= Sehingga didapatkan matriks transisi sebagai berikut: P =
0.333 0.333 0.333 0.333 0.333 0.333 0.333 0.333 0.333 Langkah 3 Tahap pembangkitan N jadwal Pada tahap ini dibangkitkan jadwal sejumlah N sebagai sampel awal. Jadwal yang dibangkitkan pada tahap ini adalah sebagai berikut: Tabel 3.4 Hasil pembangkitan jadwal metode cross entropy
Jadwal 2-3-1 1-3-2 2-1-3 1-3-2 1-3-2 1-2-3 2-3-1 2-1-3 2-1-3 1-2-3
T 3 2 3 2 2 2 3 3 3 2
C 13 13 16 13 13 15 13 16 16 15
Z 10 9.7 12.1 9.7 9.7 11.1 10 12.1 12.1 11.1
Langkah 5 Pemilihan sampel elite Dari sampel yang dibangkitkan diatas kemudaian dipilih sampel elite setelah diurutkan menurut objective function, dengan rumus rho*N, pada tahap ini diambil sebanyak 6 sampel elit seperti tabel 4.15 berikut: Tabel 4.6 Sampel elit cross entropy jadwal 2 4 5 1 7 6 Z 9.7 9.7 9.7 10 10 11.1 Langkah 6 Update parameter Setelah didapatkan sampel elite maka akan di update parameter, parameter yang dimaksud disini yaitu matriks transisi. Parameter yang baru ini selanjutnya akan digunakan untuk membangkitkan sampel yang baru yang lebih baik. Langkah 7 Ulangi langkah 2 sampai langkah 6 Setelah didapatkan parameter baru maka ulangi langkah ke dua sampai langkah ke enam begitu seterusnya hingga tercapai stopping criteria. Stopping criteria adalah ketika matriks transisi pada transisi ini tidak
ada perubahan signifikan dari matrik transisi iterasi sebelumnya, atau selisih antara matriks saat ini dengan matriks pada iterasi sebelumnya mendekati 0. Setelah delakukan 7 tahap diatas hingga tercapai stopping criteria maka akan di dapatkan jadwal optimal seperti ditunjukkan pada gambar 4.3 berikut:
bobot makespan ditentukan 0.7 seperti rumus (35). Adapun hasil dari skenario pertama ini adalah total tardiness sebesar 57 jam, makespan 168 jam dan nilai z = 134,7. Dari pengujian ini didapatkan jadawal urutan job optimal seperti pada tabel 4.16 berikut: Tabel 3.7 Output matlab untuk jadwal optimal sekenario I
Dalam running kali ini juga ditunjukkan grafik dari solusi tiap iterasi yang ditunjukkan pada gambar 4.4 Gambar 3.2 Output software matlab untuk cross entropy
3.6 Pengujian Data Pada tahap ini dilakukan pengujian dari data yang sudah dikumpulkan dengan code yang sudah dibuat untuk kasus FPMSP. Pengujian ini digunakan pembangkitan sampel dengan node placement sesuai dengan ketentuan pada pembangkitan matriks transisi pada cross entropy untuk masalah penjadwalan produksi. Stopping criteria dari permasalahan ini ditentukan jika selesih antara matriks transisi pada iterasi sekarang dan sebelumnya melebihi batas toleransi yaitu 0.005. dalam pengujian kali ini ditentukan nilai N sampel sebesar 10000 sampel yang dibangkitkan, dengan parameter lain rho = 0.01 dan alpha sebesar 0.8. Input data untuk pengujian data pada software MATLAB menggunakan data pada tabel 4.4 3.6.1 Pengujian data untuk sekenario pertama Pada sekenario pertama digunakan fungsi dengan mengutamakan makespan dimana bobot untuk total tardiness 0.3 dan
Gambar 3.3 Output MATLAB grafik solusi tiap iterasi skenario 1
3.6.2 Pengujian data untuk sekenario Kedua Pada sekenario kedua digunakan fungsi dengan mengutamakan total tardiness dimana bobot total tardiness ditentukan 0.7 dan bobot untuk makespan 0.3 seperti rumus (36). Untuk parameter inisial sama dengan sekenario pertama. Adapun hasil dari sekenario kedua ini adalah Total tardiness sebesar 48 jam, makespan 168 jam dan nilai z = 84. Dari pengujian ini didapatkan jadawal urutan job optimal seperti pada tabel 4.17 berikut:
Tabel 3.8 Output MATLAB untuk jadwal optimal sekenario II
Dalam running kali ini juga ditunjukkan grafik dari solusi tiap iterasi yang ditunjukkan pada gambar 4.6
Dalam running kali ini juga ditunjukkan grafik dari solusi tiap iterasi yang ditunjukkan pada gambar 4.5
Gambar 3.5 Output MATLAB grafik solusi tiap iterasi skenario 3
Gambar 3.4 Output MATLAB grafik solusi tiap iterasi skenario 2
3.6.3 Pengujian Data Untuk Sekenario Ketiga Pada sekenario ketiga digunakan fungsi yang seimbang dimana bobot makespan ditentukan 0.5 dan bobot untuk total tardiness 0.5 seperti rumus 37. Untuk parameter inisial sama dengan sekenario pertama. Adapun hasil dari skenario ketiga ini adalah Total tardiness sebesar 48 jam, makespan 168 jam dan nilai z = 108. Dari pengujian ini didapatkan jadawal urutan job optimal seperti pada tabel 4.17 berikut: Tabel 3.9 Output matlab untuk jadwal optimal sekenario III
4. Analisis dan Pembahasan Pada bab ini akan dijelaskan mengenai analisa dan pembahasan dari hasil pengumpulan dan pengolahan data serta pengujian algoritma pada bab sebelumnya. Hasil analisa dan pembahasan ini akan digunakan sebagai dasar untuk membuat suatu kesimpulan dan saran untuk penelitian selanjutnya. 4.1 Analisis Hasil Uji Validasi Dari pengujian contoh numerik yang di selesaikan dengan cara manual pembuatan gantchart dan menggunakan metode cross entropy didapatkan hasil solusi yang sama antara hasil manual dan cross entropy. Hal ini disebabkan karena set data yang dipakai kecil sehingga mudah untuk menemukan solusi optimalnya (global optimal solution) nya. Selain itu dengan hasil uji yang sama menunjukkan bahwa problem FSPMSP dapat diselesaikan dengan metode cross entropy dan metode cross entropy yang dibuat valid. 4.2 Analisis Hasil Pengujian Data Pada analisis hasil pengujian data ini akan di analisis hasil uji masing masing sekenario dan di bandingkan hasil yang di dapat dari penelitian dengan kondisi existing perusahaan. Dari data yang diambil dari perusahaan untuk keseluruhan
job dihasilkan makespan 181 jam dan total tardiness 63 jam. 4.2.1
Analisis Hasil Uji Sekenario I Pada sekenario pertama ini dibuat sekenario pencarian jadwal optimal jika perusahaan lebih mementingkan atau menitik beratkan makespan untuk diminimasi. Dalam pengujian sekenario ini untuk makespan diberi bobot 70 % sedangkan total tardiness diberi bobot 30 %. Pada sekenario pertama didapatkan hasil
total tardiness sebesar 57 jam, makespan 168 jam dan nilai z = 134,7. Perbaikan yang dapat dilakukan pada hasil eksperimen dari kondisi eksisting perusahaan adalah sebesar 8 % dan untuk makespan perbaikannya adalah sebesar 8 %. 4.2.2
Analisis Hasil Uji Data Sekenario II Pada sekenario kedua ini dibuat sekenario pencarian jadwal optimal jika perusahaan lebih mementingkan atau menitik beratkan total tardiness untuk diminimasi. Dalam pengujian sekenario ini untuk makespan diberi bobot 30 % sedangkan total tardiness diberi bobot 70 %. Dari hasil percobaan didapat hasil untuk total tardiness sebesar 48 jam, makespan 168 jam dan nilai z = 84, perbaikan yang didapat dari sekenario kedua untuk total tardiness sebesar 24 % dan untuk makespan sebesar 8%.
4.2.3
Analisis Hasil Uji data Sekenario III Pada sekenario ketiga ini dibuat sekenario pencarian jadwal optimal jika perusahaan sama – sama menginginkan untuk meminimasi makespan dan total tardiness tanpa ada yang diprioritaskan untuk diminimasi. Dalam pengujian sekenario ini untuk makespan diberi bobot 50 % sedangkan total tardiness diberi bobot 50 %. Dari hasil percobaan didapat hasil untuk total tardiness sebeasar 48 makespan sebesar 168 dan z sebeasar 108, perbaikan yang didapat dari sekenario kedua untuk total tardiness sebesar 24% dan untuk makespan sebesar 8%.
4.3 Analisis Performansi Model Serta Perbandingan Aktual dan Model. Dari grafik yang ditunjukkan pada iterasi I,II dan III menunjukkan grafik yang cenderung
menurun, ini menunjukkan bahwa solusi dari metode cross entropy ini merupakan solusi yang semakin mengerucut, dari iterasi ke satu sampai iterasi ke n hasilnya akan selalu lebih baik atau minimal sama dengan hasil sebelumnya, sehingga metode ini dapat menemukan titik optimal lebih cepat. Inilah salah satu keunggulan metode cross entropy dibandingkan dengan metode – metode yang lain. Dari hasil eksperimen yang dilakukan terlihat perrformansi dari model lebih tinggi dibandingkan dengan kondisi eksisting, dengan kata lain model ini dapat meningkatkan performansi perusahaan jika diterapkan dalam pencarian jadwal optimal perusahaan. Jika dilihat dari nilai prosentase peningkatan performasi maka peningkatan performansi model dari kondisi aktual tidak terlalu besar tetapi sebenarnya peningkatan yang didapatkan cukup besar mengingat pada aktual diberlakukan jam lembur sedangkan pada model tidak memperhitungkan jam lembur, sehingga jam kerja yang ada di kondisi eksisting perusahaan lebih banyak dibanding dengan model. Dengan jam kerja yang lebih sedikit jadwal hasil eksperimen bisa menyelesaikan pekerjaan lebih cepat dengan total keterlambatan yang lebih sedikit dibandingkan aktual, maka performansi model jauh lebih baik dibandingkan dengan eksisting. Dari hasil ketiga metode dihasilkan makespan yang hampir sama tetapi untuk total tardiness berbeda – beda ini menunjukkan bahwa makespan maksimal dari problem ini yang mungkin untuk di capai adalah sebesar 168 jam. sehingga dari ketiga sekenario yang dibuat sekenario kedua yang memprioritaskan total tardiness merupakan solusi terbaik untuk permasalahan penjadwalan yang ada pada perusahaan ini. 5. Kesimpulan dan Saran Bab ini dipaparkan tentang kesimpulan yang dapat diambil selama proses penelitian yang telah dilakukan serta saran-saran yang diperlukan baik bagi perusahaan maupun penelitian selanjutnya. 5.1 Kesimpulan Berikut beberapa kesimpulan yang dapat diambil dari hasil penelitian:
1. Metode cross entropy dapat diaplikasikan untuk menyelesaikan permasalahan penjadwalan sistem produksi flowshop dengan mesin paralel. 2. Metode cross entropy menghasilkan jadwal dengan makespan dan total tardiness yang lebih kecil daripada kondisi eksisting
3. Perbaikan yang dapat dilakukan pada hasil eksperimen sekenario pertama dari kondisi eksisting perusahaan adalah sebesar 8 % untuk total tardiness dan untuk makespan perbaikannya adalah sebesar 8 %. 4. Perbaikan yang dapat dilakukan pada hasil eksperimen sekenario kedua dari kondisi eksisting perusahaan untuk total tardiness sebesar 24 % dan untuk makespan sebesar 8%. 5. Perbaikan yang dapat dilakukan pada hasil eksperimen sekenario ketiga dari kondisi eksisting perusahaan untuk total tardiness sebesar 24 % dan untuk makespan sebesar 8%. 6. Dari ketiga eksperimen menghasilkan hasil dan urutan penjadwalan yang berbeda – beda namun semuanya lebih baik dari kondisi eksisting. 5.2 Saran Berikut ini beberapa saran yang diberikan untuk masukan penelitian selanjutnya dengan topik atau bahasan yang sama 1. Penelitian ini masih berpotensi untuk dikembangkan dengan mengizinkan preemption dan memperhitungkan waktu lembur karyawan. 2. Melakukan hybrid metaheuristic untuk pembangkitan random sampel awal agar waktu komputasi lebih cepat. 6. Daftar Pustaka Baker, Kenneth R. 1974. "Introduction to Sequencing and Scheduling". USA: John Wiley&Sons, inc. Doerner, Karl F. dkk. 2007. "Metaheuristics Progress in Complex Systems Optimization". New York: Springer Science+Business Media, Inc.
Dreo, Johann dkk. 2005. "Metaheuristics for Hard Optimization : simulated annealing, tabu search, evolutionary and genetic algorithms, ant colonies,…". Heidelberg: Springer. Lathifi, Muhammad Fahmi. 2010.
“Pengembangan metode hibrid tabu search-cross entropy untuk penjadwalan flowshop”. Tugas Akhir. Jurusan Teknik Industri ITS. Surabaya. Glover, Fred, Gary A. Kochenberger. 2003. "Handbook Of Metaheuristics". New York: Kluwer Academic Publishers. Nasution, Arman Hakim. 1999. "Perencanaan dan Pengendalian Produksi". Jakarta: Guna Widya Rubinstein, Reuven Y. Dirk P Kroese. 2004. "The Cross-Entropy Method: a unified approach to combinatorial optimization, monte carlo simulation, and machine learning". New York: Springer Science+Business Media, Inc. Ruiz, Ruben & Allahverdi, Ali. 2009. “Minimizing the bicriteria of makespan and maximum tardiness with an upper bound on maximum tardiness”. Computers & Operations Research, Vol. 36, pp. 1268-1283.
Rera, Gladiez Florista. 2010. “Penerapan Metode Cross Entropy dalam Penyelesaian Capacitated Vehicle Routing Problem”. Tugas Akhir. Jurusan Teknik Industri ITS. Surabaya. Sawik,
T. 2005. “Integer Programming Approach to Production Scheduling for Make-To-Order Manufacturing”. Mathematical and Computer Modelling, Vol. 41, pp. 99-118 Venkataraman, P. 2002. "Applied Optimization with MATLAB Programming". New York: The Math Work, Inc.
