Seminar Nasional Matematika IV Institut Teknologi Sepuluh Nopember, Surabaya, 13 Desember 2008
ANALISIS KEDINAMIKAN SISTEM PADA MASALAH PENJADWALAN FLOW SHOP MENGGUNAKAN ALJABAR MAX-PLUS 1
Nur Shofianah,2Subiono
1,2 Jurusan Matematika FMIPA Institut Teknologi Sepuluh Nopember Jl. Arief Rahman Hakim, Kampus Keputih - Sukolilo, Surabaya 60111 – Jawa Timur
e-mail : 1
[email protected], 2 subiono_2003@telkomnet
Abstrak. Dalam makalah ini dibahas aplikasi Aljabar Max-Plus pada masalah penjadwalan flow shop, khususnya masalah pada aliran produksi permutation flow shop dengan n job 2 mesin dimana masing-masing job harus diproses tepat satu kali pada tiap mesin dengan urutan mesin yang sama. Dengan menggunakan Aljabar Max-Plus akan dikonstruksi model dinamik dari aliran flow shop yang ada. Dari model dinamik ini dapat diketahui kedinamikan sistem dan waktu periodik sistem yang tidak lain adalah nilai eigen dari matriks transisi sistem. Jika vektor eigen yang bersesuaian dengan nilai eigen ini dijadikan sebagai waktu awal tersedianya resources, maka akan terbentuk suatu jadwal yang periodik dengan periode sama dengan nilai eigen tersebut. Selain itu, jadwal yang terbentuk juga merupakan jadwal yang steady state. Selanjutnya diberikan suatu contoh kasus flow shop dengan 2 job 2 mesin untuk lebih memahami teori pada bahasan ini. Kata kunci: Aljabar Max-Plus, permutation flow shop, penjadwalan, steady state
1. Pendahuluan Aljabar Max-Plus merupakan salah satu teknik analisis pengkajian dari sistem event diskrit yang mempunyai banyak aplikasi pada teori sistem, kontrol optimal dan Petri net. Pada makalah ini, Aljabar Max-Plus akan diaplikasikan pada masalah penjadwalan produksi. Beberapa penelitian sebelumnya mengenai aplikasi Aljabar Max-Plus pada masalah penjadwalan antara lain Goto, et al (2008) menggunakan Max-Plus Linear sebagai monitoring dan metode penjadwalan untuk sistem MIMO-FIFO (Multiple Input Multiple Output – First In First Out). Bouquard et al (2006) menggunakan Aljabar MaxPlus untuk menentukan makespan dan urutan job yang optimal pada flow shop. Pada makalah ini akan dikonstruksi model dinamik sistem dari aliran produksi flow shop dengan n job 2 mesin. Istilah penjadwalan pada makalah ini mengacu pada penyusunan jadwal reguler dari waktu mulainya pemrosesan job. Misalkan pada aliran produksi flow shop, terdapat n job {J i } yang akan dijadwalkan pada 2 mesin {M k } , dengan 1 ≤ i ≤ n dan k = 1,2 . Masing-masing job harus diproses tepat satu kali pada tiap mesin dengan urutan mesin yang sama. Permutation flow shop merupakan kelas khusus dari flow shop dimana setiap job mempunyai urutan pemrosesan yang sama pada tiap mesin. Waktu pemrosesan (processing time) job i pada mesin k dinotasikan dengan p i , k . Pre-emption tidak diperbolehkan dan pada suatu
waktu tertentu, setiap mesin hanya dapat mengerjakan satu operasi dari satu job tertentu. Dalam makalah ini, Aljabar Max-Plus akan digunakan untuk memodelkan sistem pada aliran produksi flow shop dengan n job 2 mesin. Model tersebut diuraikan dengan menggunakan terminologi Aljabar Max-Plus. Dari model dinamik sistem dapat diketahui waktu periodik sistem ini yang tidak lain adalah nilai eigen dari matriks transisi sistem . Jika vektor eigen yang bersesuaian dengan nilia eigen ini dijadikan sebagai waktu awal tersedianya resources, maka akan terbentuk jadwal yang periodik dengan periode sama dengan nilai eigen. Jadwal tersebut tidak hanya periodik, tetapi juga merupakan jadwal yang steady state, yaitu jadwal dimana waktu putar sistem (periode), jumlah dan urutan job beserta mesin yang memproduksinya sama untuk siklus produksi selanjutnya. Informasi ini sangat berguna untuk menyusun jadwal produksi yang reguler.
2. Aljabar Max-Plus Alajabar Max-Plus berkaitan dengan dua operasi, maksimum (max) dan tambah (plus). Operasi tersebut mempunyai kemiripan dengan operasi perkalian biasa dua matriks, dimana pada perkalian biasa dua matriks berkenaan dengan operasi kali dan tambah. Pada perkalian biasa dua matriks, ganti kali dengan tambah dan tambah dengan maksimum maka akan diperoleh Aljabar Max-Plus. Pendekatan ini sangat sesuai bila selang waktu berperan langsung pada masalah formulasi model. def
Aljabar Max-Plus dinotasikan dengan R = ( Rmax ,⊕,⊗, ε , e) , dimana Rmax = R ∪ ε , dengan ε = − ∞ def
dan e = 0 . Pada Aljabar Max-Plus, maksimum dinotasikan dengan ⊕ dan penjumlahan dinotasikan dengan ⊗ . ε merupakan elemen netral terhadap ⊕ sedangkan e merupakan elemen netral terhadap def
def
⊗ . Untuk setiap a, b ∈ Rmax berlaku a ⊕ b = max(a, b) dan a ⊗ b = a + b Terdapat analogi yang jelas antara Aljabar Linier dengan Aljabar Max Plus di satu sisi, juga antara teori sistem dan teori event diskret di sisi lain (Bacelli et al., 1992; Subiono, 2000). Bentuk umum dari suatu persamaan beda (aljabar biasa) adalah : x(k + 1) = Ax(k ), k = 0,1,2, " ,
dimana x∈Rn , aij ∈R. Vektor
(1)
x menyatakan keadaan dari model dan x(k ) menyatakan keadaan saat ke-k.
Sedangkan A adalah matriks berukuran n x n. Bila diberikan keadaan awal x(0) = x 0 maka evolusi keadaan mendatang dari Persamaan (1) dapat ditentukan. Jika persamaan vektor pada (1) ditulis dalam bentuk persamaan skalar didapat xi (k + 1) =
n
∑ a x (k ) ij
j
, i = 1,2,..., n; k = 0,1,...
(2)
j =1
xi menyatakan komponen ke-i dari vektor x sedangkan aij adalah elemen dari matriks A. Pada Aljabar
Max-Plus, operasi kali dan jumlah pada bentuk Persamaan (1) akan diubah, kali menjadi tambah dan jumlah menjadi maksimum, maka Persamaan (2) menjadi : xi (k + 1) = max(a i1 + x1 (k ), a i 2 + x 2 (k ),..., a in + x n (k )) = max j ( a ij + x j )
= ⊕ a ij ⊗ x j (k )
(3)
j
atau dengan notasi vektor x(k + 1) = A ⊗ x(k ) ,
(4)
n , aij ∈ Rmax . Jika Persamaan (3) memenuhi keadaan awal x(0) = x 0 maka evolusi waktu dimana x ∈ Rmax
dari Persamaan (3) dapat ditentukan. Tentunya secara umum, evolusi waktu dari (2) dan (3) berbeda. Pada Persamaan (2), argumen k pada x(k ) menyatakan waktu ke-k pada keadaan x(k ) . Sedangkan pada Persamaan (3), argumen k bukan merupakan saat waktu tetapi menyatakan saat aktif yang ke-k. Sebagai contoh pada jaringan kerja yang terdiri dari n titik, yang diwakili oleh setiap xi dan aij berkaitan dengan garis yang terhubung dari titik j ke titik i. Titik dalam jaringan kerja dapat berperan sebagai aktivitas tertentu. Aktivitas-aktivitas ini membutuhkan waktu hingga yang disebut waktu aktivitas. Diasumsika aktivitas pada titik tertentu hanya dapat dimulai jika semua aktivitas pendahulunya sudah menyelesaikan aktivitasnya dan mengirimkan hasilnya sepanjang garis yang menghubungkan titik tersebut. Dengan menyatakan jangka waktu awal dimana titik i menjadi aktif pada saat ke-k dan aij demikian, xi (k ) adalah jumlah dari waktu aktivitas titik j dan lamanya waktu perjalanan dari titik j ke titik i. Suatu perluasan dari (4) dinyatakan dengan
x(k + 1) = A ⊗ x(k ) ⊕ B ⊗ u (k ) y (k ) = C ⊗ x(k )
(5)
dimana u (k ) merupakan input dan y(k ) menyatakan outputnya. Pada jaringan kerja, u (k ) merupakan suatu vektor yang menunjukkan ketika sumber tertentu tersedia pada waktu ke-k sedangkan vektor y(k ) merujuk pada saat dimana produk akhir dari jaringan kerja ditawarkan pada dunia luar. n dinamakan nilai eigen dan vektor Pada Aljabar Max-Plus, suatu bilangan λ ∈ R dan vektor x ∈ Rmax eigen yang bersesuaian untuk suatu matriks bujur sangkar A berukuran nxn jika memenuhi A⊗v = λ ⊗v
(6)
Nilai karakteristik λ dapat ditafsirkan sebagai waktu periodik dari sistem, yaitu setiap titik dari jaringan kerja yang sesuai menjadi aktif setiap λ satuan (Subiono, 2000).
3. Konstruksi Model Setelah memahami sistem pada aliran produksi flow shop, akan dikonstruksi suatu model dari sistem dengan menggunakan terminologi Aljabar Max-Plus. Mula-mula akan digambarkan graph berarah yang merepresentasikan aliran flow shop dimana nodes nya merupakan kombinasi antara job dengan mesin, arc di antara nodes nya merupakan konstrain pendahulunya sedangkan bobot dari arc merupakan waktu pemrosesan yang bersesuaian. Graph berarah pada flow shop 2 job 2 mesin seperti ditunjukkan pada Gambar 1.
Gambar 1. Graph berarah pada flow shop 2 job 2 mesin
Sistem event diskrit deterministik berhingga dapat dipandang sebagai himpunan berhingga aktivitas A (dalam hal ini aktivitas pemrosesan job) dan himpunan berhingga resources R . Urutan aktivitas dapat dideskripsikan dengan graph berarah (A, U) . Untuk sebarang aktivitas a i dan a j , (i, j ) ∈ U menyatakan bahwa a j merupakan aktivitas pendahulu bagi a i . Artinya, kedua aktivitas itu menggunakan resources bersama, namun tidak bisa menggunakannya pada saat yang bersamaan sehingga aktivitas a i harus menunggu selesainya aktivitas a j . Misalkan x i menyatakan waktu awal pemrosesan dari aktivitas a i dan u r menyatakan waktu ketika resource r tersedia. Jika (i, j ) ∈ U , maka x i ≥ x j + p ji dimana p ji adalah waktu pemrosesan aktivitas a j menuju aktivitas ai . Jika
i merupakan aktivitas pertama untuk resource r maka xi ≥ u r .
Misalkan Γ(i ) merupakan himpunan aktivitas pendahulu dari aktivitas a i dan R (i ) himpunan resources sedemikian hingga a1 (r ) = i , maka xi didefinisikan sebagai ∀ai ∈ A
⎛ ⎞ xi = max⎜ max ( x j + pij ) , max u r ⎟ j ∈ Γ ( i ) r ∈ R ( i ) ⎝ ⎠
(7)
Misalkan y i menyatakan output, yaitu waktu ketika resources dibebaskan dari aktivitas-aktivitas yang bersesuaian dan Φ(i) merupakan himpunan aktivitas yang bersesuaian dengan output ke-i, maka y i didefinisikan sebagai yi = x j + pij ; j ∈ Φ (i )
(8)
Pada saat ke-k, Persamaan (7) dan (8) dapat dituliskan menjadi x(k ) = Ax(k ) ⊕ Bu (k )
(9)
y (k ) = Cx (k )
(10)
dimana p j ( k ) , jika proses i mempunyai proses pendahulu j ⎧ =⎨ , jika proses i tidak mempunyai proses pendahulu j ⎩ ε , jika proses i mempunyai input eksternal j e [B]ij = ⎧⎨ , jika proses i tidak mempunyai proses pendahulu j ⎩ε , jika proses j mempunyai output eksternal i p (k ) [C k ]ij = ⎧⎨ j ε , jika proses j tidak mempunyai output eksternal i ⎩
[A ] k
ij
Dalam hal ini, p j ( k ) merupakan waktu pemrosesan aktivitas j pada saat ke-k. Persamaan (9) merupakan persamaan implisit dalam x . Jika dilakukan substitusi secara berulang pada ruas kanan persamaan (9), akan diperoleh x(k ) = A( Ax(k ) ⊕ Bu (k ) ) ⊕ Bu (k ) = A 2 x (k ) ⊕ ABu ( k ) ⊕ Bu ( k ) = A 2 x ( k ) ⊕ ( A ⊕ E ) )Bu ( k )
setelah k substitusi diperoleh x (k ) = A k x ( k ) ⊕ ( A k −1 ⊕ A k − 2 ⊕ ... ⊕ A ⊕ E )Bu ( k )
(11)
Pada persamaan (11), E menyatakan matriks identitas, bernilai e pada diagonal dan ε untuk yang lain. A k menunjukkan bobot dari lintasan dengan panjang k pada graph. Karena A tidak mempunyai lintasan dengan panjang lebih besar dari n, maka A k = ε = −∞ untuk k ≥ n . Oleh karena itu, solusi dari x menjadi x ( k ) = (A k −1 ⊕ A k − 2 ⊕ ... ⊕ A ⊕ E )Bu ( k ) atau dapat dituliskan x ( k ) = A * Bu ( k ) dengan
A* = E ⊕ A ⊕ A 2 ⊕ ... ⊕ A n ⊕ A n +1 ⊕ ...
(12)
Oleh karena proses produksi ke- (k + 1) langsung dimulai setelah mesin menyelesaikan produksi yang kek dari barisan job maka akan ditambahkan feedback arc pada graph berarah seperti yang ditunjukkan pada Gambar 2. feedback arc ini digambarkan dengan garis putus-putus. Diasumsikan bahwa feedback arc mempunyai durasi nol, maka u (k ) = y (k − 1) , dimana u (k ) adalah cycle input ke-k dan y (k ) cycle output ke-k, sehingga didapatkan y ( k ) = Cx ( k ) = CA * Bu ( k ) = CA * By (k − 1)
= My (k − 1)
(13)
dengan M = CA* B merupakan matriks transisi dari y (k − 1) ke y (k ) . Nilai eigen dari matriks transisi ini menentukan waktu periodik sistem. Jika vektor eigen dijadikan sebagai nilai awal sistem, maka terbentuklah jadwal yang reguler.
Gambar 2. Graph berarah dengan arc feed back pada flow shop 2 job 2 mesin
4. Contoh Aplikasi Contoh 1 : Terdapat dua job J 1 dan J 2 yang akan dijadwalkan pada dua mesin M 1 dan M 2 dengan masingmasing waktu pemrosesannya sebagai berikut : Tabel 1. Waktu Pemrosesan job
J1
dan
J2
pada dua mesin
M1
M1
J1 1
J2 4
M2
4
1
dan
M2
Untuk mengkonstruksi model dari aliran produksi ini, akan digambarkan graph berarah sebagaimana ditunjukkan pada Gambar 3. Nodes tersebut merepresentasikan kombinasi job dengan mesin. Dengan demikian terdapat 4 nodes dimana masing-masing node merepresentasikan ( J 1 , M 1 ), ( J 1 , M 2 ), ( J 2 , M 1 ) dan ( J 2 , M 2 ) . Graph berarah terdiri dari 4 nodes, 4 input dan 4 output.
Gambar 3. Graph berarah pada flow shop 2 job 2 mesin
Berdasarkan model pada persamaan (9) dan (10) diperoleh : x = Ax ⊕ Bu y = Cx dimana ⎛ε ε ε ε ⎞ ⎛e ε e ε ⎞ ⎛ε 4 ε ε ⎞ ⎛e ε ⎜ ⎜ ⎜ ⎜ ⎟ ⎟ ⎟ ⎜1 ε ε ε ⎟ ⎜ε ε ε e ⎟ ⎜ε ε ε 1 ⎟ ⎜1 e * 2 ; B=⎜ ; C =⎜ ; A = E ⊕ A⊕ A = ⎜ A=⎜ ⎟ ⎟ ⎟ 1 ε 1 ε ε ε ε e ε ε ε ε 4 ε ⎜ ⎜ ⎜ ⎜ ⎟ ⎟ ⎟ ⎜ε 4 4 ε ⎟ ⎜ε ε ε ε ⎟ ⎜ε ε ε 1 ⎟ ⎜5 4 ⎝ ⎝ ⎝ ⎝ ⎠ ⎠ ⎠
ε ε⎞ ⎟ ε ε⎟ e ε⎟ ⎟ 4 e ⎟⎠
maka diperoleh y (k ) = My (k − 1)
dengan M menyatakan matriks transisi, yaitu ⎛ε ⎜ ⎜ε * M = CA B = ⎜ ε ⎜ ⎜ε ⎝
4 ε
ε ε ε
ε⎞
⎛e ⎟ ⎜ ε 1 ⎟ ⎜1 ⊗ 4 ε ⎟ ⎜1 ⎟ ⎜ ε 1 ⎟⎠ ⎜⎝ 5
ε ε ε ⎞ ⎛e ⎟ ⎜ e ε ε ⎟ ⎜ε ⊗ ε e ε ⎟ ⎜ε ⎟ ⎜ 4 4 e ⎟⎠ ⎜⎝ ε
ε e ε ε e ε ε ε
ε ⎞ ⎛5 ε
5 4⎞ ⎟ ⎜ ⎟ e ⎟ ⎜6 5 6 5⎟ = ε ⎟ ⎜5 4 5 ε ⎟ ⎟ ⎜ ⎟ ε ⎟⎠ ⎜⎝ 6 5 6 5 ⎟⎠
Dengan menggunakan Scilab diperoleh λ = 5 dan vektor eigen v = [20 21 20 21] λ dari matriks transisi M merupakan waktu periodik sistem. Agar lebih sederhana, vektor eigen tersebut t
dapat dituliskan menjadi v = [0 1 0 1] . Dengan demikian, diperoleh bahwa sistem akan berulang setiap 5 satuan waktu. Jika vektor eigen dijadikan sebagai nilai awal ( y (0) ) maka akan terbentuk jadwal yang reguler dari waktu selesainya pemrosesan setiap 5 satuan waktu sebagai berikut : t
y(0) ⎛0⎞ ⎜ ⎟ ⎜1⎟ ⎜0⎟ ⎜ ⎟ ⎜1⎟ ⎝ ⎠
y (1)
y (2)
⎛5⎞ ⎛10 ⎞ ⎜ ⎟ ⎜ ⎟ ⎜6⎟ ⎜ 11⎟ ; ⎜ ⎟ ; ⎜ ⎟ ; … 5 10 ⎜ ⎟ ⎜ ⎟ ⎜6⎟ ⎜ 11⎟ ⎝ ⎠ ⎝ ⎠
Untuk memperoleh jadwal dari waktu awal mulainya pemrosesan job dari sistem pada aliran produksi flow shop 2 job 2 mesin tersebut digunakan persamaan (12) sehingga dari informasi yang diperoleh mengenai nilai eigen dan vektor eigen diperoleh jadwal regular dari waktu awal mulainya pemrosesan job sebagai berikut x(1) x(2) x (3) ⎛0⎞ ⎛5⎞ ⎛10 ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ 1 6 ⎜ ⎟ ⎜ ⎟ ⎜ 11 ⎟ ⎜ 1 ⎟ ; ⎜ 6 ⎟ ; ⎜ 11 ⎟ ; … ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜5⎟ ⎜10 ⎟ ⎜15 ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ Hasil yang diperoleh ini dapat dicocokkan menggunakan Gantt Chart, yaitu bagan balok yang biasa digunakan untuk mengetahui completion time dan makespan dalam kasus penjadwalan produksi, seperti pada Gambar 4.
M1
M2
Gambar 4. Gantt Chart aliran produksi flow shop 2 job 2 mesin pada contoh 1
Contoh 2 : Terdapat dua job J 1 dan J 2 yang akan dijadwalkan pada dua mesin M 1 dan M 2 dengan masingmasing waktu pemrosesannya sebagai berikut :
Tabel 2. Waktu Pemrosesan job
J1
dan
J2
pada dua mesin
M1
M1
J1 2
J2 3
M2
5
6
dan
M2
Untuk mengkonstruksi model dari aliran produksi ini, akan digambarkan graph berarah sebagaimana ditunjukkan pada Gambar 3. Nodes tersebut merepresentasikan kombinasi job dengan mesin. Dengan demikian terdapat 4 nodes dimana masing-masing node merepresentasikan ( J 1 , M 1 ), ( J 1 , M 2 ), ( J 2 , M 1 ) dan ( J 2 , M 2 ) . Graph berarah terdiri dari 4 nodes, 4 input dan 4 output. Berdasarkan model pada persamaan (2.10) diperoleh : x = Ax ⊕ Bu y = Cx dimana ⎛ε ε ε ε ⎞ ⎛e ε e ε ⎞ ⎛ε 3 ε ε ⎞ ⎜ ⎜ ⎜ ⎟ ⎟ ⎟ 2 ε ε ε ε ε ε e ⎜ ⎜ ⎜ε ε ε 6 ⎟ ⎟ ⎟ C =⎜ A=⎜ B=⎜ 2 ε ε ε⎟ ε e ε ε⎟ ε ε 5 ε⎟ ⎜ ⎜ ⎜ ⎟ ⎟ ⎟ ⎜ε 3 5 ε ⎟ ⎜ε ε ε ε ⎟ ⎜ε ε ε 6 ⎟ ⎝ ⎝ ⎝ ⎠ ⎠ ⎠ maka diperoleh y (k ) = My (k − 1) ⎛5 ε 5 ⎜ ⎜13 11 13 * dengan M menyatakan matriks transisi, yaitu M = CA B = ⎜ 7 5 7 ⎜ ⎜13 11 13 ⎝
3⎞ ⎟ 9⎟ ε⎟ ⎟ 9 ⎟⎠
Dengan menggunakan Scilab diperoleh λ = 11 dan vektor eigen v = [31 39 33 39] . Agar lebih t
sederhana, vektor eigen tersebut dapat dituliskan menjadi v = [0 8 2 8] . λ dari matriks transisi M merupakan waktu periodik sistem. Dengan demikian, sistem akan berulang setiap 11 satuan waktu. Jika vektor eigen dijadikan sebagai nilai awal ( y (0) ) maka akan terbentuk jadwal yang reguler dari waktu selesainya pemrosesan setiap 11 satuan waktu sebagai berikut : y (0) y (1) y (2) t
⎛ 0⎞ ⎜ ⎟ ⎜8⎟ ⎜ 2⎟ ; ⎜ ⎟ ⎜8⎟ ⎝ ⎠
⎛ 11⎞ ⎛ 22 ⎞ ⎜ ⎟ ⎜ ⎟ ⎜19 ⎟ ⎜ 30 ⎟ ⎜13 ⎟ ; ⎜ 24 ⎟ ; … ⎜ ⎟ ⎜ ⎟ ⎜19 ⎟ ⎜ 30 ⎟ ⎝ ⎠ ⎝ ⎠
Untuk memperoleh jadwal dari waktu awal mulainya pemrosesan job dari sistem pada aliran produksi flow shop 2 job 2 mesin tersebut digunakan persamaan (12) sehingga dari informasi yang diperoleh mengenai nilai eigen dan vektor eigen diperoleh jadwal regular dari waktu awal mulainya pemrosesan job sebagai berikut x(1) x(2) x (3) ⎛2⎞ ⎜ ⎟ ⎜8⎟ ⎜8⎟ ⎜ ⎟ ⎜13 ⎟ ⎝ ⎠
⎛ 13 ⎞ ⎛ 24 ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ 19 ⎟ ⎜ 30 ⎟ ; ⎜ ⎟ ; ⎜ ⎟ ; … 19 30 ⎜ ⎟ ⎜ ⎟ ⎜ 24 ⎟ ⎜ 35 ⎟ ⎝ ⎠ ⎝ ⎠
Hasil yang diperoleh ini dapat dicocokkan menggunakan Gantt Chart, yaitu bagan balok yang biasa digunakan untuk mengetahui waktu selesainya pemrosesan job dan makespan dalam kasus penjadwalan produksi, seperti ditunjukkan pada Gambar 5.
M1 M2
Gambar 5. Gantt Chart aliran produksi flow shop 2 job 2 mesin pada contoh 2
Pada Gambar 5 terlihat bahwa sistem akan berulang setiap 11 satuan waktu. Terlihat pada siklus produksi yang pertama, setelah memproses job 1, mesin 1 idle (pada waktu ke 4 s.d 8) padahal baik mesin 1 maupun mesin 2 masih memungkinkan untuk memproses job. Hal ini terjadi agar untuk siklus selanjutnya sistem dapat berjalan secara steady state, yaitu aliran produksi yang mempunyai waktu putar sistem (periode), jumlah dan urutan job beserta mesin yang memproduksinya sama untuk siklus selanjutnya.
5. Kesimpulan Aljabar Max-Plus dapat diaplikasikan pada masalah penjadwalan flow shop, khususnya masalah pada aliran produksi flow shop dengan n job 2 mesin dimana masing-masing job harus diproses tepat satu kali pada tiap mesin dengan urutan mesin yang sama. Dengan menggunakan Aljabar Max-Plus dapat dikonstruksi model dinamik dari aliran flow shop yang ada, yaitu
y ( k ) = My ( k − 1)
Dari model dinamik ini dapat diketahui kedinamikan sistem dan waktu periodik sistem yang tidak lain adalah nilai eigen dari matriks transisi sistem. Jika vektor eigen yang bersesuaian dengan nilai eigen ini dijadikan sebagai waktu awal tersedianya resources, maka akan terbentuk suatu jadwal yang periodik dengan periode sama dengan nilai eigen tersebut. Selain itu, jadwal yang terbentuk juga merupakan jadwal yang steady state.
Daftar Pustaka Baccelli, F., Cohen G., Olsder G.J. dan Quadrat J.P., (1992), Synchronization and Linearity, John Wiley and Sons, New York. Bouquard, J., -L., Lente, C., dan Billaut, J,-C., (2006), “Application of an Optimization Problem in MaxPlus Algebra to Scheduling Problems”, Discrete Applied Mathematics, 154, hal. 2064-2079 Goto, H., Masuda, S., (2008), “Monitoring and Scheduling Methods for MIMO-FIFO Systems Utilizing Max-Plus Linear Representation”, IEMS Vol.7, No.1, pp.23-33, June, 2008. Subiono, (2000), “Operator linear dalam Aljabar Max-Plus dan terapannya”, prosiding Seminar Nasional Matematika, Jurusan Matematika ITS, Surabaya.
