Tugas 3 algoritma

Pemecahan Kasus

Di kasus ini, kita punya 5 pekerjaan yang harus diselesaikan secara berurutan di satu mesin. Setiap pekerjaan punya durasi (jam) dan bobot penting. Tujuannya adalah mencari urutan kerja supaya total 

$\sum (waktu\ selesai \times bobot)$

Kalau dikerjakan sembarangan, hasilnya bisa lebih besar. Jadi kita pakai strategi algoritma greedy. Algoritma ini menyarankan supaya kita mengurutkan pekerjaan berdasarkan rasio bobot per durasi (w/p). Alasannya sederhana: semakin besar bobot dibandingkan waktu, semakin penting pekerjaan itu untuk dikerjakan lebih cepat.

Langkah-langkah

1. Bayangin kita lagi dapat tugas: ada 5 pekerjaan yang harus diselesaikan di satu mesin, dan semuanya harus dikerjakan satu per satu. Setiap pekerjaan punya dua informasi penting:

   • Durasi (p): berapa lama pekerjaan itu butuh waktu,

   • Bobot (w): seberapa penting pekerjaan itu.

   Nah, tujuan kita adalah menyusun urutan pengerjaan supaya total $\sum (waktu\ selesai \times bobot)$ sekecil mungkin.

   Kamu mungkin mikir: “Enaknya dikerjain yang cepat dulu biar selesai lebih cepat?” 
   Eh ternyata tidak sesimpel itu. Bisa jadi ada pekerjaan yang durasinya agak lama tapi bobotnya penting banget, jadi justru lebih baik dikerjakan duluan.

   Langkah 1: Cari Rasio w/p

   Strategi greedy menyarankan kita hitung rasio bobot per durasi (w/p). Rasio ini kayak skor prioritas: makin tinggi nilainya, makin penting pekerjaan itu dikerjakan lebih dulu.

   Yuk kita hitung:

   • C: $w=10, p=5 → w/p = 2.0$

   • A: $w=4, p=3 → w/p ≈ 1.33$

   • B: $w=2, p=2 → w/p = 1.0$

   • D: $w=1, p=1 → w/p = 1.0$

   • E: $w=3, p=4 → w/p = 0.75$

   Kelihatan kan? Pekerjaan C punya rasio paling tinggi, jadi dia harus dikerjakan dulu. Sedangkan E paling kecil, jadi ditaruh di belakang.

   Langkah 2: Susun Urutan

   Kalau diurutkan dari rasio terbesar ke terkecil, jadinya:
   C → A → B → D → E

   Langkah 3: Hitung Waktu Selesai dan Kontribusi

   Sekarang kita simulasikan kapan tiap pekerjaan selesai dan berapa kontribusinya:

   1. C: selesai di waktu ke-5 → kontribusi $= 5 × 10 = 50$

   2. A: selesai di waktu ke-8 → kontribusi $= 8 × 4 = 32$

   3. B: selesai di waktu ke-10 → kontribusi $= 10 × 2 = 20$

   4. D: selesai di waktu ke-11 → kontribusi $= 11 × 1 = 11$

   5. E: selesai di waktu ke-15 → kontribusi $= 15 × 3 = 45$

   Total semuanya = 158.

   
   

   Dengan algoritma greedy, urutan optimalnya adalah C → A → B → D → E, dan total biaya minimum = 158.

coding:

import java.util.*;

class Job {
    String name;
    int duration;
    int weight;
    double ratio;

    public Job(String name, int duration, int weight) {
        this.name = name;
        this.duration = duration;
        this.weight = weight;
        this.ratio = (double) weight / duration;
    }
}
public class GreedyScheduling {
    public static void main(String[] args) {
        // Data pekerjaan
        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)
        };

        // Urutkan berdasarkan rasio w/p (descending)
        Arrays.sort(jobs, (j1, j2) -> Double.compare(j2.ratio, j1.ratio));

        int currentTime = 0;
        int total = 0;

        System.out.println("Urutan pekerjaan (berdasarkan greedy):");
        for (Job job : jobs) {
            currentTime += job.duration; // waktu selesai pekerjaan
            int contribution = currentTime * job.weight;
            total += contribution;
            System.out.println(job.name +
                    " (durasi " + job.duration + " jam, bobot " + job.weight +
                    ") selesai di " + currentTime +
                    " → kontribusi = " + contribution);
        }

        System.out.println("Total (Σ waktu_selesai × bobot) = " + total);
    }
}

 output:

Urutan pekerjaan (berdasarkan greedy):

C (durasi 5 jam, bobot 10) selesai di 5 → kontribusi = 50

A (durasi 3 jam, bobot 4) selesai di 8 → kontribusi = 32

B (durasi 2 jam, bobot 2) selesai di 10 → kontribusi = 20

D (durasi 1 jam, bobot 1) selesai di 11 → kontribusi = 11

E (durasi 4 jam, bobot 3) selesai di 15 → kontribusi = 45

Total (Σ waktu_selesai × bobot) = 158

Process finished with exit code 0