APLIKASI ALJABAR MAKS-PLUS PADA SISTEM PENJADWALAN KERETA REL LISTRIK (KRL) JABODETABEK
oleh AHMAD DIMYATHI M0111003
SKRIPSI ditulis dan diajukan untuk memenuhi sebagian persyaratan memperoleh gelar Sarjana Sains Matematika
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA 2016
APLIKASI ALJABAR MAKS-PLUS PADA SISTEM PENJADWALAN KERETA REL LISTRIK (KRL) JABODETABEK
oleh AHMAD DIMYATHI M0111003
SKRIPSI ditulis dan diajukan untuk memenuhi sebagian persyaratan memperoleh gelar Sarjana Sains Matematika
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA 2016
i
KATA PENGANTAR
Puji syukur kehadirat Allah SWT atas rahmat dan hidayahNya sehingga penulis dapat menyelesaikan laporan skripsi ini dengan baik dan lancar. Penulis menyadari bahwa laporan skripsi ini banyak mengalami kesulitan, namun berkat bantuan dan bimbingan dari berbagai pihak kesulitan-kesulitan dapat terselesaikan dengan baik. Oleh karena itu, penulis mengucapkan terima kasih kepada 1. Drs. Siswanto, M.Si dan Drs. Pangadi, M.Si sebagai pembimbing I dan Pembimbing II yang telah memberikan bimbingan dan arahan baik penulisan maupun materi. 2. Semua pihak yang membantu dalam penulisan skripsi ini yang tidak dapat penulis sebut satu per satu. Semoga laporan ini dapat memberikan manfaat bagi seluruh pihak yang membutuhkan. Surakarta,
Mei 2016 Penulis
iii
ABSTRAK Ahmad Dimyathi, 2016. APLIKASI ALJABAR MAKS-PLUS PADA SISTEM PENJADWALAN KERETA REL LISTRIK (KRL) JABODETABEK. Fakultas Matematika dan Ilmu Pengetahuan Alam. Universitas Sebelas Maret. Misalkan R merupakan himpunan bilangan real dan Rϵ = R ∪ {ϵ} dengan ϵ = − ∝. Aljabar maks-plus (Rmax ) merupakan himpunan Rϵ yang dilengkapi operasi maksimum (⊕) dan jumlahan (⊗). Aljabar maks-plus dapat digunakan untuk menyelesaikan masalah discrete event system (DES ), salah satunya masalah penjadwalan. Tujuan dari penelitian ini adalah mengaplikasikan aljabar maks-plus pada sistem penjadwalan kereta rel listrik (KRL) JABODETABEK dengan menentukan jadwal keberangkatan kemudian melakukan simulasi keterlambatan. Jadwal diperoleh dengan menyelesaikan sistem persamaan linier x(k + 1) = A ⊗ x(k) dengan x(k) merupakan keberangkatan ke-k dan A merupakan matriks dengan elemen berupa waktu perjalanan KRL. Selanjutnya menentukan nilai eigen dan vektor eigen dari matriks A. Nilai eigen dan vektor eigen merepresentasikan periode keberangkatan KRL dan jadwal keberangkatan KRL. Simulasi keterlambatan dilakukan dengan menentukan vektor keterlambatan z(k) = x(k) − d(k). Hasil simulasi keterlambatan diperoleh pada k ≥ 3 vektor keterlambatan z(k) bernilai 0 yang menandakan tidak terjadi lagi keterlambatan keberangkatan KRL selanjutnya, dalam hal ini dikatakan penjadwalan dalam keadaan stabil. Kata kunci: aljabar maks-plus, DES, KRL, nilai eigen, vektor eigen, penjadwalan, simulasi keterlambatan, vektor keterlambatan, stabil.
iv
ABSTRACT Ahmad Dimyathi. 2016. APPLICATIONS OF MAX-PLUS ALGEBRA ON THE SCHEDULING SYSTEM OF THE ELECTRICAL TRAIN (ET) JABODETABEK. Faculty of Mathematics and Nature Sciences. Sebelas Maret University. Let R be the set of real numbers and Rϵ = R ∪ {ϵ} with ϵ = − ∝. Maxplus algebra (Rmax ) is a set of Rϵ equipped with maximum (⊕) and sum (⊗) operations. Max-plus algebra can be used to solve the Discrete Event System (DES) problems. Scheduling is one of the problems. The purpose of this research is to apply the max-plus algebra on the scheduling system of the Electrical Train (ET) JABODETABEK to determine the departure time and then simulate a delay. The schedules are obtained by completing the linear equation system. The equation system is x(k + 1) = A ⊗ x(k) with x(k) is a departure to-k and A is a matrix element in the form of travel time ET. Furthermore, the eigenvalues and eigenvectors of matrix A are determined. The eigenvalues represent the period of departure and eigenvectors represent ET departure. The simulation of delay is obtained by determining vector z(k) = x(k) − d(k). The result of delay simulation is obtained in k ≥ 3 and delay vector z(k) is 0 so indicating no delay for the next departure of ET. In this case, the schedule is on stable condition. Keywords: max-plus algebra, DES, ET, eigenvalue, eigenvector, scheduling, simulation of delay, delay vector, stable.
v
MOTTO
If you believe, nothing is impossible (Penulis)
Sesungguhnya bersama kesulitan ada kemudahan.(Qs. Al-Insyirah:6)
vi
PERSEMBAHAN
Karya ini kupersembahkan untuk bapak dan ibu saya yang selalu memberiku semangat hingga karya ini dapat terselesaikan dengan baik dan terima kasih atas cinta kasih dan pengorbanan yang telah diberikan kepadaku.
vii
DAFTAR ISI HALAMAN JUDUL . . . . . HALAMAN PENGESAHAN KATA PENGANTAR . . . . ABSTRAK . . . . . . . . . . ABSTRACT . . . . . . . . . MOTTO . . . . . . . . . . . . PERSEMBAHAN . . . . . . . DAFTAR ISI . . . . . . . . . DAFTAR TABEL . . . . . . DAFTAR GAMBAR . . . . . NOTASI DAN SIMBOL . . . I
PENDAHULUAN 1.1 Latar Belakang . . . 1.2 Perumusan Masalah 1.3 Tujuan . . . . . . . . 1.4 Manfaat . . . . . . .
. . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
II LANDASAN TEORI 2.1 Tinjauan Pustaka . . . . . . . . . . . . 2.1.1 KRL JABODETABEK . . . . . 2.1.2 Struktur Aljabar . . . . . . . . 2.1.3 Teori Graf . . . . . . . . . . . . 2.1.4 Discrete Event System . . . . . 2.1.5 Aljabar Maks-Plus . . . . . . . 2.1.6 Matriks dan Vektor dalam Rmax 2.1.7 Sistem Linear Maks-Plus Waktu 2.1.8 Nilai Eigen dan Vektor Eigen . 2.1.9 Kestabilan Jaringan KRL . . . 2.2 Kerangka Pemikiran . . . . . . . . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Invarian . . . . . . . . . . . . . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (SLMI) . . . . . . . . . . . . . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . . .
. . . . . . . . . . .
. i . ii . iii . iv . v . vi . vii . viii . x . xi . xii
. . . .
. . . .
1 1 3 3 3
. . . . . . . . . . .
4 4 5 6 7 9 9 11 13 14 16 17
. . . . . . . . . . .
III METODE PENELITIAN
19
IV PEMBAHASAN 4.1 Sistem Penjadwalan KRL . . . . . . . . . . . . . . . . . . . . . . 4.2 Aplikasi Aljabar Maks-Plus pada Sistem Penjadwalan KRL . . . .
20 20 22
viii
4.2.1 4.2.2 4.2.3
Model Aljabar Maks-Plus . . . . . . . . . . . . . . . . . . Jadwal Keberangkatan KRL . . . . . . . . . . . . . . . . . Simulasi Terhadap Keterlambatan . . . . . . . . . . . . . .
22 27 30
V PENUTUP 5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34 34 34
DAFTAR PUSTAKA
35
ix
DAFTAR TABEL 4.1 4.2 4.3 4.4 4.5
Jadwal perjalanan KRL. . . . . . . . . . . Pemisalan Kereta. . . . . . . . . . . . . . . Jadwal Keberangkatan KRL . . . . . . . . Jadwal Keberangkatan dan Keterlambatan Simulasi Keterlambatan . . . . . . . . . .
x
. . . . . . . . . KRL . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
22 23 30 32 33
DAFTAR GAMBAR 2.1 2.2 2.3
Graf sederhana . . . . . . . . . . . . . . . . . . . . . . . . . . . . Graf berarah . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Graf berbobot . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 8 9
4.1
Jalur KRL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
xi
NOTASI DAN SIMBOL
G
: grup
R
: ring
F
: field
S
: semiring
R
: himpunan bilangan real
Rmax
: aljabar maks-plus
Rϵ
: elemen aljabar maks-plus yaitu gabungan R dan − ∝
∪
: union
ϵ
: elemen − ∝
+
:
×
: 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
