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.
