Program VB .NET Minimisasi Waktu Penjadwalan (Algoritma Greedy)

Persoalan :
Sebuah server (dapat berupa processor, pompa, kasir di bank, dll) mempunai n pelanggan (customer/client) yang harus dilayani. Waktu pelayanan untuk setiap pelanggan :

(waktu di dalam sistem)

Ekuivalen dengan meminimumkan waktu rata-rata pelanggan di dalam sistem.

Misal :

Di sebuah rumah makan, terdapat 3 pelanggan yang sama – sama belum dilayani. Pelanggan pertama perlu pelayanan selama 5 menit. Pelanggan kedua perlu pelayanan selama 10 menit. Dan pelanggan terakhir, memerlukan pelayanan selama 3 menit. Bagaimana urutan pelayanan pelanggan agar waktu yang digunakan bisa seminim mungkin?

t1 = 5 ; t2 = 10 ; t3 = 3

Urutan pelayanan yang mungkin :

============================================

Urutan                                                  T 

============================================                                               

1, 2, 3 : 5 + (5 + 10) + (5 + 10 + 3 )  = 38

1, 3, 2 : 5 + (5 + 3) + (5 + 3 + 10)     = 31

2, 1, 3 : 10 + (10 + 5) + (10 + 5 + 3) = 43

2, 3, 1 : 10 + (10 + 3) + (10 + 3 + 5) = 41

3, 1, 2 : 3 + (3 + 5) + (3 + 5 + 10)     = 29 ¬ (optimal)

3, 2, 1 : 3 + (3 + 10) + (3 + 10 + 5)   = 34

============================================

Strategi Greedy untuk permasalahan ini adalah dengan mengurutkan pelanggan yang akan dilayani mulai dari pelanggan dengan waktu pelayanan terkecil. Kemudian melakukan penjumlahan waktu seperti sebelumnya sesuai dengan urutan yang sudah diperbarui.

Dalam kasus ini menjadi :

t3 = 3 ; t1 = 5 ; t2 = 10

Waktu Minimum  = 3 + (3 + 5) + (3 + 5 + 10)

                                = 3 + 8 + 18

                                = 29

Solusi Optimal : T = {3, 1, 2}

Untuk pengaplikasiannya pada program, berikut saya lampirkan Program Minimisasi Waktu Penjadwalan yang dibuat dengan VB .NET.

Dapat didownload dengan klik disini