Job Scheduling with Deadlines là gì? Giải thích dễ hiểu kèm demo chọn công việc lợi nhuận cao nhất

Trong bài viết này, chúng ta sẽ:

• Hiểu mô hình bài toán Job Scheduling with Deadlines.
• Nắm được chiến lược greedy: ưu tiên công việc có lợi nhuận cao nhất.
• Thấy cách xếp công việc vào các slot thời gian trước deadline.
• Xem demo trực quan bằng JavaScript với log từng bước.

Mô tả bài toán Job Scheduling with Deadlines

Cho một tập các job, mỗi job có:

• id: mã công việc (A, B, C…).
• deadline: hạn cuối (slot thời gian, ví dụ 1, 2, 3…).
• profit: lợi nhuận nếu ta hoàn thành job này đúng hạn.

Giả sử:

• Mỗi job mất đúng 1 đơn vị thời gian để hoàn thành.
• Tại mỗi slot thời gian chỉ được làm tối đa 1 job.
• Job phải được xếp vào slot có chỉ số ≤ deadline của nó (không được trễ).

Mục tiêu: chọn một tập con các job và slot cho từng job sao cho:

• Không có hai job trùng slot thời gian.
• Không job nào bị vượt deadline.
• Tổng lợi nhuận là lớn nhất.

Chiến lược greedy: ưu tiên lợi nhuận cao nhất

Ý tưởng giải greedy nổi tiếng cho bài toán này:

1. Sắp xếp các job theo lợi nhuận giảm dần (job nào profit lớn đứng trước).
2. Khởi tạo một mảng slot thời gian, ví dụ từ 1 đến maxDeadline, ban đầu trống.
3. Duyệt từng job theo thứ tự đã sắp xếp:
   • Với mỗi job, tìm slot trống muộn nhất mà ≤ deadline của job.
   • Nếu tìm được slot như vậy, xếp job vào slot đó.
   • Nếu không còn slot trống nào trước deadline, bỏ qua job đó.

Trực giác: job lợi nhuận cao nên được ưu tiên, và ta cố gắng đặt nó vào slot muộn nhất có thể trước deadline để “nhường chỗ” các slot sớm hơn cho những job khác cũng có lợi nhuận cao.

Ví dụ nhanh

Giả sử ta có các job:

• A: deadline 2, profit 60
• B: deadline 1, profit 100
• C: deadline 3, profit 20
• D: deadline 2, profit 40
• E: deadline 1, profit 20
• F: deadline 3, profit 80

Sắp xếp theo lợi nhuận giảm dần: B (100), F (80), A (60), D (40), C (20), E (20).

Các slot thời gian ta có: 1, 2, 3 (vì max deadline = 3).

• B: deadline 1 → slot 1 còn trống → xếp B vào slot 1.
• F: deadline 3 → slot 3 còn trống → xếp F vào slot 3.
• A: deadline 2 → slot 2 còn trống → xếp A vào slot 2.
• D, C, E: không còn slot trống trước deadline → bỏ qua.

Kết quả: slot 1: B, slot 2: A, slot 3: F. Tổng profit = 100 + 60 + 80 = 240.

Mô hình demo: chọn job và slot thời gian

Trong demo dưới đây:

• Danh sách job gồm: A, B, C, D, E, F với deadline và profit khác nhau.
• Các slot thời gian hiển thị là 1, 2, 3, 4 (giả sử max deadline = 4).
• Khi nhấn “Chạy thuật toán”:
  • Các job được sắp xếp theo profit giảm dần.
  • Thuật toán lần lượt tìm slot thích hợp cho từng job.
  • Slot được lấp bởi job nào sẽ được tô màu xanh; job không được xếp sẽ hiển thị là “bỏ qua”.
  • Log bên dưới giải thích từng bước.

Demo Job Scheduling with Deadlines bằng JavaScript

Giải thích ngắn gọn đoạn code Job Scheduling

1. Cấu trúc dữ liệu các job

Mỗi job gồm id, deadline (slot tối đa), profit:

var jobs = [
    { id: "A", deadline: 2, profit: 60 },
    { id: "B", deadline: 1, profit: 100 },
    { id: "C", deadline: 3, profit: 20 },
    { id: "D", deadline: 2, profit: 40 },
    { id: "E", deadline: 1, profit: 20 },
    { id: "F", deadline: 3, profit: 80 }
];

Ta cũng xác định số lượng slot tối đa bằng maxDeadline:

var maxDeadline = jobs.reduce(function(max, job) {
    return Math.max(max, job.deadline);
}, 0);

2. Thuật toán greedy sắp xếp job theo profit giảm dần

Hàm chính để chọn job và slot:

function scheduleJobs(jobs) {
    var sorted = jobs.slice().sort(function(a, b) {
        return b.profit - a.profit; // sắp xếp lợi nhuận giảm dần
    });

    var maxDeadline = sorted.reduce(function(max, job) {
        return Math.max(max, job.deadline);
    }, 0);

    var slots = new Array(maxDeadline + 1).fill(null);

    var totalProfit = 0;
    var selectedJobs = [];

    for (var i = 0; i < sorted.length; i++) {
        var job = sorted[i];
        for (var t = job.deadline; t >= 1; t--) {
            if (slots[t] === null) {
                slots[t] = job;
                selectedJobs.push(job);
                totalProfit += job.profit;
                break;
            }
        }
    }

    return {
        sorted: sorted,
        slots: slots,
        selectedJobs: selectedJobs,
        totalProfit: totalProfit
    };
}

Ý tưởng:

• Duyệt job theo thứ tự lợi nhuận cao nhất.
• Với mỗi job, tìm slot trống từ deadline lùi về 1.
• Nếu tìm được slot, xếp job vào và cộng lợi nhuận.
• Nếu không tìm được, bỏ qua job đó.

3. Hiển thị job và slot trên giao diện

Danh sách job ban đầu hiển thị dưới dạng “bảng” đơn giản với id, deadline, profit. Sau khi chạy thuật toán:

• Job được chọn sẽ gán class job-sched-job--selected.
• Job không được xếp sẽ gán class job-sched-job--skipped.

Các slot được hiển thị theo dạng hộp, gắn với job tương ứng:

function renderSlots(maxDeadline, slots) {
    // Tạo các ô slot 1, 2, 3, ..., maxDeadline
    // Nếu slots[t] có job, hiển thị id job và profit
}

Trong log, ta in ra từng bước:

• Xem xét job nào (id, deadline, profit bao nhiêu).
• Cố gắng đặt vào slot nào.
• Job đó được xếp thành công hay bị bỏ qua.

Khi nào nên dùng Job Scheduling with Deadlines?

• Khi có một nguồn lực duy nhất (máy, phòng, nhân sự) và các job mất cùng một đơn vị thời gian.
• Khi mỗi job có deadline và lợi nhuận (hoặc mức độ ưu tiên).
• Khi mục tiêu là tối đa hóa tổng lợi nhuận/lợi ích mà không vi phạm deadline.

Từ đoạn code demo, bạn có thể mở rộng:

• Cho phép người dùng nhập thêm job mới, sửa deadline/profit trực tiếp trên giao diện.
• Hiển thị thêm tổng lợi nhuận tối đa, so sánh với các chiến lược “tham lam” khác.
• Kết hợp với hệ thống lịch thực tế (cron, batch job, lịch marketing) để gợi ý thứ tự ưu tiên.