PENYELESAIAN MASALAH PENJADWALAN KRU KERETA API DENGAN ALGORITMA DIVIDE – AND – PRICE

WIDYA YULI ASTUTI, Dr. Irwan Endrayanto S.Si, M.Sc.

2014 | Skripsi | MATEMATIKA

Pada tugas akhir ini akan dibahas tentang penyelesaian masalah penjadwalan kru kereta api. Masalah tersebut meliputi pembentukan tugas-tugas yang mungkin dan menentukan tugas mana yang dapat meminimalkan biaya. Masalah tersebut diselesaikan dengan algoritma Divide – and – Price. Tahap awal dari algoritma ini adalah mendekomposisikan suatu daerah yang mencakup semua perjalanan menjadi beberapa subdaerah. Tahap kedua adalah menyelesaikan secara paralel masalah penjadwalan setiap subdaerah dengan shortest path problem with resource constraint dan program linear. Tahap terakhir adalah proses pricing update dan assignment update. Tahap ini untuk memberikan hubungan antara penyelesaian pada masing-masing subdaerah, sehingga diperoleh penyelesaian optimal bagi daerah secara keseluruhan. Sebagai ilustrasi, pada skripsi ini disajikan contoh numeris penjadwalan kru kereta api.

-

Kata Kunci : -