Jadi kasusnya kita punya 5 pekerjaan A sampai E, masing-masing punya lama pengerjaan dan bobot penting. Karena mesinnya cuma bisa ngerjain satu per satu, kita harus nyusun urutan supaya nilai total (waktu selesai × bobot) sekecil mungkin.
Pada kasus ini terdapat lima pekerjaan (A, B, C, D, E) yang harus dikerjakan secara berurutan oleh satu mesin. Setiap pekerjaan memiliki durasi dan bobots ehingga tujuan dari penyusunan jadwal adalah meminimalkan jumlah total dari waktu selesai × bobot.
Algoritma yang digunakan di sini adalah Breadth-First Search (BFS). BFS itu menelusuri semua kemungkinan urutan pekerjaan dengan cara membangun pohon secara level demi level. Pada level pertama kita memilih pekerjaan awal, kemudian pada level kedua menambahkan pekerjaan berikutnya, dan seterusnya hingga terbentuk urutan yang lengkap. Setiap kali BFS mencapai urutan lengkap, total waktu selesai × bobot dihitung. Dari semua kemungkinan urutan, dipilih yang memberikan nilai minimum.
Karena jumlah pekerjaan hanya lima, maka total kemungkinan urutan adalah 5! = 120, yang masih dapat dieksplorasi penuh oleh BFS.Hasil perhitungan menunjukkan bahwa urutan yang optimal adalah C – A – B – D – E. Dengan urutan tersebut, total nilai yang diperoleh adalah 158, yang merupakan hasil paling kecil dibanding urutan lain.Dengan demikian, penerapan algoritma BFS dalam kasus ini berhasil menemukan solusi optimal, yaitu penjadwalan dengan urutan C, A, B, D, E.
pseudocode:Algorithm BFS_Scheduling(Pekerjaan)
Input: daftar pekerjaan dengan durasi dan bobot
Output: urutan optimal dan nilai minimum
1. total_min ← ∞
2. urutan_terbaik ← kosong
3. Buat queue Q
4. Masukkan [] (urutan kosong) ke Q
5. while Q tidak kosong do
cur ← dequeue(Q)
if panjang(cur) = jumlah pekerjaan then
hitung total_cost(cur):
waktu ← 0
total ← 0
untuk setiap job j dalam cur:
waktu ← waktu + durasi(j)
total ← total + (waktu × bobot(j))
if total < total_min then
total_min ← total
urutan_terbaik ← cur
else
untuk setiap job x yang belum ada di cur:
enqueue(Q, cur + [x])
6. return urutan_terbaik, total_min
implementasi di java:import java.util.*;
class Job {
String name;
int durasi;
int bobot;
Job(String name, int durasi, int bobot) {
this.name = name;
this.durasi = durasi;
this.bobot = bobot;
}
}
public class BFSScheduling {
public static void main(String[] args) {
Job[] jobs = {
new Job("A", 3, 4),
new Job("B", 2, 2),
new Job("C", 5, 10),
new Job("D", 1, 1),
new Job("E", 4, 3)
};
// BFS queue
Queue<List<Job>> queue = new LinkedList<>();
queue.add(new ArrayList<>()); // mulai dari urutan kosong
int totalMin = Integer.MAX_VALUE;
List<Job> bestOrder = null;
while (!queue.isEmpty()) {
List<Job> current = queue.poll();
if (current.size() == jobs.length) {
int cost = hitungTotal(current);
if (cost < totalMin) {
totalMin = cost;
bestOrder = current;
}
} else {
for (Job j : jobs) {
if (!current.contains(j)) {
List<Job> next = new ArrayList<>(current);
next.add(j);
queue.add(next);
}
}
}
}
System.out.println("Urutan terbaik:");
for (Job j : bestOrder) {
System.out.print(j.name + " ");
}
System.out.println("\nTotal minimum = " + totalMin);
}
// fungsi untuk menghitung total waktu × bobot
static int hitungTotal(List<Job> urutan) {
int waktu = 0;
int total = 0;
for (Job j : urutan) {
waktu += j.durasi;
total += waktu * j.bobot;
}
return total;
}
}
output:
Urutan terbaik:
C A B D E
Total minimum = 158
Komentar
Posting Komentar