BAB III PEMODELAN MASALAH Masalah penjadwalan kereta api jalur tunggal dapat dimodelkan sebagai sebuah kasus khusus dari masalah penjadwalan Job-Shop. Hal ini dilakukan dengan menganggap perjalanan sebuah kereta api sebagai pekerjaan yang harus dijadwalkan pada sekumpulan sumber daya yang berupa petak-petak blok pada jalur kereta api [OLI00]. Sebuah perjalanan kereta api terdiri atas operasi-operasi yang harus dikerjakan secara berturutan dimana setiap operasi tersebut adalah bagian perjalanan kereta api melewati sebuah petak blok. Urutan operasi-operasi yang harus dikerjakan sama dengan urutan petak blok yang harus dilewati oleh kereta api tersebut. Hal ini dapat dilihat dari rute yang harus dilalui oleh kereta api.
Tidak semua aturan-aturan atau batasan-batasan pada perjalanan kereta api jalur tunggal dapat direpresentasikan dengan baik dengan model masalah penjadwalan Job-Shop. Hal ini karena pencarian solusi masalah penjadwalan dengan batasan yang terlalu banyak membutuhkan waktu yang sangat lama. Selain itu, implementasi beberapa aturan tertentu bisa menyebabkan jadwal yang diperoleh memiliki total keterlambatan yang besar. Oleh karena itu, ada beberapa aturan yang dimodelkan dan ada beberapa yang tidak.
Hal pertama yang dilakukan dalam penyelesaian masalah penjadwalan kereta api jalur tunggal dengan menggunakan pendekatan constraint programming adalah representasi masalah menjadi sebuah CSP. Dalam hal ini, harus ditentukan variabel, domain dan batasan-batasan pada CSP tersebut. Setelah representasi CSP selesai dibuat, urutan penggunaan petak-petak blok oleh operasi-operasi semua perjalanan kereta api direpresentasikan dengan model graf disjungtif.
Algoritma Local Search yang akan digunakan pada Tugas Akhir ini untuk menyelesaikan masalah penjadwalan kereta api jalur tunggal adalah Hill Climbing. Dalam pencarian solusi dengan model penjadwalan Job-Shop, algoritma ini terdiri atas dua bagian utama [OLI00]. Bagian pertama adalah
III-1
III-2
pencarian solusi awal. Solusi awal ini mungkin memiliki total keterlambatan yang cukup besar. Pencarian solusi yang memiliki total keterlambatan lebih kecil dilakukan dengan menggunakan konsep lintasan kritis dan ketetanggaan pada solusi yang telah ditemukan. Dengan konsep ketetanggaan, dimungkinkan pembangkitan sebuah solusi baru dari solusi yang telah ditemukan sebelumnya dengan cepat. Solusi baru ini kemudian dihitung total keterlambatannya, apakah lebih kecil atau lebih besar daripada solusi awal yang ditemukan sebelumnya. Proses ini dilakukan secara iteratif sampai tidak ada tetangga yang memiliki total keterlambatan yang lebih kecil.
3.1 Deskripsi Pemodelan Masalah Penjadwalan Kereta Api Jalur Tunggal dengan Model Masalah Penjadwalan Job-Shop Bagian utama pemodelan masalah penjadwalan kereta api jalur tunggal dengan model masalah penjadwalan Job-Shop telah dijelaskan sebelumnya, yaitu peran perjalanan kereta api dan petak-petak blok sebagai pekerjaan dan sumber daya pada masalah penjadwalan Job-Shop. Untuk selanjutnya, istilah pekerjaan dan perjalanan kereta api akan dianggap sama dan digunakan secara bergantian. Demikian juga dengan sumber daya dan petak-petak blok. Penggunaan istilahistilah tesebut tergantung pada representasi yang sedang digunakan.
Sekarang misalkan diberikan n buah perjalanan kereta api J1, J2, ..., Jn yang harus dijadwalkan pada m buah rute. Setiap rute terdiri atas petak-petak blok dan stasiun yang berturutan. Jika sebuah perjalanan Ji melewati sebuah rute yang terdiri atas k buah petak blok, maka pekerjaan yang merepresentasikan perjalanan Ji tersebut terdiri atas k buah operasi oi1, oi2, ..., oik. Setiap operasi yang dilakukan dalam perjalanan Ji tersebut menggunakan tepat satu sumber daya berupa satu petak blok yang ada pada rute yang dilalui, yaitu operasi oij menggunakan petak blok ke-j pada rute yang dilalui oleh Ji. Dengan demikian, urutan operasi pada pekerjaan Ji ditentukan oleh urutan petak-petak blok pada rute yang dilalui oleh Ji.
III-3
Dalam masalah penjadwalan Job-Shop secara umum, waktu penggunaan sumber daya oleh suatu operasi diberikan sebagai input. Dalam masalah penjadwalan kereta api, waktu ini sama dengan lama waktu perjalanan kereta api melewati sebuah petak blok. Hal ini dapat ditentukan dari kecepatan kereta api dan jarak petak blok dengan rumus waktu = jarak / kecepatan. Karena kecepatan hanya digunakan untuk penentuan lama penggunaan petak blok oleh suatu kereta api, maka dalam Tugas Akhir ini, kecepatan kereta api diasumasikan selalu konstan. Percepatan ketika meninggalkan stasiun maupun perlambatan ketika kereta berhenti di stasiun tidak akan diperhitungkan.
Ada satu perbedaan antara masalah penjadwalan Job-Shop yang digunakan untuk memodelkan masalah penjadwalan kereta api jalur tunggal ini dengan masalah penjadwalan Job-Shop secara umum. Pada masalah penjadwalan Job-Shop secara umum, sebuah pekerjaan dapat ditunda di awal operasi manapun ketika operasi tersebut harus menunggu sebuah sumber daya yang sedang digunakan oleh pekerjaan lain. Pada masalah penjadwalan kereta api, hal ini tidak berlaku karena kereta api hanya boleh berhenti di stasiun dan tidak bisa berhenti di awal sembarang petak blok (di persinyalan). Dengan demikian, penundaan sebuah perjalanan kereta api hanya bisa dilakukan di awal operasi jika akhir dari operasi sebelumnya menggunakan petak blok yang berakhir di stasiun.
Secara ringkas, pemetaan (mapping) yang dilakukan dalam pemodelan ini disajikan pada Tabel III-1 berikut.
Tabel III-1 Pemetaan (Mapping) Masalah Penjadwalan Kereta Api Jalur Tunggal dengan Model Masalah Penjadwalan Job-Shop
Unsur-Unsur Masalah Penjadwalan
Model Masalah Penjadwalan Job-Shop
Kereta Api Jalur Tunggal
Perjalanan kereta api
Pekerjaan
PetakBlok
Sumber daya atau mesin
III-4
Unsur-Unsur Masalah Penjadwalan
Model Masalah Penjadwalan Job-Shop
Kereta Api Jalur Tunggal
Bagian perjalanan melewati satu petak Operasi blok Jarak petak blok dibagi kecepatan Lama waktu penggunaan sumber daya kereta api di petak blok
oleh operasi
Rute perjalanan sebagai urutan stasiun Urutan penggunaan sumber daya oleh dan petak-petak blok yang harus dilalui sutau pekerjaan perjalanan tersebut Konflik terjadi jika dua perjalanan Konflik
terjadi
jika
dua
operasi
menggunakan satu petak blok yang menggunakan sumber daya yang sama sama Penundaan
atau
pemberhentian Pekerjaan menunggu beberapa waktu
perjalanan kereta api di stasiun
untuk menggunakan suatu sumber daya
Waktu keberangkatan perjalanan di Waktu
pelepasan
pekerjaan
untuk
stasiun untuk menggunakan petak jalan menggunakan sumber daya atau sama di depannya
juga dengan waktu pelepasan operasi
Waktu tiba suatu perjalanan di stasiun Waktu harapan selesai suatu pekerjaan tujuan jika tidak terjadi penundaan Waktu tiba suatu perjalanan di stasiun Waktu
selesai
sebenarnya
suatu
tujuan setelah terjadi penundaan (untuk pekerjaan mencegah terjadinya konflik)
Penjadwalan masalah kereta api jalur tunggal selanjutnya didefinisikan sebagai pencarian waktu keberangkatan setiap kereta api di stasiun-stasiun yang harus dilaluinya. Dengan menggunakan model masalah penjadwalan Job-Shop, penjadwalan perjalanan kereta api ini kemudian didefinisikan sebagai pencarian waktu pelepasan operasi-operasi yang membentuk perjalanan-perjalanan yang ada.
III-5
3.2 CSP dari Model Masalah Setelah pemodelan masalah selesai dilakukan, hal pertama yang harus dilakukan untuk mencari solusi penjadwalan dengan pendekatan constraint programming adalah merepresentasikan model sebagai sebuah CSP [MON01]. Berikut akan diuraikan lebih jauh mengenai hal ini.
3.2.1 Variabel dan Domain CSP Masalah penjadwalan Job-Shop merupakan salah satu contoh CSP. Dengan demikian, model yang telah dibuat juga dapat direpresentasikan sebagai sebuah CSP.
Misalkan dij menyatakan waktu pelepasan setiap operasi oij pada perjalanan kereta api Ji (oij adalah bagian perjalanan Ji melewati petak blok ke-j pada rute yang dilalui). Himpunan variabel V pada CSP adalah {dij : 1 i n dan 1 j |Oi|}, dimana Oi menyatakan himpunan operasi yang harus dijalankan pada pekerjaan Ji. Hal ini karena waktu-waktu pelepasan itulah yang harus dicari dalam masalah penjadwalan kereta api.
Dalam Tugas Akhir ini, satuan waktu terkecil yang digunakan dalam penjadwalan adalah satu menit dan penjadwalan kereta api dilakukan dalam satu hari. Dengan demikian, domain dari tiap variabel pada CSP tersebut adalah bilangan asli antara 1 sampai dengan 1440 (hal ini karena satu hari terdiri atas 1440 menit).
Batasan-batasan dalam CSP dibuat berdasarkan aturan-aturan perjalanan kereta api seperti telah dijelaskan pada bab sebelumnya.
3.2.2 Batasan-Batasan yang Dimodelkan dalam CSP Tidak semua aturan atau batasan dalam perjalanan kereta api jalur tunggal akan dimodelkan sebagai batasan dalam CSP. Aturan-aturan yang akan dimodelkan adalah aturan persilangan, penyusulan, aturan headway, batas kecepatan maksimal petak blok dan batas waktu minimal dan maksimal penundaaan kereta api di
III-6
stasiun (batasan yang terakhir ini sama dengan aturan bahwa suatu kereta api harus berhenti di suatu stasiun tertentu).
Batasan urutan prioritas kereta api yang menggunakan petak blok yang sama tidak akan dimodelkan. Hal ini karena urutan kereta api yang menggunakan petak blok akan ditentukan ketika penjadwalan berlangsung. Urutan ini akan diatur untuk mendapatkan total keterlambatan yang sekecil mungkin. Jika batasan ini diimplementasikan, bisa terjadi sebuah kereta api tidak mengalami penundaan sama sekali di stasiun. Selain itu, mungkin ada kereta api lain yang akan selalu ditunda ketika akan menggunakan suatu petak blok yang sama dengan kereta api lain dengan prioritas lebih tinggi. Hal ini bisa menyebabkan total keterlambatan yang besar.
Batasan kapasitas maksimal stasiun juga tidak akan dimodelkan karena batasan tersebut merupakan batasan n-ary. Pencarian solusi CSP dengan batasan n-ary membutuhkan waktu lama [OLI01]. Selain itu, konflik karena batasan ini juga sangat jarang terjadi. Dan kalau terjadi, hal ini bisa diatasi secara manual dengan menambahkan satu batasan tambahan, yaitu salah satu kereta api harus berhenti di stasiun sebelumnya. Karena alasan ini, semua stasiun akan diasumsikan memiliki kapasitas tak-berhingga.
Jalur ganda yang akan diimplementasikan dalam Tugas Akhir ini adalah jalur kembar. Jalur kembar akan dimodelkan sebagai jalur tunggal yang tidak memiliki aturan persilangan. Jalur ganda secara umum tidak diimplementasikan karena pada prakteknya, jarang terjadi dua kereta api berjalan beriring-iringan.
3.2.3 Representasi Intensional Batasan-Batasan CSP Batasan-batasan yang akan diimplementasikan akan direpresentasikan secara intensional dengan menggunakan rumus-rumus matematis. Notasi-notasi yang digunakan sama dengan penjelasan sebelumnya, yaitu dij menyatakan operasi ke-j pada perjalanan Ji dan pij adalah lama waktu pemrosesan operasi tersebut menggunakan petak blok ke-j pada rute yang dilalui oleh perjalanan Ji.
III-7
Batasan yang pertama adalah urutan operasi pada satu perjalanan kereta api. Operasi ke-(j+1) pada perjalanan Ji hanya bisa dijalankan setelah operasi ke-j telah selesai dikerjakan. Dengan kata lain, waktu pelepasan operasi oi(j+1) harus lebih dari atau sama dengan waktu pelepasan operasi oij ditambah lama waktu pemrosesan operasi tersebut. Hal ini direpresentasikan secara intensional dengan rumus [OLI01] di(j+1) dij + pij. Dengan menggunakan graf disjungtif, batasan di atas akan menjadi sebuah sisi berarah konjungtif.
Aturan persilangan dan aturan penyusulan pada dasarnya adalah dua batasan yang sama, yaitu dua buah kereta api tidah boleh menggunakan petak blok yang sama dalam waktu yang sama. Misalkan perjalanan Ji dan perjalanan Ji’ menggunakan petak blok yang sama, yaitu petak blok ke-j pada rute yang dilalui oleh Ji dan petak blok ke-j’ pada rute yang dilalui oleh Ji’. Maka operasi oij dan oi’j’ akan menggunakan petak blok yang sama. Untuk itu urutan penggunakan petak blok harus ditentukan. Jika operasi oij ingin dikerjakan lebih dulu pada petak blok tersebut, maka batasan yang harus dipenuhi direpresentasikan secara intensional sebagai di’j’ dij + pij, dan jika sebaliknya maka representasinya adalah dij di’j’ + pi’j’. Karena urutan ini tidak diberikan ketika input (pengurutan statis), melainkan ditentukan ketika proses penjadwalan berlangsung (pengurutan dinamis), maka batasan yang harus dipenuhi menjadi [OLI01] di’j’ dij + pij atau dij di’j’ + pi’j’. Batas kecepatan maksimal kereta api tidak perlu dimodelkan sebagai batasan dalam CSP. Hal ini karena kecepatan maksimal hanya berpengaruh pada lama waktu penggunaan petak blok oleh kereta api yang bersangkutan. Jadi, batasan ini hanya digunakan untuk perhitungan pij saja.
III-8
Sekarang misalkan sebuah perjalanan Ji harus berhenti di suatu stasiun antara petak blok ke-j dan petak blok ke-(j+1) pada rute yang dilaluinya. Lama waktu minimal dan maksimal perhentian kereta tersebut di stasiun berturut-turut adalah mij dan Mij. Dengan demikian, waktu pelepasan operasi ke-(j+1) harus lebih dari atau sama dengan waktu tiba kereta api di stasiun ditambah lama waktu minimal pemberherhentian kereta api di stasiun. Representasi intensional dari batasan ini adalah di(j+1) dij + pij + mij karena dij + pij adalah waktu tiba kereta api di stasiun. Selain itu, waktu pelepasan operasi oi(j+1) harus kurang dari waktu tiba kereta di stasiun ditambah lama waktu maksimal pemberhentian kereta api di stasiun. Representasi intensional dari hal ini adalah di(j+1) dij + pij + Mij. Jadi, batas waktu minimal dan maksimal penundaan perjalanan kereta api di stasiun dapat direpresentasikan dengan batasan di(j+1) dij + pij + mij dan di(j+1) dij + pij + Mij.
3.3 Graf Disjungtif dari Model Masalah Model graf disjungtif yang digunakan untuk merepresentasikan model penjadwalan Job-Shop dari masalah penjadwalan kereta api jalur tunggal ini sama dengan graf disjungtif yang telah dijelaskan pada Bab II. Yang berbeda adalah struktur lintasan kritis dan ketetanggaan yang digunakan.
3.3.1 Struktur Lintasan Kritis Lintasan kritis dibentuk oleh beberapa operasi tertentu. Jika diberikan sebuah solusi dari masalah penjadwalan kereta api berupa jadwal yang memenuhi semua batasan yang ada, beberapa operasi yang urutan pengerjaannya tidak dapat diubah tanpa mengubah nilai fungsi objektif membentuk sebuah lintasan kritis. Definisi tersebut dapat digunakan pada masalah penjadwalan Job-Shop dengan menggunakan keterlambatan total sebagai fungsi objektifnya [OLI01].
III-9
Selama proses penjadwalan berlangung, operasi-operasi yang mengalami konflik karena menggunakan sumber daya yang sama harus ditentukan urutannya (urutan penggunaan sumber daya tersebut). Misalkan operasi oij dengan operasi oi’j’ mengalami konflik karena menggunakan sebuah sumber daya yang sama. Penentuan urutan tersebut dilakukan dengan menambahkan sebuah batasan urutan penggunaan sumber daya, misalnya oij ĺ oi’j’ yang berarti bahwa operasi oij menggunakan sumber daya sebelum operasi oi’j’. Dalam kasus seperti ini, kedua operasi tersebut mungkin memiliki jadwal yang berturutan (adjacent schedule) pada solusi yang ditemukan, yaitu operasi oi’j’ dilakukan tepat setelah operasi oij selesai. Secara matematis hal ini dituliskan sebagai di’j’ = dij + pij. Himpunan semua operasi-operasi yang memiliki jadwal berturutan akan menjadi bagian dari lintasan kritis [OLI01]. Sisi pada graf disjungtif yang menghubungkan dua operasi dengan jadwal yang berturutan disebut sebagai sisi kritis.
Algoritma untuk menjadwalkan operasi-operasi pada perjalanan kereta api didasarkan pada pengurutan operasi-operasi tersebut dalam penggunaan petakpetak blok yang ada sehingga tidak terjadi konflik. Kemudian pencarian jadwal layak yang lebih baik didasarkan pada pemilihan sisi-sisi kritis pada lintasan kritis yang akan diubah arahnya sehingga mengubah urutan operasi-operasi dalam penggunaan petak-petak blok.
3.3.2 Struktur Ketetanggaan Terdapat beberapa struktur ketetanggaan di literatur-literatur untuk masalah penjadwalan Job-Shop sebagaimana telah dijelaskan pada Bab II. Namun tidak banyak referensi yang menggunakan total keterlambatan sebagai fungsi objektif yang harus diminimalkan. Dalam Tugas Akhir ini, struktur ketetanggaan yang digunakan didasarkan pada struktur lintasan kritis dan sisi-sisi kritis yang dijelaskan pada bagian sebelumnya. Dengan menggunakan struktur ini, banyaknya tetangga dari sebuah solusi sama dengan banyaknya sisi-sisi kritis
III-10
pada solusi tersebut, yaitu banyaknya pasangan-pasangan operasi yang memiliki jadwal yang berturutan (adjacent operations).
Sisi-sisi kritis ini digunakan sebagai dasar perubahan sebuah solusi yang ditemukan menjadi solusi lain (tetangga dari solusi yang telah ditemukan) dengan tujuan mencari solusi yang lebih baik (memiliki total keterlambatan yang lebih kecil). Hal ini dilakukan dengan mengubah urutan dua buah operasi yang terhubung oleh sebuah sisi kritis [OLI01].
Dengan demikian, sebuah tetangga dari suatu solusi ditentukan oleh sepasang operasi yang terhubung oleh sebuah sisi kritis. Misalkan sebuah solusi memiliki sisi kritis (oij ĺ oi’j’), yaitu operasi oi’j’ menggunakan sumber daya yang sama dengan operasi oij dan operasi oi’j’ dilakukan tepat setelah operasi oij selesai menggunakan sumber daya (kedua operasi tersebut memiliki jadwal yang berturutan atau adjacent schedule). Salah satu tetangga dari solusi tersebut adalah solusi lain yang memiliki sisi (oi’j’ ĺ oij) dan sisi-sisi lainnya (baik sisi berarah konjungtif maupun disjungtif) sama dengan sisi-sisi pada solusi sebelumnya.
Jadi, pengubahan urutan dua buah operasi yang terhubung oleh sebuah sisi kritis ini dapat digunakan untuk membangkitkan sebuah tetangga dari solusi asal. Hal ini mengakibatkan hilangnya beberapa sisi kritis dari solusi asal dan bisa juga menambah sisi-sisi kritis baru pada tetangga yang dibangkitkan.
3.4 Pencarian Solusi Model Masalah dengan Hill Climbing Algoritma penjadwalan kereta api jalur tunggal yang digunakan pada Tugas Akhir ini terdiri atas dua bagian utama. Bagian pertama adalah pencarian sebuah solusi awal dan bagian kedua adalah pencarian solusi lain secara progresif untuk mengurangi total keterlambatan dari solusi yang telah ditemukan sebelumnya. Dalam Tugas Akhir ini, hal tersebut dilakukan dengan menggunakan algoritma Hill Climbing. Pseudo-code dari algoritma ini adalah sebagai berikut.
III-11
function Find-Good-Solution () solusi ĸ Find-First-Solution () repeat himpunan tetangga ĸ Nb (solusi) kriteria penghentian ĸ True for each tetangga in himpunan tetangga do if TT (tetangga) TT (solusi) then solusi ĸ tetangga kriteria penghentian ĸ False endif endfor until kriteria penghentian = True return solusi
Terdapat tiga fungsi utama pada skema di atas. Fungsi yang pertama adalah FindFirst-Solution (). Fungsi ini digunakan untuk mencari satu solusi awal. Pencarian ini dilakukan secara cepat, walaupun total keterlambatan yang diperoleh masih besar. Fungsi yang kedua adalah fungsi ketetanggaan Nb yang mengembalikan himpunan tetangga dari solusi yang sudah ditemukan. Fungsi yang terakhir adalah fungsi objektif TT untuk menghitung total keterlambatan dari sebuah solusi.
3.4.1 Pencarian Solusi Pertama Implementasi fungsi Find-First-Solution () dilakukan dengan algoritma Local Search. Algoritma ini dimulai dengan pemberian nilai berupa waktu pelepasan pada operasi-operasi sedemikian hingga semua batasan urutan operasi pada satu perjalanan terpenuhi. Hal ini dapat dilakukan dengan cepat menggunakan algoritma DFS pada graf disjungtif. Pemberian nilai pertama kali ini mungkin menyebabkan terjadinya konflik, yaitu adanya dua operasi berbeda yang menggunakan petak blok yang sama. Heuristic yang digunakan dalam algoritma ini untuk menyelesaikan semua konflik yang terjadi adalah strategi kronologis (chronological strategy) dan penentuan urutan operasi yang akan menggunakan petak blok pertama kali dilakukan dengan aturan Shortest Processing Time (SPT) [OLI01].
III-12
Secara ringkas, langkah-langkah yang dilakukan dalam algoritma pencarian solusi pertama ini adalah sebagai berikut: 1. Jadwalkan operasi-operasi tanpa melanggar urutan pada satu perjalanan. 2. Buat senarai yang menyimpan konflik karena penggunaan petak blok yang sama. 3. Pilih konflik yang terjadi paling awal dan urutkan penggunaan petak blok berdasarkan aturan SPT. 4. Ubah waktu pelepasan operasi yang ditunda karena konflik dan juga waktu pelepasan operasi-operasi setelahnya pada satu perjalanan yang sama. 5. Ulangi langkah 2, 3 dan 4 di atas sampai senarai pada langkah dua kosong, yaitu tidak ada lagi konflik yang terjadi.
3.4.1.1 Strategi Kronologis dalam Penyelesaian Konflik Dalam masalah penjadwalan kereta api, penyelesaian sebuah konflik dengan cara menunda salah satu perjalanan di stasiun selalu dapat menimbulkan konflik baru. Konflik yang baru ini melibatkan operasi-operasi pada perjalanan yang ditunda. Sebagai contoh,
misalkan penjadwalan dilakukan dengan menggunakan n
perjalanan kereta api. Penjadwalan pertama ini menghasilkan sebuah jadwal yang hanya mengandung satu konflik saja. Pada kasus yang ekstrim (dengan kemungkinan terburuk), penyelesaian satu konflik tersebut dapat menyebabkan terjadinya n – 2 konflik baru yang terjadi antara perjalanan yang ditunda dengan n – 2 perjalanan lain yang pada mulanya tidak terjadi konflik. Contoh kasus terburuk dengan n = 4 disajikan dengan diagram ruang-waktu pada Gambar III-1. Pada Gambar III-1 (a), sebuah jadwal hanya mengandung satu konflik. Pada Gambar III-1 (b), sebuah jadwal baru yang diperoleh dengan menunda salah satu perjalanan mengandung 4 – 2 = 2 konflik baru.
Oleh karena itu, diperlukan sebuah strategi penyelesaian konflik secara sistematis sehingga semua konflik selalu dapat diselesaikan. Salah satu strategi yang dapat digunakan adalah strategi kronologis (chronological strategy) [OLI01]. Strategi ini menyelesaikan semua konflik yang ada secara urut berdasarkan urutan waktu terjadinya konflik. Semua konflik baru yang terjadi karena penyelesaian sebuah
III-13
konflik juga selalu dapat diselesaikan dengan strategi ini. Hal ini karena dalam masalah penjadwalan kereta api, konflik baru selalu terjadi setelah konflik yang diselesaikan sebelumnya. s4
s4
Rute
Rute r3
r3
s3
s3 r2
r2
s2
s2 r1
s1
100
r1 110
120
130
s1
100
110
120
Unit-unit Waktu (a)
130
Unit-unit Waktu (b)
Gambar III-1 Contoh Kasus Terburuk Penyelesaian Konflik
3.4.1.2 Aturan Shortest Processing Time (SPT) Untuk menyelesaikan sebuah konflik yang terjadi karena penggunaan petak blok yang sama, waktu pelepasan yang baru harus diberikan pada operasi yang ditunda perjalanannya. Dengan kata lain, konflik diselesaikan dengan mengurutkan operasi-operasi yang menggunakan petak blok yang sama. Untuk mendapatkan solusi awal yang baik dalam Local Search, heuristic yang digunakan untuk menentukan urutan ini adalah aturan Shortest Processing Time (SPT). Aturan ini mengurutkan dua buah operasi untuk mendapatkan total keterlambatan terkecil antara dua buah operasi tersebut.
Sebagai contoh penggunaan aturan SPT tersebut, misalkan kereta A berangkat dari stasiun s1 ke stasiun s2 pada jam 115 dan kereta B berangkat dari stasiun s2 ke stasiun s1 pada jam 137. Antara kedua stasiun tersebut hanya terdapat sebuah petak blok r1. Misalkan lama waktu penggunaan petak blok tersebut oleh kereta A adalah 35 dan oleh kereta B adalah 27. Akibatnya, akan terjadi konflik
III-14
penggunaan petak blok r1 oleh kedua perjalanan tersebut. Hal ini terlihat dari diagram ruang-waktu pada Gambar III-2. s2
kereta A
kereta B
s1
200
100
Gambar III-2 Jadwal Dua Kereta yang Bertabrakan
Untuk menyelesaikan konflik yang terjadi di atas, terdapat dua pilihan cara. Cara yang pertama adalah kereta A ditunda perjalanannya di stasiun s1 dan yang kedua adalah stasiun B ditunda perjalanannya di stasiun s2. Dengan menggunakan aturan SPT, kereta yang harus ditunda perjalanannya adalah kereta B. Hal ini karena penundaan tersebut menimbulkan keterlambatan yang lebih kecil daripada keterlambatan yang terjadi jika kereta A ditunda. Hal ini terlihat dari diagram ruang-waktu pada Gambar III-3. s2
s2
kereta A s1
kereta B
kereta B
kereta A 200
100
s1
100
200
Gambar III-3 Jadwal Dua Kereta dengan Penundaan di Stasiun
3.4.2 Pencarian Solusi yang Lebih Baik Pencarian solusi yang lebih baik ini dilakukan dengan menggunakan struktur ketetanggaan yang telah dijelaskan sebelumnya. Fungsi ketetanggaan Nb dan fungsi objektif TT memiliki peran sangat penting pada bagian ini. Solusi-solusi yang lebih baik daripada solusi sebelumnya dipilih dari tetangga-tetangga yang dihasilkan oleh fungsi Nb. Fungsi TT digunakan untuk mengukur apakah sebuah tetangga memiliki total keterlambatan lebih kecil daripada solusi yang telah ditemukan sebelumnya.
III-15
Fungsi ketetanggaan ini didasarkan pada lintasan kritis dan struktur ketetanggaan yang telah dijelaskan sebelumnya juga. Satu hal yang harus diperhatikan dalam implementasi fungsi ini adalah tetangga yang baru mungkin memiliki lintasan kritis yang berbeda dari solusi asal. Proses pencarian tetangga baru dilakukan dengan cara mengubah arah sebuah sisi pada lintasan kritis. Hal ini juga harus diperhatikan karena dapat menyebabkan terjadinya konflik baru. Konflik baru yang mungkin terjadi di bagian ini juga diselesaikan dengan cara yang sama pada bagian sebelumnya, yaitu menggunakan aturan SPT.
Setelah mengetahui tetangga-tetangga dari sebuah solusi, pencarian solusi yang lebih baik dilakukan dengan membandingkan total keterlambatan antara solusi asal dengan tetangga-tetangganya. Jika ada tetangga yang memiliki total keterlambatan lebih kecil, tetangga ini akan digunakan sebagai solusi berikutnya. Iterasi berhenti ketika tidak ada lagi tetangga yang memiliki total keterlambatan yang lebih kecil. Solusi yang terakhir ditemukan inilah yang akan menjadi solusi algoritma Hill Climbing.
3.5 Contoh Kasus Penjadwalan dengan Algoritma Hill Climbing Untuk mengilustrasikan algoritma yang digunakan dalam Tugas Akhir ini, digunakan sebuah contoh perjalanan kereta api jalur tunggal sederhana dengan menggunakan empat stasiun, tiga perjalanan dan antara satu stasiun dengan stasiun berikutnya hanya terdapat satu petak blok saja. Rute ini dapat dilihat pada Gambar III-4 berikut.
Gambar III-4 Rute Perjalanan Kereta Api Sederhana
III-16
Selanjutnya, data perjalanan ketiga perjalanan tersebut disajikan pada Tabel III-2.
Tabel III-2 Data Perjalanan Kereta Api
Perjalanan kereta api 1 2 3
Urutan petak blok
r1, r2, r3 r3, r2, r1 r1 , r 2
Waktu berangkat 100 100 160
Lama waktu penggunaan masing-masing petak blok 20, 15, 15 20, 17, 20 15, 12
Hal pertama yang dilakukan dalam algoritma Hill Climbing adalah mencari sebuah jadwal layak yang tidak melanggar aturan-aturan perjalanan kereta api. Untuk itu, langkah pertama dilakukan adalah menjadwalkan operasi-operasi setiap perjalanan kereta api tanpa melanggar urutan operasi-operasi pada satu perjalanan. Dari data perjalanan pada Tabel III-2, operasi pertama pada perjalanan 1 dijalankan sama dengan waktu perjalanan tersebut, yaitu 100. Operasi tersebut menggunakan petak blok r1 selama 20 menit sehingga perjalanan 1 sampai di stasiun s2 pada waktu 120. Dengan demikian, operasi kedua pada perjalanan 1 dijalankan pada waktu 120. Operasi kedua ini menggunakan petak blok r2 selama 15 menit, sehingga perjalanan 1 sampai di stasiun s3 pada waktu 135. Cara penjadwalan operasi-operasi seperti ini dilakukan pada setiap operasi pada setiap perjalanan yang ada. Hasilnya adalah jadwal kereta api yang mungkin mengandung konflik. Dalam contoh kasus ini, jadwal yang dihasilkan disajikan dalam diagram ruang-waktu pada Gambar III-5.
Pada Gambar III-5, terlihat bahwa perjalanan 1 dan 2 mengalami konflik penggunaan petak blok r2 dan tidak ada konflik lain yang terjadi. Secara otomatis, konflik tersebut adalah konflik paling awal yang terjadi dalam langkah pertama algoritma sehingga konflik itulah yang akan diselesaikan (jika pada langkah pertama ini terdapat lebih dari satu konflik yang terjadi, maka konflik yang diselesaikan pertama kali adalah konflik yang paling awal).
III-17
s4 Rute kereta 2
r3 s3 r2 s2
r1
kereta 3
kereta 1
s1
100
110
120
130
140
150
160
180
170
Unit-unit Waktu
Gambar III-5 Diagram Ruang-Waktu dari Data pada Tabel III-1
Penyelesaian konflik ini dilakukan dengan mengurutkan penggunaan petak blok r2 oleh perjalanan 1 dan 2. Jika perjalanan 1 dilakukan lebih dulu, maka perjalanan 2 harus ditunda di stasiun s3 sampai perjalanan 1 selesai menggunakan petak blok r2, yaitu pada waktu 135. Dengan demikian, perjalanan 2 harus menunda perjalanan selama 135 – 120 = 15 menit. Sebaliknya, jika perjalanan 2 dikerjakan lebih dulu, maka perjalanan 1 harus ditunda di stasiun 2. Lama penundaan ini adalah 17 menit. Berdasarkan aturan SPT, perjalanan 1 lah yang akan dikerjakan lebih dulu. Hasil dari langkah ini adalah sebuah jadwal baru yang disajikan pada Gambar III-6. s4 Rute kereta 2
r3 s3 r2 s2
kereta 3 r1 s1
100
kereta 1
110
120
130
140
150
160
170
180
Unit-unit Waktu
Gambar III-6 Penyelesaian Konflik Pertama pada Penjadwalan
III-18
Penundaan perjalanan 2 di stasiun s2 selama 15 menit ini berarti waktu pelepasan operasi kedua dari perjalanan ini berubah dari 120 menajdi 135. Secara otomatis hal ini juga menyebabkan perubahan waktu pelepasan operasi ketiga dari perjalanan 2, yaitu dari 137 menjadi 152. Akibat lain dari penundaan ini adalah terjadinya konflik baru antara perjalanan 2 dan perjalanan 3 di petak blok r1 seperti terlihat pada diagram ruang-waktu pada Gambar III-6. Karena konflik tersebut adalah konflik paling awal yang terjadi pada jadwal yang baru ini, maka konflik tersebut diselesaikan aturan SPT dengan menunda perjalanan 3 di stasiun s1. Perjalanan 2 sampai di stasiun s1 pada waktu 172, sehingga perjalanan 3 harus menunda perjalanannya selama 172 – 160 = 12 menit. Hasilnya disajikan pada Gambar III-7. s4 Rute kereta 2
r3 s3 r2 s2
r1 s1
100
kereta 1
110
kereta 3 120
130
140
150
160
170
180
Unit-unit Waktu
Gambar III-7 Penyelesaian Konflik Kedua pada Penjadwalan
Jadwal terakhir ini sudah tidak mengandung konflik sama sekali sehingga merupakan sebuah solusi. Total keterlambatan yang terjadi adalah 15 + 12 = 27 menit. Langkah selanjutnya adalah mencari tetangga dari solusi yang ditemukan dengan total keterlambatan yang lebih kecil. Untuk itu dilakukan identifikasi sisisisi kritis pada graf disjungtif yang merepresentasikan solusi yang telah ditemukan. Representasi graf disjungtif tersebut disajikan pada Gambar III-8 berikut.
III-19
Gambar III-8 Graf Disjungtif dari Solusi yang Ditemukan
Pada Tugas Akhir ini, definisi sisi kritis yang digunakan adalah sisi disjungtif yang menghubungkan dua operasi yang dijadwalkan secara berurutan (adjacent schedule). Dengan demikian, pada solusi di atas, sisi kritisnya adalah sisi disjungtif yang menghubungkan operasi kedua pada perjalanan 1 dengan operasi kedua dari perjalanan 2, yaitu (o12 ĺ o22) dan juga operasi ketiga dari perjalanan 2 dan operasi petama dari perjalanan 3, yaitu (o23 ĺ o31). Dengan demikian, terdapat dua tetangga dari graf disjungtif yang dapat dilihat pada Gambar III-9.
Gambar III-9 Graf Disjungtif Tetangga dari Graf pada Gambar III-8
III-20
Tetangga pada Gambar III-9 (a) diperoleh dengan mengubah arah sisi kritis (o12 ĺ o22) menjadi (o22 ĺ o12) dan tetangga pada Gambar III-9 (b) diperoleh dengan mengubah arah (o23 ĺ o31) menjadi (o31 ĺ o23). Representasi diagram ruangwaktu dari jadwal yang baru ini berturut-turut disajikan dalam Gambar III-10 (a) dan (b).
s4 Rute r3
kereta 2
s3 r2 s2
r1 s1
100
kereta 1
110
120
kereta 3 130
140
150
160
170
180
Unit-unit Waktu
(a) s4 Rute r3
kereta 2
s3 r2 s2
r1 s1
100
kereta 1
110
kereta 3 120
130
140
150
160
170
180
Unit-unit Waktu
(b) Gambar III-10 Jadwal yang Diperoleh dari Graf Disjungtif Tetangga
III-21
Jadwal pada Gambar III-10 (a) memiliki total keterlambatan 17 menit sedangkan jadwal pada gambar III-10 (b) memiliki total keterlambatan 38 menit. Jadi, tetangga yang pertama memiliki total keterlambatan lebih kecil daripada total keterlambatan solusi yang telah ditemukan, yaitu 27 menit. Dengan demikian, tetangga tersebut dijadikan solusi berikutnya pada iterasi yang dilakukan. Algoritma ini dilanjutkan dengan menganalisa tetangga-tetangga dari solusi yang baru tersebut. Iterasi berakhir jika tetangga-tetangga dari solusi yang telah ditemukan tidak memiliki total keterlambatan yang lebih kecil. Pada contoh kasus ini, solusi yang terakhir ditemukan di atas merupakan solusi terakhir algoritma ini.
