## ALJABAR MAX PLUS DAN APLIKASINYA: MODEL SISTEM PRODUKSI SEDERHANA
( Max Plus Algebra and It’s Aplication: Model of Simple Production System )

## Tri Siwi Nasrulyati
Pascasarjana Matematika FMIPA ITS Surabaya Email: trisiwi@its.ac.id
Abstact: This paper discusses the basic understanding of max plus algebra and an example of its application will be given. Next will be discussed a simple production system model with three machines.
Keywords: Max Plus Algebra, Simple Production MSC 2020: CIS-260536

## 1. Pendahuluan
Pada  masa  ini  teknologi  yang  semakin  canggih  membuat  pengembangan  ilmu pengetahuan, termasuk matematika, terus dilakukan dan berkembang dengan pesat. Salah satu  perkembangan  ilmu  matematika  yang  sangat  berguna  adalah  aljabar  max  plus. Aljabar max plus sebagai salah satu cabang matematika modern mempunyai dua operasi aritmatik  dasar,  yaitu  pemaksimalan  dan  penjumlahan  [1].  Banyak  sistem  yang menggunakan  aljabar  max  plus  dalam  kaitannya  dengan  sistem  even  diskrit.  Seperti sistem  manufaktur,  telekomunikasi,  transportasi,  dan  lain  sebagainya  [3].  Sistem  even diskrit adalah sistem dinamik yang berkembang dalam waktu dengan kemunculan even pada interval waktu tak tentu [2]. Secara garis besar, sistem even diskrit dinamik dapat dideskripsikan dengan menggunakan dua paradigma, yaitu sinkronisasi (keselarasan) dan konkurensi. Sinkronisasi mengharuskan tersedianya beberapa sumber pada suatu waktu yang sama. Sedangkan konkurensi muncul ketika pengguna suatu sistem harus memilih satu dari beberapa sumber (dalam sistem manufaktur, sebuah pekerjaan dapat dieksekusi pada salah satu atau beberapa mesin yang menangani pekerjaan tersebut).
Suatu sistem dengan vektor keadaan berubah seiring dengan berubahnya waktu sering dijumpai.  Setiap  detik,  vektor  keadaan  diharapkan  berubah.  Sistem  seperti  ini  disebut sistem terkendali waktu (time-driven sistem). Dalam sistem semacam ini, variabel waktu k merupakan variabel bebas dan transisi keadaan (state) diselaraskan dengan waktu. Hal ini mengandung arti bahwa sebuah kejadian muncul dan menyebabkan perubahan vektor keadaan.
Selain sistem seperti yang telah disebutkan di atas, sering dijumpai pula suatu sistem yang tersusun berdasarkan waktu dengan kemunculan kejadiannya adalah pada suatu interval waktu  tertentu.  Hal  ini  mengandung  makna  bahwa  keadaan  berubah  tidak  harus bersamaan  dengan  waktu.  Dalam  kasus  ini  berubahnya  keadaan  merupakan  hasil  dari
suatu kejadian yang selaras dan kemudian waktu menjadi suatu variabel bebas. Variabel k dalam sistem ini adalah suatu pengukur kejadian. Sistem semacam ini disebut dengan sistem terkendali kejadian (event-driven sistem) [2].
Sistem even diskrit didefinisikan sebagai suatu sistem terkendali kejadian (event-driven sistem)  yang  mempunyai  keadaan  diskrit.  Terdapat  beberapa  teknik  analisa  dan pemodelan sistem even diskrit seperti teori antrian, aljabar max plus, analisis gangguan, simulasi  komputer,  dan  lain  sebagainya.  Sistem  even  diskrit  menjadi  suatu  sistem persamaan linear ketika diformulasikan ke dalam aljabar max plus.
Untuk  memberikan  motivasi,  pada  bagian  selanjutnya  dalam  paper  ini  akan  diberikan contoh pemakaian dari aljabar max plus linier sistem. Tetapi sebelumnya  dijelaskan dulu secara  singkat  pengertian  dari  aljabar  max  plus    dan  notasi-notasi  yang  digunakan. Kemudian akan dijekaskan cara untuk mengkonstruksi matriks keadaan dari suatu sistem produksi sederhana dengan  tiga unit mesin. Sebagai penutup diberikan beberapa catatan dari apa yang dibahas  dan saran.

## 2. Hasil dan Pembahasan

## Aljabar Max Plus
Di sini diberikan secara singkat pengenalan konsep dasar dari aljabar max plus yang akan digunakan untuk pembahasan berikutnya. Semesta pembicaraan aljabar max plus adalah bilangan real ditambah    . Selanjutnya himpunan
} { ε  R ditulis max R dengan R adalah himpunan bilangan real. Operasi dasar dari aljabar max plus adalah maksimum (dinotasikan  dengan  simbol  )  dan penjumlahan (dinotasikan  dengan  simbol ⊗ ).
Dengan dua operasi tersebut didefinisikan untuk setiap max , R  y x sebagai berikut: y x y x y x y x      ) , max(
Selanjutnya, dalam aljabar maxplus ab a b   : . Sebagai catatan: x x x       dan x x x     0 0 untuk semua R  x .

## Matriks dalam Aljabar MaxPlus
Himpunan matriks berukuran m n  dalam aljabar max-plus dinotasikan dengan m n  max R dengan 𝑛, 𝑚 ∈ ℕ dan 0 atau  m n . Elemen m n A   max R baris ke- i kolom ke- j dinotasikan j i a . atau j i A . ] [ untuk n i , , 2 , 1   dan m j , , 2 , 1   . Penulisan untuk matriks A adalah sebagai berikut
             m n n n m m a a a a a a a a a A . 21 . 1 . . 2 2 . 2 1 . 2 . 1 2 . 1 1 . 1
     
Dalam aljabar max-plus operasi + dan  dari vektor dan matriks dengan cara yang sama digantikan dengan  dan  . Untuk setiap n m B A   max , R berlaku n j m i b a b a B A j i j i j i j i j i , ,3 ,2 ,1 , , ,3 ,2 ,1 }, , { max ] [ , . , , ,         dan untuk  setiap n p p m B A     max max , R R diperoleh bahwa
n j m i b a b a B A j k k i j k k i p k j i   ,3 ,2 ,1 , , ,3 ,2 ,1 }, { max ] [ . . p k 1 , . 1 ,           
Dengan  menggunakan  simbol-simbol  tersebut  diskripsi  ruang  keadaan  suatu sistem diberikan dalam bentuk:
) ( ) ( ) 1 ( k u B k x A k x      (1) ) ( ) ( k x C k y   (2)
Dengan 𝐴 ∈ ℝ 𝜀 𝑛×𝑛 , 𝐵 ∈ ℝ 𝜀 𝑛×𝑚 dan 𝐶 ∈ ℝ 𝜀 𝑝×𝑛 dan x merepresentasikan  keadaan, u merepresentasikan input dan y merepresentasikan output, k indeks kejadian yang bernilai k = 0, 1, 2 … . Persamaan (1) dan (2) di  atas disebut  dengan sistem linear max-plus. Semua sistem diskrit bila diformulasikan ke dalam aljabar max-plus akan menjadi linear . Pengertian  nilai-karakteristik  dan  vektor-karakteristik  yang  bersesuaian  dari  suatu matriks bujur sangkar sebagaimana dijumpai dalam aljabar biasa juga kita jumpai dalam aljabar max-plus, yaitu bila kita mempunyai persamaan:
x x
A    λ
masing-masing vektor n max R  x dan skalar R  λ dinamakan vektor karakteristik dan nilai  karakteristik  dari  matriks A dengan  vektor   ' , ,     x .    Algoritma  untuk memperoleh  vektor  karakteristik  dan  nilai  karakteristik  dari  matriks  persegi A dapat dilihat lebih jelas pada [3].

## Sistem Produksi Sederhana
Pada bagian ini  akan diberikan pembentukan model  dari suatu  sistem linear max plus sederhana, dengan mengambil contoh pada produksi sederhana yang terdiri dari tiga unit mesin pemroses seperti terlihat pada gambar di bawah ini:
s 2 =2 t 2 =1 t 5 =0 u t 1 =1 t 3 =0 t 4 = 3 t 6 =0 y s 1 =1 s 3 =2

## Gambar 1  Sistem produksi sederhana
Marilah sekarang kita tinjau sistem produksi sederhana yang diberikan oleh Gambar 1. Sistem produksi ini terdiri dari 3 unit mesin pemroses P 1 , P 2 dan P 3 .  Bahan dimasukkan pada unit mesin P 1 dan unit mesin P 2 , setelah selesai proses dari unit mesin P 1 , bahan bisa langsung di kirim ke unit mesin P 2 dan setelah diproses oleh unit mesin P 2 hasilnya di kirimkan ke unit mesin P 3 untuk dilakukan pemrosesan terakhir dan akan menjadi produk yang siap dipasarkan. Waktu proses untuk masing-masing unit mesin diberikan oleh s 1 = 2, s 2 = 1 dan s 3 = 2 satuan waktu. Diasumsikan  waktu  yang diperlukan untuk bahan baku mencapai P 1 adalah t 1 = 1 satuan waktu, dibutuhkan t 4 = 3 untuk mencapai unit mesin P 3 . Untuk waktu perjalanan yang lainnya ( t 3 , t 5 , da n t 6 ) diasumsikan nol. Di antara masukan dan proses terdapat  buffer dengan kapasitas  yang  cukup besar untuk  menjamin  buffer tidak  akan  sampai  overflow.  Setiap  unit  mesin  hanya  akan  mulai  bekerja  untuk menghasilkan produk yang baru  jika proses sebelumnya sudah selesai. Diasumsikan juga bahwa  unit  mesin  akan  mulai  proses  bila  semua  komponen  telah  tersedia.  Untuk  itu didefinisikan :
 ) ( k u adalah  waktu  yang  dibutuhkan  bahan  masuk  ke  sistem  untuk  waktu  yang  ke (k+1) .
 ) ( k x i adalah waktu unit mesin ke- i mulai proses untuk waktu ke- k , i= 1, 2, 3
 ) ( k y adalah waktu produk selesai waktu ke- k meninggalkan sistem (dipasarkan).
Gambaran proses sistem :
Unit mesin satu mulai proses  pada kali ke-( k+1 )  ketika
1. Proses sebelumnya telah selesai, atau 1 1 ) ( s k x  (yaitu awal proses sebelumnya )
( 1 k x
dan waktu proses 1 s ).
2. Bahan telah sampai pada unit mesin satu, atau 1 ) ( t k u  (yaitu bahan dimasukkan ke sistem ) ( k u dan waktu transportasi  ). 1 t
Karena  unit  mesin  satu  mulai  proses  pada  saat  bahan  telah  tersedia  dan  produk sebelumnya telah meninggalkan unit mesin satu, maka kita dapatkan persamaanya yaitu :
) ) ( , ) ( max( ) 1 ( 1 1 1 1 t k u s k x k x     (3)
Unit mesin 2 mulai proses  pada kali ke-( k+1 )  ketika
P 2 P 1 P 3
1. Bahan telah sampai pada unit mesin dua, atau
2 ) ( t k u  (yaitu bahan dimasukkan ke sistem ) ( k u dan waktu transportasi t 2 ).
2. Proses sebelumnya telah selesai, atau 1
1 ) 1 ( s k x   (yaitu akhir proses sebelumnya / unit mesin satu selesai).
Dengan  proses  unit  mesin  dua  sendiri  atau
2 2 ) ( s k x  ,  dapat  dituliskan  persamaanya sebagai berikut :
)} 2 ) ( ( ), 2 ) ( ( ), 2 ) ( ( { max ) 1 ( 2 1 2      k u k x k x k x (4)
Begitu juga dengan unit mesin tiga mulai proses ke-( k+1 )  ketika
1. Proses  unit  mesin  dua  telah  selesai    atau
5 2 2 ) 1 ( t s k x    (yaitu  proses sebelumnya/unit mesin dua sudah  selesai dan waktu transportasi t 5 ).
2. Proses  unit  mesin  satu  telah  selesai,  atau
4 1 1 ) 1 ( t s k x    (yaitu  akhir  proses sebelumnya / unit mesin satu selesai dan waktu transportasi t 4 ).
Dengan  proses  unit  mesin  tiga  sendiri  atau
3 3 ) ( s k x  ,  dapat  dituliskan  persamaanya sebagai berikut :
      4 1 1 2 2 3 3 3 ) 1 ( , ) 1 ( , ) ( ( max{ ) 1 ( t s k x s k x s k x k x         (5)
Persamaan (5) dapat diuraikan sebagai  berikut:                                       5 ) ( 2 ) ( 4 ) ( 5 ) ( 5 ) ( 5 ) ( 4 ) ( 4 ) ( 4 ) ( 2 ) ( ) 3 1 ] 1 ) ( 1 ) ( ([ ) 2 } 2 ) ( 2 ) ( 2 ) ( ( 2 ) ( ) 1 ( ) 1 ( ) ( ( ) 1 ( 3 2 1 1 2 1 3 1 2 1 3 4 1 1 2 2 3 3 3                                              k u k x k x k x k u k x k u k x k x k x k u k x k u k x k x k x t s k x s k x s k x k x Sedangkan persaman untuk y(k) adalah: 2 ) ( ) ( ) ( 3 3 3     k x s k x k y (6)
Kemudian Persamaan (3), (4), (5) dan (6) dapat ditulis sebagi berikut:
      ) 1 ) ( ( 1 ) ( 1 ) ( 1 ) ( ) 1 ( 1 1 1          k u k x k u k x k x ) 2 ) ( ( ) 2 ) ( ( ) 2 ) ( ( ) 1 ( 2 1 2        k u k x k x k x k         5 ) ( 2 ) ( 4 ) ( 5 ) 1 ( ) 1 ( 3 2 1 3           k u k x k x k x k x 2 ) ( ) ( 3   k x k y
Dalam bentuk matriksnya adalah :
                                              5 2 1 ) ( ) ( 2 4 5 2 2 1 1 3 2 1 3 2 1 k u k x x x k x x x    atau : ) ( 5 2 1 ) ( 2 4 5 2 2 1 ) 1 ( k u k x k x                            
  ) ( 2 ) ( k x k y                ) ( ) ( ) ( ) ( 3 2 1 k x k x k x k x merupakan vektor keadaan
y(k) merupakan vektor output dan u(k) merupakan vektor input.

## 3. Kesimpulan
Dalam bagian akhir dari pembahasan paper ini perlu kami ingatkan bahwa model sistem produksi  yang  dibahas  di  atas  adalah  sangat  sederhana,  dengan  harapan  bisa mempermudah  dalam  menurunkan  model  sistem  linier  sederhana  yang  lain  dengan menggunakan aljabar max plus. Untuk  ke depannya kajian selanjutnya bisa diterapkan pada sistem produksi yang lebih rumit dan lebih kompleks

## Daftar Pustaka
[1] F. Baccelli, G. Cohen, G. J. Olsder, and J.–P. Quadrat, (1992), Synchronization and Linearity. John Wiley & Sons, Chichester.
[2] Necoara,  I., (2006), Model Predictive Control for Max-Plus-Linear and Piecewise Affine Sistems. Technise Universiteit Delft. Netherland.
[3] Subiono, (2010), Aljabar Maxplus dan Terapanya , Jurusan Matematika FMIPA ITS. Surabaya.