PENGEMBANGAN MODEL PENJADWALAN MENGGUNAKAN TEKNIK SISIPAN (INSERTION TECHNIQUE) IR. DINI WAHYUNI, MT. Fakultas Teknik Jurusan Teknik Industri Universitas Sumatera Utara 1. Latar Belakang Kecenderungan pasar sekarang ini seperti beragamnya kebutuhan konsumen, siklus hidup produk yang makin pendek, serta tekanan kompetitif untuk mengurangi ongkos, telah mengakibatkan perlunya sistem tanpa persediaan (zero inventory). Hal ini dilakukan antara lain dengan meminimasi lamanya order berada di lantai pabrik. Tetapi, di pihak lain, untuk mempertahankan atau meningkatkan pangsa pasar, sistem harus merespon permintaan dengan cepat. Hal ini mengakibatkan perlunya persediaan. Sementara itu, persaingan yang semakin ketat dalam dalam dunia bisnis mendorong pihak produsen untuk membuat produk yang sesuai dengan keinginan konsumen (customized), mempunyai tingkat kualitas yang tinggi, harga yang murah dan pengiriman yang tepat waktu. Situasi customized production biasanya berkaitan dengan sistem produksi job shop dan memiliki karakteristik dinamik dan tidak pasti, yang seringkali menimbulkan tindakan penjadwalan ulang (rescheduling). Menurut Halim (1993) dalam Barnali (1996), pada kondisi praktis ketepatan penyelesaian order cenderung dianggap lebih penting dari pada minimasi lamanya order berada di lantai pabrik. Alasannya adalah pemenuhan due date secara konsisten akan menjaga kesetiaan pelanggan, yang merupakan kunci sukses dalam bisnis di pasar global dengan tingkat persaingan tinggi. Salah satu solusi atas konflik ini adalah penjadwalan yang efisien (Jain dan Meeran, 1999). Baker (1974) mendefinisikan penjadwalan sebagai proses pengalokasian sumber-sumber yang ada untuk menjalankan sekumpulan tugas dalam jangka waktu tertentu. Penjadwalan merupakan kegiatan yang penting dalam perencanaan dan pengendalian produksi, karena jadwal yang baik akan memaksimumkan efektivitas pemanfaatan setiap sumber daya yang ada. Tetapi, masalah penjadwalan sesungguhnya merupakan masalah yang sangat kompleks, baik dalam tahap perencanaan maupun dalam tahap implementasi, terutama pada saat muncul gangguan pada jadwal tersebut. Gangguan pada jadwal akan mengakibatkan tindakan penjadwalan ulang, dan penjadwalan ulang bisa berdampak luas bagi aktivitas operasional di lantai produksi. Dengan demikian, penjadwalan ulang yang seharusnya dilakukan adalah penjadwalan ulang yang memberikan dampak minimum pada aktivitas di lantai produksi. Teknik Sisipan merupakan suatu teknik penjadwalan yang tidak melakukan perubahan pada seluruh jadwal, tetapi hanya melakukan penyisipan pada jadwal parsial yang telah ada. Nawaz et al. (1983) mengusulkan algoritma sisipan untuk melakukan penjadwalan job pada permutasi flow shop, yaitu job secara berurutan disisipkan pada jadwal parsial. Brasel et al. (1993) menggabung Teknik Sisipan dengan beam search pada masalah open shop. Hasil komputasi menunjukkan untuk jumlah job dan mesin yang besar, kualitas solusi dengan Teknik Sisipan sangat baik. Sementara itu Werner et al. (1995) menggunakan Teknik Sisipan yang digabungkan dengan beam search untuk masalah job shop tanpa setup time. Sedangkan Sotskov et al. (1999) menerapkan Teknik Sisipan pada masalah job shop dengan setup time. Tampak bahwa diantara penelitian penjadwalan dengan Teknik Sisipan di atas, penelitian Sotskov et al. (1999) merupakan penelitian yang paling mendekati masalah penjadwalan pada situasi pasar saat ini. 2002 digitized by USU digital library
1
Sotskov et al. (1999) menggunakan dua jenis kriteria dalam menilai jadwal yang dihasilkan, yaitu: • Kriteria reguler, menggunakan pendekatan maju, dengan tujuan minimasasi makespan dan minimisasi ∑wiCi, dengan wi adalah bobot job i dan Ci adalah saat selesai job i. • Kriteria non reguler, menggunakan pendekatan mundur, dengan tujuan minimisasi ongkos penalti, yaitu minimisasi ∑wi(Ci-di)2, dengan di = due date job i. Sotskov et al. (1999) pada kriteria non reguler sudah memasukkan pertimbangan due date dalam melakukan penjadwalan dan menggunakan pendekatan mundur, tetapi terlihat bahwa bila jadwal tidak fisibel (saat datang terlanggar) maka jadwal pengerjaan job digeser ke kanan (right shift), sehingga mengakibatkan due date terlanggar. Berdasarkan hal tersebut tampak diperlukan penelitian dengan Teknik Sisipan yang berbasis pada penelitian Sotskov et al. (1999) untuk mengakomodasikan kasus yang tidak mengizinkan job terlambat (no tardy jobs). 2. Rumusan Masalah Penelitian ini membahas masalah penjadwalan dengan Teknik Sisipan pada sistem produksi job shop dengan setup time yang mensyaratkan job tidak boleh terlambat. Dasar pengembangan model yang digunakan dalam penelitian ini adalah penelitian Sotskov et al. (1999) yang telah menggunakan Teknik Sisipan pada job shop dengan setup time dan mengizinkan job terlambat. Kriteria yang digunakan oleh Sotskov et al. (1999) adalah minimasi total ongkos earliness dan tardiness, sedangkan kriteria dalam model yang dikembangkan dalam penelitian ini adalah minimasi total ongkos simpan dan ongkos penolakan job. 3. Tujuan Penelitian Tujuan penelitian adalah untuk mengembangkan algoritma penjadwalan job shop dengan Teknik Sisipan dengan pembatas bahwa job tidak boleh mengalami keterlambatan. 4. Asumsi Asumsi yang digunakan dalam penelitian ini adalah: • Mesin selalu tersedia • Setiap mesin hanya dapat memproses satu job pada satu saat tertentu • Setiap job hanya dapat diproses di satu mesin pada suatu waktu tertentu • Tidak boleh terjadi interupsi, yaitu sekali suatu operasi dimulai harus dikerjakan hingga selesai • Waktu proses, waktu setup, saat datang, due date, bobot dan routing masingmasing job deterministik dan diketahui dengan baik. • Waktu setup tidak bergantung pada urutan pengerjaan job (sequence independent) • Setup dapat dimulai sebelum kedatangan job di mesin. • Tidak ada biaya simpan work in process; hanya ada biaya simpan produk jadi. 5. Batasan Masalah Permasalahan dalam penelitian ini dibatasi dalam beberapa hal, yaitu: • Setiap job tidak memiliki routing alternatif • Penelitian dilakukan untuk sistem manufaktur diskrit.
2002 digitized by USU digital library
2
6. Metodologi Penelitian Penelitian ini bertujuan untuk mengembangkan algoritma penjadwalan job shop dengan Teknik Sisipan, yang merupakan pengembangan dari penelitian Sotskov et al. (1999). Pengembangan yang dilakukan adalah berupa penambahan kendala bahwa job tidak boleh mengalami keterlambatan (no tardy jobs). Pertimbangan perlunya kendala ini adalah bahwa menurut Halim (1993) dalam Barnali (1996), pada kondisi praktis pemenuhan due date lebih penting dari minimisasi inventory. Untuk mencapai tujuan tersebut dilakukan kajian pustaka yang berkaitan dengan topik penelitian. Langkah berikutnya adalah melakukan pengembangan dan pengujian model sesuai dengan tujuan penelitian. Setelah pengujian model, dilakukan analisis terhadap hasil pengujian. Langkah terakhir adalah menyusun kesimpulan dan saran untuk tindak lanjut penelitian. 7. Algoritma Sotskov et al. (1999) Sotskov et al. (1999) tidak menunjukkan dengan jelas langkah demi langkah proses penjadwalan dengan Teknik Sisipan. Tetapi dari contoh kasus yang diberikan, Algoritma Sotskov et al. (1999) dapat disusun sebagai berikut: Algoritma Sotskov et al. (1999) Langkah 1 Identifikasi routing, kelompok, waktu setup, waktu operasi, saat datang, due date, dan bobot masing-masing job Langkah 2 Tentukan saat paling awal mulai operasi (R’) untuk semua operasi dari masing-masing job. -Untuk operasi pertama suatu job: R’=max{saat datang, waktu setup} -Untuk operasi yang bukan pertama: R’=saat selesai paling cepat dari operasi sebelumnya Langkah 3 Pilih job dengan bobot terbesar. Jadwalkan secara mundur operasi terakhir job tersebut (operasi yang terakhir dilakukan dalam pemrosesan job) agar selesai tepat pada saat due date. Langkah 4 Set j=1 Langkah 5 Jadwalkan secara mundur semua operasi lainnya dari job tersebut pada Langkah 3 (operasi pendahulu) sesuai dengan routing. Langkah 6 Pilih job dengan bobot terbesar berikutnya. Jadwalkan operasi terakhir job tersebut agar selesai tepat pada saat due date. Bila tidak mungkin selesai pada saat due date: a) jadwalkan secara mundur operasi tersebut sebelum operasi yang sudah terjadwal, hitung ongkos yang timbul. b) jadwalkan operasi tersebut secara mundur sesudah operasi yang sudah terjadwal, hitung ongkos yang timbul.
2002 digitized by USU digital library
3
c) sisipkan operasi tersebut secara mundur di antara operasi yang sudah terjadwal sedekat mungkin dengan due date. Hitung ongkos yang timbul Pilih jadwal dengan ongkos terkecil sebagai dasar penjadwalan selanjutnya. Ongkos=∑wi(Ci-di)2. Langkah 7 Set j=j+1 Langkah 8 Jadwalkan operasi lainnya. Periksa apakah saat mulai ≥ saat paling awal mulai operasi ? Bila ya : lanjutkan ke langkah 9 tidak : geser jadwal ke kanan sebanyak waktu yang diperlukan agar job yang sedang dijadwal fisibel. Hitung ongkos yang timbul. Ongkos=∑wi(Ci-di)2. Langkah 9 Ulangi Langkah 6 sampai dengan 8. Lanjutkan ke Langkah 10. Langkah 10 Apakah j sudah sama dengan jumlah job? ya : penjadwalan selesai. Lanjutkan ke Langkah 11. Tidak : ulangi langkah 9 Langkah 11 Periksa apakah ada alternatif jadwal dengan ongkos lebih kecil. Perbaikan dilakukan dengan menggeser jadwal lebih dekat ke arah due datenya Langkah 12 Pilih alternatif jadwal dengan ongkos terkecil sebagai jadwal definitif. 8. Algoritma Usulan Pada penelitian Tugas Akhir ini pengembangan model Sotskov et al. (1999) dilakukan dengan menambah kendala bahwa job tidak boleh mengalami keterlambatan (no tardy jobs). Karena tidak menginginkan adanya job yang tardy, maka bila dari hasil penjadwalan ditemui job yang saat datangnya terlanggar, maka job tersebut ditolak. Sehingga ongkos yang timbul adalah berupa ongkos simpan dan ongkos penolakan job. Besarnya ongkos simpan adalah hasil kali ongkos simpan persatuan waktu dengan lamanya job disimpan, sedangkan ongkos penolakan job diasumsikan sebagai besarnya keuntungan yang hilang bila job tersebut diterima. Sehingga total ongkos adalah penjumlahan dari ongkos simpan ditambah ongkos penolakan job. Secara matematis dinyatakan dengan:
TC = ∑ wi max(0, d i − Ci ) + ∑ Br i ∈S
r ∈R
dengan : TC=total ongkos wi=ongkos simpan job i per satuan waktu di=due date job i Ci=saat selesai job i Br=ongkos penolakan job r S=set job yang diterima (dijadwalkan) R=set job yang ditolak 2002 digitized by USU digital library
4
Kesamaan Algoritma Sotskov et al. (1999) dengan algoritma usulan adalah pada Langkah 1 (inisialisasi) sampai dengan Langkah 5. Pada Langkah 6 terdapat perbedaan tindakan yang diambil pada kedua algoritma tersebut bila job tidak mungkin selesai pada saat due date, dan merupakan pembeda utama antara algoritma usulan dengan Algoritma Sotskov et al. (1999). Pada Algoritma Sotskov et al. (1999), bila job melanggar saat datang (atau saat paling awal mulai operasi) maka waktu pengerjaannya langsung digeser ke kanan. Sedangkan pada algoritma usulan, bila saat datang (atau saat paling awal mulai operasi) terlanggar maka dilakukan pertukaran operasi, dan bila job tetap tidak fisibel maka job tersebut ditolak. Pertukaran operasi yang dilakukan pada suatu saat adalah pertukaran antara operasi yang akan dijadwalkan dari suatu job dengan operasi terjadwal dari job lain manapun, yang terletak di sebelah kiri saat tersebut. Dalam pertukaran tersebut harus diperhatikan: • routing dari masing-masing job tetap valid. • total ongkos tidak bertambah besar • sesudah dilakukan pertukaran operasi, saat mulai paling awal masing-masing operasi tidak terlanggar Pertukaran operasi dihentikan segera setelah diperoleh jadwal yang fisibel (tidak perlu mempertukarkan seluruh operasi yang mungkin). Sedangkan bila setelah dilakukan pertukaran diantara semua alternatif yang mungkin ternyata jadwal tetap tidak fisibel, maka job yang terakhir dijadwal harus ditolak dan jadwal definitif adalah jadwal terakhir sebelum pertukaran dilakukan. Mekanisme pertukaran operasi tersebut dapat disusun dalam langkah-langkah sebagai berikut: Algoritma Pertukaran Operasi Langkah 0 Tetapkan p=0 (artinya belum dilakukan pertukaran operasi, dan nilai p digunakan untuk aturan berhenti) Langkah 1 Identifikasi operasi yang belum berhasil dijadwal Langkah 2 Perhatikan operasi yang telah berhasil dijadwal dari job yang sedang dijadwal (successor dari operasi yang sedang dijadwal) Langkah 3 Catat saat mulai (t) operasi yang terakhir dijadwal pada Langkah 2 Langkah 4 Periksa operasi dari job lain (syarat: bukan operasi terakhir), yang terletak di sebelah kiri t (hasil Langkah 3) di mesin hasil Langkah 1. Banyaknya operasi tersebut nyatakan sebagai q. Langkah 5 Ambil satu operasi hasil Langkah 4 untuk dipertukarkan posisinya dengan operasi yang sedang dijadwal
2002 digitized by USU digital library
5
Langkah 6 Pertukarkan kedua operasi tersebut. Tentukan p=p+1 Langkah 7 Periksa apakah saat mulai ≥ saat mulai paling awal? Ya : pertukaran selesai, jadwal fisibel Tidak : Periksa apakah p
2
4
1
6 3
m2
5 1
7
5 6 2
4
7
m1
4 1
7 5 26
20
10
30
Gambar 1. Contoh Penjadwalan Sebelum Operasi (3,2) Dijadwalkan Bila operasi (3,2) disisipkan disebelah kiri operasi (1,2) diikuti dengan menjadwal operasi (3,1) maka pada Gambar 3.2 terlihat bahwa operasi (3,2) dan operasi (3,1) melanggar saat paling awal mulai operasi. m3
2 1
4 6 3
m2
5 3 1
4
m1
6 2 7
4 3
1
10
7
5
7 5 26
20
30
Gambar 2. Operasi (3,2) Dijadwalkan Sebelum Operasi (1,2)
2002 digitized by USU digital library
6
Karena jadwal di atas tidak fisibel maka dilakukan pertukaran operasi mengikuti langkah-langkah yang telah diuraikan sebelumnya, yaitu: Langkah 0 p=0 Langkah 1 Operasi yang belum dijadwal adalah operasi (3,2) dan (3,1), saat paling awal mulai operasi (3,2) seharusnya adalah 5 dan saat paling awal mulai operasi (3,1) seharusnya adalah 3 Langkah 2 Operasi yang sudah terjadwal dari Job 1 adalah operasi (1,3) Langkah 3 Saat mulai operasi (1,3) adalah 14 (t=14). Langkah 4 Operasi di mesin 2 yang terletak di sebelah kiri t=14 adalah operasi (1,2) dan operasi (4,2), q=2. Langkah 5 Operasi (1,2) dan operasi (4,2) akan dipertukarkan dengan operasi (3,2) Langkah 6 Operasi (1,2) dipertukarkan dengan operasi (3,2) p=1 Langkah 7 saat mulai operasi (3,2) dan operasi (3,1) ≥ saat paling awal mulai operasi, tetapi operasi (1,3) tidak fisibel. p
2002 digitized by USU digital library
7
m3
2 1
4 6 3
m2
5
5 1
3
6 2
4
7
m1
4 3
7
7 5 26
1
20
10
30
Gambar 3. Operasi (3,2) Dijadwalkan Sesudah Operasi (1,2)
m3
2 1
4 6 3
m2
5
5
6 2
3
1
4
7
m1
4 3
7
1
7 5 26
20
10
30
Gambar 4. Operasi (3,2) Dipertukarkan Dengan Operasi (4,2) Jadwal definitif adalah jadwal sebelum dilakukan pertukaran operasi seperti terlihat pada Gambar 5. m3
2
4
1
6
m2
5
5 1
4
m1
6 2 7
4 1
10
7
7 5 26
20
30
Gambar 5. Jadwal Definitif Secara lengkap prosedur penjadwalan job shop menggunakan Teknik Sisipan (Insertion Techniques) dengan syarat job tidak boleh mengalami keterlambatan (no tardy jobs), yang selanjutnya disebut sebagai Algoritma ITNT, adalah sebagai berikut:
2002 digitized by USU digital library
8
Algoritma ITNT Langkah 1 Identifikasi routing, kelompok, waktu setup, waktu operasi, saat datang, due date, bobot dan ongkos penolakan masing-masing job. Langkah 2 Tentukan saat paling awal mulai operasi (R’) untuk semua operasi dari masing-masing job: - Untuk operasi pertama suatu job: R’=maks (saat datang, waktu setup) - Untuk operasi yang bukan pertama: R’=saat selesai paling cepat dari operasi sebelumnya Langkah 3 Pilih job dengan bobot terbesar. Jadwalkan secara mundur operasi terakhir job tersebut (operasi yang terakhir dilakukan dalam pemrosesan job) agar selesai tepat pada saat due date. Langkah 4 Set j=1 Langkah 5 Jadwalkan secara mundur semua operasi lainnya dari job tersebut pada Langkah 3 (semua operasi pendahulu) sesuai routing Langkah 6 Pilih job dengan bobot terbesar berikutnya. Jadwalkan secara mundur operasi terakhir job tersebut agar selesai tepat pada saat due date. Bila tidak mungkin selesai pada saat due date: a) Geser operasi yang sudah terjadwal ke kiri sehingga job yang sedang dijadwal dapat selesai tepat waktu. Hitung ongkos yang timbul. b) Jadwalkan operasi tersebut secara mundur sesudah operasi yang sudah terjadwal (job selesai lebih cepat). Hitung ongkos yang timbul. c) Sisipkan operasi tersebut diantara operasi yang sudah terjadwal hingga job yang disisipkan dapat selesai tepat pada saat due date. Hitung ongkos yang timbul. Pilih jadwal dengan ongkos terkecil sebagai dasar penjadwalan selanjutnya.
T C = ∑ wi max(0, d i − Ci ) + ∑ Br i ∈S
r ∈R
Langkah 7 Set j=j+1 Langkah 8 Jadwalkan operasi lainnya. Periksa apakah saat mulai ≥ saat paling awal mulai operasi? ya : jadwal fisibel. Lanjutkan ke langkah 10. Tidak : jadwal tidak fisibel Langkah 9 Periksa apakah ada operasi yang bisa dipertukarkan. 2002 digitized by USU digital library
9
Gunakan Algoritma Pertukaran Operasi Langkah 10 Ulangi Langkah 6 sampai dengan 8. Langkah 11 Apakah j sudah sama dengan jumlah job? ya : penjadwalan selesai. Lanjutkan ke Langkah 12 tidak : ulangi langkah 10 Langkah 12 : Tentukan: jumlah job yang selesai tepat waktu jumlah job yang selesai lebih cepat jumlah job yang ditolak total ongkos. Agar dapat memberikan gambaran yang lengkap mengenai penerapan Algoritma ITNT, berikut ini diuraikan langkah demi langkah penerapan model tersebut untuk kasus yang terdapat pada penelitian Sotskov et al. (1999). Langkah 1 n=5, m=3 dan job terdiri dari 3 kelompok, yaitu G1={1,2,3}, G2={4} dan G3={5}. Job 1 dan 3 memiliki routing yang sama yaitu q1=q3=(1,2,3) dan Job 2, 4 dan 5 memiliki routing: q2=q4=q5=(2,1,3). Waktu setup dan waktu proses adalah sebagai berikut:
4 2 1 S = 1 3 4 5 6 2
4 6 2 2 5 3 T = 1 3 5 4 2 6 5 7 1
Saat datang, bobot dan due date masing-masing job ditunjukkan dalam Tabel 1. Tabel 1. Saat datang, bobot dan due date job i job 1 2 3 4 5 ri 0 4 8 3 12 wi 1 3 5 4 7 di 25 40 35 38 30 Bila terjadi penolakan job, maka ongkos yang timbul ditunjukkan dalam Tabel 2. Tabel 2. Ongkos penolakan job i job 1 2 3 Bi 10 30 50
4 40
5 70
Langkah 2 Dari tabel di atas diperoleh nilai saat paling awal mulai operasi (i,j) dengan mempertimbangkan hanya data job i dan setup kelompok.
2002 digitized by USU digital library
10
4 8 4 9 R' = 8 9 5 3 19 12
14 11 12 9 24
Langkah 3 Job dijadwal sesuai bobot. Job 5 dijadwal terlebih dahulu. Langkah 4 j=1 Langkah 5 Operasi (5,1) dan (5,2) dijadwalkan. Langkah 6 Job 3 dijadwalkan. a) Job 3 dijadwalkan sebelum Job 5, total ongkos =40 b) Job 3 dijadwalkan sesudah Job 5. Due date terlewati 1 satuan waktu. Pengerjaan Job 5 dimajukan 1 satuan waktu, total ongkos=7 Maka Job 3 dijadwalkan sesudah Job 5 Langkah 7 j=2 Langkah 8 Operasi (3,2) dan operasi (3,1) dijadwalkan. Saat mulai > saat paling awal mulai operasi Langkah 10 Jadwalkan Job 4. Bila dijadwal sebelum Job 5, total ongkos=55 Bila dijadwal sesudah Job 5, total ongkos=91 Maka Job 4 dijadwalkan sebelum Job 5. • j=3 • Operasi (4,1) dan (4,2) dijadwalkan • saat mulai >saat paling awal mulai operasi
Langkah 11 j < jumlah job • Jadwalkan Job 2 Job 2 dapat dijadwal tepat waktu tanpa menggeser yang lain • j=4 • Operasi (2,1) dan (2,2) dijadwalkan • saat mulai > saat paling awal mulai operasi • j < jumlah job • jadwalkan Job 1 Job 1 dijadwal sebelum Job 4, total ongkos=64 2002 digitized by USU digital library
11
• j=5 • Operasi (1,2) dan (1,1) dijadwalkan • saat mulai < saat paling awal mulai operasi, ke Langkah 9 Langkah 9 pengerjaan operasi (1,2) dan (4,2) dipertukarkan, Job 1 tetap tidak fisibel, maka Job 1 ditolak Langkah 11 • j = jumlah job Langkah 12 job yang selesai tepat waktu = 2 buah (Job 2 dan 3) job yang selesai lebih cepat = 2 buah (Job 4 dan 5) job yang ditolak = 1 buah (Job 1) Total ongkos= 55 + 10 = 65. Jadwal tersebut dalam bentuk gantt chart adalah sebagai berikut: m3
4
5 3
1
2
5
m2
5
3
2
4
m1
4
5 2
3
10
20
30
40
Gambar 6. Jadwal kasus Sotskov et al. (1999) menggunakan Algoritma ITNT dengan C2=40, C3=35, C4=26, C5=29, Job 1 ditolak, dan total total ongkos = 65.
2002 digitized by USU digital library
12
