MINIMISASI AUTOMATED GUIDED VEHICLE PADA JARINGAN TRANSPORTASI DI TERMINAL KONTAINER SEMI OTOMATIS MENGGUNAKAN METODE NODE SPLITTING
oleh Fahrizal M.0103056
SKRIPSI Ditulis dan diajukan untuk memenuhi sebagian persyaratan Memperoleh gelar Sarjana Sains Matematika
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA 2009
BAB III METODE PENULISAN
Metode yang digunakan dalam penulisan skripsi ini adalah studi literatur, yaitu mengumpulkan referensi berupa jurnal dan buku-buku yang menyajikan beberapa definisi dan teori-teori mengenai pembentukan jaringan transportasi dan cara penyelesaian dalam masalah minimisasi. Langkah operasional yang akan ditempuh guna menyelesaikan masalah berdasarkan kerangka pemikiran adalah 1. memberikan gambaran proses pengangkutan kontainer yang dilakukan oleh AGV pada terminal kontainer, 2. mengidentifikasi variabel dan hal-hal yang mempengaruhi proses pengangkutan kontainer, 3. menterjemahkan gambaran proses pengangkutan kontainer ke dalam bahasa matematis, 4. menentukan pekerjaan
dan
yang berhubungan
, dengan
adalah
banyaknya pekerjaan), 5. berdasarkan langkah 4, dibangun graf berarah dan
,
6. membentuk jaringan sumber
dengan
dari graf
dan sebuah titik target
berkapasitas satu dengan 7. mengubah jaringan
, dan
, adalah
adalah
ditambah sebuah titik
ditambah garis
dan
,
menjadi jaringan
dengan cara transformasi membagi sebuah
titik [1] yang telah diterangkan pada 2.1.5, 8. menggunakan algoritma arus minimum Vis et al [5] yang telah diterangkan pada 2.1.6 untuk memperoleh nilai minimum
,
9. membuat program aplikasi umum dari algoritma arus minimum Vis et al [5] dengan menggunakan bahasa pemograman matlab.
BAB IV PEMBAHASAN Menurut Vis et al [5], permasalahan minimisasi jumlah AGV dapat diselesaikan menggunakan algoritma arus minimum. Sebelum menggunakan algoritma arus minimum, terlebih dahulu permasalahan dimodelkan dalam bentuk jaringan berarah. 4.1. Model Permasalahan Permasalahan dimodelkan dalam bentuk jaringan berarah. Sebagaimana dijelaskan pada 2.1.4, jaringan berarah dibentuk dari suatu graf berarah. Berdasarkan 2.1.2, untuk mendapatkan hubungan antar pekerjaan yang disajikan dalam bentuk sebuah graf berarah, diberikan gambaran proses pekerjaan di terminal kontainer semi otomatis. 4.1.1. Proses Pekerjaan Proses pekerjaan dapat dijelaskan dengan proses bongkar atau muat kontainer. Proses bongkar kontainer ditunjukkan pada Gambar 4.1. Proses tersebut berawal ketika crane asal berupa QC yang bertugas mengambil dan memindahkan sebuah kontainer dari atas kapal (a) ke atas AGV tak bermuatan atau AGV kosong di titik awal (b) siap melaksanakan tugasnya. Crane Asal Kapal
Crane Tujuan AGV Tumpukan
a
b
c
d
Gambar 4.1 Proses bongkar kontainer
Sebuah AGV hanya dapat mengangkut sebuah kontainer. Ketika kontainer sudah berada di atas AGV, kontainer langsung dibawa AGV ke titik kedatangan (c). Setibanya di titik kedatangan, kontainer di atas AGV diangkat oleh crane tujuan berupa ASC untuk dipindahkan ke blok tumpukan (d) dan disimpan dalam tumpukan selama periode tertentu. Setelah kontainer berhasil ditempatkan pada posisi yang diinginkan, crane tujuan kembali ke titik kedatangan untuk mengangkat kontainer dari pekerjaan lain yang telah datang. Terdapat kesamaan dalam proses bongkar dan muat kontainer, yaitu mengangkut kontainer dari crane asal ke crane tujuan. Namun ada beberapa perbedaan dalam proses muat kontainer, yakni (1) kontainer diambil dari tumpukan kontainer dan dibawa untuk ditempatkan di atas kapal, (2) ASC berfungsi sebagai crane asal, dan (3) QC berfungsi sebagai crane tujuan.
Keseluruhan proses di atas menunjukkan bahwa setiap pekerjaan mempunyai karakteristik keterangan waktu. Nilai karakteristik setiap pekerjaan menimbulkan hubungan antar pekerjaan sebagai dasar dibentuknya sebuah graf berarah. 4.1.2. Karakteristik Setiap Pekerjaan Sebelum kapal merapat di terminal kontainer, jumlah kontainer yang akan disimpan di atas kapal atau blok tumpukan harus diketahui terlebih dahulu. Hal ini berarti terdapat N pekerjaan yang harus diselesaikan. ) memiliki beberapa karakteristik yang berbeda. Setiap pekerjaan ( Berikut karakteristik keterangan waktu yang nilainya diketahui sebelum semua pekerjaan dilaksanakan. 1. Waktu pada saat perjalanan AGV bermuatan di titik awal pekerjaan dimulai atau waktu mulai pekerjaan
( ),
2. Lama waktu yang dibutuhkan AGV bermuatan untuk bergerak dari crane asal ke crane tujuan pekerjaan
atau waktu perjalanan pekerjaan
(
),
3. Lama waktu yang dibutuhkan oleh crane tujuan untuk mengangkut kontainer pekerjaan
dari titik kedatangan ke atas sebuah kapal atau tumpukan dan kembali lagi
ke titik kedatangannya. Nilai ini disebut waktu pengkondisian pekerjaan
( ).
Dari ketiga karakteristik di atas, diperoleh waktu kedatangan pekerjaan ( ) dan waktu terkirim pekerjaan ( ). Waktu kedatangan pekerjaan adalah waktu tiba AGV bermuatan di titik kedatangan pekerjaan . Waktu ini bergantung pada waktu mulai pekerjaan dan waktu perjalanan pekerjaan , sehingga . (4.1) Waktu terkirim pekerjaan adalah waktu pada saat kontainer diangkat dari atas AGV oleh crane tujuan. Kontainer di atas AGV dapat diangkat langsung oleh crane tujuan pada saat AGV bermuatan tiba di titik kedatangan atau apabila tidak ada kontainer lain yang sedang disusun oleh crane tujuan. Apabila terdapat kontainer ( adalah pekerjaan sebelumnya) sedang disusun oleh crane tujuan, kontainer harus menunggu sampai crane tujuan kembali lagi ke titik kedatangan atau waktu terkirim pekerjaan . Berdasarkan keterangan tersebut, ditambah waktu pengkondisian pekerjaan bergantung pada atau , sehingga = max , . (4.2) datang di crane tujuan pekerjaan lebih awal dari pada pekerjaan Pekerjaan ( ). Hal ini disebabkan karena crane tujuan pekerjaan dan adalah sama. dilaksanakan crane tujuan terlebih dahulu ( ). Jika waktu Sehingga, pekerjaan selesai pekerjaan , yakni waktu terkirim ditambah waktu pengkondisian dari pekerjaan , lebih kecil atau sama dengan waktu kedatangan pekerjaan di crane tujuan tersebut, maka . Sebaliknya, jika waktu selesai pekerjaan lebih lama, AGV bermuatan
harus menunggu sampai crane tujuan menyelesaikan pekerjaan , sehingga . Apabila kontainer telah diangkat dari AGV, maka AGV kosong dapat mengerjakan pekerjaan selanjutnya (pekerjaan ). Lama waktu yang dibutuhkan AGV kosong untuk berpindah dari crane tujuan pekerjaan ke crane asal pekerjaan disebut waktu berpindah pekerjaan ke ( ). Apabila crane tujuan pekerjaan sama dengan crane asal pekerjaan maka nilai sama dengan nol. Waktu ini juga merupakan salah satu karakteristik yang diketahui nilainya sebelum semua pekerjaan dimulai. setelah pekerjaan selesai Syarat sebuah AGV dapat mengerjakan pekerjaan adalah waktu mulai pekerjaan lebih besar atau sama dengan jumlah dari waktu terkirim pekerjaan dan waktu berpindah pekerjaan ke , sehingga . (4.3) Dengan syarat pada persamaan (4.3), diperoleh hubungan antar pekerjaan yang mendasari terbentuknya suatu jaringan berarah. pekerjaan
4.1.3. Model Jaringan Berarah Menurut Johnsonbaugh [3], graf dibentuk dari himpunan titik-titik ( ) dan garisgaris ( ) yang terlihat seperti kota dan jalan pada sebuah peta. Garis yang dan titik dinotasikan dengan . Berdasarkan keterangan menghubungkan titik tersebut, setiap pekerjaan dalam permasalahan minimisasi jumlah AGV dilambangkan sebagai sebuah titik. Apabila persamaan (4.3) dipenuhi, titik dihubungkan dengan titik oleh satu garis berarah dengan kapasitas satu yang mengindikasikan bahwa sebuah AGV mempunyai kemungkinan untuk mengerjakan pekerjaan setelah pekerjaan selesai dan pekerjaan tidak dapat dikerjakan setelah pekerjaan selesai. Terbentuk graf berarah dengan dan . Selanjutnya graf berarah menurut Grimaldi [2] dapat disajikan dalam bentuk dengan menambahkan sebuah titik sumber dan sebuah titik target jaringan berarah ke dalam graf berarah . Kedua titik tersebut dihubungkan dengan semua titik anggota , sehingga terbentuklah garis dan dengan kapasitas satu. Jaringan dinyatakan dengan dan . Alasan jaringan berarah dibentuk adalah untuk mencari jumlah arus maksimum dari ke yang akan digunakan dalam algoritma arus minimum Vis et al [5]. Jaringan berarah yang dibentuk merupakan langkah awal untuk menyelesaikan permasalahan minimisasi jumlah AGV pada terminal kontainer semi otomatis. Untuk ditransformasikan menjadi dengan metoda menyelesaikan permasalahan, jaringan node splitting seperti yang telah diterangkan oleh Ahuja et al [1] pada bagian 2.1.5. Setiap titik (kecuali titik dan ) dibagi menjadi dua buah titik (asal) dan . Sehingga adalah (tujuan), kemudian tambahkan garis dan , pekerjaan dan yang terhubung
. Nilai batas bawah
untuk
adalah 1 untuk . setiap garis Sebuah lintasan berarah dalam jaringan ini mengindikasikan urutan pekerjaan yang dilaksanakan oleh sebuah AGV. Tujuan yang ingin diperoleh dalam jaringan ini adalah menentukan jumlah minimum dari lintasan berarah karena lintasan berarah menunjukkan jumlah minimum dari AGV yang dibutuhkan. Syarat lintasan berarah dalam jaringan ini adalah 1. sebuah lintasan harus melewati satu titik selain dan , 2. jika suatu titik telah dilewati oleh suatu lintasan maka lintasan lain tidak boleh melewati titik tersebut, dan 3. semua titik harus dilewati oleh lintasan. ke dalam dinotasikan sebagai . Apabila Jumlah lintasan berarah dari terdapat pekerjaan yang harus diselesaikan dan satu pekerjaan diselesaikan oleh satu sama dengan . Oleh sebab itu, tujuan dari pembuatan AGV, diperoleh nilai adalah meminimumkan dengan kendala
. Model di atas dapat diselesaikan dengan menggunakan
dan algoritma arus minimum.
4.2. Algoritma Arus Minimum , Vis et al [5] mengenalkan sebuah Untuk menyelesaikan permasalahan algoritma arus minimum seperti yang disajikan dalam tinjauan pustaka. Ide di balik algoritma arus minimum ini adalah nilai arus fisibel pada langkah 1 dapat dikurangi digunakan sebagai faktor pengurang arus menjadi arus minimal. Arus maksimum fisibel sehingga arus fisibel tersebut menjadi arus minimum. Setiap garis mundur diantara dua titik dalam arus maksimum merepresentasikan bahwa dua pekerjaan diselesaikan oleh AGV yang sama. Hal ini berarti bahwa nilai arus mengindikasikan jumlah penghematan AGV dibandingkan nilai arus maksimum mengindikasikan garis fisibel pada langkah 1. Dengan kata lain, arus maksimum yang dihilangkan dan ditambahkan pada arus fisibel , dengan , . Garis dihilangkan dari arus fisibel apabila dalam arus maksimum terdapat garis atau ditambahkan dalam arus fisibel apabila dalam arus garis maju. Sebaliknya garis maksimum terdapat garis atau garis mundur. Arus maksimum mengindikasikan banyaknya nilai arus fisibel yang harus dikurangi sampai menjadi arus minimum. 4.3. Contoh Penyelesaian Permasalahan
