Tugas 5 Algoritma

Algoritma BFS (Breadth-First Search) dalam Penjadwalan

Coba bayangin kamu seorang manajer produksi yang lagi pusing ngatur jadwal. Di depanmu cuma ada satu mesin andalan, tapi antreannya ada lima pekerjaan penting yang semuanya harus lewat mesin itu. Nah, tiap pekerjaan ini unik; ada yang cepat selesai tapi nggak begitu mendesak, ada juga yang butuh waktu lama tapi ini pesanan dari klien VVIP.

Tantangannya di sini bukan sekadar gimana caranya semua pekerjaan itu kelar, tapi gimana menyusun urutannya biar paling efisien. Maksudnya efisien itu, kita harus menekan 'biaya penalti' yang muncul setiap kali pekerjaan penting dibiarkan menunggu terlalu lama. Makin lama klien VVIP nunggu, makin besar 'denda' kita. Jadi, ini adalah kisah tentang mencari satu urutan emas di antara puluhan kemungkinan, sebuah jadwal sempurna yang bisa bikin semua berjalan lancar dengan biaya paling minimal.

Soal

Ilustrasi soal penjadwalan dengan durasi dan bobot.

Pseudocode

1.Mulai 2.Siapkan sebuah **Antrean (Queue)** dan masukkan sebuah jadwal kosong `[]` ke dalamnya. 3.Selama **Antrean** tidak kosong, ambil jadwal paling depan. 4.Untuk jadwal yang diambil, buat beberapa jadwal baru dengan menambahkan satu per satu pekerjaan yang belum ada di dalamnya. 5.Jika ada jadwal baru yang sudah lengkap (berisi 5 pekerjaan), hitung biayanya dan simpan jika itu yang terbaik. Jika belum lengkap, masukkan semua jadwal baru tersebut ke dalam **Antrean**. 6.Setelah **Antrean** kosong, tampilkan jadwal terbaik yang telah disimpan. 7.Selesai

Code Java

import java.util.Arrays;

public class PenjadwalanManual {

    public static void main(String[] args) {
        Object[][] daftarPekerjaan = {
            {"A", 3, 4, 3.0 / 4.0},
            {"B", 2, 2, 2.0 / 2.0},
            {"C", 5, 10, 5.0 / 10.0},
            {"D", 1, 1, 1.0 / 1.0},
            {"E", 4, 3, 4.0 / 3.0}
        };

        int n = daftarPekerjaan.length;
        // Proses sorting berdasarkan rasio bobot/durasi
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                double rasio1 = (double) daftarPekerjaan[j][3];
                double rasio2 = (double) daftarPekerjaan[j + 1][3];
                
                if (rasio1 > rasio2) {
                    Object[] temp = daftarPekerjaan[j];
                    daftarPekerjaan[j] = daftarPekerjaan[j + 1];
                    daftarPekerjaan[j + 1] = temp;
                }
            }
        }

        int biayaMinimum = 0;
        int waktuBerjalan = 0;

        System.out.println("Urutan pekerjaan paling optimal (berdasarkan rasio bobot/durasi):");

        for (Object[] pekerjaan : daftarPekerjaan) {
            String nama = (String) pekerjaan[0];
            int durasi = (int) pekerjaan[1];
            int bobot = (int) pekerjaan[2];

            waktuBerjalan += durasi;
            biayaMinimum += waktuBerjalan * bobot;
            
            System.out.print(nama + " -> ");
        }
        
        System.out.println("Selesai");
        System.out.println("Total biaya minimum: " + biayaMinimum);
    }
}

Output Program

Hasil eksekusi program Java di atas.