Aplikasi Aljabar Max-Plus Pada Masalah Penjadwalan Flow Shop

Aulia Nurul Ikhsani, Dr. Drs. Al. Sutjijana, M.Sc.

2025 | Skripsi | MATEMATIKA

Pada skripsi ini dibahas mengenai aljabar max-plus dan aplikasinya dalam masalah penjadwalan flow shop. Aljabar max-plus memegang peranan penting dalam penyusunan urutan job pada mesin untuk meminimalkan waktu penyelesaian yang kemudian dikenal dengan Aturan Johnson. Pada skripsi ini ditunjukkan bagaimana memperoleh algoritma Johnson pada 2 mesin flow shop dan aplikasinya. Lebih lanjut, penyusunan urutan pada 3 mesin flow shop analog dengan masalah pada 2 mesin dengan syarat khusus. Selain itu, ditunjukkan perluasan aturan Johnson serta sebuah teorema yang memberikan syarat cukup penjadwalan pada m mesin dengan menganalogikan aljabar max-plus dengan proposisi yang ada pada aljabar linear. 

This undergraduate thesis discusses max-plus algebra and its application to flow shop scheduling problems. Max-plus algebra plays a significant role in determining job sequences on machines to minimize completion time, which is commonly known as Johnson’s Rule. This study demonstrates how to derive the Johnson algorithm for a two-machine flow shop and its application. Furthermore, the sequencing problem for a three-machine flow shop is shown to be analogous to the two-machine case under certain conditions. In addition, this undergraduate thesis presents an extension of Johnson’s Rule along with a theorem that establishes sufficient conditions for scheduling in an m-machine system by drawing analogies between max-plus algebra and propositions in linear algebra.

Kata Kunci : aljabar max-plus, penjadwalan, flow shop, aturan Johnson, job matriks