Job shop scheduling (penjadwalan job shop)

Seperti telah saya singgung di post terdahulu, penjadwalan produksi adalah suatu kegiatan yang sangat penting pada perusahaan manufaktur. Model terdahulu, yakni flow shop scheduling juga dapat diaplikasikan pada perusahaan atau kegiatan jasa. Tetapi seperti telah disebutkan, urutan proses di mesin tiap job (pekerjaan) haruslah sama. Sebagai contoh, kegiatan foto kopi, periklanan, restoran, dan lain-lain. Jika urutan proses di mesin berbeda, maka model penjadwalan yang tepat adalah job shop scheduling problem.

Pada permasalahan penjadwalan job shop, ada sejumlah job dan sejumlah mesin dengan setiap job dapat memiliki urutan proses yang berbeda dengan job yang lainnya. Hal inilah yang membuat permasalahan ini lebih rumit dibandingkan dengan permasalahan penjadwalan flow shop. Sebagaimana permasalahan penjadwalan flow shop, permasalahan job shop dapat ditujukan untuk meminimumkan makespan, meminimumkan keterlambatan, meminimumkan total biaya (termasuk biaya penalti), dan lain sebagainya. Dengan keleluasaan ini, banyak permasalahan penjadwalan dapat dimodelkan sebagai job shop scheduling problem.

Model ini terutama dapat diaplikasikan untuk perusahaan manufaktur yang menganut sistem make to order, seperti pencetakan mold, bengkel bubut, dsb. Selain itu, sebagaimana disebutkan di atas, model ini juga dapat digunakan untuk menyelesaikan permasalahan penjadwalan pada bidang jasa.

Berikut kami sampaikan sebuah file excel dengan VBA yang dapat digunakan untuk menghasilkan solusi dari permasalahan penjadwalan job shop. Dalam file tsb, kami mengimplementasikan algoritma genetika dengan one-point crossover dengan beberapa penerapan local search. Selain itu, file tersebut juga dapat digunakan untuk menyelesaikan permasalahan penjadwalan job shop dengan mesin identik (job shop scheduling problem with identical machine).

Genetic Algorithm for JobShopScheduling minimize makespan LA17.xlsm

Berikut kami tampilkan manualnya (akan tetapi ada perbedaan sedikit)

Manual Penggunaan Algoritma Tabu Search untuk mengoptimasikan Penjadwalan Job Shop

Pada file tersebut, kami mengambil contoh la17 dari OR library. Metode di atas dapat menghasilkan solusi terbaik 832 sedangkan best known solution untuk problem la17 adalah 784. Untuk menggunakannya, beberapa data setting algoritma perlu ditentukan:

Kemudian karena file tersebut dapat digunakan untuk menyelesaikan problem dengan mesin identik, jumlah mesin untuk tiap tipe mesin perlu ditentukan:

Kemudian urutan mesin untuk tiap job perlu dimasukkan:

Setelah itu, data waktu pemrosesan pada mesin juga perlu ditentukan:

Setelah di-run, didapatkan hasil sebagai berikut:

Jadwal tiap job (pekerjaan) adalah sebagai berikut:

Dan detail jadwal untuk tiap mesin adalah sebagai berikut:

ditulis di umbulharjo, 12Feb2011

Update 28 January 2013:

Beberapa pemirsa masih kurang ‘engeh’ tentang bedanya antara permasalahan flow-shop dan job-shop. Saya tambahkan keterangan dan contoh untuk membantu pemirsa lebih ‘engeh’. Pada permasalahan flow-shop, sebuah job akan memiliki urutan process yg sama. Pada permasalahan job-shop, persyaratan ini tidak berlaku. Sebuah permasalahan job-shop bisa memiliki perbedaan dalam urutan process.

Contoh permasalahan “pure” flow-shop (perhatikan semua job memiliki urutan process yg sama):

  • Process pada job 1: B – C – D – F – A – E
  • Process pada job 2: B – C – D – F – A – E
  • Process pada job 3: B – C – D – F – A – E

Contoh permasalahan “general” flow-shop (perhatikan semua job bisa diurutkan dg urutan process yg hampir sama dan sebagian job boleh men-skip beberapa process):

  • Process pada job 1: B – C – [ ] – F – A – E
  • Process pada job 2: B – [ ] – D – F – A – E
  • Process pada job 3: B – C – D – [ ] – A – E

Contoh permasalahan job-shop (perhatikan tidak semua job memiliki urutan process yg sama):

  • Process pada job 1: B – C – D – F – B – E
  • Process pada job 2: C – B – D – B – F – E
  • Process pada job 3: B – C – D – F – B – E
Print Friendly
Did you like this? Share it: