Thuật toán Johnson và Bài toán lập lịch trên hai máy

Mục lục

1. Bài toán lập lịch trên hai máy

LẬP LỊCH TRÊN HAI MÁY (CPBTWOMACHINE)
Đây là một bài tập luyện tập trong sách Competitive Programming Basic 2024 của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn
Đề bài
Một sản phẩm gồm \(𝑁\) chi tiết, mỗi chi tiết phải gia công lần lượt trên hai máy \(𝐴\) và \(𝐵\) (\(𝐴\) trước, \(𝐵\) sau).
Thời gian thực hiện chi tiết \(𝑖\) trên máy \(𝐴\) là \(𝐴_𝑖\), trên máy \(𝐵\) là \(𝐵_𝑖\)
Yêu cầu: Hãy lập lịch trên hai máy để hoàn thành tất cả sản phẩm với thời gian ít nhất.
INPUT

Dòng đầu là số nguyên dương \(𝑁\) \((𝑁 \le 1000);\)
\(𝑁\) dòng tiếp theo mỗi dòng chứa hai số \(𝐴_𝑖\) và \(𝐵_𝑖\) \(( 𝐴_𝑖, 𝐵_𝑖 \le 30000)\).

OUTPUT
Ghi ra thời gian hoàn thành sản phẩm sớm nhất

INPUT

OUTPUT

2. Thuật toán Johnson

Thuật toán Johnson cung cấp một cách tối ưu để giải quyết bài toán này. Các bước của thuật toán như sau:
Bước 1: Chia công việc thành hai nhóm

Nhóm 1: Các công việc có \(A[i] \le B[i]\).
Nhóm 2: Các công việc có \(A[i] > B[i]\).

Bước 2: Sắp xếp công việc trong từng nhóm

Nhóm 1: Sắp xếp công việc theo thứ tự tăng dần của \(A[i]\).
Nhóm 2: Sắp xếp công việc theo thứ tự giảm dần của \(B[i]\).

Bước 3: Ghép hai nhóm lại

Nhóm 1 được xếp trước, sau đó đến nhóm 2.
Tính tổng thời gian hoàn thành sản phẩm theo thứ tự sắp xếp trên. Bằng cách sắp xếp như vậy, bạn có thể đảm bảo tổng thời gian xử lý là nhỏ nhất.

Áp dụng vào ví dụ của đề bài

Bước 1: Chia công việc thành hai nhóm

Nhóm 1: Các công việc \(1, 4\) có thời gian lần lượt là \( (3,3), (5,7). \)
Nhóm 2: Các công việc \(2, 3, 5\) có thời gian lần lượt là \( (4,3), (6,2), (6,3) \).

Bước 2: Sắp xếp công việc trong từng nhóm

Nhóm 1: Sau khi sắp xếp, các công việc theo thứ tự: \(1, 4\).
Nhóm 2: Sau khi sắp xếp, các công việc theo thứ tự: \(5, 2, 3\).

Bước 3: Ghép hai nhóm lại

Thứ tự thực hiện cùa các công việc lần lượt là: \(1, 4, 5, 2, 3\)
Tính tổng thời gian hoàn thành \(N\) công việc theo thứ tự sắp xếp trên:
Sử dụng sơ đồ Gantt, ta có trật tự các công việc và thời gian hoàn thành các công việc như sau:
- Theo kết quả trên sơ đồ ta thấy dòng thời gian ngắn nhất để hoàn thành cả \(5\) chi tiết trên \(2\) máy theo thuật toán Johnson là \(26\) đơn vị thời gian.
- Với máy \(A\) cho dù là trật tự bố trí nào thời gian cũng là như nhau và trong ví dụ trên là \(24\), vấn đề là ở máy \(B\).
- Ban đầu chi tiết \(1\) được đưa vào máy \(A\) để thực hiện. Máy \(B\) phải chờ chi tiết \(1\) hoàn thiện xong bên máy \(A\) mới được thực hiện tiếp.
- Tại thời điểm \(4\) máy \(B\) bắt đầu thực hiện làm chi tiết \(1\). Cùng lúc đó máy \(A\) tiếp tục thực hiện chi tiết \(4\).
- Máy \(B\) thực hiện xong chi tiết \(1\) ở thời điểm \(6\). Máy \(B\) phải đợi đến thời điểm \(9\) mới có thể tiếp tục thực hiện chi tiết \(4\).
- Cứ như vậy, cho đến khi thực hiện xong cả \(5\) công việc.

3. Code bài toán lập lịch trên hai máy

Code mẫu C++

#include <bits/stdc++.h>

    using namespace std;

    // Hàm so sánh để sắp xếp các cặp giá trị theo quy tắc của thuật toán Johnson
    bool cmp(pair<int,int> A,pair<int,int> B) {
        return A.second > B.second;
    }
    
    int main() {
        int n;
        cin >> n;
    
        vector<pair<int, int>> a;
        vector<pair<int, int>> b;
    
        for(int i = 0; i < n; i++) {
            int ai, bi;
            cin >> ai >> bi;
            if(ai <= bi) a.push_back({ai, bi});
            else b.push_back({ai, bi});
        }
    
        // Sắp xếp các công việc theo yêu cầu của thuật toán Johnson
        sort(a.begin(), a.end());
        sort(b.begin(), b.end(), cmp);
    
        // Kết hợp lại thành một lịch trình
        vector<pair<int, int>> schedule = a;
        for(auto &p : b) schedule.push_back(p);
    
        int total_time = 0;
        int time_a = 0, time_b = 0;
    
        // Tính toán thời gian hoàn thành sản phẩm
        for(auto &job : schedule) {
            time_a += job.first;
            time_b = max(time_b, time_a) + job.second;
        }
    
        total_time = time_b;
    
        cout << total_time << endl;
    
        return 0;
    }

Code mẫu Python

def cmp(pair):
        return pair[1]

        def johnson_schedule(n, jobs):
            a = []
            b = []
        
            for job in jobs:
                ai, bi = job
                if ai <= bi:
                    a.append((ai, bi))
                else:
                    b.append((ai, bi))
        
            # Sắp xếp các công việc theo yêu cầu của thuật toán Johnson
            a.sort()
            b.sort(key=cmp, reverse=True)
        
            # Kết hợp lại thành một lịch trình
            schedule = a + b
        
            total_time = 0
            time_a = 0
            time_b = 0
        
            # Tính toán thời gian hoàn thành sản phẩm
            for job in schedule:
                time_a += job[0]
                time_b = max(time_b, time_a) + job[1]
        
            total_time = time_b
        
            return total_time
        
        # Đọc dữ liệu đầu vào
        n = int(input())
        jobs = [tuple(map(int, input().split())) for _ in range(n)]
        
        # Thực hiện thuật toán Johnson
        result = johnson_schedule(n, jobs)
        print(result)

4. Kết luận

Thuật toán Johnson đúng là dựa vào nguyên tắc Shortest Processing Time (SPT) để quyết định thứ tự ưu tiên cho các công việc.
Tuy nhiên cũng cần lưu ý rằng đây là bài toán lập lịch trên hai máy do đó không phải lúc nào cũng đưa ra kết quả tối ưu hay nói cách khác phương án có thời gian ngắn nhất trong số các phương án không phải là phương án duy nhất.

Để luyện tập thêm các bài tập về Sắp xếp – Tham lam trong sách Competitive Programming Basic 2024 của Code Dream, đăng ký mua ngay và chấm bài online tại http://oj.codedream.edu.vn