IV PENYELESAIAN MASALAH PRODUKSI DAN DISTRIBUSI ZERO INVENTORY

11

Tabel 3 Tabel kefisibelan jadwal dengan setiap kemungkinan pasangan pelanggan yang dihapus dari jadwal dan nilai G   untuk setiap jadwal fisibel

 \

(i, k )

 \{1,3}  0, 2, 4,5

1,3 1, 4   2,3  2, 4   3,3  3, 4   3,5  4, 4   4,5  5,5

 \{1, 4}  0, 2,3,5

 \{2,3}  0,1, 4,5  \{2, 4}  0,1,3,5

 \{3}  0,1, 2, 4,5  \{3, 4}  0,1, 2,5 *

 \{3,5}  0,1, 2, 4  \{4}  0,1, 2,3,5

 \{4,5}  0,1, 2,3  \{5}  0,1, 2,3, 4

Jadwal  \{3, 4}  0,1, 2,5 * merupakan jadwal yang takfisibel, maka  \{3, 4} menjadi input barisan parsial berikutnya dan pencarian berlanjut sampai barisan parsial  \{3, 4,5}  0,1, 2 ditemukan, dengan nilai

G    70.

Kefisibelan

G  

fisibel

110

fisibel

140

fisibel

100

fisibel

130

fisibel

140

takfisibel

-

fisibel

100

fisibel

170

fisibel

130

fisibel

160

Berdasarkan persamaan (12), diperoleh batas bawah dari total permintaan yang fisibel ialah G0  170 (penghitungan lengkap dapat dilihat di Lampiran 7). Berikut diberikan gambar bagan produksi dan distribusi jadwal   0,1, 2,3,5 dengan G( )  170.

5

5

3

3

2

2

1

1 3

7

13

17

21

produksi i

= pelanggan ke-i

27

30 31

36 waktu

distribusi = time window

= waktu tunggu

Gambar 11 Bagan produksi dan distribusi jadwal   0,1, 2,3,5 .

IV PENYELESAIAN MASALAH PRODUKSI DAN DISTRIBUSI ZERO INVENTORY Metode heuristik digunakan hanya untuk mencari batas bawah. Jadwal fisibel yang ditemukan menggunakan metode heuristik tidak terjamin keoptimalannya, maka jumlah permintaan dari jadwal yang ditemukan menggunakan metode heuristik dijadikan batas bawah untuk mencari jadwal yang optimal. Pencarian jadwal yang akan dibahas dalam karya ilmiah ini menggunakan proses pencarian pencabangan dan pembatasan menggunakan search tree. Untuk setiap barisan pelanggan S yang diberikan,

didefinisikan search tree sebagai berikut. Misalkan simpul i menyatakan pelanggan i, dengan 1  i  n, dan simpul 0 menyatakan pabrik. Bersumber dari setiap simpul i, dengan 0  i  n, terdapat tepat n  1 cabang yang berbeda yang mengarah ke simpul j , dengan j  i  1, i  2,..., n  1, dan n. Artinya, dari simpul 0, terdapat n cabang yang keluar mengarah ke simpul 1, 2,..., n pada level 1. Dari simpul 1 pada level 1 pada tree, terdapat

12

n  1 cabang yang keluar mengarah ke simpul 2,3,..., n pada level 2, sementara dari simpul n  1 pada level 1 hanya mempunyai 1 cabang keluar yang mengarah ke simpul n di level 2. Tree yang dihasilkan merupakan tree yang tidak seimbang, memiliki n  1 level dan



n! total simpul. k 0,1,.., n k ! n  k  ! Gambar 12 menunjukkan contoh search tree dengan semua kemungkinan jadwal dengan n  5.

memiliki

Gambar 12 Search tree dengan semua kemungkinan jadwal dengan n  5. Dapat dilihat, sembarang barisan parsial sepanjang cabang dari simpul 0 ke sembarang simpul i dalam tree tersebut mendefinisikan suatu jadwal  . Misalkan [ k ]  [0],[1],...,[i],[k ] |1  [k ]

n ialah barisan parsial fisibel yang menunjukkan urutan dari root (pabrik) ke simpul (pelanggan) pada level k sepanjang cabang. Beberapa definisi di bawah ini digunakan untuk menentukan parameter yang terkait dengan  [ k ] . Definisi

21

(Keterlambatan waktu pengiriman simpul [i]) Keterlambatan waktu pengiriman simpul [i]  [ k ] , ialah

(14) s[Ti]  b[i ]  T[i ]  w[i ] yang menyatakan penundaan maksimum dalam waktu pengiriman ke simpul [i] tanpa membuat pengiriman terlambat. (Armstrong et al. 2008)

Definisi

22

(Keterlambatan waktu pengiriman jadwal  [ k ] )

Keterlambatan pengiriman pada barisan parsial  [ k ] , ialah sT[ k ]  min{s[Ti] | [i]  [ k ]}

(15)

yang menyatakan penundaan maksimum pada waktu pengiriman dalam barisan parsial  [ k ] . (Armstrong et al. 2008) Contoh 14 Jadwal  5 \{4}  0,1, 2,3,5 fisibel dengan s1T  3

s2T  5

adalah jadwal

s3T  6 s5T  1

sT5 \{4}  1

(proses penghitungan dapat dilihat di Lampiran 8). s1T  3 berarti penundaan maksimum waktu pengiriman ke simpul 1 adalah 3 satuan waktu dan sT5 \{4}  1 berarti setiap simpul di dalam  5 \{4} dapat ditunda sebanyak 1 satuan waktu tanpa mengubah  5 \{4}. Bagan produksikefisibelan distribusi diberikan pada Gambar 13 berikut.

13

5

5

3

3

2

2

1 3

7

1 17 18

13

22

28

produksi i

31

36 waktu

distribusi

= pelanggan ke-i

= time window

= penundaan pengiriman

Gambar 13 Bagan produksi dan distribusi jadwal  5 \{4}  0,1, 2,3,5 setelah distribusi ditunda 1 satuan waktu.

 [ k ] tanpa melanggar kendala lifespan di

Definisi 23 (Keterlambatan lifespan dari simpul [i]) Keterlambatan lifespan dari simpul [i ],

setiap simpul. (Armstrong et al. 2008) Contoh 15 Berdasarkan Contoh 13 didapatkan barisan parsial yang fisibel yaitu 

dengan [i]   [ k ] , dinotasikan sebagai s[Li] , dengan s[Li]  B  [T[i ] 



d h 1,..,i [ h]

/ r]

(16)

 5 \{4}  0,1, 2,3,5 dengan

mendefisinisikan penundaan maksimum waktu pengiriman ke simpul [i ] tanpa membuat produk kadaluarsa. (Armstrong et al. 2008)

sL[ k ]

adalah

s2L  2

s5L  3

(proses perhitungan dapat dilihat di Lampiran 9). s1L  4 berarti penundaan maksimum waktu pengiriman ke simpul 1 adalah 4 satuan waktu dan sL5 \{4}  2 berarti setiap simpul

keterlambatan

lifespan dari barisan parsial  [ k ] , dengan sL[ k ]  min{s[Li] | [i]  [ k ]}

s3L  4

sL5 \{4}  2

Definisi 24 (Keterlambatan lifespan dari jadwal  [ k ] ) Misalkan

s1L  4

dalam  5 \{4} dapat ditunda sebanyak 2 satuan waktu tanpa membuat produk kadaluarsa di setiap simpul pada  5 \{4}. Bagan produksi dan distribusi diberikan pada Gambar 14 berikut.

(17)

sL[ k ] mendefinisikan penundaan maksimum

pada waktu pengiriman pada barisan parsial

5

5

3

3

2

2

1

1 3

7

13

17

19

23

produksi i

= pelanggan ke-i

29

32

37 waktu

distribusi = time window

= penundaan pengiriman

Gambar 14 Bagan produksi dan distribusi jadwal  5 \{4}  0,1, 2,3,5 setelah distribusi ditunda 2 satuan waktu.

14

Penyelesaian masalah produksi dan distribusi zero inventory adalah sebagai berikut. Analisis yang akan dibahas memperkenalkan skema pencabangan yang menjamin pencarian cabang hanya untuk jadwal yang fisibel dan skema pembatasan yang mem-fathom solusi fisibel yang lebih kecil dari batas bawah. 4.1 Proses Pencabangan Dalam bahasan sebelumnya  [ k ] ialah barisan parsial fisibel yang menunjukkan urutan dari root (pabrik) ke simpul (pelanggan) pada level k sepanjang cabang. Misalkan  [ k ] dipadankan dengan [k] pada level k pada search tree, dan misalkan [k ]  i, 1  i  n. Ketika pencarian sampai pada simpul [k], dengan [k ]  i, barisan parsial

 [ k ] dan parameter sT[ k ] dan sL[ k ] dapat diketahui. Bersumber dari simpul [k ]  i, terdapat tepat n  i cabang ke simpul i  1,..., j,..., n. Misalkan simpul j, dengan i  j  n, adalah salah satu kandidat simpul yang berpadanan pada level k  1. Jika dilakukan pencabangan dari simpul i ke simpul j, maka barisan parsial pada simpul j  [k  1], yaitu  [ k 1] , dibentuk dengan menambahkan simpul j ke ujung  [ k ] , dituliskan  [ k 1]  [ k ] || j . (Armstrong et al. 2008) Pada

 [ k 1] ,

truk

pengangkut

harus

menunggu di pabrik sampai pesanan pelanggan j selesai diproduksi, dan waktu kedatangan truk ke pelanggan pertama di  [ k 1] ditunda selama   d j / r. Jika waktu pengiriman pada simpul pertama pada  [ k ] ditunda selama 

  min{sT[ k ] , sL[ k ] },

satuan waktu, dengan maka

setidaknya

pengiriman ke satu simpul di  [ k ] menjadi takfisibel sehingga membuat barisan parsial [k ] menjadi takfisibel. Jadi aturan pencabangan dari simpul [k ]  i ke simpul j untuk setiap barisan parsial  [ k ] ialah sebagai berikut: jika salah satu kondisi di bawah ini dilanggar: d j r  min{sT[ k ] , sL[ k ] }, atau (18)

T[k 1]  T j  b j

(19)

maka pencabangan tidak dilakukan. (Armstrong et al. 2008) 4.2 Proses Pembatasan Misalkan  [ k ] ialah sembarang barisan parsial pada level k , 1  k  n, pada search tree. Jumlah maksimum permintaan yang dapat dipenuhi oleh sembarang cabang yang memuat  [ k ] sebagai barisan parsial ialah



tidak lebih dari

h [ k ]

dh  g , dengan [k ]

[ k ]  { j | [k ]  j  n} adalah himpunan dari kandidat pesanan yang ditambahkan ke dalam  [ k ] untuk membentuk jadwal akhir. Nilai g

dapat ditentukan dengan menyelesaikan [k ]

masalah knapsack 0 – 1 berikut: Max g  djX j



[k ]

terhadap

 

j

j[ k ]

d j X j  r.min{sT[ k ] , sL[ k ] }

[ k ]

X j  {0,1}, j   [ k ]

dengan Xj = 1 jika pelanggan j dipilih sebagai kandidat pelanggan yang menerima pengiriman dan Xj = 0 jika selainnya. (Armstrong et al. 2008) Proposisi 3 Misalkan G0 adalah batas bawah dari G* . Untuk sembarang simpul [k] di level k pada search tree, 1  k  n, yang berpadanan dengan barisan parsial  [ k ] , jika



h [ k ]

dh  g

 G0 ,

maka

semua

[k ]

simpul keturunan dari simpul [k] harus difathom. (Armstrong et al. 2008) Bukti Proposisi 3 dapat dilihat di Lampiran 10. Proposisi 3 berfungsi untuk mendapatkan kandidat pelanggan yang akan masuk ke dalam jadwal akhir. Setelah kandidat pelanggan didapatkan, nilai G( ) dari  yang didapatkan diperiksa apakah lebih besar dari batas bawah atau tidak. Jika lebih besar, maka jadwal yang optimal telah ditemukan, jika tidak maka pencarian kandidat pelanggan dilakukan sampai diperoleh jadwal  optimal. Dalam Gambar 16 diberikan skema keseluruhan penyelesaian masalah produksi dan distribusi zero inventory dalam bentuk diagram alir.

15

Tingkat produksi pabrik terbatas

Permintaan

Pelanggan memesan produk

Pesanan diproduksi

Apakah jadwal pengiriman fisibel?

Diperoleh

Ya

Solusi optimal ditemukan

Tidak Umur produk terbatas

Time window

Diperoleh

Penghapusan pelanggan dengan kriteria seperti pada Proposisi 1 & 2

dan diperoleh

batas bawah

Tidak

dari total

Ya

permintaan jadwal optimal

Ya

Mencari yang optimal dengan metode search tree (inisiasi setiap pelanggan ke-[i] ke dalam )

Apakah jadwal pengiriman fisibel? Tidak

Apakah

Proses pencabangan (penghitungan

Pelanggan ke-[i] menjadi kandidat pelanggan yang masuk ke dalam jadwal

dan

dari jadwal

)

Tidak

Apakah memenuhi kondisi (18) & (19)

Ya

Tidak

Proses pembatasan (mencari menggunakan masalah knapsack)

Apakah Proposisi 3 dipenuhi?

Ya

Semua simpul yang bersumber dari simpul [i] (pada search tree) di-fathom

Gambar 15 Skema penyelesaian masalah produksi dan distribusi zero inventory.

16

customer sequence yang ditulis oleh Ronald Armstrong, Su Gao, dan Lei Lei pada tahun 2008. Semua detail penghitungan diberikan di Lampiran 8. Dengan n  7, maka tree yang dihasilkan akan mempunyai 7!  128 simpul. Tree k 0,1,..,7 k ! 7  k  !

4.3

Contoh Penggunaan Proses Pencabangan dan Pembatasan Misalkan terdapat 7 pelanggan yang memesan produk dengan data permintaan dan time window terdapat pada Tabel 4 serta data waktu pengiriman antarpelanggan terdapat pada Tabel 5. Misalkan umur produk B  26, dan tingkat produksi pabrik r  10. Jadi

S  0,1, 2,3, 4,5,6,7 .

Data



tersebut merupakan tree lengkap sebelum dilakukan proses pencabangan dan pembatasan.

diambil dari

artikel berjudul A zero-inventory production and distribution problem with a fixed

Tabel 4 Pesanan dan time window pelanggan Pelanggan j

  Waktu awal penerimaan  a j  Waktu akhir penerimaan  b j  Pesanan pelanggan d j

1 2

2 3 4

3 4 3 5

Langkah 0 Inisialisasi   S , maka didapatkan barisan parsial  , yaitu [7]  [0],[1],[2],[3],[4],[5],

[6],[7] . Menurut Definisi 18,  merupakan jadwal

yang

2

3

4

5

6

7

30

20

40

60

40

30

50

15

18

20

31

32

36

38

20

23

28

36

35

39

39

Tabel 5 Waktu pengiriman (dalam satuan waktu) Waktu pengiriman  i , j

(i, j ) 0 1 2 3 4 5 6

1

takfisibel

karena

[i ]  0,

i   . Karena  [7] merupakan jadwal yang takfisibel, yang bermakna pengiriman akan mengalami keterlambatan jika semua pesanan dipenuhi, maka harus ada pelanggan yang dihapus dari  [7] .

4 5 6 5 7

5 3 4 4 2 6

6 6 4 7 4 4 6

7 4 3 4 6 2 4 5

Langkah 1 Akan digunakan Proposisi 1 dan 2, serta (13a) dan (13b) untuk menentukan batas bawah. Diketahui p[4]  [5] . Menurut Proposisi 1, penghapusan pelanggan [1], [2], dan [3] tidak akan mengubah ketakfisibelan pelanggan [5]. Kemudian menurut Proposisi 2 pelanggan [5] adalah pelanggan yang mengalami keterlambatan pengiriman dan pelanggan [4] adalah pelanggan terdekat yang memesan sebelum pelanggan [5], maka

*  {i*, k*}, dengan i*  k*, yang mungkin adalah ({(i, k ) | v  i  k  n}), yaitu {4}, {4,6}, {4,7}, {6}, {6,7}, dan {7}. Kefisibelan jadwal dengan setiap  pada iterasi pertama akan disajikan dalam tabel berikut.

17

Tabel 6 Tabel kefisibelan jadwal dengan setiap kemungkinan pasangan pelanggan yang dihapus dari jadwal dan nilai G   pada iterasi pertama

 [ n] \ 

 i, k 

Kefisibelan

G  

[7] \{[4]}  [0],[1],[2],[3],[5],[6],[7] *

(4, 4)

takfisibel

-

[7] \{[4],[6]}  [0],[1],[2],[3],[5],[7] *

(4, 6)

takfisibel

-

[7] \{[4],[7]}  [0],[1],[2],[3],[5],[6]

(4, 7)

fisibel

160

[7] \{[6]}  [0],[1],[2],[3],[4],[5],[7] *

(6, 6)

takfisibel

-

[7] \{[6],[7]}  [0],[1],[2],[3],[4],[5] *

(6, 7)

takfisibel

-

[7] \{[7]}  [0],[1],[2],[3],[4],[5],[6] *

(7, 7)

takfisibel

-

[7] \{[4]}, [7] \{[4],[6]}, [7] \{[6]}, [7] \{[6],[7]}, dan [7] \{[7]}

berlanjut sampai barisan parsial fisibel ditemukan. Berikut akan disajikan pada Tabel 7 jadwal fisibel setelah dilakukan beberapa iterasi dengan nilai G   .

Jadwal

merupakan jadwal yang takfisibel, maka jadwal-jadwal tersebut menjadi input barisan parsial iterasi berikutnya dan pencarian

Tabel 7 Tabel jadwal fisibel setelah dilakukan beberapa iterasi  [ n] \  pada iterasi pertama  [ n] \  saat jadwal fisibel

G  

[7] \{[4]}  [0],[1],[2],[3],[5],[6],[7]

[7] \{[4],[7]}  [0],[1],[2],[3],[5],[6]

160

[7] \{[4],[6]}  [0],[1],[2],[3],[5],[7]

[7] \{[4],[6],[7]}  [0],[1],[2],[3],[5]

130

[7] \{[6]}  [0],[1],[2],[3],[4],[5],[7]

[7] \{[5],[6],[7]}  [0],[1],[2],[3],[4]

150

[7] \{[6],[7]}  [0],[1],[2],[3],[4],[5]

[7] \{[4],[5],[6],[7]}  [0],[1],[2],[3]

90

[7] \{[7]}  [0],[1],[2],[3],[4],[5],[6]

[7] \{[4],[5],[7]}  [0],[1],[2],[3],[6]

120

Dapat dilihat pada Tabel 7 diperoleh jadwal yang fisibel. Berdasarkan persamaan (12), diperoleh batas bawah G0  160 (penghitungan lengkap dapat dilihat di Lampiran 11). Berikut bagan jadwal produksi

dan

distribusi dari barisan parsial [7] \ [4],[7] akan diberikan pada Gambar

16 berikut.

6

6

5

5

3

3

2

2

1

1 3

5

9

13

16

18

22

produksi i

= pelanggan ke-i

27

32

38 waktu

distribusi = time window

= waktu tunggu

Gambar 16 Bagan jadwal produksi dan distribusi dari barisan parsial [7] \ [4],[7]. Langkah 2 Setelah didapatkan batas bawah, jadwal yang optimal akan ditentukan oleh search tree menggunakan metode pencabangan dan pembatasan. Karena  [7] takfisibel, maka

simpul yang akan dihapus dari  [7] harus ditentukan. Berikut akan ditampilkan proses pencarian jadwal sampai ditemukan jadwal yang optimal.

5

4

3

2

6

7

1

5

4

7

5

7

6

4

7

Gambar 17 Search tree untuk pencarian jadwal optimal.

6

3 5

6

7

0

18