MATA KULIAH RISET OPERASIONAL - PROGRAM DINAMIS

Pengertian Network Planning

Suatu kegiatan yang merupakan rangkaian penyelesaian pekerjaan haruslah direncanakan dengan sebaik-baiknya. Sedapat mungkin semua kegiatan atau aktivitas dalam perusahaan dapat diselesaikan dengan efisien. Semua aktivitas tersebut diusahakan untuk dapat selesai dengan cepat sesuai dengan yang diharapkan serta terintegrasi dengan aktivitas yang lainnya.

Dengan adanya Network, manajemen dapat menyusun perencanaan penyelesaian proyek dengan waktu dan biaya yang paling efisien. Pada prinsipnya Network tersebut digunakan untuk merencanakan penyelesaian berbagai macam pekerjaan/proyek.

Ahyari (1986: 457) menyatakan :

Pada prinsipnya Network Planning digunakan untuk merencakan penyelesaian berbagai macam pekerjaan, dengan menggunakan Network sebagai alat perencanaan dapatlah disusun perencanaan yang baik serta dapat diadakan realokasi tenaga kerja. Adapun keuntungan menggunakan analisis Network adalah sebagai berikut :

1.      Mengorganisir data dan informasi secara sistematis.

2.      Penentuan urutan pekerjaan.

3.      Dapat menemukan pekerjaan yang dapat ditunda tanpa menyebabkan terlambatnya penyelesaian proyek secara keseluruhan sehingga dari pekerjaan tersebut dapat dihemat tenaga, waktu dan biaya.

4.      Dapat menentukan pekerjaan-pekerjaan yang harus segera diselesaikan tepat pada waktunya, karena penundaan pekerjaan tersebut dapat mengakibatkan tertundanya penyelesaian secara keseluruhan.

5.      Dapat segera mengambil keputusan apabila jangka waktu kontrak tidak sama dengan jangka waktu penyelesaian proyek secara normal.

6.      Dapat segera menentukan pekerjaan-pekerjaan mana yang harus dikerjakan dengan lembur, atau pekerjaan mana yang harus di sub-kontrak-kan agar penyelesaian proyek secara keseluruhan dapat sesuai dengan permintaan konsumen.

Dari berbagai keuntungan penggunaan Network sebagai perencanaan tersebut, maka jelaslah bahwa Network sangat membantu manajemen untuk menyusun perencanaan.

Menurut Subagya (2000: 169) “Hubungan antar aktivitas ditunjukkan dengan network, yaitu jaringan kerja yang menggunakan simbol lingkaran untuk awal atau akhir aktivitas dan anak panah untuk kegiatan”.

2.2.3 Penyusunan Diagram Network

Untuk mempermudah penyelesaian proyek secara keseluruhan diperlukan adanya suatu diagram yang menunjukkan urutan pekerjaan.

Menurut Ahyari (1986: 457-459) :

Diagram Network merupakan proses pekerjaan secara visual. Cara menyusun Diagram Network :

a.       Setiap pekerjaan untuk penyelesaian proyek secara keseluruhan ditulis didalam bentuk simbol misalnya angka atau huruf.

b.      Waktu yang diperlukan ditulis disampingnya dan pekerjaan yang harus diselesaikan sebelum pekerjaan diselesaikan ditulis disebelah pekerjaan yang bersangkutan.

c.       Setiap pekerjaan digambarkan dalam bentuk lingkaran dengan waktu yang dipergunakan untuk menyelesaikan pekerjaan dan tiap pekerjaan disusun menurut urutan yang telah ditentukan dan dihubungkan dengan anak panah.

Dalam metode ini dikenal simbol-simbol sebagai beerikut:

               = anak panah penuh sebagai simbol daripada kegiatan

               = lingkaran sebagai simbol daripada kejadian

               = anak panah terputus-putus sebagai simbol aktifitas semu

Menurut Yamit (2000:297-305), dalam diagram Network perlu diperhatikan ketentuan-ketentuan sebagai berikut :

1.      Simbol-simbol Diagram Network:

Simbol yang digunakan dalam Diagram Network adalah :

a.       Anak panah (      ) melambangkan kegiatan. Diatas anak panah ditulis kegiatan, sedangkan dibawah anak panah adalah waktu kegiatan.

b.      Lingkaran              yang berarti event yang terjadi.

c.       Anak panah putus-putus (          ) berarti semu (dummy) kegiatan semu dimunculkan untuk menghindari 2 peristiwa atau lebih.

Gambar 2.1

Diagram Network

Sumber : Lock dalam Kramadibrata (1999:226)

Keterangan :

           = jalur kritis  

           = garis

           = Dummy

2.      Meghitung Saat Paling Cepat (SPC), SPC adalah saat paling cepat dan setiap kegiatan berada diantara dua peristiwa dan bila ada beberapa peristiwa maka dipilih waktu yang paling besar.

 

                                                                Li

Gambar 2.2

Hubungan Kegiatan

Sumber, Yamit (2000: 299)

Keterangan :

SPCi = Saat Paling Cepat untuk memulai kegiatan

SPCj = Saat Paling Cepat untuk menyelesaikan kegiatan

Li      = Lama kegiatan

i        = Nomer urut kegiatan

Rumus :

SPCj = Maks (SPCi + Li).

3.      Menghitung Saat Paling Lambat (SPL), SPL adalah saat paling lambat yang berada dibagian bawah lingkaran untuk menyelesaikan kegiatan dan untuk memulai kegiatan, apabila terdapat dua kegiatan atau lebih maka SPL yang diambil adalah jumlah yang terkecil.

 

                                                              Li

Gambar 2.3

Hubungan Kegiatan

Sumber, Yamit (2000: 300)

Keterangan :

SPLi = Saat Paling Lambat untuk memulai kegiatan

SPLj = Saat Paling Lambat untuk menyelesaikan kegiatan

Li      = Lama kegiatan

i        = Nomer urut kegiatan

Rumus :

SPLi = Min (SPLj - Li).

§  Diagram Jaringan Kerja

a.       Perancangan Proyek

b.      Gambar kegiatan proyek

c.       Simbol – simbol yang digunakan :

    1. Anak Panah

Menyatakan kegiatan

                Gambar :  

    2. Anak Panah Terputus – putus

               Menyatakan kegiatan semu atau Dummy

               Gambar : 

§  Metode CPM (Critical Path Method)

a.       Earliest Start Time (ES) : waktu tercepat untuk bisa memulai suatu kegiatan dengan waktu normal, tanpa mengganggu kegiatan lain.

b.      Latest Start Time (LS) : waktu paling lambat untuk bisa memulai kegiatan dengan waktu normal, tanpa menggangu kegiatan-kegiatan lainnya.

c.       Earliest Finish Time (EF) : waktu paling cepat untuk menyelesaikan suatu pekerjaan dalam waktu normal, tanpa mengganggu kegiatan lain.

d.      Latest Finish Time (LF) : waktu paling lambat untuk menyelesaikan suatu kegiatan dalam waktu normal, tanpa mengganggu kegiatan lain.

1.1       Pengertian Program Dinamis

            Menurut Dimayati (1992), program dinamis adalah suatu teknik matematis yang biasannya digunakan untuk membuat suatu keputusan dari serangkaian keputusan yang saling berkaitan. Tujuan utama model ini adalah untuk mempermudah penyelesaian persoalan optimasi yang mempunyai karakteristik tertentu. Istilah program dinamis, pertama kali diperkenalkan pada era 1950-an oleh Richard Bellman seorang professor di Universitas Princeton dan juga bekerja pada RAND corporation, perlu diketahui bahwa RAND corporation pada era itu merupakan suatu perusahan yang dibentuk untuk menawarkan analisis dan riset untuk angkatan bersenjata Amerika Serikat.

Saat itu, Bellman bekerja di bidang pengambilan keputusan multi tahap (multistage desicion process) dan mengerjakan beberapa metode matematis, beberapa tahun kemudian setelah Bellman berada di RAND, lahirlah istilah pemrograman dinamis. Istilah ini tidak secara langsung berhubungan dengan pemrograman, melainkan digunakan sebagai judul project yang kemudian yang diusulkan RAND coorporation pada Angkatan Udara Amerika Serikat.

Sedangkan menurut Siagian (2003), program dinamis adalah satu teknik matematis yang digunakan untuk mengoptimalkan proses pengambilan keputusan secara bertahap-ganda. Dalam teknik ini, keputusan yang menyangkut suatu persoalan dioptimalkan secara bertahap dan bukan secara sekaligus. Inti teknik ini adalah membagi satu persoalan atas beberapa bagian persoalan yang dalam program dinamis disebut tahap, kemudian memecahkan tiap tahap dengan mengoptimalkan keputusan atas tiap tahap sampai seluruh persoalan telah terpecahkan.

Selanjutnya, pada penerapanya pemrograman dinamis banyak digunakan pada proses optimalisasi masalah. Program dinamis merupakan sebuah algoritma pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah atau tahapan sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan.

Penyelesaian metode ini menggunakan persyaratan optimasi dan kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap. Ciri utama dari program dinamis adalah prinsip optimalitas yang berbunyi “jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal”. Dalam menyelesaikan persoalan dengan program dinamis, dapat digunakan dua pendekatan berbeda yaitu:

1.      Maju (forward atau top-down) : bergerak mulai dari tahap 1 terus maju ke tahap 2, 3, .., n. Urutan variabel keputusannya adalah (x1,x2,…,xn).

2.      Mundur (backward atau bottom-up) : bergerak mulai dari tahap n terus mundur ke tahap n-1, n-2, n-3, 2, 1. Urutan variabel keputusannya adalah (xn, xn-1, xn-2, xn-3, x2, x1).

Prinsip yang digunakan pada program dinamis yaitu prinsip optimalitas prinsip optimalitas berarti bahwa jika bekerja dari tahap k ke tahap k + 1, dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal. Dengan prinsip optimalitas ini dijamin bahwa pengambilan keputusan pada suatu tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya.

Metode greedy hanya satu rangkaian keputusan yang pernah dihasilkan, sedangkan pada metode program dinamis lebih dari satu rangkaian keputusan. Hanya rangkaian keputusan yang memenuhi prinsip optimalitas yang akan dihasilkan.

Program Dinamis (dynamic programming):

-          metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan tahapan (stage).

-          Sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan  yang saling berkaitan.

-          Istilah “program dinamis” muncul karena perhitungan solusi menggunakan tabel-tabel.

Pada program dinamis, rangkaian keputusan yang optimal dibuat dengan menggunakan Prinsip Optimalitas. Prinsip Optimalitas: jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal.

•         Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal.

•         ongkos pada tahap k +1 =  (ongkos yang dihasilkan pada tahap k )  + (ongkos dari tahap k ke tahap k + 1).

1.2    Karakteristik Program Dinamis

         Persoalan pada program dinamis dirancang untuk memberikan suatu interpretasi secara fisik dari struktur yang abstrak dari persoalan program dinamis. Salah satu cara untuk mengelal situasi yang dapat diformulasikan sebagai persoalan program dinamis ini ialah dengan memperhatikan karakteristik yang ada pada program dinamis. Berikut ini merupakan gambaran dasar atau karakteristik program dinamis:

1. Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil satu keputusan.
2. Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan yang ada pada tahap tersebut.
3. Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.
4. Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan bertambahnya jumlah tahapan.
5. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan dan ongkos pada tahap tersebut.
6. Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan pada tahap sebelumnya.
7. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1
8. Prinsip optimalitas berlaku pada persoalan tersebut.

Dua pendekatan yang digunakan dalam PD:

1.      PD maju (forward atau up-down).

2.      PD mundur (backward atau bottom-up).

Misalkan x₁, x₂, …, x_n menyatakan peubah (variable) keputusan yang harus dibuat masing-masing untuk tahap 1, 2, …, n. Maka,

1.      Program dinamis maju. Program dinamis bergerak mulai dari tahap 1, terus maju ke tahap 2, 3, dan seterusnya sampai tahap n. Runtunan peubah keputusan adalah x₁, x₂, …, x_n.

2.      Program dinamis mundur. Program dinamis bergerak mulai dari tahap n, terus mundur ke tahap n – 1, n – 2, dan seterusnya sampai tahap 1. Runtunan peubah keputusan adalah x_n, x_n-1, …, x₁.

Prinsip optimalitas pada PD maju:

Ongkos pada tahap k +1 =  (ongkos yang dihasilkan pada tahap k )  + (ongkos dari tahap k ke tahap k + 1) k = 1, 2, …, n – 1

Prinsip optimalitas pada PD mundur:

Ongkos pada tahap k =  (ongkos yang dihasilkan pada tahap k + 1)  + (ongkos dari tahap k + 1 ke tahap k ) k = n, n – 1, …, 1

Langkah-langkah Pengembangan Algoritma Program Dinamis

1. Karakteristikkan struktur solusi optimal.
2. Definisikan secara rekursif nilai solusi optimal.
3. Hitung nilai solusi optimal secara maju atau mundur.
4. Konstruksi solusi optimal.