Job shop scheduling (penjadwalan job shop)

- Download With DAP
- DAP Link Checker Settings

blognya komarudin bin sayuti Weblog seputar teknik industri, terutama bidang optimasi (Operations Research) dan simulasi

# Job shop scheduling (penjadwalan job shop)

By
– February 12, 2011Posted in: Scheduling

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

Did you like this? Share it:
Tags: Jobshop, scheduling

#### 31 Comments

1. Reply
   raras
   Posted July 27, 2011 at 10:46 AM

   bagaimana jika kedaannya seperti ini :
   terdapat 7 line, dimana tiap line dikerjakan oleh 1 operator, dan tiap line dapat mengerjakan semua jenis komponen (ada 3 jenis komponen), tidak ada pengkhususan komponen di linenya.
   misal :
   operator A mengerjakan transmission WD600-3, ketika selesai operator tersebut langsung mengerjakan komponen selanjutnya yang telah tersedia, misalnya power module, kemudian ketika sdh selesai operator bisa mengerjakan komponen lainnya.
   disitu terlihat bahwa tidak ada pengkhususan.
   di line ini tidak ada mesin, melainkan perakitan dikerjakan manual oleh operator.
   bagaimana cara penjadwalannya, guna mengoptimalkan jmlh produksi?

   - Reply
     Komarudin
     Posted July 27, 2011 at 5:00 PM

     Mbak, gimana kalau pakek linear programming?

     misalkan i adalah komponen i dan j adalah line j,
     n adalah jumlah komponen i dan m adalah jumlah line j,
     Bisa dicari jumlah produksi tiap komponen untuk tiap line, baru tinggal dijadwalkan secara linear.

     Mencari jumlah produksi tiap line:
     misal cij: waktu yang dibutuhkan line j untuk memproduksi komponen i
     Tj: waktu produksi yang tersedia untuk line j
     dan xij: jumlah komponen i yang diproduksi oleh line j

     Maximize: ∑ ∑ xij
     s.t. ∑ cijxij <= Tj (∀ line j, i = 1, 2, .. n)
     xij integer

     Dengan relaksasi linier (seharusnya pakek IP), bisa dicoba solver untuk LP berikut: http://staff.blog.ui.ac.id/komarudin74/2011/07/13/algoritma-simpleks-untuk-programa-linier/
     Perlu diingat, dengan jumlah produksi yang tinggi, selisih nilai optimum antara model LP dan IP akan menjadi kecil

     komar

2. Reply
   raras
   Posted July 28, 2011 at 1:38 PM

   maaf sebelumnya pak komar,,
   jujur saya kurang mengerti ttg algoritma tsb.
   konsep dari algoritma itu sendiri saya belum paham, sehingga untuk di aplikasikan ke kasus yg saya sampaikan kmrn, saya kesulitan.
   apakah ada metode lain dalam penyelesaian kasus ini pak?
   saya berpikir untuk :
   1. mencari leadtime standart untuk setiap komponen (3 jenis) yang diberlakukan di perusahaan tsb.
   2. mencari data jumlah semua jenis komponen yang dirakit pada bulan ini.
   3. menghitung waktu aktual dalam pengerjaan tiap jenis komponen sesuai dengan operator masing-masing tiap line.
   operator memiliki kecepatan yang berbeda dalam penyelesaiannya ada yang cepat, ada yang lama, sehingga saya bermaksud, untuk komponen yang sulit dan terdiri dari banyak item dikerjakan oleh operator yang handal sehingga diharapkan perakitan akan lebih cepat selesai dan antrian komponen yang akan dirakit dapat diminimalisir, produksipun bisa lebih optimal.
   tapi saya kurang paham, seperti itu masuk di metode apa?
   mohon bantuannya pak komar,
   terimakasih..

   - Reply
     Komarudin
     Posted July 28, 2011 at 6:12 PM

     Kalo dalam “teori antrian”, prinsip seperti itu mirip dengan model ‘multi-server priority queuing‘. Kalo dalam bahasa penjadwalan jobshop, itu mirip dengan Shortest Processing Time (SPT) dispatching rule.

3. Reply
   leni
   Posted August 20, 2011 at 11:59 PM

   pak..
   ada bahan tentang panjadwalan jobshop dengan menggunakan algoritma simulated annealing ga pak?
   Tugas akhir saya menggunakan algoritma tersebut dan sekarang sedang mengalami kesulitan..
   mohon bantuannya pak…
   terimakasih..:)

   - Reply
     Komarudin
     Posted August 21, 2011 at 3:09 AM

     Halo mbak Leni,
     Silahkan Mbak Leni mencari banyak sumber online yang tersedia. Selain itu, saya ada buku yang sedikit membahas Simulated Annealing and Jobshop scheduling. Mungkin Mbak bisa dateng ke Lab SEMS untuk meminjam dengan buat janji terlebih dahulu.

4. Reply
   leni
   Posted September 9, 2011 at 10:16 PM

   buat janjinya ke siapa ya pak??
   klo boleh tau judul bukunya apa ya pak??
   saya kuliah di bandung pak..
   saya sudah ada bukunya Rosnani ginting yg penjadwalan mesin..
   tapi ternyata yg dibahas disana lebih ke implementasi flowshop…
   saya bingung buat mengerjakan perhitungan manualnya pak..
   terimakasih..

5. Reply
   ferdy
   Posted January 13, 2012 at 1:23 PM

   maaf pak, saya mw tanya sedikit untuk input serta outputnya.
   Input:
   1. Data algoritma
   a. untuk jumlah populasi maksudnya apa ya pa? apakah jumlah operator?
   b. untuk jumlah local search maksdunya apa?
   c. itu semua dapat dari mana ya pa?
   2. Data Terminasi
   a. Jumlah iterasi dapat dari mana ya pa? apakah ada rumus tertentu?
   3. bila setiap part jumlah operasinya tidak sama, apakah bisi digunakan metode ini?
   Output:
   a. apa perbedaan solusi awal dan akhir? yang lebih baik digunakan yang mana? serta apa kriteria pemilihannya?

   - Reply
     Komarudin
     Posted January 14, 2012 at 12:20 AM

     Halo Ferdy,

     Saya coba menjawab pertanyaan-pertanyaan anda.

     Untuk pertanyaan 1 dan 2:
     Algoritma yang digunakan pada template ini adalah algoritma metaheuristics. Anda perlu melakukan trial-dan error untuk mencari nilai dari parameter2 tersebut. Selain itu, parameter2 ini juga disesuaikan dengan kebutuhan dan kemampuan komputasi anda. Saya biasanya menentukan nilai parameter2 (untuk ersoalan job shop/ flow shop) tersebut sbb:
     - jumlah populasi = jumlah job
     - jumlah local search = 100
     - jumlah iterasi = 1000
     Coba anda run beberapa kali dengan nilai parameter2 diatas. Jika terlalu lama, anda dapat mengurangi nilai2 tsb di atas. Tapi kalau menurut anda hasilnya masih belum bagus, coba anda naikkan nilai2 parameter di atas.
     Sekedar saran, sebelum anda me-run dengan jumlah iterasi yg besar, saya sarankan untuk me-run algoritma tsb dengan nilai jumlah iterasi kecil, katakanlah 10. Kemudian anda dapat mengira-ngira berapa waktu yg dibutuhkan untuk jumlah iterasi yg besar (misal 1000)

     pertanyaan 3:
     Bisa digunakan. Kalau anda berkenan, anda saya harapkan men-share ke saya seberapa efektif dan efisien alat bantu ini.

     pertanyaan output:
     Algoritma metaheuristik bekerja dengan berusaha memperbaiki solusi-solusi sekarang. Maka solusi akhir-lah yg seharusnya dilihat. Pada template ini, solusi awal dan solusi akhir ditampilkan untuk memperlihatkan seberapa bagus kinerja algoritma metaheuristik tsb.

6. Reply
   halim
   Posted March 2, 2012 at 11:26 PM

   pak saya mau tanya ini algoritma nya untuk min. makespan aja ya?
   tidak bisa diganti untuk min. flow time??
   tolong bntuannya pak,, karena butuh untuk min. flow time nih..

   - Reply
     Komarudin
     Posted March 3, 2012 at 4:40 AM

     Halo Halim, boleh tau anda butuhnya untuk apa?

7. Reply
   halim
   Posted March 3, 2012 at 10:26 AM

   untuk tugas dari kampus pak,,
   saya ada tugas untuk jadwalkan produksi gt dengan konsep non delay dan priority dispatching nya minimasi flow time pak,,
   mohon bantuannya pak,, soalnya ini tugas untuk 12 macam mesin dan jumlah mesinnya cukup bnyak,,T.T

8. Reply
   halim
   Posted March 7, 2012 at 4:23 PM

   pak bgmn ?
   bsa bntu saya tidak jadwalkan produksi gt dengan konsep non delay dan priority dispatching nya minimasi flow time pak,,
   terima kasih,,

   - Reply
     Komarudin
     Posted March 8, 2012 at 3:19 AM

     Halim, bisa kamu kasi contoh bagaimana menghitung flow time?

9. Reply
   halim
   Posted March 18, 2012 at 11:26 AM

   minimasi flow time yang saya maksud itu pake SPT pak (Short Processing Time)
   misal pada
   pekerjaan 1 operasi 3 menggunakan mesin H waktu operasi 4 mnt
   pekerjaan 4 operasi 2 menggunkana mesin H waktu operasi 6 mnt
   nah dengan konsep non-delay kan kalau misalnya waktu mulai bekerjanya lebih duluan pekerjaan 4 operasi 2 maka pekerjaan 4 operasi 2 menggunkana mesin H yang dikerjakan kan..
   nah kalau waktu mulainya sama,, dengan konsep minimasi flow time,, maka pekerjaan yang dikerjakan dahulu ya perkerjaan 1 pak karena wktu operasi nya paling kecill,, begitu,,
   nah begitu pak demikian juga klaau jumlah mesin a nya lebih dari satu gt pak,,misal 2 ato 3 gt mesin a nya
   mohon bantuaanya pak,,
   soalnya kalau itung manual,, makan waktu yang lama pak,,
   terima kasih ^^

   - Reply
     Komarudin
     Posted March 19, 2012 at 4:49 AM

     Halo Halim,

     Penerapan Algoritma genetika untuk meminimumkan total FlowTime (atau average FlowTime) bisa anda unduh di halaman unduh. Tetapi mungkin interpretasi saya berbeda dengan interpretasi yg anda maksud.

10. Reply
    halim
    Posted March 20, 2012 at 5:20 PM

    ok pak,, saya coba liat dulu,,hehe,,
    btw ini algortima nya ada non delay nya juga kan prioritasnya??'
    terima kasih banyak ya pak ^^

11. Reply
    halim
    Posted March 25, 2012 at 3:01 PM

    pak,, itu rumusnya ga pk non delay ya?
    soalnya aku coba kok prinsip non delay nya ga ada gt,, T.T

12. Reply
    halim
    Posted March 25, 2012 at 3:02 PM

    oh ya atau yg saya salah masukkan data ya?
    yang dimaksud dengan jumlah populasi dan jumlah local search tuh apa ya pak??

13. Reply
    shinta
    Posted March 25, 2012 at 8:32 PM

    pak saya mau tanya,,ini algoritma bisa untuk penjadwalan penempatan plat cetak sbb:
    ada mesin 6warna, 4 warna , 2 warna, 2 warna
    tiap mesin sudah memiliki job masing2,,misalnya:
    6 warna : etiket rokok, etiket sabun, poster, stiker vinil
    4 warna : hampir sama dengan 6warna tp tidak bisa vinil
    2 warna: untuk kwartet, umbul
    persiapan pasang plat per unit 5 menit, jadi untuk mesin 6 warna membutuhkan waktu 30 menit, (5×6=30) registes (mengepaskan posisi cmyk) membutuhkan waktu 15 menit, dalam kurun waktu 12 jam, mesin 6 w.dr jam 8 sampe jam 8 itu 30rb lembar atau 14 rim.4 w 20rb atau 10 rim.2 w 7rb atau 3-4 rim.
    apakah algorima genetika ini cocok untuk penjadwalan seperti ini?? ataukah ada algoritma penjadwalan lain yang lebih cocok pak?? mohon bantuannya

    - Reply
      Komarudin
      Posted March 26, 2012 at 4:08 PM

      Halo Shinta, algoritma ini bisa diterapkan untuk permasalahan penjadwalan yg anda utarakan.
      Selain itu, jika anda berniat memisahkan job-job yg berbeda jenis dengan resiko bertambahnya setup time, mungkin anda bisa mempertimbangkan postingan saya yg lain:
      http://staff.blog.ui.ac.id/komarudin74/2012/02/05/job-shop-scheduling-with-setup-time/

14. Reply
    Alex
    Posted April 25, 2012 at 8:26 AM

    Misi pak, saya mau tanya. apakah konsep Job Shop ini bisa di selesaikan dengan algoritma cheapest insertion heuristic??

    - Reply
      Komarudin
      Posted April 25, 2012 at 11:01 AM

      Secara teori algoritma tersebut bisa diterapkan Pak Alex. Tapi saya tidak tahu seberapa bagus performanya jika diterapkan untuk permasalahan Job Shop. Improvement besar yang didapat di awal belum tentu menjustifikasi improvement yg didapat di akhir-akhir iterasi.

15. Reply
    Alex
    Posted April 25, 2012 at 7:42 PM

    Terima kasih atas jawaban dari bapak, kira2 yg menjadi pertimbangan algo CIH dalam menyelesaikan jobshop itu apa saja. soalnya saya memahami algo CIH masi sebatas untuk konsep TSP. Apakah ada perbedaan dengan algo yg bapak pakai diatas dgn algo CIH ? Trims

    - Reply
      Komarudin
      Posted April 25, 2012 at 9:23 PM

      Maaf Pak Alex. Saya tidak sedang mempertimbangkan algoritma CIH untuk menyelesaikan job shop. Jadi saya tidak tahu harus menjawab bagaimana pertanyaan Bapak. Kalau algoritma yg saya pakai di atas adalah algoritma Tabu Search.

16. Reply
    anisa
    Posted July 7, 2012 at 3:57 PM

    assalamualaikum pak,
    saya mahasiswa tingkat akhir lagi mencoba untuk menyusun skripsi. dan saya tertarik untuk membahas tentang algoritma tabu ini pak. tapi saya belum begitu paham tentang materi ini. terutama dalam pembentukan tabu listnya.kalau bapak ada waktu bisa saya belajar sedikit tentang ini pak.. terima kasih banyak..

    - Reply
      Komarudin
      Posted July 15, 2012 at 11:08 AM

      wa’alaikumsalam,
      Jika anda membutuhkan sesuatu untuk didiskusikan, silahkan hubungi saya via e-mail.

17. Reply
    Rifdan
    Posted September 11, 2012 at 11:37 AM

    Assalamu'alaikum
    1. Pak sya mahasiswa teknik informatika, sya sedang ada tugas akhir untuk membuat Aplikasi Sistem Pendukung Keputusan Perencanaan waktu produksi di perusahaan percetakan. Kira2 kasus apa yang harus saya angkat sehingga nantinya bisa sya jadikan SPK?
    2. Di dalam perusahaan percetakan itu penjadwalan termasuk dalam kategori jop shop, flow shop, seri, atau pararel atau apa pak?
    Mohon penjelasannya y pak, karena saya mahasiswa teknik informatika dan kurang mengerti dengan dunia industri. Disini sya hanya ingin mengimplementsikan ke sebuah aplikasi SPK.
    Trimakasih

    - Reply
      Komarudin
      Posted September 11, 2012 at 2:27 PM

      Wa’laikumsalam,

      1. Banyak kasus yg bisa anda angkat, tergantung permasalahan perusahaan percetakan tersebut. Sebagai contoh, apakah perusahaan sering mengalami keterlambatan pemenuhan pesanan? Atau perusahaan terlalu banyak inventory? Atau apakah mesin percetakan sering rusak? Atau karyawan berketrampilan tertentu sering tidak tersedia? Apakah bahan baku sering tidak tersedia? dll..

      2. Biasanya job shop.

18. Reply
    Albert
    Posted September 18, 2012 at 1:48 AM

    Permisi pa, saya adalah mahasiswa teknik informatika..saat ini saya sedang menyusun skripsi tentang sistem informasi yang menerapkan MRP pada perusahaan yang bergerak di bidang part manufacturing(bubut).. karena salah satu tahapan di MRP adalah shop schedulling, saya ingin menerapkan shop schedulling tersebut, tapi saya bingung harus memakai flow shop atau job shop, karena dunia industri masi asing bagi saya…
    terima kasih pa..

    - Reply
      Komarudin
      Posted September 18, 2012 at 6:05 PM

      Coba anda baca2 dulu tentang job shop dan flow shop

### Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Name *

Email *

Website

Anti-spam math answer: (Required)*
To prove you're a person (not a spam script), type the answer to the math equation shown in the picture. Click on the picture to hear an audio file of the equation.

Comment

Styles Styles Styles Font Font Font Size Font Size Size Bold Italic Strike Through Text Color Background Color

This visual editor brought to you by fckeditor for wordpress plugin

You may use these HTML tags and attributes: `<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <font color="" face="" size=""> <span style="">`