BAB II DASAR TEORI Pada bab ini akan diuraikan mengenai deskripsi perjalanan kereta api yang terkait dengan masalah penjadwalan. Hal ini meliputi pokok-pokok perjalanan kereta api dan
aturan-aturan
atau
batasan-batasan
yang
harus
dipenuhi
dalam
penjadwalannya. Selain itu juga akan dijelaskan mengenai masalah penjadwalan Job-Shop dan penyelesaiannya dengan pendekatan Constraint Programming secara umum (tanpa harus terikat pada masalah penjadwalan kereta api).
2.1 Deskripsi Perjalanan Kereta Api Jalur Tunggal 2.1.1 Pokok-Pokok Perjalanan Kereta Api Jalur Tunggal Jaringan kereta api jalur tunggal yang dibahas dalam Tugas Akhir ini terdiri atas sekumpulan stasiun dan petak-petak blok atau segmen-segmen jalur. Petak blok atau segmen jalur adalah bagian jalan kereta api yang dibatasi oleh dua buah sinyal berturutan. Dua buah sinyal tersebut digunakan sebagai tanda apakah sebuah kereta api boleh masuk atau keluar dari petak blok yang bersangkutan. Hal ini diperlukan untuk mencegah terjadinya tabrakan dua buah kereta api dengan membuat aturan bahwa pada setiap waktu, hanya terdapat satu kereta api yang menempati petak blok tersebut. Dalam hal ini, konflik perjalanan kereta api terjadi jika terdapat dua atau lebih kereta api yang menggunakan satu petak blok pada waktu yang sama. Ini adalah aturan dasar dalam penjadwalan perjalanan kereta api jalur tunggal [SUP01].
Selanjutnya, rute perjalanan kereta api dipandang sebagai himpunan terurut stasiun-stasiun dan petak-petak blok. Antara satu stasiun dengan stasiun berikutnya bisa terdiri atas satu atau lebih petak-petak blok. Dengan demikian, perjalanan kereta api dapat dipandang sebagai sekumpulan operasi melewati petak-petak blok tersebut atau menunda perjalanan dengan menunggu penggunaan petak-petak blok di stasiun (untuk menghindari penggunaan satu petak blok oleh dua kereta api) [OLI01]. Dalam hal ini, kapasitas maksimum stasiun (banyaknya kereta api yang dapat ditampung di stasiun dalam satu waktu) juga harus
II-1
II-2
diperhatikan. Sebagaimana konflik perjalanan kereta api terjadi di petak blok, konflik di stasiun juga dapat terjadi jika kapasitas maksimum stasiun ini dilanggar.
Sebuah contoh sebuah rute perjalanan kereta api jalur tunggal dapat dilihat pada Gambar II-1 berikut.
Gambar II-1 Rute Perjalanan Kereta Api dengan Enam Stasiun
Rute pada Gambar II-1 terdiri atas enam stasiun dan delapan petak blok. Antara stasiun s1 dan s2 terdapat dua petak blok, antara stasiun s3 dan s4 terdapat tiga petak blok dan yang lainnya hanya terdiri atas satu petak blok. Kumpulan petakpetak blok antara satu stasiun dengan stasiun berikutnya disebut sebagai petak jalan. Petak-petak blok dalam satu petak jalan dipisahkan oleh sinyal.
Sebuah jadwal keberangkatan kereta api pada umumnya diberikan oleh perusahaan-perusahaan kereta api yang mengelola kereta api yang bersangkutan. Selain itu, untuk setiap perjalanan kereta api, stasiun asal, stasiun tujuan dan stasiun-stasiun lain yang harus dilalui juga dispesifikasikan sebagai input. Proses penjadwalan kereta api kemudian dapat didefinisikan sebagai proses pencarian waktu-waktu keberangkatan kereta api di tiap stasiun yang dilalui agar tidak terjadi konflik, baik konflik di petak blok maupun di stasiun.
Dalam Tugas Akhir ini, satuan waktu terkecil yang digunakan dalam penjadwalan adalah menit. Penjadwalan dilakukan untuk perjalanan-perjalanan kereta api
II-3
dalam satu hari saja. Dengan demikian, waktu yang digunakan dalam penjadwalan adalah bilangan asli antara 1 sampai dengan 1440 (sama dengan 24×60). Bilangan-bilangan tersebut menyatakan menit-menit yang ada dalam satu hari.
Dalam masalah penjadwalan kereta api, jadwal pada umumnya dinyatakan dalam diagram ruang-waktu (time-space diagram) [OLI01]. Sebagai contoh, misalkan sebuah kereta api melakukan perjalanan menggunakan rute pada Gambar II-1 dari stasiun s1 menuju stasiun s4. Perjalanan dilakukan pada waktu 180, berhenti di stasiun s2 selama 20 menit dan di stasiun s3 selama 20 menit juga. Kereta api sampai di stasiun s2 pada waktu 310, di stasiun s3 pada waktu 435 dan terakhir di stasiun s4 pada waktu 657. Jadwal tersebut direpresentasikan dalam diagram ruang-waktu pada Gambar II-2 berikut s4
Rute
r6 r5 r4
s3
r3 s2 r2 r1 s1
100
200
300
400
500
600
700
800
Unit-unit Waktu
Gambar II-2 Jadwal Kereta Api Menggunakan Diagram Ruang-Waktu
2.1.2 Aturan-Aturan Umum Perjalanan Kereta Api Jalur Tunggal Sebagaimana telah dijelaskan sebelumnya, konflik pada perjalanan kereta api dapat terjadi di petak blok dan stasiun. Konflik di stasiun terjadi karena kereta api yang berhenti di stasiun tersebut melanggar batas maksimum kapasitas stasiun dan konflik di petak blok terjadi karena terdapat dua atau lebih kereta api yang menggunakan petak blok tersebut pada waktu yang sama. Konflik di petak blok dapat terjadi pada dua kereta api yang berjalan pada arah yang berlawanan
II-4
maupun arah yang sama. Konflik pada dua kereta api yang berjalan pada arah yang sama terjadi karena kereta yang di belakang lebih cepat daripada kereta api yang di depan. Untuk mencegah terjadinya konflik, salah satu kereta harus ditunda perjalanannya di stasiun sampai salah satu kereta selesai menggunakan petak blok yang digunakan bersama-sama.
Jika arahnya berlawanan, aturan
penundaan perjalanan kereta api ini biasa disebut sebagai aturan persilangan (crossing rule) dan jika arahnya sama disebut aturan penyusulan (passing rule) [SUP01].
Untuk dua kereta api yang berjalan pada jalur dan arah yang sama, selain aturan penyusulan (tidak boleh menggunakan petak blok yang sama) juga terdapat aturan headway, yaitu selisih waktu minimal antara kedua kereta api tersebut [OLI01][SUP01]. Aturan ini juga bertujuan untuk mencegah terjadinya tabrakan karena aturan petak blok saja tidak cukup untuk menjamin keselamtan dua buah kereta api yang berjalan pada jalur dan arah yang sama. Misalnya ketika kereta api yang di depan lebih lambat dan berada di ujung masuk suatu petak blok, sedangkan kereta api di belakang lebih cepat dan berada di ujung keluar petak blok sebelumnya.
Selain tiga aturan di atas yang menjamin keselamatan perjalanan kereta api, terdapat aturan-aturan lain yang harus diperhatikan dalam penjadwalan kereta api, antara lain: 1. Batas kecepatan maksimal kereta api di petak blok (speed constraint) [SUP01]. Selain kecepatan maksimal yang dapat dicapai oleh kereta api sendiri, terdapat kecepatan maksimal yang diperbolehkan dalam suatu petak blok. Kecepatan maksimal ini tidak tergantung oleh jenis kereta api dan hanya tergantung oleh petak blok yang bersangkutan. Pada prakteknya, kecepatan yang digunakan adalah yang terkecil diantara kecepatan maksimal kereta api dan kecepatan maksimal petak blok. 2. Batas waktu minimal dan maksimal penundaan perjalanan kereta api di stasiun [MLA07].
II-5
Batas waktu minimal digunakan agar kereta api berhenti di suatu stasiun selama waktu tertentu. Aturan ini digunakan antara lain untuk menaikkan atau menurunkan penumpang dan barang di stasiun. Sedang batas waktu maksimal digunakan agar kereta api tidak berhenti di satu stasiun terlalu lama. 3. Urutan prioritas dua kereta api yang menggunakan petak blok yang sama [SUP01]. Beberapa negara menggunakan kelas-kelas kereta api untuk menentukan urutan prioritas ini. Misalnya di Indonesia, terdapat tiga kelas kereta api, yaitu kelas eksekutif, bisnis dan ekonomi. Ketika kereta api kelas eksekutif dan ekonomi akan bertemu di satu petak blok, pada umumnya kereta api kelas eksekutif lebih diprioritaskan menggunakan petak blok tersebut. Dengan demikian, kereta api kelas ekonomi harus menunggu di stasiun selama penggunaan petak blok tersebut oleh kereta api kelas eksekutif. Oleh karena itulah kereta api kelas ekonomi di Indonesia sering berhenti di stasiun-stasiun walaupun tidak menaikkan atau menurunkan penumpang sama sekali. 4. Batas waktu minimal antara dua kereta api yang berlawanan arah di stasiun [SUP01]. Aturan ini digunakan pada dua kereta api yang berlawanan arah jika salah satu kereta api akan masuk ke sebuah stasiun melewati suatu petak blok dan yang satu lagi keluar dari stasiun yang sama dan masuk ke petak blok yang sama juga. Batas waktu tersebut digunakan untuk persiapan masuk dan keluar kedua kereta api tersebut dari stasiun yang bersangkutan. 5. Dua buah kereta bertemu di sebuah stasiun selama suatu selang waktu tertentu [OLI01][MLA07]. Batasan ini digunakan jika dua buah kereta api harus bertemu di sebuah stasiun selama suatu selang waktu tertentu. Misalnya untuk pemindahan barang dari satu kereta api ke kereta api lainnya atau pemindahan gerbong kereta.
2.1.3 Jalur Ganda dan Jalur Kembar Masalah penjadwalan kereta api jalur tunggal juga dapat diaplikasikan pada rute perjalanan yang mengandung beberapa jalur ganda. Jalur-jalur ganda dapat
II-6
dipandang sebagai sebuah stasiun dengan kapasitas maksimum dua [OLI01]. Kemudian perjalanan pada jalur ganda tersebut dapat dianggap sebagai penundaan perjalanan kereta api di stasiun. Dalam kenyataannya, kedua hal tersebut memang sebenarnya sangat berbeda, misalnya di stasiun, kereta api dapat menambah jumlah penumpang atau menurunkan barang. Tapi dalam konsep penjadwalan kereta api, hal tersebut dapat dianggap sama, yaitu sebagai tempat untuk mengatasi konflik yang mungkin terjadi. Hal ini karena kereta api bisa berhenti di stasiun maupun jalur ganda untuk menunggu penggunaan petak blok di depannya.
Satu tipe khusus dari jalur ganda adalah jalur kembar. Jalur kembar adalah jalur ganda yang digunakan untuk dua arah yang berlawanan [SUP01]. Ini lebih khusus karena jalur ganda yang lebih umum dapat digunakan untuk dua arah yang sama. Jadi, jalur ganda memungkinkan terjadinya penyusulan kereta api sedangkan jalur kembar tidak. Dalam masalah penjadwalan kereta api jalur tunggal, jalur kembar dapat dipandang sebagai jalur tunggal dimana dua kereta api yang berlawanan arah boleh menggunakan petak blok yang sama pada jalur kembar tersebut. Dengan kata lain, jalur kembar dapat dianggap sebagai jalur tunggal tanpa aturan persilangan. Namun demikian, aturan penyusulan dan aturan headway tetap berlaku pada jalur kembar. Aturan-aturan lainnya juga tetap berlaku pada jalur ganda dan jalur kembar.
2.1.4 Contoh Kasus Perjalanan Kereta Api Jalur Tunggal Sebagai ilustrasi dari deskripsi perjalanan kereta api jalur tunggal dan aturanaturannya, berikut akan diberikan contoh kasus tiga perjalanan kereta api yang menggunakan satu rute yang sama, yaitu rute pada Gambar II-1. Tiga kereta api yang melakukan perjalanan tersebut adalah kereta A, B, dan C. Kereta A berangkat dari stasiun s1 menuju stasiun s8, kereta B berangkat dari stasiun s5 menuju s1 dan kereta C berangkat dari stasiun s2 menuju s8. Kereta A berangkat pada pukul 275, kereta B pada pukul 217, dan kereta C pada pukul 543. Misalkan juga lama waktu penggunaan petak blok oleh tiap kereta sudah diperhitungkan dari kecepatan kereta api dan jarak petak blok. Semua data perjalanan tersebut disajikan pada Tabel II-1
II-7
Tabel II-1 Data Perjalanan Kereta Api
Perjalanan kereta api A B C
Urutan petak blok r1, r2, r3, r4, r5, r6, r7, r8 r7, r6, r5, r4, r3, r2, r1 r3, r4, r5, r6, r7, r8
Waktu berangkat 275 217 543
Lama waktu penggunaan masing-masing petak blok 85,40,75,52,90,60,88,87 40,56,40,30,50,75,87 51,47,43,30,25,30
Dari data yang diberikan, diagram ruang-waktu dari jadwal perjalanan kereta api di atas dapat dilihat pada Gambar II-3. Rute
s6 r8 s5 r7
kereta B
s4 r6 r5 s3
r4 r3
kereta C
s2 r2
kereta A
r1 s1
100
200
300
400
500
600
700
800
900
Unit-unit Waktu
Gambar II-3 Jadwal Perjalanan Kereta Api yang Mengandung Konflik
Pada jadwal di atas, terlihat bahwa konflik terjadi antara kereta A dengan kereta B di petak blok r3 dan antara kereta A dengan kereta C pada petak blok r7. Dalam hal ini, Kereta A dan kereta B melanggar aturan persilangan sementara kereta A dan kereta C melanggar aturan penyusulan. Untuk mengatasi konflik ini, kereta A ditunda perjalanannya di stasiun s2. Gambar II-4 menunjukkan penundaan ini sehingga tidak ada lagi konflik yang terjadi pada jadwal yang baru. Pada jadwal yang baru, terlihat juga bahwa kereta A dan kereta B bertemu di stasiun s2 dan kereta A dan kereta C bertemu di stasiun s4.
II-8
s6
Rute
r8
s5 r7
kereta B
s4 r6 r5 s3
r4 r3
kereta C
s2 r2
kereta A
r1 s1
100
200
300
400
500
600
700
800
900
Unit-unit Waktu
Gambar II-4 Jadwal Kereta Api yang Tidak Mengandung Konflik
2.2 Masalah Penjadwalan Job-Shop 2.2.1 Definisi Formal Masalah penjadwalan Job-Shop terdiri atas sebuah himpunan pekerjaan J = {J1, J2,..., Jn} yang harus dijadwalkan pada sebuah himpunan sumber daya atau mesin R. Setiap pekerjaan Ji terdiri atas sekumpulan operasi terurut yang harus dilakukan, yaitu Oi = {oi1, oi2, ..., oik} dengan k = |Oi| adalah banyaknya operasi pada pekerjaan Ji. Kemudian setiap operasi oij menggunakan sebuah sumber daya yang tunggal rij R selama suatu selang waktu tertentu. Lama waktu penggunaan sumber daya oleh operasi oij juga diberikan sebagai input ketika pendefinisian masalah penjadwalan Job-Shop tersebut, misalkan pij. Dalam satu waktu, sebuah sumber daya hanya boleh digunakan oleh satu operasi saja. Dengan demikian, konflik terjadi ketika dua operasi yang berbeda menggunakan sumber daya yang sama dalam waktu yang sama juga [OLI01].
II-9
Setiap pekerjaan Ji memiliki waktu pelepasan (release date) di, yaitu waktu dimulainya pekerjaan tersebut. Selain itu, Ji juga memiliki waktu harapan selesai (expected completion date) ci. Pada Tugas Akhir ini, waktu harapan selesai didefinisikan sebagai jumlah waktu penggunaan sumber daya oleh setiap operasi pada pekerjaan tersebut. [MLA07] Secara matematis, hal ini ditulis sebagai k
ci
di ¦ pij , dengan k = |Oi|. j 1
Selain waktu pelepasan dan waktu harapan selesai, pekerjaan Ji yang sudah dijadwalkan akan memiliki waktu selesai yang sebenarnya (actual completion date), yaitu Ci. Waktu tersebut adalah waktu selesainya operasi terakhir pada pekerjaan Ji. Jika dij menyatakan waktu pelepasan operasi oij pada pekerjaan Ji, kita memiliki beberapa hubungan matematis, misalnya di = di1, dan Ci = dik + pik, dengan k = |Oi|. Masalah penjadwalan Job-Shop kemudian didefinisikan sebagai pencarian waktu pelepasan setiap operasi oij pada pekerjaan-pekerjaan yang ada sehingga tidak terjadi konflik, yaitu penggunaan satu sumber daya oleh dua operasi yang sama pada waktu yang sama juga.
2.2.2 Kriteria Optimasi pada Masalah Penjadwalan Job-Shop Beberapa kriteria optimasi dapat digunakan untuk mendapatkan jadwal dengan kualitas yang sebaik mungkin. Kriteria-kriteria tersebut antara lain [MLA07]: 1. Minimalisasi makespan, yaitu waktu selesai sebenarnya pekerjaan terakhir. Secara matematis, hal ini ditulis sebagai Cmax
max{Ci :1 d i d n} .
Kriteria ini cocok digunakan jika pekerjaan-pekerjaan yang akan dijadwalkan memiliki waktu pelepasan yang relatif sama. 2. Minimalisasi banyaknya pekerjaan yang terlambat. Suatu pekerjaan Ji terlambat jika Ci > ci. Dengan demikian banyaknya pekerjaan yang terlambat adalah |LJ|, dimana LJ = {Ji : Ci > ci}.
II-10
3. Minimalisasi keterlambatan maksimal (maximum tardiness). Keterlambatan (tardiness) dari pekerjaan Ji didefinisikan sebagai Ti = max {Ci – ci, 0}. Dengan demikian, keterlambatan maksimal dirumuskan sebagai max{Ti :1 d i d n} .
Tmax
4. Minimalisasi total keterlambatan (total tardiness), yaitu n
TT
¦ T , dengan n = |J|. i
i 1
5. Minimalisasi total keterlambatan berbobot (weighted total tardiness), yaitu n
WTT
¦ w T , dengan n = |J| i i
i 1
dan wi menyatakan bobot keterlambatan pekerjaan Ji. Dalam hal ini, pekerjaan yang tidak boleh terlambat lama memiliki bobot yang besar dan pekerjaan yang boleh terlambat lama memiliki bobot kecil.
2.2.3 Representasi dengan Graf Disjungtif Masalah penjadwalan Job-Shop dapat direpresentasikan secara elegan dengan menggunakan model graf disjungtif [OLI01]. Graf disjungtif didefinisikan sebagai graf berarah
G
( N ; A, B) , dimana N adalah himpunan simpul yang
merepresentasikan operasi-operasi yang akan dijadwalkan, A adalah himpunan sisi berarah konjungtif (conjunctive directed arc) yang merepresentasikan urutan operasi-operasi pada satu pekerjaan, dan B adalah himpunan sepasang sisi berarah disjungtif (disjunctive directed arc) yang merepresentasikan operasi-operasi yang menggunakan sumber daya atau mesin yang sama.
Pada setiap pekerjaan Ji, operasi oi(j+1) dijalankan setelah operasi oij. Dengan demikian, terdapat sisi berarah (oij ĺ oi(j+1)) di A. Dua operasi pada pekerjaan berbeda yang menggunakan sumber daya yang sama dihubungkan oleh dua sisi berarah dengan arah yang berlawanan. Arti semantik dari dua sisi berarah ini adalah adanya dua kemungkinan urutan operasi yang dapat dikerjakan pada sumber daya yang sama. Arah yang satu menyatakan bahwa operasi yang satu dikerjakan lebih dulu dan arah yang satunya lagi menyatakan bahwa operasi
II-11
tersebut dikerjakan di akhir setelah operasi lainnya selesai. Misalkan operasi oij pada pekerjaan Ji menggunakan sumber daya yang sama dengan operasi oi’j’ pada pekerjaan Ji’. Dengan demikian, terdapat sisi berarah (oij ĺ oi’j’) dan (oi’j’ ĺ oij) di
B. Sisi berarah (oij ĺ oi’j’) menyatakan bahwa operasi oij dikerjakan lebih dulu daripada operasi oi’j’ dan sisi berarah (oi’j’ ĺ oij) menyatakan sebaliknya. Dengan demikian, upagraf dari G yang terdiri atas simpul-simpul berupa operasi yang dikerjakan pada satu sumber daya yang sama membentuk sebuah graf berarah lengkap. Selanjutnya setiap sisi berarah konjungtif (oij ĺ oi(j+1)) A diasosiasikan dengan lama waktu pemrosesan operasi oij, yaitu pij. Demikian juga dengan sisi-sisi berarah di B,
sisi (oij ĺ oi’j’) diasosiasikan dengan lama waktu pemrosesan oij
dan sisi (oi’j’ ĺ oij) diasosiasikan dengan lama waktu pemrosesan oi’j’, yaitu pi’j’. Sebagai contoh, tinjau masalah penjadwalan Job-Shop dengan tiga pekerjaan dan empat sumber daya berikut. Data penggunaan sumber daya, urutan penggunaan sumber daya dan lama waktu pemrosesan sumber daya tersebut dinyatakan dalam Tabel II-2 berikut.
Tabel II-2 Data Masalah Penjadwalan Job-Shop
Pekerjaan 1 2 3
Urutan sumber daya r1, r2, r3 r2, r1, r4, r3 r1, r2, r4
di
Waktu pemrosesan
ci
0 0 0
p11 = 11, p12 = 9, p13 = 5 p21 = 9, p22 = 4, p23 = 6, p24 = 7 p31 = 5, p32 = 8, p13 = 4
25 26 17
Pada contoh di atas, setiap pekerjaan dapat mulai dikerjakan pada waktu 0. Pekerjaan 1 menggunakan tiga buah sumber daya r1, r2, dan r3. Waktu pemrosesan pekerjaan tersebut oleh pekerjaan 1 berturut-turut adalah 11, 9, dan 5. Dengan demikian, waktu harapan selesai pekerjaan 1 adalah 11+9+5 = 25. Pekerjaan 2 dan 3 pada Tabel II-2 dibaca dengan cara yang sama. Selanjutnya, Graf disjungtif yang merepresentasikan masalah penjadwalan Job-Shop tersebut dapat dilihat pada Gambar II-5.
II-12
Gambar II-5 Graf Disjungtif dari Masalah Penjadwalan Job-Shop
Ketika kriteria optimasi yang dipilih adalah minimalisasi makespan, dua buah simpul dummy ditambahkan pada graf disjungtif. Satu simpul digunakan sebagai simpul sumber yang dihubungkan dengan operasi pertama pada setiap pekerjaan dengan sisi berarah konjungtif dari simpul sumber ke operasi pertama pada setiap pekerjaan. Simpul yang satunya sebagai simpul akhir yang dihubungkan dengan operasi terakhir pada setiap pekerjaan dengan sisi berarah konjungtif dari operasi terakhir setiap pekerjaan ke simpul akhir. Simpul akhir ini digunakan untuk menentukan waktu selesai sebenarnya pada pekerjaan terakhir. Tetapi jika kriteria optimasi yang dipilih adalah minimalisasi keterlambatan (jumlah pekerjaan yang terlambat,
keterlambatan
maksimal,
total
keterlambatan
maupun
total
keterlambatan berbobot), dibutuhkan n+1 buah simpul tambahan, dimana n menyatakan banyaknya pekerjaan yang harus dijadwalkan. Satu simpul digunakan sebagai simpul sumber, sama seperti sebelumnya dan n simpul yang lain dihubungkan dengan satu operasi terakhir tiap pekerjaan [OLI01]. Dengan cara ini, keterlambatan setiap pekerjaan dapat ditentukan. Contoh penggunaan simpul
dummy pada graf disjungtif sebelumnya dapat dilihat pada Gambar II-6. Pada gambar tersebut, S menyatakan simpul dummy sebagai simpul sumber dan N1, N2, dan N3 menyatakan simpul akhir.
II-13
Gambar II-6 Graf Disjungtif dengan Simpul Dummy
Pada masalah penjadwalan Job-Shop, urutan dua buah operasi yang menggunakan sumber daya yang sama harus ditentukan. Hal ini sama dengan membuang salah satu sisi berarah dari setiap pasang sisi berarah disjungtif. Penentuan urutan atau sisi berarah yang akan dibuang dilakukan sedemikian hingga tidak ada sirkuit pada graf disjungtif yang merepresentasikan penjadwalan Job-Shop tersebut. Hal ini karena sirkuit akan menyebabkan terjadinya konflik pada penjadwalan. Sebagai contoh, tinjau sebuah upagraf disjungtif dari graf disjungtif sebelumnya yang debentuk dari simpul o12, o21, dan o32 dengan sisi berarah (o12 ĺ o21), (o21 ĺ
o32), dan (o32 ĺ o12). Upagraf tersebut disajikan pada Gambar II-7 berikut.
Gambar II-7 Upagraf Disjungtif yang Mengandung Sirkuit
Pada upagraf disjungtif di atas, terdapat sirkuit o12 ĺ o21 ĺ o32 ĺ o12. Hal ini berarti, operasi o12 dilakukan sebelum operasi o21, operasi o21 dilakukan sebelum operasi o32 dan operasi o32 dilakukan sebelum operasi o12, yang jelas tidak mungkin dapat dilakukan.
Di sisi lain, sebuah jadwal yang layak selalu dapat dibentuk berdasarkan urutan operasi-operasi sebuah graf disjungtif yang tidak mengandung sirkuit. Salah satu
II-14
caranya adalah dengan memberi nilai waktu pelepasan sebuah operasi dengan waktu tercepat setelah semua operasi predecessor-nya selesai dijadwalkan [OLI01]. Sebagai contoh, tinjau graf pada Gambar II-8 yang dihasilkan dari graf disjungtif sebelumnya dengan menghilangkan satu sisi berarah dari setiap sisi berarah disjungtif. Graf tersebut tidak mengandung sirkuit sama sekali.
Gambar II-8 Graf Tak-Bersirkuit yang Dibentuk dari Graf Disjungtif
Salah satu jadwal layak yang dibentuk dari graf disjungtif tak-bersirkutit di atas disajikan dalam Gantt-Chart pada Gambar II-9 berikut.
Gambar II-9 Jadwal Masalah Penjadwalan Job-Shop
Jadi, masalah penjadwalan Job-Shop dengan menggunakan representasi graf disjungtif dapat didefinisikan sebagai pencarian urutan-urutan operasi pada graf disjungtif sedemikian hingga tidak ada sirkuit pada graf tersebut. Dalam hal ini, solusi dari masalah penjadwalan Job-Shop adalah graf disjungtif yang tidak mengandung sirkuit. Untuk seterusnya, pada Tugas Akhir ini, istilah jadwal layak (feasible schedule), solusi, dan graf disjungtif tak-bersirkuit (acyclic disjunctive
graph) akan dianggap sama dan digunakan secara bergantian tergantung representasi yang sedang digunakan.
II-15
2.2.4 Ketetanggaan dan Lintasan Kritis Definisi lintasan kritis (critical path) dan ketetanggaan (neighbourhood) yang baik pada graf disjungtif merupakan salah satu aspek penting dalam beberapa algoritma pencarian solusi dengan suatu fungsi objektif yang harus diminimalkan seperti Hill Climbing yang digunakan dalam Tugas Akhir ini. Tujuan dari konsep ketetanggaan dan lintasan kritis adalah pembangkitan solusi-solusi baru dari sebuah solusi yang telah ditemukan secara cepat, sederhana dan lebih baik daripada solusi sebelumnya.
Solusi sebuah masalah penjadwalan Job-Shop yang berupa jadwal atau waktu pelepasan operasi terkait erat dengan urutan operasi-operasi yang harus dijadwalkan pada sumber daya yang ada. Hal ini karena jadwal semua operasi dapat ditentukan dengan mudah jika urutan operasi-operasi tersebut sudah ditentukan. Karena sebab ini, konsep ketetanggaan dan lintasan kritis sebuah solusi hanya akan diuraikan dengan menggunakan representasi graf disjungtif saja.
2.2.4.1 Definisi Formal Misalkan F menyatakan himpunan semua solusi dalam masalah penjadwalan Job-
Shop. Hal ini sama juga dengan himpunan semua graf disjungtif tak-bersirkuit yang merepresentasikan masalah penjadwalan Job-Shop tersebut. Terdapat dua fungsi utama yang dapat didefinisikan pada F. Fungsi pertama adalah fungsi objektif f : F ĺ R, dimana R adalah himpunan bilangan real. Fungsi tersebut menyatakan suatu nilai yang ingin dioptimalkan dalam penjadwalan. Salah satu contoh fungsi ini adalah makespan dan keterlambatan (banyaknya pekerjaan yang terlambat, keterlambatan maksimum dan total keterlambatan) seperti telah dijelaskan sebelumnya.
Fungsi yang kedua adalah fungsi ketetanggaan Nb: F ĺ ((F), dimana ((F) menyatakan power set dari himpunan F, yaitu himpunan yang berisi semua himpunan bagian dari F. Dengan kata lain, Nb adalah sebuah fungsi yang memetakan setiap solusi x F dengan sebuah himpunan bagian Nb(x) F.
II-16
Anggota-anggota Nb(x) (yang berupa solusi-solusi di F juga) selanjutnya disebut sebagai tetangga dari x [OLI01].
2.2.4.2 Ketetanggaan dalam algoritma Hill Climbing Algoritma Hill Climbing pada Tugas Akhir ini digunakan untuk mencari solusi optimal lokal. Hal ini dilakukan dengan menganalisa nilai fungsi objektif pada tetangga-tetangga dari solusi yang telah ditemukan. Tetangga yang memiliki fungsi objektif lebih baik daripada solusi sebelumnya akan digunakan sebagai solusi berikutnya pada iterasi yang dilakukan.
Sebagai contoh, misalkan telah ditemukan sebuah solusi masalah penjadwalan
Job-Shop. Dengan menggunakan fungsi ketetanggaan Nb, beberapa solusi lain dapat dibangkitkan secara efisien. Solusi-solusi lain yang merupakan tetangga dari solusi asal tersebut kemudian dihitung nilai fungsi objektifnya. Jika ada tetangga yang memiliki nilai fungsi objektif lebih optimal dibandingkan dengan solusi asal, maka tetangga tersebut akan dipilih sebagai solusi yang baru. Langkah selanjutnya adalah mencari solusi yang lainnya lagi dengan menganalisa tetanggatetangga dari solusi yang baru. Iterasi ini dilakukan terus sampai tidak ada tetangga yang memiliki fungsi objektif yang lebih optimal.
2.2.4.3 Lintasan Kritis Dari sembarang jadwal layak yang direpresentasikan dengan graf disjungtif takbersirkuit, jadwal baru selalu bisa dibangkitkan dengan cara mengubah arah sebuah sisi pada graf disjungtif. Arah yang bisa diubah ini hanyalah arah pada sisi-sisi berarah disjungtif. Arah pada sisi-sisi berarah konjungtif tidak dapat diubah karena merepresentasikan urutan operasi-operasi pada satu pekerjaan. Arah pada sisi-sisi berarah disjungtif menyatakan urutan penggunaan sumber daya oleh operasi-operasi pada beberapa pekerjaan. Dengan demikian, mengubah arah sisi-sisi disjungtif sama halnya dengan mengubah urutan operasi-operasi yang menggunakan sumber daya yang sama. Hal inilah yang menjadi dasar dalam penentuan tetangga-tetangga dari sebuah solusi yang telah ditemukan.
II-17
Namun jadwal yang baru dibangkitkan dengan cara seperti di atas tidak menjamin kelayakan jadwal tersebut (tidak adanya konflik dalam jadwal yang baru). Hal ini dikarenakan pengubahan sebuah arah pada sisi disjungtif bisa menyebabkan adanya sirkuit pada graf disjungtif yang baru. Adanya sirkuit ini akan menyebabkan konflik pada penggunaan sumber daya. Selain itu, pengubahan sebuah arah sebuah sisi secara sembarang tidak menjamin terbentuknya jadwal baru dengan nilai fungsi objektif yang lebih optimal.
Oleh karena itu, diperlukan suatu kriteria untuk menentukan sisi-sisi mana saja yang bisa diubah tanpa menyebabkan terjadinya sirkuit pada graf disjungtif. Kriteria tersebut juga harus dapat digunakan untuk menemukan solusi lain dengan fungsi objektif yang lebih optimal. Dengan kata lain, kriteria tersebut menjadi dasar dalam pendefinisian fungsi ketetanggaan Nb.
Sisi disjungtif pada graf disjungtif yang memenuhi kriteria di atas disebut sebagai sisi kritis (critical arc). Sepasang operasi yang terhubung oleh sebuah sisi kritis selanjutnya disebut sebagai operasi-operasi kritis (critical operations) dan lintasan yang dibentuk oleh sisi-sisi kritis disebut sebagai lintasan kritis. Dalam hal optimasi suatu nilai fungsi objektif, operasi-operasi kritis dapat didefinisikan sebagai operasi-operasi yang menggunakan sumber daya yang sama dan urutannya tidak bisa diubah tanpa mengubah nilai fungsi objektif yang ingin dioptimalkan [OLI01].
Salah satu contoh lintasan kritis adalah lintasan terpanjang pada graf disjungtif [FOR97]. Jika sebuah sisi pada lintasan kritis ini diubah arahnya, tidak akan mungkin terbentuk sebuah sirkuit pada graf disjungtif. Karena jika bisa terbentuk sebuah sirkuit baru pada graf disjungtif, maka lintasan tersebut tidak mungkin merupakan lintasan yang terpanjang. Kriteria ini sangat cocok diaplikasikan jika fungsi objektif yang ingin diminimalkan adalah makespan. Hal ini karena lintasan yang sangat panjang pada umumnya menyebabkan nilai makespan yang besar. Dengan mengubah arah salah satu sisi pada lintasan terpanjang, akan terbentuk
II-18
dua lintasan yang lebih pendek. Akibatnya, akan terbentuk solusi baru dengan nilai makespan yang lebih kecil.
Sebagai contoh, tinjau kembali graf disjungtif pada Gambar II-7. Salah satu lintasan terpanjang pada graf tersebut adalah lintasan o21 ĺ o32 ĺ o12 ĺ o13 ĺ
o24. Dengan demikian, lintasan tersebut merupakan lintasan kritis. Salah satu tetangga dapat didapatkan dengan cara mengubah arah sebuah sisi berarah disjungtif pada lintasan tersebut. Misalnya dengan mengubah sisi berarah disjungtif (o32 ĺ o12) menjadi sisi berarah disjungtif (o12 ĺ o32), akan dihasilkan sebuah graf disjungtif baru yang merupakan tetangga dari graf disjungtif pada Gambar II-8. Graf tersebut disajikan pada Gambar II-10 berikut.
Gambar II-10 Graf Disjungtif Tetangga
2.2.4.4 Struktur Ketetanggaan Literatur-literatur masalah penjadwalan Job-Shop yang ada selama ini menyebutkan paling sedikit ada enam cara membangun struktur ketetanggaan untuk menemukan solusi-solusi baru dari satu solusi yang telah ditemukan. Keenam struktur ketetanggaan tersebut menggunakan lintasan kritis sebagai dasar penentuan tetangga-tetangga dari satu solusi asal. Struktur yang pertama meninjau semua kemungkinan tetangga yang bisa dibangkitkan dengan cara mengubah arah setiap sisi pada setiap lintasan kritis. Dengan demikian banyaknya tetangga yang diperoleh dengan cara ini sangat besar dan memang merupakan yang terbesar dibandingkan dengan struktur lainnya. Struktur yang lainnya lebih ketat daripada struktur yang pertama, yaitu ada beberapa sisi kritis yang arahnya diubah dan beberapa sisanya tidak. Ini akan mengurangi banyaknya tetangga yang harus dianalisa nilai fungsi objektifnya untuk memperoleh solusi yang lebih baik.
II-19
Untuk menjelaskan keenam struktur tersebut, digunakan beberapa definisi. Pada operasi-operasi yang menggunakan satu sumber daya yang sama, rp(oij) didefinsikan sebagai operasi yang dikerjakan sebelum operasi oij (predecessor
operations) dan rs(oij) sebagai operasi yang dikerjakan setelahnya (successor operations).
Enam struktur ketetanggaan tersebut adalah [OLI01]: 1. Tetangga dari solusi awal diperoleh dengan cara mengubah sembarang satu sisi pada setiap lintasan kritis yang terdapat pada graf disjungtif. Dengan demikian, ukuran ketetanggaan yang dibangun dengan cara ini tergantung pada banyaknya lintasan kritis yang terdapat pada graf disjungtif dan banyaknya sisi-sisi pada tiap lintasan kritis. Ukuran ketetanggaan pada struktur yang pertama ini tergolong sangat besar. 2. Pada struktur yang kedua ini, sisi kritis yang diubah arahnya adalah sisi kritis (oij ĺ oi’j’) sedemikian hingga salah satu diantara sisi (rp(oij) ĺ oij) atau (oi’j’ ĺ rs(oi’j’)) bukan merupakan sisi pada lintasan terpanjang. 3. Struktur ketetanggaan ini meninjau semua permutasi dari himpunan tiga operasi {rp(oij), oij, oi’j’} dan {oij, oi’j’, rs(oi’j’)} dimana sisi kritis (oij ĺ oi’j’) diubah arahnya dan menghasilkan graf disjungtif baru yang tidak mengandung sirkuit. 4. Struktur ketetanggaan yang keempat ini terdiri dari pengubahan sebuah operasi oij pada suatu blok operasi-operasi yang dijalankan berturutan (adjacent operations) ke bagian awal atau bagian akhir dari blok tersebut. 5. Pada struktur yang kelima ini, sisi kritis yang diubah arahnya hanyalah sisi yang berada pada batas blok operasi-operasi yang dijalankan berturutan. Lebih jauh, hanya satu lintasan kritis saja yang ditinjau. Pemilihan lintasan kritis ini dilakukan secara acak. 6. Struktur terakhir ini berbeda dari lima struktur sebelumnya. Pada struktur ini, sebuah tetangga diperoleh dengan mengubah arah lebih dari satu sisi kritis pada lintasan kritis. Berbeda dengan struktur-struktur sebelumnya dimana hanya satu sisi kritis saja yang diubah arahnya.
II-20
2.3 Constraint Programming Constraint Programming adalah metode penyelesaian masalah yang terdiri atas dua langkah, yaitu modelling dan resolution [MON01]. Modelling dilakukan dengan cara merumuskan masalah yang diberikan sebagai sebuah Constraint
Satisfaction Problem (CSP). Selanjutnya, proses pencarian solusi CSP dilakukan pada langkah resolution dengan menggunakan constraint solvers.
2.3.1 Constraint Satisfaction Problem (CSP)
2.3.1.1 Definisi Formal Sebuah CSP dapat didefinisikan secara formal sebagai tripel (V, D, C), dimana V menyatakan sebuah himpunan variabel {v1, v2, ..., vn} dan D adalah fungsi domain pada variabel, yaitu fungsi yang memetakan setiap variabel vi di V dengan sebuah himpunan objek dengan suatu tipe tertentu [OLI01], [SMI01] , [STU03]. Dengan demikian, D(vi) = Di menyatakan domain dari variabel vi. Selanjutnya, C menyatakan himpunan batasan (constraint) pada CSP. Sebuah batasan ci C terkait dengan suatu himpunan bagian dari V dan menspesifikasikan kombinasi nilai-nilai yang diperbolehkan pada variabel-variabel di himpunan bagian tersebut. Dengan kata lain, ci(vj, vk, ...) merupakan himpunan bagian dari Dj ×Dk × ... (produk Cartesius dari domain-domain variabel yang terkait dengan batasan ci). Tetapi pada umumnya, batasan-batasan dari masalah di dunia nyata tidak direpresentasikan
seperti
itu.
Representasi
ekstensional
seperti
di
atas
membutuhkan memori yang besar untuk menyimpan kombinasi nilai-nilai variabel yang diperbolehkan. Sebagai gantinya, representasi yang sering digunakan adalah representasi intensional, misalnya vi vj, vi vj + vk, dan 2vi = 3vj + 1, dan sebagainya. Sebagai contoh, tinjau masalah matematika berikut
4 x y d 20 ® ¯ x, y 3, 4,5
II-21
Masalah di atas merupakan contoh sebuah CSP dengan V = {x,y}, D(x) = D(y) = {3,4,5} dan representasi batasan C dilakukan secara intensional. Representasi batasan secara ekstensional adalah {(3,3), (3,4), (3,5), (4,4)}.
Sebuah solusi CSP adalah pemberian nilai semua variabel di V dari domainnya masing-masing sedemikian hingga semua batasan di C terpenuhi. Dengan menggunakan representasi batasan secara ekstensional, sebuah solusi CSP adalah anggota dari irisan semua batasan yang ada. Sebagai contoh, tinjau masalah matematika di atas. Solusi dari CSP tersebut jelas adalah {(3,3), (3,4), (3,5), (4,4)}. Jika masalah tersebut ditambahi sebuah batasan x = y dengan representasi ekstensional berupa {(3,3), (4,4), (5,5)}, maka solusinya menjadi {(3,3), (4,4)} yang merupakan irisan dari dua buah batasan secara ekstensional tersebut.
Pada CSP, domain-domain tiap variabel pada umumnya merupakan himpunan berhingga. Dengan demikian, banyaknya kemungkinan pemberian nilai pada setiap variabel dari domainnya dapat dihitung, yaitu | D1 | u | D2 | u"u | Dn | (banyaknya anggota produk Cartesius dari semua domain variabel). Nilai ini menjadi salah satu patokan untuk menentukan ukuran sebuah CSP, walaupun dalam prakteknya, banyaknya solusi CSP jauh lebih kecil dibandingkan dengan nilai tersebut.
Constraint Programming menggunakan strategi constraint propagation untuk mengurangi ukuran domain ini. Hal ini dilakukan dengan cara menambahkan batasan-batasan baru yang diturunkan dari batasan-batasan yang diberikan dan juga dengan membuang nilai-nilai di domain yang tidak mengarah ke solusi. Dengan demikian ukuran domain variabel menjadi lebih kecil dan pencarian solusi dapat dilakukan dengan cepat. Salah satu teknik dalam strategi constraint
propagation ini adalah Arc Consistency.
2.3.1.2 Arc Consistency Seperti halnya masalah penjadwalan Job-Shop yang dapat direpresentasikan dengan graf disjungtif, sembarang CSP juga dapat direpresentasikan dengan suatu
II-22
graf berarah, tetapi tidak harus sama seperti graf disjungtif. Simpul dan sisi pada graf berarah yang merepresentasikan CSP memiliki peran yang sama seperti graf disjungtif, yaitu simpul digunakan untuk merepresentasikan variabel dan sisi berarah untuk merepresentasikan batasan CSP.
Berdasarkan banyaknya variabel yang terkait, batasan-batasan CSP dapat dikelompokkan menjadi tiga. Batasan uner adalah batasan CSP yang menyangkut satu variabel saja. Sebagai contoh, batasan pada variabel v dalam sebuah CSP yang mengharuskan nilai v ganjil. Dalam hal ini, teknik node consistency digunakan untuk membuang semua nilai genap pada domain asal variabel v. Batasan biner pada CSP menyangkut dua variabel dalam sebuah CSP, misalnya adalah batasan 4 x y d 20 seperti di atas. Batasan CSP yang paling umum adalah
batasan n-ary, yaitu batasan yang menyangkut n buah variabel bersamaan. Sebagai contoh, sebuah CSP yang terdiri dari n buah variabel dan mengharuskan nilai semua variabelnya berbeda.
Dalam Tugas Akhir ini, batasan-batasan CSP yang digunakan hanyalah batasan uner dan biner saja. Dalam masalah penjadwalan Job-Shop, contoh batasan uner adalah waktu pelepasan sebuah pekerjaan, misalnya di 100, yang berarti bahwa pekerjaan Ji harus dimulai setelah waktu 100. Urutan dua buah operasi dalam satu pekerjaan atau karena menggunakan sumber daya yang sama merupakan contoh sebuah batasan biner.
Dengan menggunakan graf berarah, batasan biner pada variabel x dan y pada umumnya direpresentasikan dengan sepasang sisi berarah dari dua buah simpul yang merepresentasikan variabel x dan y tersebut. Hal ini sama seperti sisi disjungtif pada graf disjungtif. Sebuah sisi berarah dari simpul yang merepresentasikan variabel x ke simpul yang merepresentasikan variabel y dikatakan arc consistent jika untuk setiap nilai a di D(x), terdapat paling sedikit satu nilai b di D(y), sedemikian hingga pemberian nilai x = a dan y = b memenuhi batasan biner c(x,y) pada CSP tersebut. Dengan menggunakan representasi ekstensional, hal ini sama dengan mengatakan bahwa (a, b) merupakan anggota
II-23
c(x, y). Salah satu teknik dalam strategi constraint propagation yaitu arc consistency digunakan untuk menghilangkan semua nilai pada domain asal variabel sehingga semua sisi berarah pada graf yang merepresentasikan CSP tersebut arc consistent.
Selain dapat mengurangi ukuran domain variabel, arc consistency juga dapat digunakan untuk mendeteksi bahwa sebuah CSP tidak memiliki solusi. Hal ini dapat diketahui jika domain sebuah variabel menjadi kosong setelah proses pembuangan nilainya selesai. Pendeteksian ini dapat dilakukan secara cepat karena tidak perlu melakukan pemberian nilai pada semua variabel terlebih dahulu untuk mengetahui apakah CSP tersebut memiliki solusi atau tidak.
Sebagai contoh, misalkan sebuah CSP terdiri atas dua variabel x dan y dengan D(x) = D(y) = {1,2,3,4}. Batasan dalam CSP tersebut misalkan x + 1 = y. Nilai 4 pada domain variabel x menyebabkan sisi berarah dari x ke y menjadi tidak arc consistent. Hal ini karena (4, b) tidak mungkin memenuhi batasan yang diberikan untuk sembarang b di domain variabel y. Dengan demikian nilai 4 di domain variabel x dapat dibuang. Dengan cara yang sama, nilai 1 pada domain varibel y juga dibuang. Jadi, algoritma arc consistency ini menyebabkan domain variabel x menjadi {1,2,3} dan domain variabel y menjadi {2,3,4}.
Terdapat beberapa algoritma untuk membuat semua sisi berarah pada graf menjadi arc consistent dengan cara membuang beberapa nilai pada domaindomain asal variabel. Algoritma-algoritma tersebut antara lain, AC-n, mulai dari AC-1 sampai dengan AC-7 dan juga AC-2001. Dalam Tugas Akhir ini, algoritma yang digunakan adalah AC-2001.
2.3.2 Algoritma dan Stretegi Pencarian Solusi Setelah memodelkan masalah sebagai sebuah CSP, langkah berikutnya dalam constraint programming adalah mencari solusi CSP tersebut [MON01]. Pada umumnya, semua CSP dapat diselesaikan dengan sembarang algoritma pencarian yang menggunakan pohon ruang status [STU03]. Bahkan exhaustive search juga
II-24
dapat digunakan dengan cara mencoba setiap kemungkinan pemberian nilai pada setiap variabel dari domainnya dan mengecek apakah pemberian nilai tersebut memenuhi batasan-batasan CSP. Namun pencarian solusi dengan exhaustive search sangatlah buruk karena ukuran ruang pencarian yang sangat besar.
2.3.2.1 Pencarian Solusi CSP secara Komplit (Complete Search) Selain exhaustive search, terdapat banyak algoritma lain yang telah digunakan dalam literatur-literatur untuk melakukan pencarian solusi CSP secara sistematis dan komplit. Komplit di sini berarti tanpa mempedulikan waktu yang diperlukan, solusi selalu dapat ditemukan atau memang tidak ada solusi dalam CSP tersebut. Sebagian besar algoritma-algoritma tersebut merupakan variasi dari algoritma Backtracking [OLI01].
Dengan menggunakan algoritma Backtracking, pohon ruang status dibentuk selama proses pencarian dengan cara memilih sebuah variabel untuk diberi nilai dari domainnya. Pemberian nilai ini kemudian diperiksa dengan nilai-nilai variabel lain untuk mengetahui apakah pemberian nilai yang telah dilakukan tidak melanggar batasan-batasan CSP yang ada. Jika pemberian nilai ini melanggar sebuah batasan yang ada, maka variabel tersebut diberi nilai lain dari domainnya dan nilai yang menyebabkan pelanggaran tadi dibuang sementara dari domainnya. Jika domain dari variabel tersebut menjadi himpunan kosong karena semua nilai pada domain tersebut dibuang secara sementara, maka backtrack dilakukan dengan memberi nilai lain pada variabel sebelumnya. Sebagai contoh, Gambar II11 menyajikan contoh pohon ruang status yang dibentuk dari masalah N-Queen dengan ukuran 4×4.
Algoritma Backtracking murni tidak menggunakan keuntungan yang dimiliki oleh strategi constraint propagation. Perbaikan dari algoritma Backtracking dengan menggunakan strategi tersebut disebut algoritma Forward Checking (FC). Sama seperti algoritma Backtracking, algoritma FC juga melakukan pemberian nilai pada setiap algoritma secara sistematis dengan membangun pohon ruang status. Tapi berbeda dengan algoritma Backtracking, pada FC, setelah sebuah variabel
II-25
diberi nilai, nilai-nilai pada domain variabel lain yang tidak konsisten dengan pemberian nilai yang telah dilakukan akan langsung dibuang. Dalam hal ini, kekonsistenan nilai-nilai pada domain variabel berarti tidak melanggar batasanbatasan yang ada. Pada FC, backtrack dilakukan jika domain sebuah variabel menjadi kosong karena pembuangan nilai pada domain tersebut.
Gambar II-11 Pohon Ruang Status pada Masalah N-Queen Berukuran 4×4
Dengan demikian, kelebihan dari algoritma FC dibandingkan Backtracking adalah FC tidak melakukan pemeriksaan apakah pemberian nilai pada sebuah variabel akan menyebabkan suatu pelanggaran batasan dengan variabel-varibel lain yang telah diberi nilai sebelumnya. Kelemahan dari FC adalah FC tidak dapat mengecek dua variabel yang belum diberi nilai. Walaupun domain variabel tersebut konsisten dengan variabel-variabel lain yang telah diberi nilai, tetapi masih ada kemungkinan bahwa kedua variabel yang belum diberi nilai tersebut tidak konsisten satu sama lain setelah diberi nilai dari domainnya.
2.3.2.2 Variable and Value Ordering Pengurutan variabel yang akan diberi nilai maupun pengurutan nilai yang akan diberikan pada suatu variabel dari domainnya bisa mengurangi banyaknya backtrack yang dilakukan dalam proses pencarian solusi. Banyaknya backtrack ini
II-26
sering digunakan untuk mengukur efisiensi algoritma Backtracking dan variasinya [OLI01].
Pengurutan variabel yang akan diberi nilai dapat dilakukan secara statis dan dinamis. Pengurutan variabel secara statis artinya urutan ini sudah ditentukan sejak awal dan tidak akan diubah selama proses pencarian solusi berjalan. Pada pengurutan variabel secara dinamis, urutan variabel yang akan diberi nilai berikutnya akan selalu berubah tergantung pada heuristic yang digunakan dan status ruang pencarian solusi atau pohon ruang status.
Pengurutan variabel secara statis tidak membutuhkan informasi tambahan apapun. Sedangkan pengurutan variabel secara dinamis membutuhkan beberapa informasi tambahan, yaitu domain-domain dari semua variabel. Dengan demikian, strategi pengurutan variabel secara dinamis tidak dapat dilakukan pada algoritma Backtracking murni karena domain semua variabel pada algoritma ini tidak akan berubah selama proses pencarian solusi berlangsung. Pengurutan variabel secara dinamis dapat digunakan pada algoritma FC, karena domain variabel selalu berubah dengan cara menghilangkan nilai-nilai pada domain yang mengarah pada pelanggaran batasan CSP.
Salah satu heuristic yang sering digunakan dalam pengurutan variabel secara dinamis adalah strategi minimum remaining values (MRV) [STU03]. Pada stretegi ini, variabel yang akan diberi nilai berikutnya adalah variabel yang memiliki ukuran domain paling kecil. Strategi MRV tidak dapat membantu dalam menentukan pengurutan variabel jika domain semua variabel tersebut memiliki ukuran yang sama, misalnya pada awal pencarian solusi. Strategi lain yang dapat digunakan sebagai tie-breaker ini adalah degree heuristic [STU03]. Strategi ini berusaha untuk mengurangi percabangan yang akan terjadi pada pohon ruang status dengan cara memilih sebuah variabel yang memiliki batasan paling banyak dengan variabel-variabel lain.
II-27
Setelah sebuah variabel terpilih untuk diberi nilai berikutnya, nilai-nilai yang ada pada domain variabel tersebut juga perlu ditentukan urutan pemberiannya dengan tujuan mengurangi backtrack yang akan terjadi. Selain itu, pemilihan urutan nilai domain yang tepat juga dapat mempengaruhi seberapa cepat sebuah solusi ditemukan. Urutan pemberian nilai ini pada umumnya sangat tergantung pada jenis masalah yang ingin dicari solusinya. Pada masalah penjadwalan Job-Shop, pengurutan nilai yang paling tepat adalah urut dari kecil ke besar. Hal ini berarti bahwa setiap operasi dijadwalkan pada waktu tercepat yang diperbolehkan tanpa menyebabkan terjadinya konflik penggunaan sumber daya.
2.3.2.3 Constraint Satisfaction and Optimization Problem Beberapa masalah CSP bertujuan untuk mencari solusi yang tidak hanya memenuhi batasan-batasan yang ada saja. Seringkali terdapat sebuah fungsi objektif yang ingin dioptimalkan untuk mengukur kualitas sebuah solusi. Jadi CSP tersebut juga bertujuan untuk mencari solusi yang terbaik dengan memaksimalkan atau meminimalkan nilai suatu fungsi objektif. Untuk melakukan hal ini, digunakan pemodelan masalah sebagai sebuah Constraint Satisfaction and Optimization Problem (CSOP), yaitu sebuah CSP bersamaan dengan sebuah fungsi objektif f yang memetakan setiap solusi yang ada pada CSP tersebut dengan suatu nilai bilangan real. Nilai inilah yang akan menjadi ukuran kualitas solusi CSP tersebut.
Jadi, CSOP secara formal dapat didefinisikan sebagai sebuah quadruple (V, D, C, f) dimana V, D, dan C didefinisikan samap seperti definisi CSP biasa dan f : S ĺ R, dimana S menyatakan himpunan semua solusi pada CSP asal, yaitu (V, D, C).
Pada umumnya fungsi f ini dapat dihitung secara langsung dari nilai variabelvariabel pada solusi di S dengan menggunakan ekspresi-ekspresi aritmetis biasa.
Misalkan sebuah CSP bertujuan mencari solusi dengan meminimalkan nilai fungsi objektif f. Jika diketahui bahwa nilai fungsi objektif dari solusi yang dicari tidak boleh melebihi suatu batas U, maka pemodelan masalah menjadi CSOP dilakukan dengan menambahkan sebuah batasan tambahan, yaitu f(x) < U dimana x adalah
II-28
solusi yang dicari. Hal ini sama saja dengan CSP (V, D, C {f(x) < U}). Jika solusi yang diinginkan adalah solusi optimal global, yaitu solusi yang memiliki nilai fungsi objektif paling besar atau paling kecil diantara semua solusi yang ada, maka sebuah batasan tambahan seperti di atas harus ditambahkan ke dalam CSP setiap kali sebuah solusi baru yang lebih baik telah ditemukan.
2.3.2.4 Local Search Pada suatu masalah CSP dengan ukuran yang sangat besar, pencarian solusi optimal global dengan menggunakan algoritma pencarian yang komplit akan membutuhkan waktu yang sangat lama. Seringkali, solusi yang diinginkan hanyalah solusi yang baik, tidak terlalu buruk dan tidak harus merupakan solusi optimal global, tetapi proses pencariannya dapat dilakukan dalam waktu yang jauh lebih singkat.. Dengan demikian, diperlukan sebuah algoritma untuk menemukan solusi yang dekat dengan solusi optimal secara cepat.
Beberapa algoritma yang telah diajukan oleh peneliti-peneliti di bidang ini merupakan variasi dari algoritma Local Search. Algoritma-algoritma ini antara lain adalah Hill Climbing, Genetic Algorithm, Simulated Annealing dan Tabu Search. Pada Tugas Akhir ini, variasi algoritma Local Search yang akan digunakan adalah Hill Climbing.
Pada algoritma Local Search secara umum, langkah pertama yang dilakukan adalah melakukan pemberian nilai pada semua variabel secara sembarang. Hal ini mungkin menyebabkan banyak pelanggaran batasan CSP. Untuk mendapatkan sebuah solusi CSP yang tidak mengandung pelanggaran batasan sama sekali, dilakukan perbaikan secara progresif dengan cara mengubah pemberian nilai yang dilakukan untuk mengurangi pelanggaran batasan CSP. Setiap perbaikan mungkin masih mengandung pelanggaran batasan CSP, tetapi pelanggaran yang terjadi setelah perbaikan menjadi lebih sedikit. Iterasi ini berhenti ketika tidak ada lagi pelanggaran batasan sama sekali.
II-29
Prinsip di atas juga dapat diaplikasikan untuk mendapatkan solusi yang relatif baik. Dengan mengubah masalah CSP menjadi masalah CSOP, setelah satu solusi ditemukan, langkah berikutnya adalah melakukan perbaikan solusi tersebut secara progresif untuk mendapatkan solusi yang lebih baik daripada solusi yang telah ditemukan. Ini adalah prinsip utama algoritma Hill Climbing. Penggunaan algoritma Hill Climbing untuk mencari solusi optimal lokal masalah penjadwalan kereta api jalur tunggal akan dibahas pada bab berikutnya.
