Panduan Intuitif dan Praktis Terkait Aljabar Max-Plus dalam Masalah Penjadwalan

Panduan Intuitif dan Praktis Terkait Aljabar Max-Plus dalam Masalah Penjadwalan v=R∗(n)⊗u Rizal Purnawan 2025 DOI: 10.5281/zenodo.17798786 ii Prakata Alhamdulillah, dengan izin dan rahmat Allah jalla jal¯ aluhu, penulisan buku ini, Panduan Intuitif dan Praktis Terkait Aljabar Max-Plus dalam Masalah Penjadwalan, dapat terselesaikan dalam waktu yang cukup singkat. Shalawat serta salam semoga senantiasa tercurah kepada Rasulullah Muhammad Shallallahu ‘alaihi wasallam, beserta keluarga dan sahabat beliau. Penulis ucapkan terimakasih dan syukur kepada rekan-rekan dari Universitas Gajah Mada yang terlibat dalam penelitian terkait simulasi pemodelan dan optimasi project concreting sequence. Buku ini lahir melalui penelitian tersebut, sebagai bentuk interdisciplinary knowledge transfer antara rekan-rekan dari matematika kepada teknik sipil. Kemudian, buku ini juga merupakan salah satu buah dari perjalanan pribadi penulis dalam menekuni matematika secara mandiri, yang berawal dari rasa ingin tahu dan berlanjut menjadi sebuah kebutuhan intelektual untuk memahami keindahan matematika. Dalam perjalanan ini, Allah jalla jal¯ aluhu telah membimbing penulis menelusuri berbagai cabang matematika, mulai dari matematika abstrak seperti aljabar abstrak, analisis fungsional dan topologi, hingga cabang terapan seperti optimasi dan aplikasi kontemporer pada machine learning. Bahkan tidak jarang iii dalam proses pembelajaran tersebut, penulis merasa tak sengaja mempelajari suatu topik karena sedang membaca topik lain. Sungguh, hal ini jelas merupakan arahan Allah Al-‘Alim. Penulis bersyukur kepada Allah jalla jal¯ aluhu yang telah menganugerahkan petunjuk dan ketekunan dalam menjelajahi bidangbidang tersebut, serta mengarahkan pengetahuan ini agar dapat dimanfaatkan untuk menyelesaikan masalah nyata dan, insyaAllah, memberi manfaat bagi umat manusia. Ucapan terima kasih penulis haturkan kepada istri dan keluarga yang telah memberikan dukungan, semangat, dan doa. Kehadiran mereka menjadi penguat dalam proses penulisan karya ini. Semoga Allah jalla jal¯ aluhu membalas kebaikan mereka dengan berlipat ganda. Dalam buku ini, penulis mencoba memberikan penjelasan yang seimbang antara teori aljabar max-plus secara intuitif dengan aplikasi nyata pada penjadwalan suatu proyek yang sangat sederhana, dengan titik berat agar pembaca tanpa latar belakang matematika dapat memahami esensi teori tersebut dan dapat menerapkan untuk kasus tersebut. Jika secara formal pembaca sebenarnya perlu memahami konsep-konsep aljabar abstrak seperti monoid,group,semifield, dan semimodule pada semifield agar dapat memahami aljabar max-plus secara komprehensif, maka dalam buku ini penulis memilih untuk tidak membahas secara rinci konsep-konsep tersebut, melainkan langsung fokus pada alasan yang telah disebutkan sebelumnya. Akhir kata, semoga buku sederhana ini dapat menjadi panduan praktis sekaligus jendela bagi pembaca untuk mengenal lebih dalam aljabar max-plus dan potensinya dalam berbagai aplikasi, khususnya dalam masalah penjadwalan. Penulis menyadari buku ini masih sangat jauh dari sempurna, dan sangat mengapresiasi saran dan masukan konstruktif dari pembaca. iv Daftar Isi 1 Mengapa Aljabar Max-Plus? 1 1.1 Pemodelan dengan Graf ............. 1 1.2 Critical Path dan Durasi Total .......... 3 2 Penjelasan Intuitif Aljabar Max-Plus 5 2.1 Overview ..................... 5 2.2 Aljabar Linear Standar v Max-Plus ....... 6 2.2.1 Struktur Dasar (Skalar) ......... 6 2.2.2 Struktur Modul ............. 9 2.2.3 Operator Linear ............. 11 2.3 Notasi Kleene-Star ................ 16 2.3.1 Penjelasan Notasi Kleene-Star ...... 16 2.3.2 Notasi Kleene-Star Terpotong ...... 18 3 Komputasi Durasi Total Proyek dengan Aljabar MaxPlus 19 3.1 Model Semimodul Max-Plus ........... 19 3.2 Matriks Max-Plus Penjadwalan ......... 21 3.3 Waktu Dimulainya Setiap Aktivitas ....... 23 3.4 Durasi Total Proyek ............... 25 3.5 Kesimpulan .................... 26 v vi Bab 1 Mengapa Aljabar Max-Plus? Dalam pekerjaan-pekerjaan seperti menentukan penjadwalan dari suatu proyek, atau kegiatan lain seperti penjadwalan jalur kereta, sering kali diperlukan operasi matematika max dan penjumlahan terkait dengan durasi masing-masing aktivitas. Hal ini dilakukan agar sistem terhubung dengan baik dan tidak menimbulkan kekacauan. 1.1 Pemodelan dengan Graf Misalnya, pada suatu proyek, terdapat aktivitas-aktivitas A, B, C, D dan E dengan relasi sequential yang diberikan oleh diagarm pada Gambar 1.1. Kemudian, setiap aktivitas memiliki durasi pekerjaan rata sebesar 7 (satuan waktu). Diagram pada Gambar 1.1 disebut sebagai graf (graph) dalam matematika, dan dipelajari secara formal dalam sub-bidang ma1 BAB 1 doi: 10.5281/zenodo.17798786 tematika bernama Teori Graf/Graph Theory (Guichard,2025). Komponen-komponen utama graf adalah nodes dan edges. Pada Gambar 1.1,nodes diberikan sebagai lingkaran dengan label A, B, C, D dan E, sedangkan edges diberikan sebagai garis dengan anak panah. Gambar 1.1: Model aktivitas-aktivitas pada suatu proyek sederhana menggunakan graf Graf yang kita miliki pada Gambar 1.1 secara spesifik disebut sebagai weighted DAG (Directed Acyclic Graph–Graf Tak Bersiklus Terarah), karena edges pada graf tersebut memiliki arah (dengan indikasi anak panah), graf tersebut tidak membentuk siklus yang berulang, dan terdapat weight (pembobotan) yang berupa angka-angka pada edges. Hal ini memberikan implikasi bahwa tidak semua graf harus memiliki edges dengan arah/anak panah dan pembobotan. Pada dasarnya, suatu graf hanya perlu memiliki nodes dan edges (Guichard,2025). Komponen-komponen dari graf yang kita miliki, dalam konteks ini, memodelkan hal-hal sebagai berikut: •Nodes memodelkan aktivitas-aktivitas pada suatu proyek. •Edges memodelkan keterkaitan antar aktivitas. ©2025 Rizal Purnawan. Licensed under CC BY-NC 4.0 Hal. 2 BAB 1 doi: 10.5281/zenodo.17798786 •Angka pada edges–yang merupakan weights–merupakan waktu delay dari dimulainya suatu aktivitas: Misalkan, aktivitas B dapat dimulai setelah 7 (satuan waktu) dari dimulainya aktivitas A. 1.2 Critical Path dan Durasi Total Umumnya, tujuan dari pemodelan penjadwalan proyek menggunakan graf adalah untuk mendapatkan durasi dari critical path. Critical Path dalam scheduling didefinisikan sebagai chain terpanjang dari graf. Sedangkaan suatu chain dalam graf didefinisikan sebagai suatu struktur terdiri dari nodes yang tersambung berurutan oleh edges. Sedangkan tujuan utama dari penentuan critical path adalah untuk mendapatkan durasi total proyek tersebut, karena total waktu pada critical path merpresentasikan total durasi proyek. Dalam kasus yang sangat sederhana seperti contoh proyek yang kita miliki dengan model graf tersebut, kita mungkin dapat langsung menentukan critical path sebagai A−B−D−E dengan durasi total yang diberikan sebagai Waktu mulai aktivitas E +Durasi aktivitas E (7+2+2)+7= 18 , hanya dengan melihat graf yang kita miliki. Tetapi hal ini tidak akan mudah untuk kasus yang sangat rumit. ©2025 Rizal Purnawan. Licensed under CC BY-NC 4.0 Hal. 3 BAB 2 doi: 10.5281/zenodo.17798786 Untuk semimodul max-plus Zn max, operasi ⊕berlaku pada Zn max layaknya +sebagai penjumlahan vektor pada Rn. Misalkan a,b∈Zn max dengan a=     a1 a2 . . . an      ,b=     b1 b2 . . . bn      , maka kita dapatkan a⊕b=     a1 a2 . . . an      ⊕     b1 b2 . . . bn      =     a1⊕b1 a2⊕b2 . . . an⊕bn      =     max{a1, b1} max{a2, b2} . . . max{an, bn}      . Kemudian operasi ⊗juga berlaku pada Zn max layaknya perkalian skalar ·pada ruang vektor Rn. Jika ν∈Zmax, maka kita dapatkan ν⊗a=ν⊗     a1 a2 . . . an      =     ν⊗a1 ν⊗a2 . . . ν⊗an      =     ν+a1 ν+a2 . . . ν+an      . Suatu contoh konkrit operasi semimodul max-plus diberikan sebgai berikut. Contoh 1 (Demonstrasi Operasi Semimodule Max-Plus).Diberikan semimodul max-plus Z3 max. Maka   2 7 1 ,  0 ε 1 ∈Z3 max . ©2025 Rizal Purnawan. Licensed under CC BY-NC 4.0 Hal. 10 BAB 2 doi: 10.5281/zenodo.17798786 Maka kita peroleh   2 7 1 ⊕  0 ε 3 =  2⊕0 7⊕ε 1⊕3 =  max{2,0} max{7, ε} max{1,3} =  2 7 3 . Kemudian, kita juga peroleh 7⊗  0 ε 3 =  7⊗0 7⊗ε 7⊗3 =  7+0 7+ε 7+3 =  7 ε 10 . Perbandingan level semimodul antara aljabar linear standar dan aljabar max-plus diberikan pada Tabel 2.2. Tabel 2.2: Perbandingan aljabar linear dan max-plus pada level semimodul Komponen Aljabar Linear Max-Plus Ruang Vektor/Semimodul RnZn max Skalar R Zmax Penjumlahan +⊕ Perkalian Skalar · ⊗ Identitas Vektor/Semimodul 0= (0,...,0) ε= (ε, . . . , ε) Identitas Skalar 1 0 2.2.3 Operator Linear Operator linear pada suatu ruang vektor merupakan komponen penting dalam aljabar linear. Untuk ruang vektor seperti Rn, sering kali suatu operator linear diberikan sebagai suatu perkalian matriks. Untuk me-review kembali tentang perkalian matriks ©2025 Rizal Purnawan. Licensed under CC BY-NC 4.0 Hal. 11 BAB 2 doi: 10.5281/zenodo.17798786 pada ruang vektor berdimensi terhingga, mari kita amati contoh berikut. Contoh 2 (Review Perkalian Matriks).Diberikan ruang vektor R3dan suatu vektor x∈R3dengan x=  0.5 2 −0.25 . Kemudian diberikan suatu matriks 3×3sebagai A∈R3×3dengan A=  1 2 1 2−1−2 1−2 1  . Perkalian matriks Adengan vektor xdiberikan sebagai berikut: Ax=  1 2 1 2−1−2 1−2 1    0.5 2 −0.25  =  1·0.5+2·2+1·(−0.25) 2·0.5 + (−1) ·2+(−2) ·(−0.25) 1·0.5 + (−2) ·2+1·(−0.25)   =  0.5+4−0.25 1−2 + 0.5 0.5−4−0.25  =  4.25 −0.5 −3.75  Ilustrasi intuitif mengenai mekanisme perkalian matriks dengan vektor diberikan pada Gambar 2.1. ©2025 Rizal Purnawan. Licensed under CC BY-NC 4.0 Hal. 12 BAB 2 doi: 10.5281/zenodo.17798786 Gambar 2.1: Mekanisme intuitif perkalian Ax Diberikan suatu matriks n×nsebagai A∈Rn×n. Suatu pemetaan T:Rn→Rnyang didefinisikan sebagai T(x) := Ax untuk setiap x∈Rn, merupakan suatu operator linear arena kondisi T(αx+βy) = A·(αx+βy) = αAx+βAy=αT (x) + βT (y) terpenuhi berdasarkan sifat linearitas perkalian matriks (Strang, 2021;Roman,2005), untuk setiap α, β ∈Rdan x,y∈Rn. Dalam aljabar max-plus, kita juga memiliki matriks. Jika pada aljabar linear standar sistem perkalian matriks mengikuti kaidah operasi +dan ·seperti yang dijelaskan dalam Contoh 2 dan Gambar 2.1, maka untuk matriks max-plus, digunakan ⊕dan ⊗sebagai gantinya. Misalkan diberikan suatu matriks max-plus n×nsebagai R∈Zn×n max yang dapat diekspresikan sebagai R=     r11 r12 · · · r1n r21 r22 · · · r2n . . .. . ..... . . rn1rn2· · · rnn      ©2025 Rizal Purnawan. Licensed under CC BY-NC 4.0 Hal. 13 BAB 2 doi: 10.5281/zenodo.17798786 di mana rij ∈Zmax. Jika a∈Zn max dengan a=     a1 a2 . . . an      , maka perkalian matriks max-plus antara Rdan adiberikan sebagai R⊗a:=      r11 r12 · · · r1n r21 r22 · · · r2n . . .. . ..... . . rn1rn2· · · rnn      ⊗     a1 a2 . . . an      :=      (r11 ⊗a1)⊕(r11 ⊗a1)⊕···⊕(r1n⊗an) (r21 ⊗a1)⊕(r21 ⊗a1)⊕···⊕(r2n⊗an) . . . (rn1⊗a1)⊕(rn1⊗a1)⊕···⊕(rnn ⊗an)      =     Ln k=1 r1k⊗ak Ln k=1 r2k⊗ak . . . Ln k=1 rnk ⊗ak      . Untuk memahami mekanisme perkalian matriks max-plus secara intuitif, mari kita amati contoh berikut. Contoh 3 (Perkalian Matriks Max-Plus).Diberikan suatu semimodul max-plus Z3 max. Diberikan suatu matriks max-plus R∈ Z3×3 max sebagai R=  0ε ε ε0 1 ε2 3 . ©2025 Rizal Purnawan. Licensed under CC BY-NC 4.0 Hal. 14 BAB 2 doi: 10.5281/zenodo.17798786 Kemudian diberikan suatu elemen semimodul max-plus a∈Z3 max sebagai a=  0 1 ε . Perkalian max-plus matriks antara Rdan adiberikan sebagai berikut: R⊗a=  0ε ε ε0 1 ε2 3 ⊗  0 1 ε  =  (0 ⊗0) ⊕(ε⊗1) ⊕(ε⊗ε) (ε⊗0) ⊕(0 ⊗1) ⊕(1 ⊗ε) (ε⊗0) ⊕(2 ⊗1) ⊕(3 ⊗ε)  =  max{0+0, ε + 1, ε +ε} max{ε+ 0,0+1,1+ε} max{ε+ 0,2+1,3+ε}  =  max{0, ε, ε} max{ε, 1, ε} max{ε, 3, ε}  =  0 1 3  Ilustrasi intuitif mengenai mekanisme perkalian di atas diberikan pada Gambar 2.2. ©2025 Rizal Purnawan. Licensed under CC BY-NC 4.0 Hal. 15 BAB 2 doi: 10.5281/zenodo.17798786 Gambar 2.2: Mekanisme intuitif perkalian R⊗a Sama halnya dengan aljabar linear standar, perkalian matriks max-plus juga merupakan operator linear pada semimodul maxplus, karena R⊗(µ⊗a⊕ν⊗b) = (µ⊗R⊗a)⊕(ν⊗R⊗b)(2.1) berlaku untuk setiap a,b∈Zn max dan µ, ν ∈Zmax. 2.3 Notasi Kleene-Star 2.3.1 Penjelasan Notasi Kleene-Star Salah satu atribut penting pada aljabar max-plus adalah notasi Kleene-star. Jika R∈Zn×n max merupakan suatu matriks max-plus, maka Kleene-star dari Rdiberikan sebagai R∗:= ∞ M k=0 R⊗(k)=R⊗(0) ⊕R⊗(1) ⊕R⊗(2) · · · (2.2) di mana notasi (·)⊗kadalah pemangkatan matriks hingga kkali, yaitu, R⊗(k):= k O i=0 R=I⊗R⊗···⊗R | {z } kkali ©2025 Rizal Purnawan. Licensed under CC BY-NC 4.0 Hal. 16 BAB 2 doi: 10.5281/zenodo.17798786 untuk setiap bilangan bulat tak negatif k∈N, di mana I∈Zn×n max adalah matriks max-plus identias yang diberikan sebagai I=     0ε . . . ε ε0··· ε . . .. . ....ε ε ε · · · 0      . Jika dioperasikan dengan suatu elemen semimodul max-plus a∈Zn max melalui perkalian matriks max-plus, maka berdasarkan sifat distribusi ⊗terhadap ⊕dalam aljabar max-plus, kita dapatkan R∗⊗a= ∞ M k=0 R⊗(k)!⊗a= ∞ M k=0 R⊗(k)⊗a.(2.3) Kemudian, jika diberikan suatu pemetaan T:Zn max →Zn max yang didefinisikan dengan perkalian di atas, yaitu T(a) := R∗⊗a, maka Tjuga merupakan suatu operator linear karena T(µ⊗a⊕ν⊗b)=R∗⊗(µ⊗a⊕ν⊗b) = ∞ M k=0 R⊗(k)!⊗(µ⊗a⊕ν⊗b) =µ⊗ ∞ M k=0 R⊗(k)⊗a! ⊕ν⊗ ∞ M k=0 R⊗(k)⊗b! ©2025 Rizal Purnawan. Licensed under CC BY-NC 4.0 Hal. 17 BAB 2 doi: 10.5281/zenodo.17798786 =µ⊗T(a)⊕ν⊗T(b) terpenuhi berdasarkan Ekspresi 2.3 serta berdasarkan linearitas perkalian matriks max-plus (Ekspresi 2.1), untuk setiap a,b∈ Zn max dan µ, ν ∈Zmax. Pada bab selanjutnya kita akan melihat bagaimana notasi Kleene-star akan mempermudah kita dalam melakukan komputasi terkait waktu dimulainya tiap aktivitas pada proyek. 2.3.2 Notasi Kleene-Star Terpotong Dalam konteks komputasi, kita tidak mungkin melakukan operasi sampai waktu tak terhingga. Sehingga, kita akan perlu memotong operasi Kleene-star untuk keperluan tersebut. Modifikasi yang akan dijelaskan ini dapat kita sebut Kleene-star terpotong (truncated Kleene-star). Diberikan suatu matriks R∈Zn×n max , Kleene-star terpotong dari Rhingga qdiberikan sebagai R∗(q):= q−1 M k=0 R⊗(k),(2.4) untuk suatu bilangan bulat positif q∈Ndengan q≥1. Kemudian perkalian Kleene-star dari Rdengan suatu a∈Zn max diberikan serupa dengan Ekspresi 2.3 sebagai R∗(q)⊗a:= q−1 M k=0 R⊗(k)⊗a.(2.5) ©2025 Rizal Purnawan. Licensed under CC BY-NC 4.0 Hal. 18 Bab 3 Komputasi Durasi Total Proyek dengan Aljabar Max-Plus Dalam Bab ini kita akan mempelajari demonstrasi untuk menghitung durasi total proyek menggunakan aljabar max-plus. Contoh proyek yang digunakan adalah sama persis dengan yang diberikan pada Bab 1.1 dan Gambar 1.1. 3.1 Model Semimodul Max-Plus Pertama kita harus menentukan semimodul max-plus yang kita gunakan sebagai model untuk permasalah proyek tersebut. Tepatnya, kita harus menentukan nilai npada Zn max. Nilai ndalam Zn max pada masalah penjadwalan proyek didefinisikan sebagai jumlah aktivitas-aktivitas yang ada dalam proyek tersebut. 19 BAB 3 doi: 10.5281/zenodo.17798786 = 11 + 7 = 18 , yang juga sama dengan hasil komputasi maupun perhitungan manual pada Bab 1.2. Hasil ini sama persis dengan hasil pada Bab 1.2 yang sebelumnya kita dapatkan dengan pengamatan secara langsung pada critical path dari graf pada Gambar 1.1. 3.5 Kesimpulan Pada Bab ini, kita telah mendemonstrasikan penggunaan aljabar max-plus untuk menentukan penjadwalan suatu proyek sederhana yang diberikan pada Bab 1.1 dan Gambar 1.1. Hasil yang diberikan pada Bab 3.4 telah terkonfirmasi sama dengan hasil perhitungan manual pada Bab 1.2. Hal ini menunjukkan validitas teori aljabar max-plus dalam terapan penjadwalan. Dalam kasus penjadwalan sederhana seperti yang kita gunakan, mungkin penerapan aljabar max-plus akan terlihat rumit, terutama jika diterapkan melalui perhitungan manual. Tetapi, memang seharusnya aljabar max-plus diimplementasikan sebagai teknik komputasi menggunakan komputer. (Kami telah memberikan demonstrasi komputasi menggunakan Python yang dapat diakses melalui tautan ini). Untuk kasus yang sangat rumit, komputasi dengan aljabar max-plus akan menjadi sangat superior dibanding teknik konvensional lain. Ini dikarenakan kita dapat mereduksi permasalahan penjadwalan hingga menjadi hanya sebuah perkalian matriks max-plus. ©2025 Rizal Purnawan. Licensed under CC BY-NC 4.0 Hal. 26 Bibliografi Baccelli, F., Cohen, G., Olsder, G. J., and Quadrat, J.-P. (1992). Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley. Golan, J. S. (1999). Semirings and their Applications. Springer Dordrecht. Guichard, D. (2025). An Introduction to Combinatorics and Graph Theory, chapter Graph Theory. Whitman College, https://www.whitman.edu/mathematics/ cgt_online/book/chapter05.html. Judson, T. W. (2013). Abstract Algebra: Theory and Applications, chapter Fields. Orthogonal Publishing L3C. Roman, S. (2005). Advanced Linear Algebra, chapter Linear Transformations. Springer. Strang, G. (2021). Introduction to Linear Algebra (Edition 5). Wellesley-Cambridge Press, Cambridge, UK. 27