“Job Shop Schedulling Problems (JSSP)”

Scientific Journal. Published by LENSA : 2008

Masalah penjadwalan job shop merupakan salah satu masalah optimasi kombinatorial non deterministik dengan waktu polinomial (NP-complete) yang paling rumit. Waktu komputasi untuk mencari solusi optimal yang meningkat secara exponensial seiring dengan membesarnya nilai parameter masalah (jumlah mesin dan jumlah job) [Panggabean: 2002].

Salah satu teknik penjadwalan yang paling banyak digunakan dalam pemecahan masalah optimasi, yaitu algoritma penjadwalan Simulated Annealing (SA). Algoritma tersebut merupakan teknik pencarian probabilistik yang umum digunakan untuk menemukan solusi yang optimal.

Elsayed dan Laarhoven et al. [dalam Panggabean] melakukan suatu penelitian bahwa algoritma SA dapat menghasilkan suatu solusi yang optimal atau mendekati optimal dengan waktu relatif singkat, sehingga dapat dikatakan lebih baik bila dibandingkan dengan metode heuristik. Liu et al. [dalam Panggabean] mengemukakan bahwa hasil yang diperoleh konvergen lebih baik menuju nilai global minimum seiring dengan bertambahnya jumlah iterasi ke arah tak hingga serta bersifat problem independent sehingga fleksibel diterapkan dalam berbagai masalah dan lebih mudah dikomputerisasikan.

Kenyataan tersebut memberi harapan bahwa algoritma SA dapat menghasilkan jadwal produksi job shop dengan kualitas jadwal yang baik dengan waktu komputasi yang masih dapat diterima. Panggabean [2002] melakukan suatu penelitian penjadwalan job shop statik dengan menggunakan algoritma SA. Penelitian yang dilakukannya bertujuan untuk membuktikan validitas hasil penjadwalan SA dengan mencoba membandingkan hasil perhitungan algoritma dengan hasil perhitungan pada perangkat lunak penjadwalan Quant system.

Dari serangkaian percobaan yang dilakukan diperoleh suatu simpulan bahwa kualitas solusi yang dihasilkan oleh algoritma SA lebih baik bila dibandingkan dengan hasil penjadwalan Quant system terutama untuk kasus job shop berukuran besar, meskipun untuk itu diperlukan waktu komputasi yang relatif lebih besar bila dibandingkan dengan Quant system.

Algoritma penjadwalan Simulated Annealing (SA) untuk kasus penjadwalan job shop pertama kali ditemukan dan dikembangkan oleh Metropolis et al. pada tahun 1953. Aplikasi SA dalam masalah optimasi dikerjakan pertama kali oleh kirpatrick et al. pada tahun 1983. Algoritma ini beranalogi pada proses annealing (pendinginan) yang diterapkan dalam pembuatan material glassy (terdiri atas butir kristal). Dalam konteks optimasi, temperatur adalah variabel kontrol yang berkurang nilai sisanya selama proses optimasi tersebut dijalankan.

Skenario pendinginan dianalogikan dengan prosedur search yang menggantikan satu state dengan state lainnya dengan memperbaiki nilai fungsi objektif. Sebagai contoh, masalah optimasi kombinatorial (S, F) dimana i adalah konfigurasi/solusi sekarang (current) dengan fungsi cost F(i) dan j adalah konfigurasi berikutnya dengan fungsi cost F(j).

Kriteria penerimaan yang mewakili kriteria Metropolis didefinisikan sebagai berikut :

Prob(menerima j)= Min [1, exp(-(F(i)-F(j)/c)],
dimana c∈R+ adalah parameter kontrol, dan
i,j ∈ S adalah dua konfigurasi yang berbeda.

Pada saat ini, teknik penjadwalan job shop mengalami banyak perkembangan, diantaranya yang dikenal ialah metode program integer, metode branch and bound, serta metode heuristik.Metode pemrograman integer dan branch and bound pada dasarnya memiliki tingkat kesukaran yang tinggi dan belum tentu menghasilkan jadwal yang benar-benar optimal. Metode heuristik adalah suatu metode yang dapat menghasilkan solusi yang cukup baik tapi tidak menjamin perolehan jadwal yang benar-benar optimal [Kusuma:1999].

Dewasa ini, berbagai perkembangan dari penjadwalan ditemukan seiring dengan perkembangan ilmu pengetahuan dan teknologi, berbagai macam pendekatan dengan model dan solusi dilakukan dengan meramu beberapa literatur keilmuan seperti operations research dan juga teknis matematis. Disamping itu terdapat beberapa metode penjadwalan yang umum dikenal, diantaranya dispatching rules, expert systems (AI agents), neural networks, tabu search, simulated annealing, genetic alghoritms, fuzzy logic, inductive learning dan lain sebagainya [Jones et al].

Teknik optimasi penjadwalan sering digunakan dengan menggunakan teknik pemrograman matematis yang dewasa ini dikembangkan secara ekstensif untuk berbagai kasus penjadwalan. Pemecahahan persoalan penjadwalan dengan menggunakan teknik matematis seringkali didekati dengan menggunakan metode integer linear programmimg, mixed integer programming, dan dynamic programming.

Dewasa ini, penggunaan pendekatan matematis dengan teknik tersebut di atas semakin jarang digunakan seiring dengan kompleksitas persoalan penjadwalan yang mendekati tingkat kesukaran masing-masing [Jones et al].

Metode penjadwalan heuristik adalah salah satu teknik penjadwalan yang pertama kali ditemukan dan menjadi akar pengembangan dari metode penjadwalan lain yang bersifat non-heuristik. Teknik penjadwalan tersebut menggunakan algoritma yang lebih sederhana, meski tidak ‘reliable’ untuk kasus-kasus penjadwalan yang kompleks.

Salah satu metode heuristik yang cukup umum dikenal ialah metode priority dispatching yang dikemukakan oleh Giffler dan Thompson [Kusuma: 1999]. Metode tersebut berprinsip pada pembuatan jadwal secara parsial (bertahap), dan terdiri atas dua (2) macam algoritma, yaitu algoritma untuk pembuatan jadwal aktif dan penjadwalan non delay [Kusuma: 1999].

Pada persoalan penjadwalan job shop klasik, job dinotasikan dengan J, dan operasi dinotasikan dengan Oij operasi yang mengikuti sekuens operasi tertentu (struktur presedens operasi serial), dan setiap job (yang terdiri atas operasi-operasi) ditugaskan pada sebuah mesin Mj tertentu [Morton. et al].

Gambar 1.1 Skema Penjadwalan Job Shop [Unachak]

Bedworth [1986] membagi aktivitas penjadwalan (scheduling activity) menjadi dilakukan melalui 2 (dua) tahapan (two stages) yaitu :
(1) Alokasikan setiap task pada tiap mesin (first stages), dan
(2) Memperhitungkan decision rules (second stages).

Decison rules yang dimaksud dalam tahap dua (2) yaitu aturan prioritas penjadwalan yang dapat berupa SPT (Shortest Processing Time), FIFO (First In First Out), Random, EDD (Earliest Due Date), MWKR (Most Work Remaining) yaitu memilih pekerjaan yang memiliki waktu proses keseluruhan yang masih tersisa paling besar, LWKR (Least Work Remaining) dengan jalan memilih pekerjaan yang memiliki waktu proses keseluruhan yang masih tersisa paling kecil, serta MONPR (Most Operation Remaining) [Bedworth :1986].

Gambar 1.2 Representasi Graph untuk Masalah Job Shop

Teknik lain yang digunakan dalam pemecahan masalah job shop yaitu teknik AI (Artificial Intelligences) yang melibatkan teknik intelligensi dengan merangkum berbagai pendapat dari para pakar penjadwalan [Jones et al]. Langkah awal dalam teknik ini yaitu : (1) Membangun studi empiris dengan menggunakan teknik-teknik dari kombinasi pengetahuan kuntitatif dan kualitatif dalam proses pengambilan keputusan, (2) Membuat penyelesaian persoalan penjadwalan heuristik yang sedikit lebih kompleks dari aturan priority dispatching, dan (3) Pemilihan solusi dari teknik heurustik terbaik yang dibuat sebelumnya, serta (4) Merumuskan keterkaitan hubungan antar struktur data untuk memudahkan manipulasi informasi yang terdapat pada struktur data tersebut.

Penjadwalan yang biasa diterapkan di lantai produksi secara umum dibedakan atas jumlah mesin atau kriteria lantai produksi, diantaranya sebagai berikut [Jones. et al] :

a. One stage, one processor
b. One stage, multiple processors
c. Multistages, flow shop
d. Multistages, job shop

Jones et al. mengemukakan bahwa pada tipikal penjadwalan one stage dan one processor, permasalahan cukup diselesaikan dalam satu tahap pemrosesan (one processing step) yang melewati satu sumber daya (mesin). Pada one stage, multiple processors tahapan pemrosesan melewati banyak sumber daya (mesin). Dalam kasus multistage pada persoalan penjadwalan flow shop, setiap pekerjaan (job) memiliki beberapa tugas (task) atau langkah kerja yang diproses oleh mesin yang spesifik namun melewati rute yang sama untuk setiap job tersebut. Pada kasus multistage job shop, sumber daya (mesin) diatur dan diset sedemikian rupa dengan rute operasi yang dipilih dan ditentukan sebelumnya namun memiliki berbagai macam variasi produksi.

Berdasarkan literatur-literatur tersebut di atas dapat disimpulkan bahwa penjadwalan job shop (JSSP) memiliki berbagai teknik penyelesaian dan algoritma penjadwalan. Diantara metode
Scientific Journal. Published by LENSA : 2008
yang umum digunakan dalam riset penelitian diantaranya dispatching rules, expert systems (AI agents), neural networks, neighborhood, tabu search, simulated annealing, integer programming, branch and bound genetic alghoritms, fuzzy logic, inductive learning dan lain sebagainya. Beberapa metode tersebut memiliki keunggulan dan kekurangan masing-masing apabila ditinjau dari kompleksitas masalah, pengetahuan peneliti, tujuan penelitian, batasan variabel dan lain sebagainya.

Simple Dispatching Rules merupakan teknik penjadwalan heuristik yang sangat sederhana dan umum digunakan tetapi tidak ‘reliable’ untuk kasus penjadwalan yang berukuran besar dengan tingkat kompleksitas yang rumit. Demikian sebaliknya teknik-teknik lain seperti , tabu search, simulated annealing, integer programming, branch and bound genetic alghoritms memiliki tingkat kesukaran yang lebih tinggi daripada metode Priority Dispatching, namun sangat cocok digunakan untuk kasus yang kompleks dengan jumlah variabel yang lebih banyak. Teknik AI agents dan inductive learning mengkombinasikan antara kemampuan kualitatif (intuitif) dengan kuantitatif (matematis) dengan merujuk pada pengalaman ‘meneliti’ dan studi empiris. Namun, demikian keseluruhan metode tersebut dapat digunakan untuk berbagai kalangan berdasarkan variabel dan karakteristik penelitian yang diinginkan.

Padang, Januari 2008

Referensi :

(1) Albert Jones. et al. International Jounal :
Survey of Job Shop Schedulling
Techniques. jonesa@cme.nist.gov.
(2) David D. Betworth. et al. 1986.
”Integrated Production Control Systems”.
Jhon Wiley & Sons.
(3) Hendra Kusuma. 1999. ”Perencanaan
dan Pengendalian Produksi”. PT. Andi
Yogyakarta. Yogyakarta.
(4) Henry Pantas Panggabean. 2002. Jurnal:
Penjadwalan Job Shop Statik dengan
Algoritma Simulated Annealing.
Universitas Katolik Parahyangan :
Bandung.
(5) Thomas E.Morton. et al. 1993. “Heuristic
Schedulling Systems: with applications to
production systems & project
management”. Jhon Wiley&Sons, Inc,
Canada : USA.
(6) Prakarn Unachak. International Jounal :
Genetic Alghorithm in Job Shop Schedulling.
(Power Point Presentation).