Job Scheduling

Bayangkan seorang freelancer dengan banyak tawaran proyek, masing-masing punya tenggat waktu (deadline) dan bayaran (profit). Ia hanya bisa mengerjakan satu proyek pada satu waktu dan setiap proyek memakan satu unit waktu. Tujuannya: pilih himpunan proyek yang bisa diselesaikan sebelum deadline-nya masing-masing, dengan total bayaran maksimum. Inilah job scheduling problem (kadang disebut job sequencing with deadlines). Algoritma greedy yang menyelesaikannya: sort by profit descending, lalu jadwalkan tiap job di slot terbaru yang masih kosong sebelum deadline-nya. Pada Chapter ini kita akan mengimplementasikannya dengan Disjoint Set Union (DSU) untuk menemukan slot kosong dalam waktu hampir konstan.

Aturan: Maksimalkan Profit dengan Constraint Deadline #

Diberikan n job dengan deadline[i] dan profit[i]. Setiap job membutuhkan satu unit waktu. Hanya satu job yang bisa dijalankan per unit waktu. Job i harus selesai paling lambat pada waktu deadline[i] (artinya dijadwalkan di slot t ≤ deadline[i]). Tujuan: maksimalkan total profit dari job yang berhasil dijadwalkan.

Strategi greedy:

1. Sort job by profit descending.
2. Inisialisasi array slot kosong dengan ukuran max(deadline).
3. Untuk setiap job: cari slot kosong terbesar t ≤ deadline[i]. Bila ada, isi slot dengan job; bila tidak ada, skip job.
4. Output total profit dan job yang dijadwalkan.

Greedy choice = profit tertinggi, jadwalkan selambat mungkin. Mengapa selambat mungkin? Karena slot awal lebih fleksibel — bisa dipakai job lain dengan deadline lebih ketat. Menunda pengisian slot awal sebanyak mungkin memaksimalkan peluang job lain dijadwalkan.

Mekanisme: DSU untuk Pencarian Slot Cepat #

Tanpa optimasi, mencari slot kosong terbesar ≤ d membutuhkan O(d) per job, sehingga total O(n · max_deadline). Dengan DSU, kita bisa lakukan dalam O(α(n)) per job.

Ide DSU: parent[t] menyimpan slot kosong terbesar berikutnya yang ≤ t. Setelah slot t diisi, parent[t] = t - 1 sehingga find(t) berikutnya akan melompat ke slot t-1. Path compression membuat operasi ini hampir konstan.

Implementasi C++ dengan DSU #

#include <iostream>
#include <vector>
#include <algorithm>

struct Job {
    int id;
    int deadline;
    int profit;
};

// DSU find dengan path compression
int findSlot(std::vector<int>& parent, int x) {
    if (parent[x] == x) return x;
    return parent[x] = findSlot(parent, parent[x]);
}

// Job scheduling — return (totalProfit, listOfJobIdScheduled)
std::pair<int, std::vector<int>>
jobScheduling(std::vector<Job> jobs) {
    // Sort by profit descending
    std::sort(jobs.begin(), jobs.end(),
              [](const Job& a, const Job& b) {
                  return a.profit > b.profit;
              });

    // Tentukan deadline maksimum untuk ukuran array slot
    int maxDeadline = 0;
    for (const auto& j : jobs) {
        maxDeadline = std::max(maxDeadline, j.deadline);
    }

    // DSU: parent[i] = slot kosong terbesar ≤ i
    std::vector<int> parent(maxDeadline + 1);
    for (int i = 0; i <= maxDeadline; ++i) parent[i] = i;

    int totalProfit = 0;
    std::vector<int> scheduled;

    for (const auto& j : jobs) {
        int slot = findSlot(parent, j.deadline);
        if (slot > 0) {
            parent[slot] = slot - 1; // tandai slot terpakai
            totalProfit += j.profit;
            scheduled.push_back(j.id);
        }
        // else: tidak ada slot kosong sebelum deadline, skip
    }
    return {totalProfit, scheduled};
}

int main() {
    std::vector<Job> jobs = {
        {1, 2, 100}, {2, 1, 19},  {3, 2, 27},
        {4, 1, 25},  {5, 3, 15}
    };

    auto [profit, scheduled] = jobScheduling(jobs);

    std::cout << "Job terjadwal (id): ";
    for (int id : scheduled) std::cout << id << ' ';
    std::cout << '\n';
    std::cout << "Jumlah job terjadwal: " << scheduled.size() << '\n';
    std::cout << "Total profit: " << profit << '\n';
    return 0;
}

Output yang Dihasilkan:

Job terjadwal (id): 1 3 5
Jumlah job terjadwal: 3
Total profit: 142

Bedah Kode Baris-per-Baris #

1. struct Job { int id; int deadline; int profit; };: rekam job dengan id, deadline, dan profit. id dipakai untuk identifikasi output.
2. std::sort(jobs.begin(), ..., [](...) { return a.profit > b.profit; }): sort by profit descending. Job dengan profit tertinggi dipertimbangkan lebih dulu — inilah greedy choice.
3. int maxDeadline = 0; for (const auto& j : jobs) maxDeadline = std::max(maxDeadline, j.deadline);: cari deadline maksimum untuk menentukan ukuran array slot. Slot maksimum yang dapat dipakai = maxDeadline.
4. std::vector<int> parent(maxDeadline + 1); for (int i = 0; i <= maxDeadline; ++i) parent[i] = i;: inisialisasi DSU. Awalnya setiap slot i menunjuk ke dirinya sendiri (kosong).
5. int findSlot(std::vector<int>& parent, int x): DSU find dengan path compression. Mencari slot kosong terbesar yang ≤ x. Path compression mempercepat query berikutnya.
6. return parent[x] = findSlot(parent, parent[x]);: path compression — setelah find, setiap node di sepanjang path langsung di-point ke root. Kompleksitas amortized O(α(n)).
7. int slot = findSlot(parent, j.deadline);: cari slot kosong terbesar yang ≤ deadline. Bila slot == 0, tidak ada slot tersedia.
8. if (slot > 0) { parent[slot] = slot - 1; totalProfit += j.profit; scheduled.push_back(j.id); }: bila ada slot kosong, isi slot dengan job, tandai parent[slot] = slot - 1 agar query berikutnya melompat ke slot bawah. Tambahkan profit dan id job.
9. Output 1 3 5: job 1 (profit 100, deadline 2) → slot 2; job 3 (profit 27, deadline 2) → slot 1; job 5 (profit 15, deadline 3) → slot 3. Job 4 dan 2 di-skip karena slot ≤ 1 sudah penuh. Total = 100 + 27 + 15 = 142.

Trace Step-by-Step #

Job setelah sort by profit desc: J1(100, d=2), J3(27, d=2), J4(25, d=1), J2(19, d=1), J5(15, d=3).

Hasil akhir: 3 job terjadwal di slot {1, 2, 3} dengan total profit 142.

Kompleksitas #

Kompleksitas waktu praktis O(n log n) karena α(n) ≤ 4 untuk n realistis (≤ 10^80).

Pembuktian Greedy-Choice Property (Ringkas) #

Misalkan S* adalah solusi optimal yang tidak memuat job g dengan profit tertinggi. Maka S* memuat job lain dengan profit lebih rendah di salah satu slot ≤ g.deadline. Karena g punya profit lebih tinggi dan bisa menempati slot yang sama (atau slot lain yang masih kosong), tukar job tersebut dengan g. Total profit naik atau sama — kontradiksi dengan asumsi S* optimal bila tidak memuat g.

Argumen serupa untuk greedy choice selanjutnya: setelah g dijadwalkan di slot terbesar yang ≤ g.deadline, sub-masalah adalah penjadwalan job tersisa pada slot kosong. Sub-masalah independen dan punya struktur identik — optimal substructure terpenuhi.

Variasi Job Scheduling #

Aplikasi Nyata #

• Freelance project selection: pilih proyek dengan bayaran tinggi yang bisa selesai sebelum tenggat.
• Compiler instruction scheduling: pilih instruksi dengan profit (priority) tinggi.
• OS task scheduling (real-time): deadline-aware scheduling untuk task hard real-time.
• Cloud spot instance bidding: pilih job dengan profit tinggi yang bisa selesai sebelum spot dicabut.
• Manufacturing: jadwal produksi batch dengan tenggat pengiriman.

Komparasi dengan Variasi Lain #

Ringkasan #

• Job scheduling: pilih himpunan job dengan total profit maksimum, tiap job satu unit waktu, harus selesai sebelum deadline.
• Greedy choice: job dengan profit tertinggi, jadwalkan di slot kosong terbesar yang ≤ deadline.
• DSU dengan path compression mempercepat pencarian slot ke O(α(n)) per job.
• Kompleksitas total O(n log n) — didominasi sort.
• Optimal karena greedy-choice property: tukar job profit rendah dengan profit tinggi pada slot sama → profit naik.
• Aplikasi: freelance selection, instruction scheduling, real-time OS.

Chapter berikutnya akan membahas Pembuktian Algoritma Greedy — teknik formal (exchange argument, greedy stays ahead, matroid theory) untuk menjamin greedy menghasilkan solusi optimal.