Implementasi Model Penjadwalan Job-Shop dalam Masalah Penjadwalan Kereta Api Jalur Tunggal dengan Pendekatan Constraint Programming
LAPORAN TUGAS AKHIR
Disusun sebagai syarat kelulusan tingkat sarjana
oleh: Fajar Yuliawan / 13503022
PROGRAM STUDI TEKNIK INFORMATIKA SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA INSTITUT TEKNOLOGI BANDUNG 2008
LEMBAR PENGESAHAN
Program Studi Sarjana Teknik Informatika
Implementasi Model Penjadwalan Job-Shop dalam Masalah Penjadwalan Kereta Api Jalur Tunggal dengan Pendekatan Constraint Programming
Tugas Akhir Program Studi Teknik Informatika ITB
oleh: Fajar Yuliawan / 13503022
Telah disetujui dan disahkan sebagai laporan Tugas Akhir di Bandung, pada tanggal 23 Juni 2008
Pembimbing
Ir. Rinaldi Munir, M.T. NIP 132084796
ii
ABSTRAK
Masalah penjadwalan kereta api jalur tunggal dapat diselesaikan dengan pendekatan Constraint Programming. Hal ini dilakukan dengan memodelkan masalah sebagai sebuah Constraint Satisfaction Problem (CSP) kemudian menyelesaikan CSP tersebut dengan teknik-teknik pencarian solusi CSP. Dalam Tugas Akhir ini, CSP yang digunakan untuk memodelkan masalah penjadwalan kereta api jalur tunggal adalah masalah penjadwalan Job-Shop. Pemodelan dilakukan dengan menganggap perjalanan-perjalanan kereta api sebagai sekumpulan pekerjaan (jobs) yang dijadwalkan pada sekumpulan sumber daya (resources) yang berupa segmen-segmen jalur kereta api. Selanjutnya, algoritma yang digunakan dalam pencarian solusi adalah Hill-Climbing. Dalam masalah penjadwalan kereta api, solusi yang dimaksud adalah jadwal perjalanan kereta api yang memenuhi semua aturan yang diajukan. Tugas Akhir ini membahas aturan-aturan umum dalam penjadwalan kereta api jalur tunggal, pemodelannya sebagai masalah penjadwalan Job-Shop dan penyelesaiannya dengan Hill-Climbing. Selanjutnya, analisis, perancangan dan implementasi dilakukan untuk menghasilkan sebuah perangkat lunak penjadwalan kereta api jalur tunggal Kimspoor Scheduler. Perangkat lunak ini diimplementasikan dengan paradigma pemrograman berorientasi objek menggunakan bahasa pemrograman Java. Sistem operasi yang digunakan dalam pengembangan adalah Microsoft Windows XP Professional. Perangkat lunak Kimspoor Scheduler dapat digunakan untuk memasukkan data perjalanan kereta api, menampilkan data yang telah dimasukkan, melakukan penjadwalan dan menampilkan hasil penjadwalan. Pengujian penjadwalan dilakukan dengan menggunakan data perjalanan kereta api di Indonesia yang diperoleh dari PT Kereta Api (Persero). Dalam setiap pengujian yang dilakukan, perangkat lunak selalu dapat menemukan jadwal yang memenuhi semua aturan umum perjalanan kereta api yang diajukan dalam Tugas Akhir. Keluaran perangkat lunak yang berupa jadwal perjalanan kereta api tersebut ditampilkan dengan menggunakan representasi diagram ruang-waktu.
Kata Kunci: masalah penjadwalan kereta api jalur tunggal, Constraint Programming, Constraint Satisfaction Problem, masalah penjadwalan Job-Shop, Hill-Climbing.
iii
KATA PENGANTAR Alhamdulillaah, segala puji bagi Allah, atas segala rahmat dan karunia-Nya, Penulis dapat menyelesaikan Tugas Akhir yang berjudul Implementasi Model Penjadwalan Job-Shop dalam Masalah Penjadwalan Kereta Api Jalur Tunggal dengan Pendekatan Constraint Programming.
Tugas Akhir ini disusun sebagai syarat kelulusan tingkat sarjana di Program Studi Teknik Informatika, Institut Teknologi Bandung. Dengan selesainya Tugas Akhir ini, Penulis ingin menyampaikan terima kasih kepada semua pihak yang secara langsung maupun tidak langsung telah memberikan banyak bantuan dan dukungan moral kepada Penulis selama masa pelaksanaan Tugas Akhir, yaitu: 1. Bapak Ir. Rinaldi Munir, M.T. selaku dosen pembimbing Tugas Akhir yang selalu meluangkan waktunya untuk memberikan bimbingan dan pengarahan yang diperlukan dalam penyusunan Tugas Akhir ini. 2. Ibu Dra. Harlili, M.Sc. selaku dosen penguji pre proposal, seminar, pra sidang dan sidang, dan Bapak Dr. dr. Oerip S. Santoso, M.Sc. selaku dosen penguji sidang Tugas Akhir yang telah memberikan banyak kritikan dan masukan. 3. Semua anggota keluarga di Solo: bapak, ibu, adik, dan lain-lain dan juga keluarga om Wahyono di Bandung yang senantiasa mendoakan dan memberi dukungan moral bagi Penulis selama pelaksanaan Tugas Akhir ini. 4. Ibu Nur Ulfa Maulidevi, S.T., M.Sc. selaku dosen wali Penulis selama masa pendidikan di Teknik Informatika ITB. 5. Semua dosen di KK IRK, Basis Data, Pemrograman, Intelegensia Buatan, dan RPL yang telah memberikan banyak ilmu yang sangat penting untuk pemahaman Penulis tentang Tugas Akhir yang dilaksanakan. 6. Seluruh staf Tata Usaha, Dukungan Teknis dan Administrasi Lab di Program Studi Teknik Informatika ITB yang telah membantu kelancaran administrasi dan teknis yang diperlukan dalam semua tahap pelaksanaan Tugas Akhir. 7. Mas Dodik, Arif, Nugroho, Tyok dan Indra selaku rekan penulis pada waktu proyek yang telah banyak membantu Penulis dalam pemahaman masalah
iv
penjadwalan kereta api, pemodelan masalahnya, analisis dan perancangan perangkat lunak, serta impelementasi dan pengujian perangkat lunak yang dikembangkan dalam Tugas Akhir ini. 8. Agam, Neni, Mbak Suci, Unggul dan Rolan atas pinjaman laptop-nya serta Nugroho dan Iput atas pinjaman kemeja, dasi dan sepatu yang sangat penting untuk presentasi proposal, seminar, pra sidang dan sidang Tugas Akhir. 9. Hafidh, Syafiq, Andhy, Rohul, Rolan, Fauzan, dan Yoga selaku sahabat yang pernah tinggal serumah dengan Penulis dan selalu menghadirkan suasana menyenangkan di rumah. 10. Teman-teman Penulis di Cisitu: Dean, Neni, Febrian, Eriek, Diko, Jaya, Yavta, Fahris, dan lain-lain dan juga teman Penulis di IRK dan Labdas 4: Ihsan, Taufik, Teguh, Dewangga, Agam, Novis, Andres, Yandri, Dicky, Goro, Nunu, Hananto, Tyok, Indra, dan lain-lain serta semua teman di ITB yang sering Penulis tanyai mengenai Tugas Akhir dan juga hal-hal lain yang penting untuk refreshing ketika pelaksanaan Tugas Akhir: film, serial TV, komik, dan lain-lain. 11. Semua rekan, guru, dan murid Penulis di dunia olimpiade matematika Indonesia: Nanang, Syafri, Prastudy, Hafiz, Pak Muchlis, Pak Hery, Bu Hilda, Bu Utari, Pak Jaka, Rudi, Dimas dan lain-lain yang selalu mendorong Penulis untuk segera menyelesaikan Tugas Akhir ini. 12. Pihak-pihak lain yang telah berkontribusi dalam Tugas Akhir Penulis yang tidak dapat disebutkan satu per satu.
Penulis berharap agar Tugas Akhir ini dapat benar-benar bermanfaat bagi semua pihak yang tertarik dengan masalah penjadwalan kereta api. Penulis juga meminta maaf atas segala kesalahan dan kekurangan yang ada dalam Tugas Akhir ini. Akhir kata, Penulis mengharapkan adanya kritik dan saran yang dapat membantu meningkatkan kualitas Tugas Akhir ini.
Bandung, 23 Juni 2008
Penulis
v
DAFTAR ISI ABSTRAK ............................................................................................................ iii KATA PENGANTAR.......................................................................................... iv DAFTAR ISI......................................................................................................... vi DAFTAR GAMBAR............................................................................................ ix DAFTAR TABEL ................................................................................................ xi BAB I PENDAHULUAN...................................................................................I-1 1.1
Latar Belakang .......................................................................................I-1
1.2
Rumusan Masalah ..................................................................................I-3
1.3
Tujuan ....................................................................................................I-4
1.4
Batasan Masalah ....................................................................................I-4
1.5
Metodologi .............................................................................................I-5
1.6
Sistematika Pembahasan ........................................................................I-6
BAB II DASAR TEORI................................................................................... II-1 2.1
Deskripsi Perjalanan Kereta Api Jalur Tunggal................................... II-1
2.1.1
Pokok-Pokok Perjalanan Kereta Api Jalur Tunggal ................... II-1
2.1.2
Aturan-Aturan Umum Perjalanan Kereta Api Jalur Tunggal ..... II-3
2.1.3
Jalur Ganda dan Jalur Kembar .................................................... II-5
2.1.4
Contoh Kasus Perjalanan Kereta Api Jalur Tunggal .................. II-6
2.2
Masalah Penjadwalan Job-Shop .......................................................... II-8
2.2.1
Definisi Formal ........................................................................... II-8
2.2.2
Kriteria Optimasi pada Masalah Penjadwalan Job-Shop............ II-9
2.2.3
Representasi dengan Graf Disjungtif ........................................ II-10
2.2.4
Ketetanggaan dan Lintasan Kritis ............................................. II-15
2.3
2.2.4.1
Definisi Formal ..................................................................... II-15
2.2.4.2
Ketetanggaan dalam algoritma Hill Climbing ...................... II-16
2.2.4.3
Lintasan Kritis....................................................................... II-16
2.2.4.4
Struktur Ketetanggaan .......................................................... II-18
Constraint Programming ................................................................... II-20
2.3.1 2.3.1.1
Constraint Satisfaction Problem (CSP) .................................... II-20 Definisi Formal ..................................................................... II-20
vi
2.3.1.2 2.3.2
Arc Consistency .................................................................... II-21 Algoritma dan Stretegi Pencarian Solusi .................................. II-23
2.3.2.1
Pencarian Solusi CSP secara Komplit (Complete Search) ... II-24
2.3.2.2
Variable and Value Ordering ............................................... II-25
2.3.2.3
Constraint Satisfaction and Optimization Problem .............. II-27
2.3.2.4
Local Search ......................................................................... II-28
BAB III PEMODELAN MASALAH ........................................................... III-1 3.1
Deskripsi Pemodelan Masalah Penjadwalan Kereta Api Jalur Tunggal dengan Model Masalah Penjadwalan Job-Shop.................................. III-2
3.2
CSP dari Model Masalah .................................................................... III-5
3.2.1
Variabel dan Domain CSP ......................................................... III-5
3.2.2
Batasan-Batasan yang Dimodelkan dalam CSP......................... III-5
3.2.3
Representasi Intensional Batasan-Batasan CSP......................... III-6
3.3
Graf Disjungtif dari Model Masalah................................................... III-8
3.3.1
Struktur Lintasan Kritis.............................................................. III-8
3.3.2
Struktur Ketetanggaan ............................................................... III-9
3.4
Pencarian Solusi Model Masalah dengan Hill Climbing .................. III-10
3.4.1 3.4.1.1
Strategi Kronologis dalam Penyelesaian Konflik ................ III-12
3.4.1.2
Aturan Shortest Processing Time (SPT) .............................. III-13
3.4.2 3.5
Pencarian Solusi Pertama......................................................... III-11
Pencarian Solusi yang Lebih Baik ........................................... III-14
Contoh Kasus Penjadwalan dengan Algoritma Hill Climbing.......... III-15
BAB IV ANALISIS DAN PERANCANGAN ...............................................IV-1 4.1
Analisis ...............................................................................................IV-1
4.1.1
Deskripsi Umum Perangkat Lunak ............................................IV-1
4.1.2
Kebutuhan-Kebutuhan Perangkat Lunak ...................................IV-2
4.1.2.1
Kebutuhan Fungsional Perangkat Lunak ...............................IV-2
4.1.2.2
Kebutuhan Non-Fungsional Perangkat Lunak.......................IV-3
4.1.3
Diagram Use-Case .....................................................................IV-4
4.1.4
Analisis Kelas-Kelas ..................................................................IV-5
4.1.4.1
Identifikasi Kelas-Kelas.........................................................IV-5
4.1.4.2
Diagram Kelas Tahap Analisis ..............................................IV-6
vii
4.2
Perancangan ........................................................................................IV-6
4.2.1
Perancangan Antarmuka ............................................................IV-6
4.2.2
Perancangan Kelas-Kelas.........................................................IV-10
4.2.2.1
Identifikasi Kelas-Kelas Tahap Perancangan ......................IV-10
4.2.2.2
Diagram Kelas Tahap Perancangan .....................................IV-13
BAB V IMPLEMENTASI DAN PENGUJIAN............................................. V-1 5.1
Lingkungan Implementasi dan Pengujian............................................ V-1
5.2
Implementasi........................................................................................ V-1
5.2.1
Batasan Implementasi ................................................................. V-2
5.2.2
Proses dan Hasil Implementasi ................................................... V-3
5.3
5.2.2.1
Implementasi Kelas-Kelas dan Paket-Paketnya...................... V-3
5.2.2.2
Implementasi Algoritma ......................................................... V-6
5.2.2.3
Struktur Data yang Digunakan Dalam Implementasi ........... V-10
5.2.2.4
Antarmuka Perangkat Lunak ................................................ V-11
Pengujian............................................................................................ V-15
5.3.1
Tujuan Pengujian ...................................................................... V-15
5.3.2
Rencana dan Kriteria Keberhasilan Pengujian.......................... V-16
5.3.3
Kasus-Kasus Uji........................................................................ V-19
5.3.4
Pelaksanaan Pengujian.............................................................. V-20
5.3.5
Hasil dan Analisis Pengujian .................................................... V-21
5.3.5.1
Hasil Pengujian Fungsional .................................................. V-21
5.3.5.2
Hasil dan Analisis Pengujian Penjadwalan........................... V-22
BAB VI KESIMPULAN DAN SARAN ........................................................VI-1 6.1
Kesimpulan .........................................................................................VI-1
6.1.1
Kesimpulan Pemodelan dan Penyelesaian Masalah ..................VI-1
6.1.2
Kesimpulan Perangkat Lunak yang Dikembangkan..................VI-2
6.2
Saran ...................................................................................................VI-3
DAFTAR PUSTAKA.......................................................................................... xii LAMPIRAN A CONTOH KASUS UJI DAN PENJADWALANNYA .......A-1
viii
DAFTAR GAMBAR Gambar I-1 Contoh Rute Perjalanan Kereta Api ..................................................I-2 Gambar II-1 Rute Perjalanan Kereta Api dengan Enam Stasiun ........................ II-2 Gambar II-2 Jadwal Kereta Api Menggunakan Diagram Ruang-Waktu............ II-3 Gambar II-3 Jadwal Perjalanan Kereta Api yang Mengandung Konflik............ II-7 Gambar II-4 Jadwal Kereta Api yang Tidak Mengandung Konflik ................... II-8 Gambar II-5 Graf Disjungtif dari Masalah Penjadwalan Job-Shop.................. II-12 Gambar II-6 Graf Disjungtif dengan Simpul Dummy....................................... II-13 Gambar II-7 Upagraf Disjungtif yang Mengandung Sirkuit............................. II-13 Gambar II-8 Graf Tak-Bersirkuit yang Dibentuk dari Graf Disjungtif ............ II-14 Gambar II-9 Jadwal Masalah Penjadwalan Job-Shop....................................... II-14 Gambar II-10 Graf Disjungtif Tetangga ........................................................... II-18 Gambar II-11 Pohon Ruang Status pada Masalah N-Queen Berukuran 4×4.... II-25 Gambar III-1 Contoh Kasus Terburuk Penyelesaian Konflik.......................... III-13 Gambar III-2 Jadwal Dua Kereta yang Bertabrakan........................................ III-14 Gambar III-3 Jadwal Dua Kereta dengan Penundaan di Stasiun ..................... III-14 Gambar III-4 Rute Perjalanan Kereta Api Sederhana...................................... III-15 Gambar III-5 Diagram Ruang-Waktu dari Data pada Tabel III-1 ................... III-17 Gambar III-6 Penyelesaian Konflik Pertama pada Penjadwalan ..................... III-17 Gambar III-7 Penyelesaian Konflik Kedua pada Penjadwalan........................ III-18 Gambar III-8 Graf Disjungtif dari Solusi yang Ditemukan ............................. III-19 Gambar III-9 Graf Disjungtif Tetangga dari Graf pada Gambar III-8............. III-19 Gambar III-10 Jadwal yang Diperoleh dari Graf Disjungtif Tetangga............ III-20 Gambar IV-1 Diagram Use-Case Perangkat Lunak Kimspoor Scheduler......... IV-4 Gambar IV-2 Diagram Kelas Analisis Perangkat Lunak Kimspoor Scheduler . IV-6 Gambar IV-3 Rancangan Antarmuka Utama Perangkat Lunak......................... IV-7 Gambar IV-4 Rancangan Antarmuka Koneksi Basis Data................................ IV-8 Gambar IV-5 Rancangan Antarmuka Panel Masukan dan Penampilan Data.... IV-8 Gambar IV-6 Rancangan Antarmuka Utama dengan Tiga Panel Terbuka........ IV-9 Gambar IV-7 Rancangan Antarmuka Pemilihan Rute....................................... IV-9 Gambar IV-8 Rancangan Antarmuka Penampilan Diagram Ruang-Waktu .... IV-10
ix
Gambar IV-9 Diagram Kelas pada Paket Antarmuka...................................... IV-14 Gambar IV-10 Diagram Kelas pada Paket Basis Data .................................... IV-14 Gambar IV-11 Diagram Kelas pada Paket Penjadwalan ................................. IV-15 Gambar IV-12 Diagram Kelas Antarpaket ...................................................... IV-16 Gambar V-1 Antarmuka Utama Perangkat Lunak............................................ V-12 Gambar V-2 Antarmuka Koneksi Basis Data ................................................... V-12 Gambar V-3 Antarmuka Panel Masukan dan Penampilan Data Stasiun.......... V-13 Gambar V-4 Antarmuka Panel Masukan dan Penampilan Data Petak Jalan.... V-13 Gambar V-5 Antarmuka Panel Masukan dan Penampilan Rute....................... V-14 Gambar V-6 Antarmuka Panel Masukan dan Penampilan Data Perjalanan..... V-14 Gambar V-7 Antarmuka Penampilan Diagram Ruang Waktu.......................... V-15 Gambar V-8 Hasil Penjadwalan yang Mematuhi Aturan Persilangan.............. V-23 Gambar V-9 Hasil Penjadwalan dengan Jalur Kembar .................................... V-24 Gambar V-10 Hasil Penjadwalan yang Mematuhi Aturan Penyusulan dan Headway ................................................................................... V-25 Gambar V-11 Hasil Penjadwalan yang Mematuhi Aturan Waktu Minimum Penundaan di Stasiun ................................................................ V-25 Gambar V-12 Hasil Penjadwalan yang Mematuhi Aturan Kecepatan Maksimal Petak Jalan ................................................................................ V-26 Gambar V-13 Diagram Ruang-Waktu Salah Satu Rute yang Diujikan............ V-28 Gambar A-1 Diagram Ruang-Waktu Hasil Penjadwalan Contoh Kasus Uji...... A-3 Gambar A-2 Pembesaran Rute Klari-Cisomang pada Pukul 06:00-11:00 ......... A-4 Gambar A-3 Pembesaran Rute Cisomang-Bandung pada Pukul 06:00-11:00 ... A-4
x
DAFTAR TABEL Tabel II-1 Data Perjalanan Kereta Api ............................................................... II-7 Tabel II-2 Data Masalah Penjadwalan Job-Shop.............................................. II-11 Tabel III-1 Pemetaan (Mapping) Masalah Penjadwalan Kereta Api Jalur Tunggal dengan Model Masalah Penjadwalan Job-Shop............................... III-3 Tabel III-2 Data Perjalanan Kereta Api ........................................................... III-16 Tabel IV-1 Kebutuhan Fungsional Perangkat Lunak ........................................ IV-2 Tabel IV-2 Kelas-Kelas Tahap Analisis ............................................................ IV-5 Tabel IV-3 Kelas-Kelas pada Paket Antarmuka .............................................. IV-11 Tabel IV-4 Kelas-Kelas pada Paket Basis Data............................................... IV-11 Tabel IV-5 Kelas-Kelas pada Paket Penjadwalan............................................ IV-12 Tabel V-1 Kelas-Kelas Implementasi pada Paket kimspoor.ui ................... V-4 Tabel V-2 Kelas-Kelas pada Pustaka GapekaChart............................................ V-4 Tabel V-3 Kelas-Kelas pada Paket kimspoor.db.......................................... V-5 Tabel V-4 Kelas-Kelas pada Paket kimspoor.scheduler ......................... V-5 Tabel V-5 Kelas-Kelas pada Paket kimspoor.disjunctive .................... V-5 Tabel V-6 Rencana Pengujian Fungsional........................................................ V-16 Tabel V-7 Rencana Pengujian Penjadwalan ..................................................... V-18 Tabel V-8 Hasil Penjadwalan dengan 100 Perjalanan dan 3 Rute.................... V-27 Tabel V-9 Hasil Beberapa Penjadwalan ........................................................... V-29 Tabel A-1 Data Petak Jalan pada Rute JKT-MRI-CKP-PWK-PDL -BDG........ A-1 Tabel A-2 Data Perjalanan dari Jakarta (Gambir) ke Bandung dan Sebaliknya. A-2
xi
