Penjadwalan Tugas

Sistem operasi menjadwalkan ratusan proses per detik, sistem CI/CD mengatur urutan build-deploy-test, dan kanban board tim engineering menampilkan urutan tugas berdasarkan dependensi. Penyatuan dua konsep DSA — topological sort untuk dependensi dan priority queue untuk prioritas — menjadi fondasi hampir semua sistem scheduler modern. Pada Chapter ini kita akan membangun task scheduler yang menghormati dependency graph sekaligus mengurutkan tugas siap dieksekusi berdasarkan prioritas. Kombinasi Kahn algorithm dengan max-heap ini secara matematis menjamin urutan valid (dependency terpenuhi) sekaligus optimal (task prioritas tinggi dieksekusi lebih dahulu ketika banyak task siap).

Konsep: Dependency Graph dan Prioritas #

Tugas dengan dependensi membentuk DAG (Directed Acyclic Graph). Setiap task adalah vertex; edge A → B berarti A harus selesai sebelum B mulai. Tanpa dependensi, urutan eksekusi bebas — di sinilah prioritas berperan: bila dua atau lebih task siap (semua dependensinya selesai), pilih yang prioritasnya paling tinggi.

Topological Sort dengan Kahn Algorithm: Aturan dan Mekanisme #

Aturan #

Kahn algorithm bekerja dengan prinsip: task dengan in-degree 0 (tidak punya dependensi tersisa) siap dieksekusi. Setelah task dieksekusi, semua dependennya berkurang in-degree-nya; bila mencapai 0, dependen itu juga siap. Algoritma berhenti ketika semua task terproses — bila ada sisa, graph mengandung cycle dan penjadwalan tidak mungkin.

Mekanisme di Balik Layar #

Tanpa prioritas, Kahn menggunakan queue biasa (FIFO) untuk ready set. Dengan prioritas, kita ganti ke max-heap berbasis priority_queue. Heap selalu mengembalikan task dengan prioritas tertinggi dalam O(log n) — efisien dibanding sorting ulang seluruh ready set setelah iterasi.

Pseudocode Kahn + Priority:

1. Hitung in_degree[v] untuk semua vertex.
2. Masukkan semua vertex dengan in_degree == 0 ke priority_queue.
3. Selama queue tidak kosong:
   • Pop task terprioritas-tinggi → tambahkan ke urutan eksekusi.
   • Untuk setiap dependen next, dekrementasi in_degree[next].
   • Bila in_degree[next] == 0, push ke queue.

Kompleksitas #

Faktor log V muncul karena setiap push/pop dari priority queue adalah O(log V). Untuk graph tanpa prioritas (queue FIFO), kompleksitas turun ke O(V + E).

Kode: Task Scheduler dengan Prioritas #

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>
#include <iomanip>
using namespace std;

struct Task {
    int id;
    string name;
    int priority;       // lebih tinggi = lebih prioritas
    int duration_min;
};

class TaskScheduler {
public:
    void addTask(const Task& t) {
        tasks_[t.id] = t;
    }

    // Tambah dependency: t2 tergantung pada t1 (t1 harus selesai dulu)
    void addDependency(int t1, int t2) {
        adj_[t1].push_back(t2);
        in_degree_[t2]++;
    }

    // Jadwalkan dengan topological sort + priority queue
    vector<int> schedule() {
        auto cmp = [this](int a, int b) {
            if (tasks_[a].priority != tasks_[b].priority)
                return tasks_[a].priority < tasks_[b].priority;
            return a > b;  // tie-break: id kecil lebih dulu
        };
        priority_queue<int, vector<int>, decltype(cmp)> ready(cmp);

        // Masukkan task dengan in_degree 0
        for (const auto& kv : tasks_) {
            int id = kv.first;
            if (in_degree_[id] == 0) ready.push(id);
        }

        vector<int> order;
        int total_time = 0;

        while (!ready.empty()) {
            int id = ready.top(); ready.pop();
            order.push_back(id);
            total_time += tasks_[id].duration_min;

            // Untuk setiap task yang tergantung pada id
            for (int next : adj_[id]) {
                if (--in_degree_[next] == 0) ready.push(next);
            }
        }
        total_time_ = total_time;
        return order;
    }

    int totalTime() const { return total_time_; }
    const Task& get(int id) const { return tasks_.at(id); }

private:
    unordered_map<int, Task> tasks_;
    unordered_map<int, vector<int>> adj_;
    unordered_map<int, int> in_degree_;
    int total_time_ = 0;
};

int main() {
    TaskScheduler sched;

    sched.addTask({1, "Setup Environment", 3, 30});
    sched.addTask({2, "Design Database",    4, 60});
    sched.addTask({3, "Implement API",      5, 120});
    sched.addTask({4, "Write Tests",        2, 45});
    sched.addTask({5, "Deploy",             1, 20});
    sched.addTask({6, "Documentation",      2, 30});

    // Dependency: t1 -> t2 berarti t1 harus selesai sebelum t2 mulai
    sched.addDependency(1, 2);
    sched.addDependency(2, 3);
    sched.addDependency(3, 4);
    sched.addDependency(3, 5);
    sched.addDependency(4, 5);
    sched.addDependency(1, 6);

    auto order = sched.schedule();

    cout << "=== Penjadwalan Tugas (Topo + Priority) ===\n\n";
    cout << left << setw(6) << "Urut" << setw(22) << "Task"
         << setw(12) << "Prioritas" << setw(10) << "Durasi" << "\n";
    cout << "-----|---------------------|-----------|---------\n";

    int cum = 0;
    for (size_t i = 0; i < order.size(); ++i) {
        const Task& t = sched.get(order[i]);
        cum += t.duration_min;
        cout << left << setw(6) << (i+1)
             << setw(22) << t.name
             << setw(12) << t.priority
             << t.duration_min << " min (selesai t=" << cum << ")\n";
    }

    cout << "\nTotal durasi kritis: " << sched.totalTime() << " menit\n";

    if ((int)order.size() != 6) {
        cout << "WARNING: cycle terdeteksi, beberapa task tidak terjadwal.\n";
    }
    return 0;
}

Output yang Dihasilkan:

=== Penjadwalan Tugas (Topo + Priority) ===

Urut  Task                  Prioritas Durasi
-----|---------------------|-----------|---------
1     Setup Environment     3         30 min (selesai t=30)
2     Design Database       4         60 min (selesai t=90)
3     Implement API         5         120 min (selesai t=210)
4     Write Tests           2         45 min (selesai t=255)
5     Documentation         2         30 min (selesai t=285)
6     Deploy                1         20 min (selesai t=305)

Total durasi kritis: 305 menit

Bedah Kode Baris-per-Baris #

1. struct Task { int id; string name; int priority; int duration_min; }: setiap task membawa metadata. priority menentukan urutan antar task yang siap; duration_min dipakai untuk estimasi waktu selesai.
2. unordered_map<int, Task> tasks_;: lookup task by ID dalam O(1) rata-rata. Penggunaan hash map (bukan array) mengizinkan ID sparse — task 1, 7, 100 tanpa mengalokasikan slot kosong.
3. adj_[t1].push_back(t2); in_degree_[t2]++;: daftarkan dependensi. Adjacency list adj_[t1] berisi task yang menunggu t1; in_degree menghitung berapa dependensi yang belum selesai untuk setiap task.
4. auto cmp = [this](int a, int b) { ... }: comparator untuk priority queue. Lambda menangkap this agar dapat mengakses tasks_ untuk membaca prioritas. Comparator mengembalikan true jika a harus diletakkan di bawah b dalam heap — karena priority_queue adalah max-heap, kita return true ketika prioritas a lebih kecil.
5. priority_queue<int, vector<int>, decltype(cmp)> ready(cmp);: priority queue custom dengan comparator lambda. Vector sebagai underlying container; tipe comparator diturunkan via decltype.
6. for (const auto& kv : tasks_) { if (in_degree_[id] == 0) ready.push(id); }: inisialisasi. Semua task tanpa dependensi dimasukkan ke ready set sekaligus — urutan keluar ditentukan oleh prioritas.
7. int id = ready.top(); ready.pop();: ekstrak task prioritas tertinggi. Operasi O(log n) karena heap merestuktur diri setelah pop.
8. for (int next : adj_[id]) { if (--in_degree_[next] == 0) ready.push(next); }: dekrementasi in-degree dependen. Bila mencapai 0, dependen siap dieksekusi dan masuk ready queue.
9. if ((int)order.size() != 6): deteksi cycle. Bila urutan tidak mencakup seluruh task, berarti ada cycle yang membuat beberapa task tidak pernah mencapai in-degree 0.

Strategi Penjadwalan Lanjutan #

Deteksi Cycle dan Recovery #

Bila scheduler mendeteksi cycle (urutan tidak mencakup seluruh task), beberapa tindakan bisa diambil:

Ringkasan #

• Topological sort menjamin urutan eksekusi yang menghormati dependensi DAG.
• Priority queue memilih task prioritas tertinggi di antara yang siap dieksekusi.
• Kahn algorithm + max-heap menghasilkan kompleksitas O((V+E) log V).
• Deteksi cycle: bila urutan tidak mencakup seluruh task, ada dependensi siklik.
• Pada sistem produksi, tambahkan critical path analysis untuk meminimalkan makespan.
• Varian populer: FIFO (fairness), aging (anti-starvation), round robin (interaktif).