SEBUAH MODEL PEMROGRAMAN BILANGAN BULAT UNTUK PENYELESAIAN MASALAH PENJADWALAN SUMBER MAJEMUK PARALEL SIMULTAN Parwadi Moengin dan Felia Indah Kusuma Jurusan Teknik Industri, Universitas Trisakti
ABSTRACT Manufacturing company engaged in textile manufacturing in the Job Order system with an extensive network and market orientation requires more attention to the quality of products and services that meet customer requirements, one of them by way of the fulfillment of an order at the time agreed in advance. The problems are often found in the companies are delays in the completion of orders. This is due to less optimal job scheduling order by weight or penalty different on each job which will ultimately lead to the total weighted delay of the delay comes from the accumulation of a different job with the weights. This paper is intended to help companies create a new and more optimal scheduling in order to minimize the total weighted delay in the completion of order. The model used in this paper is an integer linear programming model for resourcescheduling problem for multiple simultaneous parallel job-compound and compound-operation. The initial steps of the use of this model is the formulation of the decision variables, and the objective function is minimizing total weighted tardiness or delay subject to the limiting functions. Software used in the processing of this data is WinQSB. At the end of the text is given a numerical example using the proposed model. Keywords: manufacturing, integer programming model 1. PENDAHULUAN1 Setiap perusahaan manufaktur yang bergerak dalam sistem job order dengan jaringan yang luas menyadari pentingnya pelayanan yang memenuhi persyaratan konsumen untuk memenangkan persaingan pasar, penjadwalan merupakan unsur penting didalam pemenuhan pesanan (order) tepat waktu. Penjadwalan yang baik dapat meminimasi keterlambatan dan resiko pinalty karena keterlambatan tersebut, memberikan kepuasan dan mempertahankan loyalitas konsumen, dan dapat membawa perusahaan pada keunggulan bersaing. Bagaimana mengatasi kurang optimalnya penjadwalan job-job dengan bobot yang berbeda pada masingmasing job yang dapat mengakibatkan keterlambatan tertimbang total yang besar untuk perusahaan. Keterlambatan ini akan memberi dampak kerugian berupa pinalty yang harus ditanggung oleh perusahaan.
Korespondensi : Parwadi Moengin E-mail :
[email protected]
Tujuan penelitian dalam tulisan ini adalah merancang sebuah model penjadwalan baru yang lebih optimal dengan menggunakan model pemrograman linier bilangan bulat untuk masalah penjadwalan sumber-majemuk paralel simultan untuk job-majemuk operasimajemuk dengan tujuan meminimalkan keterlambatan tertimbang total penyelesaian order.
2. USULAN MODEL PENJADWALAN SUMBER MAJEMUK PARALEL SIMULTAN Pengertian Model Model ini membahas masalah penjadwalan sumber majemuk paralel simultan (simultaneous parallel multiresource scheduling problem) (Kerzner, 1995). Paralel berarti bahwa jenis sumber yang sama digunakan untuk job yang berlainan pada waktu yang sama, pengerjaan tiap job memerlukan beberapa sumber secara bersamaan (simultan) dengan menggunakan model pemrograman linier bilangan bulat (Pinedo & Chao, 1999;
Model Pemrograman Bilangan Bulat (Parwadi Moengin)
91
Sipper & Bulfin, 1997). Istilah “sumber” digunakan untuk menggantikan istilah mesin yang banyak dijumpai dalam teori penjadwalan. Setiap sumber hanya dapat mengerjakan satu operasi pada suatu waktu dan preemption tidak diperbolehkan, yang artinya suatu operasi tidak dapat diinterupsi (Bodington, 1995). Fungsi Tujuan Tardiness Tertimbang Tardiness tertimbang (weighted tardiness) merupakan salah satu fungsi tujuan yang umum dalam masalah penjadwalan. Dalam masalah penjadwalan dengan fungsi tujuan tardiness tertimbang, tiap job memiliki due date dan bobot (kepentingan). Jika waktu akhir penyelesaian job melebihi due-datenya, job tersebut dikenakan suatu penalty yang direpresentasikan oleh bobotnya. Tardiness didefinisikan sebagai selisih waktu antara waktu akhir penyelesaian dengan due date jika waktu akhir penyelesaian lebih besar dari due date. Tardiness tertimbang total didefinisikan sebagai total dari seluruh keterlambatan dari job-job dengan bobot yang berbeda-beda (Suprayogi, dkk, 2002). Asumsi-asumsi Misalkan terdapat N job dan terdapat H jenis sumber. Tiap job i terdiri atas Ni operasi. Due date untuk setiap job dinyatakan dengan Di. Tiap operasi j untuk job i memerlukan waktu pengerjaan ti. Hij menyatakan himpunan sumber yang
digunakan untuk mengerjakan operasi j untuk job i. Horizon waktu didiskretisasi dalam K satuan waktu. Pada slot waktu k, tiap jenis sumber h (h H) mempunyai ketersediaan Mhk. Bobot (kepentingan) tiap job i dinyatakan dengan wi. Permasalahannya adalah menentukan jadwal pengerjaan masing-masing operasi untuk setiap job agar diperoleh keterlambatan tertimbang total yang minimum. Hubungan ketergantungan dari operasi untuk suatu job dianggap membentuk suatu directed acyclic graph, dan tiap job diasumsikan berakhir dengan satu operasi tunggal. Dengan demikian, waktu akhir penyelesaian tiap job Ci, sama dengan waktu akhir penyelesaian operasi terakhir pada job i tersebut, yaitu Ci = ciNi. Gambar 1 memperlihatkan suatu contoh rencana proses dari suatu job. Pengerjaan suatu operasi diasumsikan nonpreemtive (tanpa interupsi) sehingga suatu blok waktu dengan panjang tij dibutuhkan untuk pengerjaan operasi j job i. Lamanya waktu pengerjaan tiap operasi pada setiap sumber yang digunakan adalah sama. Untuk setiap jenis sumber, tiap unit dianggap identik. Semua job dianggap tersedia pada waktu k = 1. Horizon waktu K dianggap cukup panjang untuk menyelesaikan semua job, Ci K untuk semua i.
Operasi 1 Operasi 4 Operasi 2 Operasi 6
Operasi 3
Operasi 5
Gambar 1 : Contoh rencana proses suatu job Notasi Notasi-notasi yang digunakan di dalam perumusan model ini adalah : N Himpunan job. Ni Himpunan operasi pada job i. Pij Himpunan semua operasi lain yang mendahului operasi j pada job i.
92
Jurnal Teknik Industri, ISSN:1411-6340
H Hij
Himpunan jenis sumber. Himpunan jenis sumber yang digunakan mengerjakan operasi j untuk job i (HijH, Hij). Release time job i Panjang horizon waktu perencanaan. Konstanta yang menunjukkan ketersediaan sumber h pada slot waktu k (k = 1,…,K). Lamanya waktu pengerjaan operasi j untuk job i (tij>0). Tardiness dari setiap job. Earliness dari setiap job. Bobot (kepentingan) job i (wi>0). Due date job i (Di>0). Saat akhir pengerjaan job i, Ci = ciNi, dimana ciNi adalah waktu akhir penyelesaian operasi terakhir pada job i. Saat awal pengerjaan operasi j untuk job i. Saat akhir pengerjaan operasi j untuk job i. Saat awal pengerjaan operasi j untuk job i pada sumber h. Saat akhir pengerjaan operasi j untuk job i pada sumber h. Variabel biner 0-1; cijhk = 1 jika job i yang dikerjakan pada sumber h diselesaikan pada waktu k, cijhk = 0 sebaliknya. Variabel biner 0-1; xijhk = 1 jika operasi j untuk job i menggunakan sumber h pada slot waktu k, xijhk = 0 sebaliknya.
ri K Mhk tij L E wi Di Ci bij cij bijh cijh cijhk Xijhk
Perumusan Model Model pemrograman bilangan bulat horizon waktu diskret untuk masalah penjadwalan sumber-majemuk parallel simultan dengan fungsi tujuan meminimumkan tardiness tertimbang total adalah sebagai berikut :
Minimasi Z wi Li ……………… (1) i
dengan pembatas:
Ci Di ri Li Ei 0, i ………. (2)
Ci ciNi , i ………………………… (3) cij cim tij , i, j; j, m J i , m Pij … (4) cij t ij ri , i, j; j J i ……………. (5) cijh cij , i, j, h; j J i , h H ij ……… (6)
cijh kcijhk ,i, j, h; j J i , h H ij …(7) k
xijhk
c
ijhl k l k tij 1
,i, j, h; j J i , h H ij
…………………………………………..(8) cijhk 1,i, j, h; j J i , h H ij …... (9)
k
x i
jJ i
ijhk
M hk ,h, k ; h H ij ……..(10)
cijhk 0,1, h, k ; j J i , h H ij …….(11) bij cij tij 1, i, j; j J i ………... .(12)
bijh bij , i, j, h, j J i , h H ij ……. (13) Rumusan (1) merupakan fungsi tujuan yang meminimumkan tardiness tertimbang total. untuk fungsi tujuan minimasi tardiness tertimbang total, nilai E tidak diperhitungkan (dianggap 0). Pembatas (2) merupakan bentuk linerisasi dari fungsi tujuan tardiness. Pembatas (3) mendefinisikan bahwa waktu akhir penyelesaian setiap job adalah sama dengan waktu akhir penyelesaian operasi terakhir pada job tersebut. Pembatas (4) merupakan pembatas hubungan ketergantungan, yaitu waktu akhir suatu operasi harus lebih besar atau sama dengan waktu akhir penyelesaian semua operasi yang mendahului ditambah dengan lamanya waktu yang dibutuhkan untuk mengerjakan operasi tersebut. Pembatas (5) menjamin bahwa waktu akhir penyelesaian tiap job selalu lebih besar atau sama dengan waktu pengerjaannya. Pembatas (6) menentukan bahwa waktu penyelesaian untuk setiap operasi adalah sama dengan waktu penyelesaian operasi tersebut pada masing-masing sumber yang digunakan. Persamaan (7) menentukan waktu akhir penyelesaian setiap operasi pada masing-masing sumber. Dalam persamaan (7), karena cijhk sama dengan nol kecuali dalam saat waktu akhir
Model Pemrograman Bilangan Bulat (Parwadi Moengin)
93
penyelesaian, maka penjumlahan pada ruas kanan adalah sama dengan k* kali 1, dimana k* adalah waktu akhir penyelesaian. Persamaan (8) menjamin bahwa jika operasi tersebut diselesaikan pada waktu k, maka antara slot waktu k-ti+1 dan k pengerjaan operasi j pada job i menggunakan sumber h (hHij). Pembatas (9) menjamin bahwa tiap operasi j untuk job i pada setiap sumber h (hHi) hanya diselesaikan sekali sepanjang horizon waktu. Pembatas (10) merupakan pembatas ketersediaan sumber. Pembatas (11) merupakan pembatas biner bagi variable keputusan cijhk. Disini, walaupun variabel keputusan xijhk tidak dibatasi sebagai variable biner 0-1, nilai variable keputusan selalu nol atau satu berdasarkan hubungan antara persamaan (8) dan persamaan (11). Waktu awal pengerjaan setiap operasi ditentukan dengan menggunakan persamaan (12). Waktu awal pengerjaan setiap operasi pada masing-masing jenis sumber ditentukan dengan menggunakan persamaan (13). Waktu awal ini dapat ditentukan dengan menambahkan kedua
persamaan di atas langsung pada perumusan model di atas, atau dapat ditentukan setelah solusi optimal diperoleh. Cara kedua lebih menguntungkan karena akan mengurangi jumlah variabel keputusan dan pembatas yang dilibatkan.
3. CONTOH NUMERIK Berikut ini adalah contoh umerik untuk menerapkan model penjadwalan yang diusulkan. Data Umum Produksi yang diperlukan adalah: 1. Jenis proses manufaktur. 2. Proses produksi dan Peta Proses Operasi. 3. Waktu tiap operasi. 4. Data jenis dan jumlah mesin. 5. Data order job beserta tanggal pemesanan dan pengiriman. 6. Bobot tiap job. Pada penelitian ini, dikumpulkan data dari 2 job di minggu pertama (dalam slot waktu 7 hari).
Tabel 1. Rumusan hasil pengumpulan data No Job 1 Job 1
Kuantitas (pieces) 2750
Sumber
Operasi
Waktu tij Tgl Tgl Due date Bobot (hari) pesan kirim (Slot ke) 1 2 3 4 5 6
1 Weaving O 2 Dyeing
2 O O
3 Hemming
O O O
O O
Keterangan tabel : 1. Sumber adalah mesin-mesin digunakan untuk operasi Sumber 1 : Ms. Weaving
94
1 O
5 Packing
1 O
yang
2
1 O
4 Sewing
6
1 2
3 Hemming
2-Sep 6-Sep
2
1 Weaving O 2 Dyeing
1
1
5 Packing 1430
5
1
4 Sewing
2 Job 2
1-Sep 5-Sep
1 Sumber 2 : Ms. Celup Sumber 3 : Ms. Tumbler Sumber 4 : Ms. Long Hemming Sumber 5 : Ms. Cross Sewing
Jurnal Teknik Industri, ISSN:1411-6340
Sumber 6 : Ms. Packing 2. Lambang O pada tabel diatas menandakan pada job i dilakukan operasi j dengan menggunakan sumber h. 3. Kuantitas pesanan untuk Job 1 adalah 2500 pcs. Kebijakan perusahaan adalah memproduksi 10% lebih banyak dari kuantitas order untuk mengantisipasi cacat dan kerusakan lain yang mungkin terjadi dalam proses produksi, sehingga kuantitas yang dijadwalkan untuk diproduksi adalah (2500+10%*2500) = 2750 pcs. Demikian pula untuk Job 2 kuantitas yang dijadwalkan untuk diproduksi adalah (1300+10%*1300) = 1430 pcs. Benang
O-1 Weaving
Ms. Tenun
Air
O-2 Dyeing
Ms. Celup & Ms. Tumbler
Gunting
O-3 Hemming
Ms. Long Hemming
Benang&Aplikasi
O-4 Sewing
Ms. Cross Sewing
Polybag&Doos
O-5 Packing
Tahap pertama pengolahan data adalah pendefinisian masalah berdasarkan model pemrograman linier bilangan bulat untuk masalah penjadwalan dimulai dengan : 1. Perumusan notasi 2. Perumusan variabel keputusan L Tardiness tiap job Z Tardiness tertimbang total Ci Saat akhir pengerjaan job i, Ci = ciNi, dimana ciNi adalah waktu akhir penyelesaian operasi terakhir pada job i. bij Saat awal pengerjaan operasi j untuk job i. cij Saat akhir pengerjaan operasi j untuk job i. bijh Saat awal pengerjaan operasi j untuk job i pada sumber h. cijh Saat akhir pengerjaan operasi j untuk job i pada sumber h. cijhk Variabel biner 0-1; cijhk = 1 jika job i yang dikerjakan pada sumber h diselesaikan pada waktu k, cijhk = 0 sebaliknya. Xijhk Variabel biner 0-1; xijhk = 1 jika operasi j untuk job i menggunakan sumber h pada slot waktu k, xijhk = 0 sebaliknya. 3. Perumusan fungsi tujuan dan fungsifungsi pembatas.
Ms. Packing
Gambar 2 : Peta Proses Operasi
Tahap pengolahan data selanjutnya dilakukan dengan Software WinQSB dengan input data ke dalam software WinQSB sesuai dengan perumusan model yang telah dibuat. WinQSB akan menjalankan proses komputasi, mengolah data dan menghasilkan answer report. Result tersebut diterjemahkan ke dalam tabel hasil penjadwalan. Hasil Penjadwalan Hasil yang diperoleh diterjemahkan ke dalam tabel penjadwalan untuk 2 job, dimana masing-masing job terdiri dari 5 operasi majemuk dengan 6 sumber. Penjadwalan dilakukan di dalam slot waktu yang telah ditentukan yaitu 7 hari. Tabel penjadwalan tersebut dapat dilihat pada Tabel 2.
Model Pemrograman Bilangan Bulat (Parwadi Moengin)
95
Sumber
Job
Operasi
1
1
Tabel 2. Hasil Penjadwalan Baru Slot waktu (hari) 1
2
3
4
5
6
7
1
1
1
0
0
0
0
0
2
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
1
0
1
1
0
0
0
0
2
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
Sumber terpakai
1
2
1
0
0
0
0
Sumber tersedia
118
118
118
118
118
118
118
1
0
0
0
0
0
0
0
2
0
0
1
0
0
0
0
3
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
2
0
0
0
1
0
0
0
3
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
Sumber terpakai
0
0
1
1
0
0
0
Sumber tersedia
14
14
14
14
14
14
14
1
0
0
0
0
0
0
0
2
0
0
1
0
0
0
0
2
2
1
2
3
1
96
Jurnal Teknik Industri, ISSN:1411-6340
Sumber
Job
Tabel 2. Hasil Penjadwalan Baru (Lanjutan) Slot waktu (hari) Operasi 1 2 3 4 5
6
7
3
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
2
0
0
0
1
0
0
0
3
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
Sumber terpakai
0
0
1
1
0
0
0
Sumber tersedia
4
4
4
4
4
4
4
1
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
3
0
0
0
1
0
0
0
4
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
3
0
0
0
0
1
0
0
4
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
Sumber terpakai
0
0
0
1
1
0
0
Sumber tersedia
12
12
12
12
12
12
12
1
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
4
0
0
0
0
1
1
0
2
4
1
2
5
1
Model Pemrograman Bilangan Bulat (Parwadi Moengin)
97
Sumber
Job
Tabel 2. Hasil Penjadwalan Baru (Lanjutan) Slot waktu (hari) Operasi 1 2 3 4 5
6
7
5
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
4
0
0
0
0
0
1
0
5
0
0
0
0
0
0
0
Sumber terpakai
0
0
0
0
1
2
0
Sumber tersedia
120
120
120
120
120
120
120
1
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
5
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
5
0
0
0
0
0
0
1
Sumber terpakai
0
0
0
0
0
0
2
Sumber tersedia
6
6
6
6
6
6
6
2
6
1
2
Keterangan tabel : Xijhk adalah variabel biner 0-1; xijhk = 1 jika operasi j untuk job menggunakan sumber h pada slot waktu k, xijhk = 0 sebaliknya.
4. ANALISIS HASIL Perbandingan penjadwalan lama dengan penjadwalan baru
98
Jurnal Teknik Industri, ISSN:1411-6340
Tabel 3 Penjadwalan lama (diperoleh melalui pengumpulan data) Slot waktu 1
2
3
4
5
6
7
8
9
Job 1 Job 2
Dari dua job ini dihitung keterlambatan tertimbang total sebesar Z = 1.L1 + 2.L2. L1 adalah keterlambatan untuk job 1 yang diperoleh dari completion time dikurangi due date yaitu 4 hari sedangkan L2 adalah keterlambatan untuk job 2 yang diperoleh dari completion time dikurangi due date yaitu 2 hari.
Berdasarkan bobot yang telah disepakati sebelumnya berdasarkan pinalty yang akan dikenakan kepada perusahaan (bobot untuk job 1 adalah 1 dan bobot untuk job 2 adalah 2), keterlambatan tertimbang total untuk kedua job tersebut menjadi :1*4 hari + 2*2hari = 8 hari.
Tabel 4 Penjadwalan baru (merupakan bentuk penyederhanaan dari tabel 2) Slot waktu 1
2
3
4
5
6
7
8
9
Job 1 Job 2
Dari dua job ini dihitung keterlambatan tertimbang total sebesar Z = 1.L1 + 2.L2. L1 adalah keterlambatan untuk job 1 yang diperoleh dari completion time dikurangi due date yaitu 2 hari sedangkan L2 adalah keterlambatan untuk job 2 yang diperoleh dari completion time dikurangi due date yaitu 1 hari. Dengan bobot untuk job 1 adalah 1 dan bobot untuk job 2 adalah 2, keterlambatan tertimbang total untuk kedua job adalah :1*2 hari + 2*1hari = 4 hari. Analisa kelebihan dan kekurangan model Model pemrograman linier bilangan bulat untuk masalah penjadwalan ini cukup akurat dan cukup lengkap dalam memperhitungkan variabel-variabel yang terkait dalam penjadwalan dan memberikan solusi penjadwalan yang lebih optimal sesuai dengan tujuannya untuk meminimumkan keterlambatan tertimbang total. Dari hasil penjadwalan dengan menggunakan model ini, dapat diketahui
secara langsung data-data variabelnya seperti : Saat awal dan saat akhir pengerjaan setiap job dan setiap operasi pada setiap sumber yang ada. Beginning time dan completion time untuk setiap job secara keseluruhan. Ketersediaan sumber pada setiap slot waktu. Untuk banyak model penjadwalan, algoritma eksakta yang diketahui adalah algoritma yang didasarkan pada enumerasi (menyebutkan satu per satu). Pada kenyataan sesungguhnya, kombinasi yang natural dari masalah penjadwalan menyebabkan proses pemodelan dan proses komputasi yang sulit. Inilah letak kekurangan dari model pemrograman linier bilangan bulat untuk masalah penjadwalan ini. Model ini sulit diterapkan untuk kasus penjadwalan yang besar dengan horizon waktu yang panjang dikarenakan penambahan variabel pada job, operasi, sumber, maupun slot waktu akan menyebabkan bertambah banyaknya variabel dan pembatas secara eksponensial.
Model Pemrograman Bilangan Bulat (Parwadi Moengin)
99
Hal ini berkaitan erat dengan rumitnya proses perumusan masalah berdasarkan model dan keterbatasan kapasitas dari software dan waktu komputasi yang relatif lama untuk memproses data dalam ukuran besar.
5. KESIMPULAN Perancangan penjadwalan baru dengan menggunakan model pemrograman linier bilangan bulat untuk masalah penjadwalan sumber-majemuk paralel simultan untuk job-majemuk operasi-majemuk untuk studi kasus tersebut dapat meminimalkan keterlambatan tertimbang total penyelesaian order dibandingkan dengan penjadwalan yang lama dari 8 hari menjadi 4 hari.
100
6. DAFTAR PUSTAKA [1] Bodington, C. Edward. (1995). Planning, Scheduling, and Control Integration In The Process Industries. McGraw-Hill, Inc USA. [2] Kerzner, Harold. (1995). Project Management : A System Approach to Planning, Scheduling, and Controlling. International Thompson Publishing Inc. New York. USA. [3] Pinedo, Michael., Xiuli Chao. (1999). Operations Scheduling : With Aplications in Manufacturing and Services. McGraw-Hill Inc. Singapore. [4] Sipper, Daniel., Robert L. Bulfin Jr. (1997). Production Planning, Control, and Integration. McGraw-Hill Inc. USA. [5] Suprayogi., Isa Setiasyah Toha. (2002). Jurnal TMI 22 : Model Pemrograman Linier Bilangan Bulat Untuk Masalah Penjadwalan Sumber-Majemuk Paralel Simultan. ITB. Bandung.
Jurnal Teknik Industri, ISSN:1411-6340
