Tugas 2 Algoritma

Apa itu Algoritma Brute Force?

Algoritma brute force adalah cara penyelesaian masalah dengan mencoba semua kemungkinan solusi yang ada, kemudian memilih yang terbaik. Sederhananya, brute force itu seperti “cek satu per satu” tanpa trik khusus.

Kelebihan: Hasilnya pasti optimal karena semua kemungkinan dihitung.
Kekurangan: Sangat lambat jika jumlah data besar, karena banyaknya kombinasi akan meledak sangat cepat.

Penjelasan Soal: Penjadwalan Kerja

Dalam soal ini kita punya lima pekerjaan, masing-masing dengan durasi pengerjaan dan bobot kepentingan. Semua pekerjaan dikerjakan secara berurutan pada satu mesin, jadi tidak bisa paralel. Tujuannya adalah mencari urutan pekerjaan supaya jumlah total (waktu selesai × bobot) menjadi sekecil mungkin.

Berikut adalah data pekerjaannya:

• Pekerjaan A: Durasi 3, Bobot 4
• Pekerjaan B: Durasi 2, Bobot 2
• Pekerjaan C: Durasi 5, Bobot 10
• Pekerjaan D: Durasi 1, Bobot 1
• Pekerjaan E: Durasi 4, Bobot 3

Pseudocode Algoritma

MULAI
  // 1. Siapkan data
  data nama = {"A", "B", "C", "D", "E"}
  data durasi = {3, 2, 5, 1, 4}
  data bobot = {4, 2, 10, 1, 3}

  // 2. Siapkan variabel untuk menyimpan hasil terbaik
  biayaTerbaik = Tak Terhingga
  urutanTerbaik = ""

  // 3. Coba semua 120 kemungkinan urutan dengan 5 loop
  UNTUK setiap pekerjaan p1 DARI 0 SAMPAI 4:
    UNTUK setiap pekerjaan p2 DARI 0 SAMPAI 4:
      ... (lanjutkan untuk p3, p4, p5)
      
      // Pastikan tidak ada pekerjaan yang sama dalam satu urutan
      JIKA ada pekerjaan duplikat, LANJUT

      // Jika urutan valid, hitung biayanya
      biayaSekarang = hitung_total_biaya(urutan_p1_p2_p3_p4_p5)

      // Bandingkan dengan juara bertahan
      JIKA biayaSekarang < biayaTerbaik:
        biayaTerbaik = biayaSekarang
        urutanTerbaik = urutan_nama_p1_p2_p3_p4_p5
      AKHIR JIKA
    ...
  AKHIR UNTUK

  // 4. Tampilkan hasilnya
  CETAK urutanTerbaik, biayaTerbaik
SELESAI

Implementasi Kode Program (Java)

public class SchedulingBruteForceLoop {
    public static void main(String[] args) {
        String[] nama = {"A", "B", "C", "D", "E"};
        int[] durasi = {3, 2, 5, 1, 4};
        int[] bobot  = {4, 2, 10, 1, 3};

        int bestCost = Integer.MAX_VALUE;
        String bestOrder = "";

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (j == i) continue;
                for (int k = 0; k < 5; k++) {
                    if (k == i || k == j) continue;
                    for (int l = 0; l < 5; l++) {
                        if (l == i || l == j || l == k) continue;
                        for (int m = 0; m < 5; m++) {
                            if (m == i || m == j || m == k || m == l) continue;

                            int[] urut = {i, j, k, l, m};

                            // hitung total cost
                            int waktu = 0, total = 0;
                            for (int idx : urut) {
                                waktu += durasi[idx];
                                total += waktu * bobot[idx];
                            }

                            if (total < bestCost) {
                                bestCost = total;
                                bestOrder = nama[i] + " " + nama[j] + " " + nama[k] + " " + nama[l] + " " + nama[m];
                            }
                        }
                    }
                }
            }
        }
        System.out.println("Urutan terbaik: " + bestOrder);
        System.out.println("Total (waktu × bobot) = " + bestCost);
    }
}

Solusi Akhir

Pada algoritma brute force, kita perlu mencoba semua kemungkinan urutan pekerjaan (total 5! = 120 urutan). Untuk tiap urutan, kita menghitung waktu selesai kumulatif lalu mengalikan dengan bobot, dan hasilnya dijumlahkan. Dari semua hasil itu kita pilih yang paling kecil.

Karena jumlah pekerjaan hanya lima, brute force masih memungkinkan. Jika kode program di atas dijalankan, hasil optimal yang didapatkan adalah:

• Urutan Terbaik: C → A → B → D → E
• Total Biaya Minimum: 158