## Penyelesaian Penjadwalan Flexible Job Shop untuk Minimasi Due Windows dengan Algoritma Genetika

## Ferdinan Rinaldo Tampubolon
Polliteknik Negeri Medan Email: ferdinantampubolon@polmed.ac.id
Artikel info Artikel history: Diterima : 15-05-2021 Direvisi : 10-06-2021
Disetujui : 15-06-2021
Keywords: due windows, flexible job shop; genetika
Kata kunci: due windows, flexible job shop; genetik

## Abstract:
Flexible  Job  Shop  (FJSP)  is  the  development  of  a  job  shop  where  there  is more than one machine that can process a job. This study aims to model and complete  the  FJSP  with  a  due  windows  objective  function  where  each  job must  be  completed  within  a  certain  time  span.  The  method  used  in  this research is the Genetic Algorithm method. The result obtained is scheduling in the form of a Gantt Chart which has a minimum penalty value.

## Abstrak:
Flexible  Job  Shop  (FJSP)  adalah  pengembangan  dari job  shop dimana terdapat  lebih  dari  satu  mesin  yang  dapat  memproses  suatu  pekerjaan. Penelitian  bertujuan  untuk  memodelkan  dan  menyelesaikan  FJSP  dengan fungsi  tujuan due  windows dimana  tiap-tiap  pekerjaan  harus  selesai  dalam suatu  rentang  waktu.  Metode  yang  digunakan  dalam  penelitian  ini  adalah metode Algoritma Genetika. Hasil yang diproleh adalah penjadwalan dalam bentuk Gantt Chart yang memiliki nilai penalti yang minimum.
Coresponden author: Ferdinan Rinaldo Tampubolon Email: ferdinantampubolon@polmed.ac.id artikel dengan akses terbuka dibawah lisensi
CC BY SA 2021

## Pendahuluan
Penjadwalan  adalah  suatu  permasalahan  dalam  bidang  Operasi  Riset  dimana  terdapat sejumlah  sumber  daya  yang  terbatas  untuk  menyelesaikan  banyak  pekerjaan.  Pengambil keputusan harus membuat prioritas untuk memilih pekerjaan yang harus diselesaikan terlebih dahulu  berdasarkan  tujuan  yang  akan  dicapai  ( Saudagar ,  Kamboj,  Mohan,  Patil,  &  Powar, 2020).
Job  Shop adalah  salah  satu  jenis  penjadwalan  dimana  sumber  daya  berupa  mesin  dan masing-masing pekerjaan mempunyai operasi-operasi yang harus diproses secara berurut oleh satu buah mesin. Flexible Job Shop (FJSP) adalah pengembangan dari Job Shop dimana tiap operasi dapat diproses oleh beberapa mesin. Sehingga waktu pemerosesan dari suatu operasi bergantung pada mesin yang terpilih untuk menyelesaikan operasi tersebut.  ( Marzouki , Driss,
&  Ghédira,  2018). Flexible  Job  Shop memiliki  kerumitan  yang  lebih  tinggi  dari Job  Shop

## Jurnal Indonesia Sosial Sains
Vol. 2, No. 6, Juni 2021 E-ISSN:2723 – 6595
http://jiss.publikasiindonesia.id/
P-ISSN:2723 – 6692
karena  yang  harus  diselesaikan  tidak  hanya  menentukan  pekerjaan  mana  yang  harus diselesaikan  terlebih  dahulu  akan  tetapi  juga  mesin  yang  akan  dipilih  untuk  menyelesaikan pekerjaan tersebut. ( Ahmadi , Zandieh, Farrokh, & Emami, 2016)
Fungsi tujuan yang paling umum dari Job Shop adalah meminimumkan makespan yaitu penyelesaian keseluruhan pekerjaan. Pada kasus tertentu suatu pekerjaan mempunyai prioritas untuk diselesaikan terlebih dahulu. ( Alzahrani , 2019). Fungsi tujuan Job Shop yang demikian adalah tardiness ,  yaitu  apabila pekerjaan diselesaikan melebihi  waktu  yang diberikan maka akan  diberikan  penalti.  Hal  ini  sesuai  dengan  keadaan  sehari-hari  dimana customer sewajarnya akan menunutut kompensasi apabila barang yang diantarkan terlambat. ( Kim , Jun, Bang, Shin, & Choi, 2020). JIT (Just In Time Scheduling) adalah suatu konsep dimana suatu pekerjaan  harus  diselesaikan  sesuai  waktu  yang  ditentukan.  Hal  ini  sesuai  dengan  realita dimana  suatu  barang  yang  diselesaikan  terlalu  cepat  akan  membuat  barang  menumpuk  di gudang (earliness) .      ( Idowu ,  Adamu,  &  Sawyerr,  2020).  Pada  JIT  terdapat  penalti  apabila pekerjaan diselesaikan lebih cepat ( earliness ) ataupun lebih lama ( tardiness ) dari waktu yang ditentukan  ( due  date ).  ( Ahmadian ,  Salehipour,  &  Cheng,  2021). Due  date yang  berupa interval  waktu  disebut  sebagai due  windows .  Suatu  pekerjaan  diharapkan  dapat  diselesaikan pada suatu rentang waktu. Penalti akan diberikan apabila pekerjaan diselesaikan tidak berada pada rentang waktu yang diberikan ( Lin, 2020).
Pada  penelitian  Idowu,  Lin,  Ahmadian  yang  sudah  dilaksanakan  berbasis  pekerjaan yang diharapkan dapat diselesaikan pada suatu rentang waktu. Penalti akan diberikan apabila pekerjaan  diselesaikan  tidak  berada  pada  rentang  waktu  yang  diberikan,  konsep  tersebut diterapkan pada kasus mesin tunggal (single machine), sedangkan pada penelitian ini konsep tersebut akan diterapkan pada kasus flexible job shop, dimana terdapat beberapa mesin yang dapat  menyelesaikan  beberapa  buah  operasi  (multi  purpose  machine)  Penelitian  ini  akan meminimumkan due  windows pada  penjadwalan  FJSP.  Model  matematis  akan  dibentuk terlebih  dahulu.  Selanjutnya  model  tersebut  akan  diselesaikan    dengan  Algoritma  Genetika, suatu  algoritma  yang  paling  populer  untuk  menyelesaikan  FJSP  ( Amjad et  al.,  2018). Penggunaan elite  strategy maupun dispatching  rule pada    insialisasi  populasi  akan menghasilkan penjadwalan FJSP dengan penalti yang minimum.

## Metode Penelitian
Penelitian  ini  merupakan  studi  literatur,  dimulai  dengan  menyusun  model  matematis dari permasalahan kemudian menyelesaikan permasalahan tersebut dengan metode Algoritma Genetika.  Untuk  melihat  apakah  metode  yang  digunakan  sudah  cukup  baik  dilakukan perbandingan  hasil  dari  penelitian  sebelumnya.  Adapun  langkah-langkah  penelitian  sebagai berikut:

## Model Matematis
Langkah  pertama  dalam  penelitian  ini  adalah  menyusun  pemodelan  matematis  terkait Flexible Job Shop dengan fungsi tujuan setiap pekerjaan selesai pada rentang waktu tertentu ( due windows). Pada penelitian ini pekerjaan masing-masing memiliki interval waktu dimana pekerjaan  diharapkan  dapat  diselesaikan  pada  interval  tersebut  { 𝑑 𝑖 𝑙 , 𝑑 𝑖 𝑢 }.  Apabila  pekerjaan diselesaikan  diluar  selang  waktu  tersebut  maka  akan  diberikan  penalti.  Gambar  1
menunjukkan 𝐶 1 menujukkan  penyelesaian  lebih  cepat  dari  yang  ditentukan,  sementara 𝐶 2 menjukkan penyelesaian yang dilakukan melewati batas waktu.

## Gambar 1 Due Windows
Kendala-kendala dari penjadwalan flexible job shop harus memenuhi kriteria-kriteria dari job shop , menurut ( Kuhpfahl , 2015) sebagai berikut:
1. Setiap mesin hanya dapat memproses satu pekerjaan dalam suatu waktu interval
2. Setiap operasi pada tiap pekerjaan harus dikerjakan secara berurutan
3. Setiap operasi hanya dapat diselesaikan oleh satu buah mesin tanpa delay
4. Operasi yang berbeda pada suatu pekerjaan tidak dapat dikerjakan bersamaan.

## Penyelesaian Dengan Algoritma Genetika
Langkah-langkah  penyelesaian  Algoritma  Genetika  yaitu  inisialisasi  populasi,  nilai fitness,  seleksi,  persilangan  dan  mutasi.  Inisialisasi  populasi  dilakukan  dengan membangkitkan  beberapa  kromosom  urutan  pekerjaan  dan  kromosom  penugasan  mesin. Bentuk kromosom seperti penelitian ( Bierwirth , 1995). Kromosom-kromosom tersebut akan dimunculkan  berdasarkan  metode  heuristik  sederhana.  Kromsom  penugasan  mesin berdasarkan ( Kacem , Hammadi, & Borne, 2002) .Kromsom urutan pekerjaan menggunakan dispatching  rule ( Michael ,  2018)  yaitu Most  Operation  work  remaining , Most  operation remaining Earliest due data dan Random .
Nilai fitness menghitung penalti due windows untuk tiap-tiap kromosom akan dihitung (F(x)).  Semakin  kecil  nilai  F(x)  maka  akan  semakin  baik  kromosom  tersebut.  Dengan demikian  nilai fitness adalah 𝑓(𝑥) = 1 𝐹(𝑥) . Kromosom  terbaik  akan  disimpan  untuk dimunculkan  pada  iterasi  selanjutnya.  Hal  ini  dilakukan  agar  kromosom  tersebut  tidak mengalami perubahan-perubahan pada langkah persilangan maupun mutasi.
Proses  seleksi  dilakukan  dengan  metode Roullete  Wheel  Selection yaitu  dengan membangkitkan  sembarang  bilangan  acak r dan  memilih  kromosom  yang  memiliki  nilai kumulatif  individu  lebih  kecil  dari r untuk  tetap  bertahan.  Proses  persilangan  dilakukan dengan mempertukarkan gen antara dua kromosom yaitu kromosom pendonor dan reseptor. Kedua  kromosom  ini  akan  disebut  sebagai  kromosm  induk.  Kromosom  pendonor  akan memberikan  beberapan  gen  kepada  kromosom  reseptor  sehingga  menghasilkan  anak ( offspring )  Proses  mutasi  adalah  perubahan  gen  pada  suatu  kromosom  sehingga
menghasilkan  kromosom  baru.  Karena  penelitian  ini  merupakan Flexible  Job  Shop maka mutasi dilakukan secara dua tahap yaitu untuk urutan pekerjaan dan penugasan mesin seperti pada  penelitian    ( Piroozfard ,  Wong,  &  Wong,  2018).  Proses  ini  akan  dilakukan  secara berulang-ulang  sampai  maksimum  iterasi  (MaxGen)  tercapai.  Berikut  adalah flowchart Algoritma Genetika

## Gambar 2 Flowchart Algoritma Genetika

## Pengumpulan data dan Perbandingan Hasil
Data yang digunakan adalah kasus Flexible Job Shop dari (L Yin , X Li, L Gao, C Lu, &  Z  Zhang,  2017).  Karena  penelitian  ini  memiliki  fungsi  tujuan  yang  berbeda  maka  untuk menguji  keakuratan  algoritma  ini,  dilakukan  perbandingan  hasil  untuk  fungsi  tujuan makespan . Semakin kecil hasil untuk makespan yang maka semakin baik performa algoritam tersebut.  Sementara  untuk due  windows dilakukan  penambahan  data  untuk  { 𝑑 𝑖 𝑙 , 𝑑 𝑖 𝑢 }  pada tiap-tiap  pekerjaan  secara  acak.  Software  yang  digunakan  adalah  Matlab  2014a.  Berikut adalah flowchart dari Algoritma Genetika

## Hasil dan Pembahasan Model Matematis
Model matematis Mixed Integer Programming dengan fungsi tujuan meminumkan due windows adalah sebagai berikut:
Notasi yang digunakan
𝑖, 𝑔 : indeks job , 𝑖 = 1. . , 𝑛, 𝑔 = 1 … , 𝑛 𝑗, ℎ : indeks operasi 𝑗 = 1. . , 𝑚, ℎ = 1 … , 𝑚 𝑘 : indeks operasi 𝑘 = 1. . , 𝑜 𝑝 𝑖𝑗𝑘 : waktu pemerosesan untuk operasi 𝑂 𝑖𝑗 dengan mesin- k 𝑑 𝑖 𝑢 : batas atas waktu penyelesaian pekerjaan ke-i 𝑑 𝑖 𝑙 : batas bawah waktu penyelesaian pekerjaan ke-i
𝑇 𝑖 : tardiness pekerjaan ke-i, 𝑖 = 1. . , 𝑛 𝐸 𝑖 : earliness pekerjaan ke-i, , 𝑖 = 1. . , 𝑛 𝑐 𝑖𝑗 : waktu penyelesaian operasi 𝑂 𝑖𝑗 𝑐 𝑘 : waktu penyelesaian operasi terakhir pada mesin ke-k 𝑤 𝑒 : penalti untuk earliness 𝑤 𝑡 : penalti untuk tardiness
Variabel biner yaitu
𝑥 𝑖𝑗𝑘 = { 1,    operasi 𝑂 𝑖𝑗 diselesaikan dengan mesin − k 0,   lainnya
Fungsi  tujuan dan kendala
min 𝐷 = 𝑤 𝑒 ∑ 𝐸 𝑖 + 𝑤 𝑡 𝑛 𝑖=1 ∑ 𝑇 𝑖 𝑛 𝑖=1 (1)

## Kendala
∑ 𝑥 𝑖𝑗𝑘 = 1     ∀i, j 𝑜 𝑘=1 (2) 𝑐 𝑘 ≥ 𝑐 𝑖𝑗 . 𝑥 𝑖𝑗𝑘 (3)
𝑇 𝑖 = 𝑛 max 𝑖 = 1 {0, 𝑐 𝑖 − 𝑑 𝑖 𝑢 }                                                                                                                        (4)
𝐸 𝑖 = 𝑛 max 𝑖 = 1 {𝑑 𝑖 𝑙 − 𝑐 𝑖 , 0}                                                                                                                         (5)
𝑐 𝑖 = 𝑛 max 𝑖 = 1 {𝑐 𝑖𝑗 }                                                                                                                                      (6)
𝑐 𝑖𝑗 = 𝑠 𝑖𝑗 + (𝑝 𝑖𝑗𝑘 + 𝑥 𝑖𝑗𝑘 )    ∀i, j, k                                                                                                    (7)
𝑐 𝑖𝑗 ≤ 𝑠 𝑖(𝑗+1) ∀i, j                                                                                                                              (8)
𝑠 𝑖𝑗 + 𝑝 𝑖𝑗𝑘 ≤ 𝑠 𝑔ℎ + 𝑀(1 − 𝑦 𝑖𝑗𝑔ℎ𝑘 )   ∀i, j, g, h, k                                                                            (9)
𝑠 𝑔ℎ + 𝑝 𝑔ℎ𝑘 ≤ 𝑠 𝑖𝑗 + 𝑀𝑦 𝑖𝑗𝑔ℎ𝑘 ∀i, j, g, h, k                                                                                     (10)
𝑠 𝑖𝑗 ≥ 0, 𝑠 𝑔ℎ ≥ 0, 𝑐 𝑖𝑗 ≥ 0                                                                                                                   (11)
Persamaan (1) menunjukkan fungsi tujuan meminimumkan due windows, kendala (2) memastikan tiap operasi diselesaikan oleh satu buah mesin, kendala (3) menunjukkan waktu pemerosesan operasi terakhir pada mesin, kendala (4) dan (5) menujukkan perhitungan untuk tardiness dan earliness ,  dimana  nilai  keduanya  harus  bernnilai  positif,  kendala  (6) menunjukkan  waktu  penyelesaian  pekerjaan  yaitu  waktu  pemerosesan  terbesar  untuk pekerjaan  tersebut,  kendala  (7)  menunjukkan  waktu  penyelesaian  operasi  adalah penjumlahan  waktu  operasi  mulai  dikerjakan  dan  waktu  pemerosesan,  kendala  (8) menunjukkan  setiap  operasi  harus  dikerjakan  secara  berurutan,  kendala  (9)  dan  (10) memastikan tiap mesin hanya dapat memroses suatu pekerjaan dalam suatu selang waktu

## Penyelesaian dengan Algoritma Genetika
Data waktu pemerosesan mesin diproleh dari (Lvjiang Yin , Xinyu Li, Liang Gao, Chao Lu, & Zhao Zhang, 2017)dengan penambahan data untuk rentang waktu  keterlambatan due windows, 𝑫 𝒍 untuk earliness dan 𝑫 𝒖 untuk tardiness, maka persoalan yang akan diselesaikan seperti pada tabel 4.1
Tabel 1 Kasus 4 Job dan 5 Mesin Job Operasi 𝑴 𝟏 𝑴 𝟐 𝑴 𝟑 𝑴 𝟒 𝑴 𝟓 𝑫 𝒍 𝑫 𝒖 𝑱 𝟏 𝑂 11 9 6 - 12 - 10 12 𝑂 12 - - 6 - 7 𝑂 13 - 2 4 - - 𝑱 𝟐 𝑂 21 5 - - 7 9 7 12 𝑂 22 - 4 6 8 - 𝑂 23 - - 4 - 8 𝑱 𝟑 𝑂 31 3 - - - - 8 13 𝑂 32 - 3 - 5 - 𝑂 33 8 - 10 - 13 𝑱 𝟒 𝑂 41 6 - 9 - 10 9 12 𝑂 42 - 3 - - - 𝑂 43 2 - - 4
Untuk  memastikan  program  sudah  berjalan  dengan  baik,  dilakukan  pengujian  dengan menggunakan penelitian (Lvjiang Yin et al., 2017) sebagai perbandingan untuk kasus single objective makespan. Parameter  yang  digunakan  adalah,  jumlah  populasi  =200,  jumlah
iterasi=100,  probabilitas  persilangan=0,9,  probabilitas  mutasi=0,8,  dan  probabilitas  elit=0,1 Pada penelitian ini diproleh hasil 17 yang mana sama dengan hasil pada penelitian tersebut.
Untuk  penyelesaian due  windows dilakukan  pada  beberapa  kombinasi  bobot  untuk earliness ( 𝑊 𝑒 ) dan bobot untuk tardiness (𝑊 𝑡 ) . Berikut hasil yang diproleh Tabel 2 Kasus 4 Job dan 5 Mesin Bobot Due Windows Makespan 𝑾 𝒆 = 𝟎, 𝟐𝟓; 𝑾 𝒕 = 𝟎, 𝟕𝟓 11,25 20 𝑾 𝒆 = 𝟎, 𝟓; 𝑾 𝒕 = 𝟎, 𝟓 7,5 20 𝑾 𝒆 = 𝟎, 𝟕𝟓; 𝑾 𝒕 = 𝟎, 𝟐𝟓 3,75 20 Dari tabel terlihat penalti
terkecil diproleh pada
𝑊 𝑒 = 0,75; 𝑊 𝑡 = 0,25 .  Hal  ini  terjadi  karena  penalti  yang  diberikan  apabila  pengerjaan terlambat  lebih  besar  daripada  pengerjaan  yang  terlalu  cepat.  Bentuk Gantt  Chart untuk permasalahan tersebut adalah sebagai berikut.

## Gambar 3 Gantt Chart
Jika  dilihat  pada  diagram Gantt  Chart due  windows juga  berkaitan  erat  dengan  nilai makespan,  semakin  kecil  due  windows  yang  didapat  maka  semakin  kecil  nilai makespan yang diproleh. Dari gambar
terlihat hanya pekerjaan
𝑱 𝟐 dan 𝑱 𝟒 yang  waktu  penyelesaiannya  berada  pada  selang  waktu  yang  diberikan. 𝑱 𝟐 diselesaikan  pada  waktu  11,  sehingga  berada  pada  rentang  {7,12},  sementara 𝑱 𝟒 diselesaikan pada waktu 11 berada pada rentang  {9,12}

## Kesimpulan
Due  Windows menjadi  alternatif  untuk  Penjadwalan  Flexible  Job  Shop  terkait  dengan penyelesaian  pekerjaan.  Selang  waktu  yang  diberikan  memberikan  toleransi  pada penyelesaian  pekerjaan  sehingga  lebih  sesuai  dengan  kehidupan  sehari-hari.  Performa  dari
Algoritma Genetika cukup baik dalam menyelesaikan kasus Flexibel Job Shop , terbukti hasil yang  cukup  baik  terkait  dengan  hasil makespan. Penelitian  ini  dapat  dikembangkan  dengan melakukan penggabungan algoritma ( hybrid) untuk hasil yang lebih baik.

## Bibliografi
Ahmadi,  E.,  Zandieh,  M.,  Farrokh,  M.,  &  Emami,  S.  M.  (2016). A  multi  objective optimization  approach  for  flexible  job  shop  scheduling  problem  under  random machine breakdown by evolutionary algorithms . Computers  & Operations Research , 73, 56-66.
Ahmadian, M. M., Salehipour, A., & Cheng, T. (2021). A meta-heuristic to solve the just-in- time  job-shop  scheduling  problem . European  Journal  of  Operational  Research, 288 (1), 14-29.
Alzahrani,  J. S. (2019). Job Shop Scheduling Considering Makespan, Penalties Of  Machine Idling,  And  Job  Out  Of  Time . International  Journal  of  Research-Granthaalayah , 7(1), 73-82.
Amjad, M. K., Butt, S. I., Kousar, R., Ahmad, R., Agha, M. H., Faping, Z., . . . Asgher, U. (2018). Recent research trends in genetic algorithm based flexible job shop scheduling problems . Mathematical Problems in Engineering, 2018 .
Bierwirth,  C.  (1995). A  generalized  permutation  approach  to  job  shop  scheduling  with genetic algorithms . Operations-Research-Spektrum, 17 (2), 87-92.
Idowu, G. A., Adamu, M. O., & Sawyerr, B. S. (2020). Hybrid Metaheuristic for Just In Time Scheduling  in  a  Flow  Shop  with  Distinct  Time  Windows . International  Journal  of Mathematical  Sciences  and  Optimization:  Theory  and  Applications,  2020 (1),  741- 756.
Kacem,  I.,  Hammadi,  S.,  &  Borne,  P.  (2002). Approach  by  localization  and  multiobjective evolutionary  optimization  for  flexible  job-shop  scheduling  problems . IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 32 (1), 1-13.
Kim, J.-G., Jun, H.-B., Bang, J.-Y., Shin, J.-H., & Choi, S.-H. (2020). Minimizing Tardiness Penalty  Costs  in  Job  Shop  Scheduling  under  Maximum  Allowable  Tardiness . Processes, 8 (11), 1398.
Kuhpfahl, J. (2015). Job shop scheduling with consideration of due dates: Potentials of local search based solution techniques : Springer.
Lin,  S.-S.  (2020). Due-Window  Assignment  and  Resource  Allocation  Scheduling  with Truncated  Learning  Effect  and  Position-Dependent  Weights . Discrete  Dynamics  in Nature and Society, 2020 .
Marzouki, B., Driss, O. B., & Ghédira, K. (2018). . Solving distributed and flexible job shop scheduling  problem  using  a  chemical  reaction  optimization  metaheuristic . Procedia Computer Science 126 , 1424-1433.
Michael, L. P. (2018). Scheduling: theory, algorithms, and systems : Springer.
Piroozfard, H., Wong, K. Y., & Wong, W. P. (2018). Minimizing total carbon footprint and
total late work criterion in flexible job shop scheduling by using an improved multi- objective genetic algorithm . Resources, Conservation and Recycling , 128, 267-283.
Saudagar, S., Kamboj, A., Mohan, N., Patil, S., & Powar, N. (2020). Resource Allocation and Task Scheduling with Skill Level and Time Bound Constraints . International Journal of Industrial and Manufacturing Engineering, 14 (9), 732-738.
Yin, L., Li, X., Gao, L., Lu, C., & Zhang, Z. (2017). A novel mathematical model and multi- objective  method  for  the  low-carbon  flexible  job  shop  scheduling  problem . Sustainable Computing: Informatics and Systems 13, 15-30.