Job Scheduling dengan Deadline

Greedy adalah sebuah algoritma untuk mencari solusi yang paling optimum yang mana bernilai maksimum pada setiap langkahnya, atau bisa juga disebut local maximum. Namun pada kebanyakan kasus, greedy tidak bisa menghasilkan nilai optimal, tapi biasanya bisa memberikan solusi yang mendekati nilai paling optimum.
Untuk skema umum algoritma greedy dalam pscedu-code, bisa dilihat di sini.
Kita bisa menemukan masalah sehari-hari yang dapat kita selesaikan dengan algoritma greedy.

Dari gambar di atas, diibaratkan huruf sebagai sebuah tempat yang berbeda dan jarak yang berbeda dengan garis sebagai jalur. Kita akan mencoba mencari jalur terpendek untuk bisa mengelilingi semua tempat dari posisi A dan kembali lagi ke posisi A, menggunakan algoritma greedy.
Dari semua tempat, pilih jarak terdekat dan tempat yang belum pernah dikunjungi kecuali akhir di saat kembali lagi ke titik awal.

A ke E ke D ke C ke B ke G ke F ke A

9 + 12 + 13 + 14 + 11 + 10 + 15 = 84

Kita berharap dengan menggunakan algoritma greedy kita bisa mendapatkan nilai yang optimum. Namun nyatanya algoritma greedy hanya mengambil pilihan terbaik pada tiap langkahnya tanpa memikirkan apa yang akan terjadi selanjutnya. Padahal jika kita menggunakan exhaustive search (solusi optimal), kita bisa mendapatkan nilai yang lebih optimum.

A ke E ke F ke G ke B ke C ke D ke A

9 + 13 + 10 + 11 + 14 + 13 + 12 = 82

Jadi tidak selamanya algoritma tersebut benar, namun masih bisa dikatakan mendekati nilai kebenaran.

Pemecahan Masalah dengan Algoritma Greedy

Strategi greedy untuk memilih job:    

                        Pada setiap langkah, pilih job i dengan

                        p_i yang terbesar untuk menaikkan nilai

                        fungsi obyektif F.

Contoh:

(p₁, p₂, p₃, p₄) = (50, 10, 15, 30)

(d₁, d₂, d₃, d₄) = (2, 1, 2, 1)

 

Solusi optimal: J = {4, 1} dengan F = 80.

 

Kompleksitas algoritma greedy : O(n²).

Kesimupulan

Algoritma greedy merupakan algoritma yang bersifat heuristik, mencari nilai maksimal sementara dengan harapan akan mendapatkan solusi yang cukup baik. Meskipun tidak selalu medapatkan solusi terbaik (optimum), algoritma greedy umumnya memiliki kompleksitas waktu yang cukup baik, sehingga ini sering digunakan untuk kasus yang memerlukan solusi cepat meskipun tidak optimal seperti sistem real-time atau game.

Dari implementasi yang kita lakukan, dapat dilihat bagaimana algoritma greedy memiliki beberapa fungsionalitas dasar, yaitu:

  1. Fungsi untuk melakukan penelusuran masalah.

  2. Fungsi untuk memilih local maximum dari pilihan-pilihan yang ada tiap langkahnya.

  3. Fungsi untuk mengisikan nilai local maximum ke solusi keseluruhan.

  4. Fungsi yang menentukan apakah solusi telah didapatkan.

Tentunya fungsi-fungsi di atas juga dapat digabungkan atau dipecah lebih lanjut lagi, menyesuaikan dengan strategi greedy yang dikembangkan.

Referensi:

• Kurniadi, Addi, 2014, Materi Analisis Algoritma: Algoritma Greedy, [online],
  (http://kurniadi-addi.blogspot.co.id/2015/07/materi-analisis-algortima-algoritma.html, diakses 04/12/2016)
• Xandra Albert Sim., Alex, 2013, Algoritma Greedy, [online],
  (https://bertzzie.com/knowledge/analisis-algoritma/Greedy.html, diakses 02/12/2016)