Optimization Story: Menyelesaikan Masalah Schedulling Produksi dengan Algoritma Travelling Salesperson Problem

Mungkin rekan-rekan bingung saat membaca judul dari tulisan ini.

Bagaimana caranya algoritma yang biasa digunakan untuk menentukan rute terbaik salesperson bisa digunakan untuk menyelesaikan masalah penjadwalan?

Dalam dunia optimization, ada banyak sekali bentuk dari penjadwalan. Setidaknya saya pernah menuliskan 4 kasus penjadwalan di blog saya ini:

1. Pemilahan jadwal peserta training,
2. Penjadwalan perawat di rumah sakit - detail,
3. Penjadwalan interviewer di lokasi survey,
4. Penjadwalan shift tenaga kesehatan di rumah sakit.

Kali ini saya akan menuliskan salah satu kasus penjadwalan lain terkait jadwal produksi suatu industri. Masalah ini masuk ke dalam contoh kasus sederhana.

---

Perusahaan Cat

Suatu perusahaan cat memproduksi 4 warna cat yaitu:

• Putih,
• Kuning,
• Hitam, dan
• Merah.

Keempat cat tersebut diproduksi di mesin-mesin yang sama, sehingga ada keperluan untuk mencuci mesin-mesin (cleaning) tersebut di antara produksi 2 cat yang berbeda warna.

Kita mempunyai masalah untuk menentukan urutan produksi cat harian yang optimal, yakni urutan produksi cat yang menghasilkan total waktu pencucian paling kecil.

Urutan harian ini akan dipakai tiap hari, karena perusahaan setiap hari harus memproduksi keempat cat tersebut.

Tabel berikut menampilkan waktu pencucian antara produksi cat di suatu baris jika akan dilanjutkan dengan cat di suatu kolom.

## Matriks Cleaning Mesin Cat (dalam menit)

	putih	kuning	hitam	merah
putih	~	5	12	14
kuning	15	~	20	20
hitam	35	40	~	28
merah	30	35	25	~

Urutan produksi cat seperti apa yang meminimalkan waktu cleaning?

---

Sebenarnya masalah di atas mirip sekali dengan Travelling Salesperson Problem, yakni suatu masalah optimization yang mencari rute terpendek dari beberapa tempat.

Kenapa kok mirip dengan TSP?

Jika pada TSP kita bertujuan untuk meminimalisir jarak dan/atau waktu tempuh, maka di kasus ini kita akan meminimalisir waktu cleaning.

Formulasi Matematika

Menggunakan formula Miller-Tucker_Zemlin, saya akan memecahkan masalah ini.

Misalkan saya tuliskan:

• sebagai himpunan warna cat yang diproduksi.
  • 1 menunjukkan putih,
  • 2 menunjukkan kuning,
  • 3 menunjukkan hitam, dan
  • 4 menunjukkan merah.
• menunjukkan waktu cleaning antara produksi cat warna ke , dimana .

Mari kita bangun beberapa constraints dari kasus ini.

Constraint dasar adalah tidak boleh dari cat warna yang sama menuju cat warna yang sama.

Constraint pertama adalah satu warna hanya bisa diikuti oleh satu warna yang lain. Maksudnya dari warna ke , hanya bisa diikuti unique oleh warna ke . Saya tuliskan ekspresinya menjadi:

Constraint kedua adalah satu warna hanya bisa berasal dari satu warna yang lain. Maksudnya dari warna , hanya bisa berasal unique dari warna ke . Saya tuliskan ekspresinya menjadi:

Kedua constraints yang di atas ternyata belum cukup untuk menjelaskan kondisi real-nya. Kenapa? Kita harus pastikan:

Semua terlewati. Solusi yang ada harus melibatkan semua warna.

Lantas bagaimana caranya?

Misalkan saya definisikan:

Sebagai urutan tour. Misalkan , artinya kota dikunjungi terlebih dahulu baru kota .

Lalu saya akan paksakan agar rute yang ada tidak memiliki subtour dengan:

---

Solver R

Berikut adalah algoritma di R-nya:

# memanggil libraries
library(ompr)
library(ompr.roi)
library(ROI.plugin.glpk)

# memasukkan matriks jarak
distance = as.matrix(data)

# banyaknya cat
n = 4

# menuliskan model matematika
model <- MIPModel() %>%
  # decision variabel I
  # berupa binary, 1 jika dari i ke j,
  # 0 jika lainnya
  add_variable(x[i, j], i = 1:n, j = 1:n, 
               type = "integer", lb = 0, ub = 1) %>%
  # dummy variabel
  # agar memastikan tidak ada subtour
  add_variable(u[i], i = 1:n, lb = 1, ub = n) %>% 
  # objective function
  # minimize waktu cleaning
  set_objective(sum_expr(distance[i, j] * x[i, j], i = 1:n, j = 1:n), "min") %>%
  # tidak boleh dari dan ke warna yang sama
  set_bounds(x[i, i], ub = 0, i = 1:n) %>%
  # pergi dari setiap warna cat
  add_constraint(sum_expr(x[i, j], j = 1:n) == 1, i = 1:n) %>%
  # masuk ke setiap warna cat
  add_constraint(sum_expr(x[i, j], i = 1:n) == 1, j = 1:n) %>%
  # ensure no subtours (arc constraints)
  add_constraint(u[i] >= 2, i = 2:n) %>% 
  add_constraint(u[i] - u[j] + 1 <= (n - 1) * (1 - x[i, j]), i = 2:n, j = 2:n)

model

## Mixed integer linear optimization problem
## Variables:
##   Continuous: 4 
##   Integer: 16 
##   Binary: 0 
## Model sense: minimize 
## Constraints: 20

Saya solve sehingga hasilnya:

result <- solve_model(model, with_ROI(solver = "glpk", verbose = TRUE))

## <SOLVER MSG>  ----
## GLPK Simplex Optimizer, v4.65
## 20 rows, 20 columns, 56 non-zeros
##       0: obj =   0.000000000e+00 inf =   1.100e+01 (11)
##      14: obj =   8.500000000e+01 inf =   1.110e-16 (0)
## *    19: obj =   7.966666667e+01 inf =   4.441e-16 (0)
## OPTIMAL LP SOLUTION FOUND
## GLPK Integer Optimizer, v4.65
## 20 rows, 20 columns, 56 non-zeros
## 16 integer variables, 12 of which are binary
## Integer optimization begins...
## Long-step dual simplex will be used
## +    19: mip =     not found yet >=              -inf        (1; 0)
## +    21: >>>>>   8.300000000e+01 >=   8.300000000e+01   0.0% (2; 0)
## +    21: mip =   8.300000000e+01 >=     tree is empty   0.0% (0; 3)
## INTEGER OPTIMAL SOLUTION FOUND
## <!SOLVER MSG> ----

Berikut adalah solusinya:

solution = get_solution(result, x[i, j]) %>% filter(value > 0)
solution

##   variable i j value
## 1        x 4 1     1
## 2        x 1 2     1
## 3        x 2 3     1
## 4        x 3 4     1

result

## Status: optimal
## Objective value: 83

Total waktu cleaning yang dihasilkan adalah 83 menit dengan urutan sebagai berikut:

putih - kuning - hitam - merah.

---

if you find this article helpful, support this blog by clicking the ads.