Penjadwalan Job Shop
- Diperkenalkan oleh
- Pinedo, M. L.
- Tahun
- 2016
- Jenis
- Combinatorial scheduling problem
- Keluarga
- Optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Penjadwalan job shop adalah masalah penugasan sekumpulan pekerjaan (tugas) ke sekumpulan mesin (sumber daya) dari waktu ke waktu, tunduk pada kendala pendahuluan dan kapasitas, dengan tujuan mengoptimalkan metrik kinerja seperti makespan (total waktu penyelesaian), keterlambatan, atau biaya.
Masalah job shop adalah masalah optimasi kombinatorial klasik dalam riset operasi, yang diatasi melalui heuristik (aturan pengiriman serakah, simulated annealing, algoritma genetik) dan algoritma eksak (branch-and-bound, constraint programming). Ini fundamental untuk manufaktur, manajemen proyek, dan penjadwalan komputasional.
Intuisi di balik metode
Bayangkan sebuah bengkel mesin kecil dengan 10 mesin. Pesanan pelanggan (pekerjaan) terdiri dari 5 komponen, masing-masing memerlukan urutan operasi pada mesin yang berbeda: Komponen 1 memerlukan pemesinan pada Mesin A, lalu pengeboran pada Mesin C. Komponen 2 memerlukan pengeboran pada Mesin B, lalu pengelasan pada Mesin D. Semua komponen bertemu untuk perakitan akhir. Tantangannya: menjadwalkan semua operasi untuk meminimalkan total waktu penyelesaian, tanpa melebihi kapasitas mesin, sambil menghormati urutan operasi untuk setiap komponen. Jika Anda menugaskan Komponen 1 ke Mesin A terlalu lambat, Mesin C akan menganggur. Jika Anda membebani Mesin C, semuanya akan tertunda. Masalah job shop menangkap kompleksitas ini: dengan 100 pekerjaan dan 20 mesin, jumlah kemungkinan jadwal sangat astronomis, membuat solusi eksak tidak praktis. Sebaliknya, Anda menggunakan heuristik untuk menemukan jadwal yang baik (belum tentu optimal) dengan cepat.
Sejarah
Masalah penjadwalan job shop muncul pada tahun 1950-an sebagai masalah penelitian dalam riset operasi. Karya seminal oleh Johnson (1954) memecahkan masalah dua mesin secara optimal; Fisher dan Thompson (1963) menciptakan masalah benchmark yang masih digunakan hingga kini. Masalah ini adalah NP-hard (terbukti pada tahun 1970-an), memacu pengembangan heuristik dan metaheuristik. Pendekatan modern meliputi constraint programming (1990-an–2000-an), algoritma genetik, dan metode hibrida. Penjadwalan job shop kini merupakan bidang yang matang dengan aplikasi yang meluas di luar manufaktur ke komputasi awan, telekomunikasi, dan transportasi.
Kapan digunakan
Penjadwalan job shop berlaku untuk lingkungan manufaktur atau layanan apa pun dengan banyak mesin/sumber daya dan pekerjaan dengan urutan operasi yang berbeda. Aplikasi tipikal meliputi bengkel mesin, pabrik percetakan, fabrikasi wafer semikonduktor, rumah sakit (penjadwalan ruang bedah), dan penjadwalan proyek. Gunakan ketika kompleksitas pekerjaan tinggi (beberapa operasi per pekerjaan), utilisasi mesin kritis, atau tanggal jatuh tempo ketat. Kurang kritis dalam lingkungan jalur perakitan (aliran linier) atau operasi mesin tunggal yang sederhana.
Batasan dan pertimbangan
- Kompleksitas kombinatorial: menemukan solusi optimal adalah NP-hard; solusi praktis memerlukan heuristik yang mungkin tidak optimal secara global
- Solusi heuristik bergantung pada konteks; aturan yang bekerja dengan baik untuk satu bengkel mungkin berkinerja buruk di bengkel lain, memerlukan penyesuaian dan validasi
- Mengasumsikan input statis (pekerjaan dan mesin tetap); bengkel nyata mengalami kedatangan dinamis, pembatalan, dan kegagalan peralatan, memerlukan penjadwalan ulang yang sering
- Stabilitas jadwal: perubahan jadwal yang sering (karena pekerjaan baru atau gangguan) dapat meningkatkan biaya dan mempersulit koordinasi dengan pekerja dan pelanggan
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Mengakomodasi kendala realistis yang kompleks (pendahuluan, kemampuan mesin, tanggal jatuh tempo) yang tidak dapat ditangani oleh aturan penjadwalan sederhana
- Mengoptimalkan metrik bisnis yang relevan (makespan, keterlambatan, utilisasi mesin) daripada aturan ad-hoc
- Memungkinkan respons cepat terhadap gangguan; algoritma penjadwalan ulang dapat menghasilkan rencana yang direvisi ketika mesin rusak atau pekerjaan mendesak tiba
- Formulasi matematis memungkinkan analisis sensitivitas dan eksplorasi trade-off (misalnya, keterlambatan vs. makespan)
- Didukung oleh alat perangkat lunak yang efisien dan algoritma metaheuristik yang matang
Penerapan
- Sebuah bengkel mesin presisi menggunakan penjadwalan job shop dengan simulated annealing untuk menjadwalkan 200+ komponen kustom di 15 mesin CNC, mengurangi makespan sebesar 15 persen dan meningkatkan pengiriman tepat waktu dari 85 persen menjadi 95 persen
- Sebuah pabrik fabrikasi semikonduktor menerapkan penjadwalan berbasis kendala untuk mengelola 500+ langkah proses di 50 alat, meminimalkan waktu siklus wafer dan mengurangi inventaris dalam proses sebesar 20 persen
- Sebuah perusahaan percetakan menggunakan penjadwalan job shop dinamis untuk menugaskan pekerjaan cetak ke 8 mesin cetak dengan kemampuan berbeda, mengoptimalkan campuran pekerjaan (volume tinggi vs. khusus) dan meminimalkan waktu pergantian
- Sebuah tim penjadwalan rumah sakit mengimplementasikan algoritma job shop untuk penjadwalan ruang operasi, mengoordinasikan ahli bedah, tim bedah, dan peralatan, meningkatkan utilisasi ruang operasi dari 65 persen menjadi 82 persen
Cara kerjanya
Cara kerjanya
Definisikan pekerjaan (pesanan, tugas) dengan urutan operasi, persyaratan mesin, waktu pemrosesan, dan tanggal jatuh tempo. Definisikan mesin yang tersedia dan jendela ketersediaannya.
Tentukan kendala: pendahuluan operasi (Komponen 1 harus menyelesaikan operasi A sebelum memulai operasi B), kapasitas (setiap mesin dapat memproses satu pekerjaan pada satu waktu), dan secara opsional, waktu rilis dan tanggal jatuh tempo.
Terapkan aturan pengiriman (misalnya, waktu pemrosesan terpendek, tanggal jatuh tempo paling awal, rasio kritis) untuk mengurutkan pekerjaan di setiap mesin, menghasilkan jadwal awal.
Gunakan metaheuristik (simulated annealing, tabu search, algoritma genetik, ant colony optimization) untuk meningkatkan jadwal melalui pencarian lokal atau metode berbasis populasi.
Nilai kualitas jadwal (makespan, keterlambatan, waktu menganggur, waktu penyangga). Jika dapat diterima, terapkan; jika tidak, sesuaikan parameter dan optimalkan kembali.
Kesalahan umum
- Mengoptimalkan metrik yang salah; memaksimalkan utilisasi mesin dapat meningkatkan keterlambatan pekerjaan, sementara memenuhi semua tanggal jatuh tempo mungkin memerlukan waktu menganggur yang signifikan
- Mengabaikan waktu penyiapan dan pergantian; jadwal yang meminimalkan waktu menganggur tetapi memerlukan penyiapan yang sering dan memakan waktu mungkin suboptimal dalam praktik
- Terlalu mengandalkan jadwal heuristik tanpa validasi terhadap perilaku bengkel nyata; kendala seringkali lebih kompleks daripada yang ditangkap model
Pertanyaan yang sering diajukan
Apa itu makespan, dan mengapa itu penting?
Makespan adalah total waktu dari awal operasi pertama hingga penyelesaian operasi terakhir. Ini berkorelasi langsung dengan utilisasi peralatan, arus kas (penyelesaian lebih cepat = pembayaran lebih cepat), dan kepuasan pelanggan. Meminimalkan makespan adalah tujuan utama yang umum dalam penjadwalan job shop.
Apa perbedaan antara penjadwalan job shop statis dan dinamis?
Penjadwalan statis mengasumsikan semua pekerjaan diketahui di muka; Anda mengoptimalkan satu set tetap. Penjadwalan dinamis menangani pekerjaan yang tiba dari waktu ke waktu; jadwal direvisi saat pekerjaan baru tiba atau gangguan terjadi. Sebagian besar bengkel nyata bersifat dinamis, memerlukan algoritma optimasi ulang yang cepat.
Aturan pengiriman mana yang harus kita gunakan?
Tidak ada satu aturan pun yang mendominasi. Shortest Processing Time (SPT) meminimalkan makespan; Earliest Due Date (EDD) meminimalkan keterlambatan; Critical Ratio menyeimbangkan keduanya. Uji aturan dengan data historis atau simulasi untuk menemukan yang paling sesuai dengan prioritas dan kendala bengkel Anda.
Bisakah penjadwalan job shop menangani keterampilan pekerja dan pelatihan silang?
Ya, dengan memperluas model sumber daya: alih-alih hanya 'Mesin A,' tentukan 'Mesin A dengan Pekerja 1' atau 'Mesin A dengan Pekerja 2.' Namun, ini meningkatkan kompleksitas masalah; pastikan perangkat lunak penjadwalan Anda mendukung kendala multi-sumber daya.
Metode terkait
Sumber
Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Cham: Springer.
Buka referensi DOIDisalin.Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
Buka referensi DOIDisalin.