ii
ABSTRAK Dwi Setiawan, 2016. APLIKASI ALJABAR MAKS-PLUS PADA MASALAH PENJADWALAN PENGOPERASIAN BUS BATIK SOLO TRANS (BST) KORIDOR SATU DI SURAKARTA. Fakultas Matematika dan Ilmu Pengetahuan Alam. Universitas Sebelas Maret. Aljabar maks-plus merupakan cabang ilmu matematika bidang aljabar. Aljabar maks-plus dinotasikan dengan Rmax yang merupakan himpunan dari Rϵ = R∪{ϵ = −∞} dengan dua operasi biner yaitu maksimum yang dinotasikan ⊕ dan penjumlahan yang dinotasikan ⊗. Aljabar maks-plus dapat digunakan untuk menyelesaikan beberapa permasalahan dalam kehidupan sehari-hari. Permasalahan tersebut diantaranya, masalah sistem produksi, sistem transportasi, dan sistem penjadwalan. Contoh yang disebutkan merupakan contoh dari discrete event system (DES). Suatu DES dapat diselesaikan dengan sistem linier maks-plus waktu invarian. Tujuan dari penelitian ini adalah mengaplikasikan aljabar maks-plus pada masalah penjadwalan. Penjadwalan yang dimaksud adalah jadwal pengoperasian bus BST koridor satu di Surakarta dengan menentukan waktu keberangkatan dari setiap shelter. Dalam penelitian ini ditentukan jadwal keberangkatan bus BST dari dua model yang berbeda, yaitu model yang mengabaikan lampu merah (model bus priority) dan model yang memperhatikan lampu merah (model bus reguler). Dalam pembuatan jadwal, secara umum dilakukan dengan menyelesaikan sistem persamaan linier v(k + 1) = A ⊗ v(k). Dengan v(k) merupakan keberangkatan ke-(k) dan A merupakan matriks yang elemennya berupa waktu tempuh bus antar shelter. Selanjutnya menentukan nilai eigen dan vektor eigen dari matriks A. Dari nilai eigen dan barisan vektor eigen diperoleh jadwal keberangkatan bus BST dari setiap shelter. Nilai eigen yang dihasilkan merepresentasikan periode keberangkatan bus dengan nilai eigen model bus priority adalah 13.2 menit dan model bus reguler adalah 17.733 menit. Jadwal keberangkatan BST secara periodik berdasarkan persamaan v(k + 1) = λ ⊗ v(k), dengan λ merupakan nilai eigen dari masing-masing model. Kata kunci: aljabar max-plus, BST, bus, nilai eigen, penjadwalan, shelter, dan vektor eigen.
iii
ABSTRACT Dwi Setiawan. 2016. APPLICATIONS OF MAX-PLUS ALGEBRA ON THE SCHEDULING PROBLEMS OPERATION OF THE FIRST CORRIDOR BATIK SOLO TRANS (BST) IN SURAKARTA. Faculty of Mathematics and Natural Sciences. Sebelas Maret University. The max-plus algebra is a branch of mathematical sciences field of algebra. The max-plus algebra is denoted by Rmax sets of Rϵ = R ∪ {ϵ = −∞} with two binary operations, there are maximum dentoted by ⊕ and addition denoted by ⊗. Max-plus algebra is appropiately to solve live problems. Those problems include the problems of production system, transportation system, and scheduling system. The examples of that are examples of discrete event system (DES). A DES can be solved with a system of max-plus linear invariant time. The purpose of this research is to apply the max-plus algebra in scheduling problems. Scheduling in question is operating schedules of the first corridor BST in Surakarta to determine the time of departure for each shelter. In this research the schedule of BST departure is determined by two different models. There are bus priority model and regular bus model. The schedule of manufacture was done by complete the linear equation system v(k + 1) = A ⊗ v(k), with v(k) is a departure to-k and A is a matrix element in the form of travel time bus between the shelter. Furthermore determine the eigenvalues and eigenvectors of matrix A. Base on eigenvalues and rows of eigenvectors were obtained schedule of BST for each shelter. The result of eigenvalues represent the period of bus departure, with eigenvalues bus priority model is 13.2 minutes and regular bus model is 17.733 minutes. Departures of BST periodically based on the equation v(k + 1) = λ ⊗ v(k), with λ is the eigenvalues of each model. Keywords: max-plus algebra, BST, bus, eigenvalue, scheduling, eigenvector.
iv
MOTO
If you believe, nothing is impossible (Penulis)
Change your habbit or Habbit will be change you (Penulis)
Alon-alon waton kelakon (Falsafah Jawa)
Hasil tidak akan mengkhianati usaha (Penulis)
Niat, usaha, dan doa satu paket menuju keberhasilan yang tidak bisa terpisahkan (Penulis)
v
PERSEMBAHAN
Karya sederhana ini kupersembahkan untuk
Ibuku Sumiyem dan bapakku Suparman yang senantiasa mendoakan dan memberikan kasih sayangnya selama ini
Kakak dan Adik-adiku si Kembar (Alex Nugroho dan Adi Mustofa) yang senantiasa memberikan motivasi serta memberikan waktu bercandanya disela-sela pennyusunan karya ini
Om, Bude dan Bulik terimakasih atas bantuan dan doa-doanya
Teman-teman matematika 2011 terimakasih untuk empat tahun terakhir ini yang telah membuat cerita dalam perjalananku hingga terselesaikanya karya ini
vi
KATA PENGANTAR Puji syukur kepada Tuhan Yang Maha Esa atas limpahan berkat dan rahmatNya sehingga penulis dapat menyelesaikan skripsi ini. Ucapan terima kasih penulis sampaikan kepada 1. Drs. Siswanto, M.Si. sebagai Pembimbing I yang telah memberikan bimbingan materi dan penulisan dalam skripsi ini, 2. Dr. Sutanto, S.Si., DEA sebagai Pembimbing II yang telah memberikan bimbingan, saran, dan masukan dalam penulisan skripsi ini, dan 3. teman-teman matematika 2011 serta semua pihak yang tidak dapat penulis sebutkan satu persatu yang telah membantu penulis dalam penulisan karya ini. Semoga skripsi ini bermanfaat.
Surakarta, Januari 2016
Penulis
vii
DAFTAR ISI
ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
ABSTRACT
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
MOTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
v
PERSEMBAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
I
DAFTAR TABEL . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
x
DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xi
NOTASI DAN SIMBOL . . . . . . . . . . . . . . . . . . . . . . . . . .
xii
PENDAHULUAN
1
1.1
Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Perumusan Masalah
. . . . . . . . . . . . . . . . . . . . . . . . .
3
1.3
Tujuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.4
Manfaat Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . .
3
II LANDASAN TEORI
4
2.1
Tinjauan Pustaka . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
Landasan Teori . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2.1
Batik Solo Trans . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.2
Struktur Aljabar . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.3
Teori Graf . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2.4
Discrete Event System (DES) . . . . . . . . . . . . . . . .
9
2.2.5
Aljabar Maks-Plus . . . . . . . . . . . . . . . . . . . . . .
9
2.2.6
Matriks dalam Rmax . . . . . . . . . . . . . . . . . . . . .
11
viii
2.3
2.2.7
Sistem Linear Maks-Plus Waktu Invarian (SLMI) . . . . .
13
2.2.8
Nilai Eigen dan Vektor Eigen . . . . . . . . . . . . . . . .
13
Kerangka Pemikiran . . . . . . . . . . . . . . . . . . . . . . . . .
15
III METODE PENELITIAN
17
IV HASIL DAN PEMBAHASAN
18
4.1
Kondisi Pengoperasian BST di Lapangan . . . . . . . . . . . . . .
18
4.2
Model Aljabar Maks-Plus Pada Masalah Penjadwalan BST . . . .
20
4.3
Jadwal Pengoperasian BST
. . . . . . . . . . . . . . . . . . . . .
28
4.3.1
Kendala (Lampu Merah) Diabaikan . . . . . . . . . . . . .
29
4.3.2
Pengoperasian BST dengan Kendala Diperhatikan . . . . .
36
V PENUTUP
41
5.1
Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
5.2
Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
DAFTAR PUSTAKA
43
LAMPIRAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
45
DAFTAR TABEL
2.1
Lama bus BST berhenti di shelter . . . . . . . . . . . . . . . . . .
16
4.1
Waktu tempuh perjalanan bus BST . . . . . . . . . . . . . . . . .
19
4.2
Pemisalan shelter . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
4.3
Jadwal keberangkatan BST 1 . . . . . . . . . . . . . . . . . . . .
35
4.4
Jadwal keberangkatan BST 2 . . . . . . . . . . . . . . . . . . . .
39
5.1
Jadwal keberangkatan BST . . . . . . . . . . . . . . . . . . . . .
41
5.2
Jadwal keberangkatan bus BST model bus priority
. . . . . . . .
48
5.3
Jadwal keberangkatan bus BST model bus reguler . . . . . . . . .
49
x
DAFTAR GAMBAR
2.1
Graf sederhana . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2
Graf berarah
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.3
Graf berbobot . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
4.1
Rute sederhana yang dilalui BST . . . . . . . . . . . . . . . . . .
18
4.2
Jadwal Keberangkatan BST . . . . . . . . . . . . . . . . . . . . .
40
5.1
Rute yang ditempuh BST . . . . . . . . . . . . . . . . . . . . . .
45
5.2
Bus BST tampak depan . . . . . . . . . . . . . . . . . . . . . . .
46
5.3
Bus BST tampak belakang . . . . . . . . . . . . . . . . . . . . . .
46
5.4
Bus BST tampak samping . . . . . . . . . . . . . . . . . . . . . .
47
5.5
Bus BST tampak dalam . . . . . . . . . . . . . . . . . . . . . . .
47
xi
NOTASI DAN SIMBOL
G
: grup
R
: ring
F
: field
S
: semiring
R
: himpunan bilangan real
Rmax
: aljabar maks-plus
Rϵ
: himpunan elemen pada aljabar maks-plus yaitu R dan ϵ = − ∝
∪
: union
+
:
×
: operasi perkalian dalam aljabar biasa
⊕
: operasi maksimum dalam aljabar maks-plus
⊗
: operasi penjumlahan dalam aljabar maks-plus
Rm×n max
: himpunan matriks berukuran m × n dalam aljabar maks-plus
λ
: nilai eigen
v
: vektor eigen
V (G)
:
himpunan vertex pada graf G
V (G)
:
himpunan edge pada graf G
operasi penjumlahan dalam aljabar biasa
xii
BAB I PENDAHULUAN 1.1
Latar Belakang
Aljabar maks-plus merupakan cabang dari ilmu matematika bidang aljabar. Struktur aljabar maks-plus mengacu pada struktur aljabar secara umum. Dalam aljabar operasi yang digunakan secara umum adalah penjumlahan (+) dan perkalian (×). Menurut Muchlisah [9, 10] dan Hungerford [7] suatu himpunan tak kosong yang dilengkapi dengan operasi biner penjumlahan dan perkalian akan membentuk suatu ring(R) jika merupakan suatu grup komutatif terhadap penjumlahan dan bersifat asosiatif terhadap perkalian serta bersifat distributif terhadap penjumlahan dan perkalian. Suatu ring(R) dapat membentuk suatu field (F) atau lapangan jika merupakan division ring yang bersifat komutatif. Menurut Rudhito [11] struktur dari aljabar maks-plus adalah semifield idempoten yang dinotasikan sebagai Rmax . Aljabar maks-plus (Rmax ) merupakan himpunan dari Rϵ = R ∪ {ϵ = −∞} dengan dua operasi biner yaitu maksimum yang dinotasikan ⊕ dan penjumlahan yang dinotasikan ⊗. Aljabar maks-plus dapat digunakan untuk menyelesaikan beberapa permasalahan dalam kehidupan sehari-hari. Permasalahan tersebut diantaranya, masalah sistem manufaktur fleksibel, jaringan telekomunikasi, sistem proses paralel, sistem traffic control, dan sistem logistik [14]. Contoh yang disebutkan merupakan contoh dari discrete event system (DES). Suatu sistem dikatakan DES apabila sistem tersebut akan bekerja pada suatu komponen jika telah selesai dari komponen sebelumnya. Menurut Schutter [12] beberapa klasifikasi masalah yang termasuk ke dalam DES dapat diselesaikan dengan menggunakan sistem linier maks-plus waktu invarian (SLMI). Menurut Heidergot [6] SLMI dibedakan menjadi dua, yaitu SLMI yang mempunyai jadwal keberangkatan khusus dan SLMI 1
yang tidak memiliki jadwal keberangkatan khusus. SLMI yang tidak memiliki jadwal keberangkatan khusus disebut SLMI autonomous. Aljabar maks-plus juga dapat diaplikasikan dalam masalah penjadwalan [1, 17, 18]. Sebagai contoh aplikasi penjadwalan dalam bidang transportasi publik. Transportasi publik merupakan sistem transportasi yang disediakan pemerintah untuk masyarakat umum. Salah satu contohnya adalah transportasi publik di kota Solo yaitu Batik Solo Trans (BST). Keberadaan BST diharapkan dapat membantu masyarakat dalam beraktivitas sehari-hari. Dengan adanya aktivitas masyarakat yang beragam tentu saja kebutuhan akan transportasi dengan BST juga beragam. Sehingga diperlukan adanya jadwal dalam pengoperasian BST agar semua kebutuhan masyarakat terpenuhi. Dalam pembuatan jadwal, kondisi lapangan merupakan satu hal yang sangat perlu diperhatikan. Kondisi lapangan yang perlu diperhatikan dalam masalah penjadwalan ini adalah rute yang akan dilalui serta tempat pemberhentian bus (shelter ) yang disinggahi BST sementara dan waktu tempuh antar shelter. Data tersebut akan direpresentasikan ke dalam bentuk graf berarah dengan vertex-vertexnya adalah shelter pilihan dan jarak antar shelter sebagai edge serta waktu tempuh antar shelter sebagai bobot dari edge. Selanjutnya, graf tersebut diubah ke dalam bentuk matriks dan diselesaikan dengan menggunakan SLMI. Pada sistem linier maks-plus waktu invarian akan diperoleh nilai eigen dan vektor eigen sebagai hasil akhir dari penelitian ini. Nilai eigen dan vektor eigen tersebut selanjutnya direpresentasikan dalam masalah penjadwalan. Penelitian ini mengacu pada Anderson [1], Vries [17], dan Winarni [18] yang menerapkan aplikasi aljabar maks-plus pada masalah penjadwalan keberangkatan pesawat disuatu bandara, keberangkatan kereta api dan keberangkatan bus. Aplikasi tersebut selanjutnya diaplikasikan untuk masalah penjadwalan pengoperasian bus BST di Surakarta dengan menyesuaikan keadaan lapangan di Surakarta. Penjadwalan yang dimaksud dalam hal ini adalah waktu keberangkatan bus di setiap shelter.
2
1.2
Perumusan Masalah
Berdasarkan latar belakang masalah, didapat rumusan masalah yaitu bagaimana mengaplikasikan aljabar maks-plus pada masalah penjadwalan pengoperasian BST koridor satu di Surakarta.
1.3
Tujuan
Tujuan dari penelitian ini adalah dapat mengaplikasikan aplikasi aljabar maks-plus pada masalah penjadwalan pengoperasian BST koridor satu di Surakarta dengan menentukan waktu keberangkatan dari setiap shelter dalam model aljabar maks-plus.
1.4
Manfaat Penelitian
Manfaat dari penelitian ini dibagi menjadi dua, yaitu manfaat teoritis dan manfaat praktis. 1. Manfaat Teoritis Manfaat teoritis dari penelitian ini dapat memberikan wawasan yang lebih luas tentang aljabar maks-plus khususnya pada masalah nilai eigen dan vektor eigen. 2. Manfaat Praktis Manfaat praktis dari penelitian ini dapat memberikan wawasan tentang aplikasi aljabar maks-plus. Penelitian ini difokuskan pada aplikasi aljabar maks-plus tentang masalah penjadwalan keberangkatan bus BST di Surakarta. Hal serupa juga dapat dikerjakan pada masalah penjadwalan keberangkatan dan kedatangan kereta api di stasiun, penjadwalan keberangkatan dan kedatangan pesawat di suatu bandara serta masalah sistem produksi.
3
