Phân tích và Tối ưu hóa Bài toán Three Servers

Bài toán đặt ra yêu cầu phân chia một chuỗi các tác vụ có thời gian thực thi xác định vào ba máy chủ sao cho sự chênh lệch giữa máy chủ bận nhất và máy chủ nhàn rỗi nhất là nhỏ nhất.

Hướng tiếp cận ban đầu

Xét trạng thái quy hoạch động với dp[i][j][k], đại diện cho khả năng đạt được sau khi đã xét i tác vụ đầu tiên, trong đó máy thứ hai đang chạy tổng thời gian j và máy thứ ba là k. Máy thứ nhất sẽ tự động có tổng thời gian bằng tổng tất cả trừ đi j và k.

Với cách định nghĩa này, độ phức tạp về bộ nhớ sẽ rơi vào mức O(n * T^2) (với T là tổng thời gian), điều này vượt quá giới hạn cho phép của đề bài do kích thước ma trận quá lớn.

Tối ưu hóa 1: Sử dụng Bitset

Do giá trị trả về của hàm DP chỉ mang tính chất đúng/sai (boolean), ta có thể sử dụng cấu trúc std::bitset để nén thông tin và tăng tốc độ xử lý. Các phép chuyển trạng thái tương ứng với việc gán thêm tác vụ vào máy chủ.

Cụ thể, nếu ở bước i trạng thái (j, k) là hợp lệ, thì tại bước i+1 chúng ta có thể:

1. Thêm tác vụ vào máy thứ nhất (không thay đổi j và k): giữ nguyên vị trí bit.
2. Thêm tác vụ vào máy thứ hai (tăng j lên): dịch trái mảng bitset hoặc cập nhật trực tiếp theo chỉ số.
3. Thêm tác vụ vào máy thứ ba (tăng k lên): sử dụng phép dịch bit trên toàn bộ hàng.

// Logic chuyển trạng thái cơ bản
dp_next[j] |= dp_curr[j];               // Máy 1 nhận task
dp_next[j + duration] |= dp_curr[j];    // Máy 2 nhận task
dp_next[j] |= (dp_curr[j] << duration); // Máy 3 nhận task

Tối ưu hóa 2: Giới hạn miền giá trị

Chúng ta có thể chứng minh rằng trong phương án tối ưu, hiệu số thời gian giữa máy chủ lâu nhất và ngắn nhất thường rất nhỏ (dưới 30 đơn vị thời gian). Giả sử tồn tại một phân bố mà chênh lệch lớn hơn ngưỡng này, ví dụ máy c nặng hơn máy a một lượng đáng kể, việc di chuyển một tác vụ từ c sang a sẽ làm giảm hiệu số chênh lệch, đưa hệ thống tiến gần đến trạng thái cân bằng hơn.

Kết luận này giúp thu hẹp phạm vi cần duyệt cho biến thời gian của máy chủ thứ hai, tuy nhiên vẫn chưa đủ để đáp ứng giới hạn bộ nhớ nếu không kết hợp với kỹ thuật khác.

Tối ưu hóa 3: Chia khối thời gian và tái tạo đường đi

Nếu chỉ quan tâm đến giá trị tối ưu, ta có thể dùng mảng xoay để tiết kiệm bộ nhớ. Tuy nhiên, bài toán yêu cầu in ra chi tiết từng tác vụ được gán cho máy nào. Để giải quyết vấn đề thiếu bộ nhớ khi lưu trữ lịch sử đầy đủ, ta chia quá trình tính toán thành các đoạn nhỏ.

Cuối mỗi đoạn cố định, ta lưu lại trạng thái hiện tại. Sau khi tính xong toàn bộ, ta sẽ quay ngược lại từng đoạn để khôi phục lộ trình phân bổ nhiệm vụ dựa trên các điểm mốc đã lưu.

Triển khai Chi tiết

Dưới đây là mã nguồn mẫu được viết lại với các biến đặt tên rõ ràng hơn và logic được tổ chức mạch lạc hơn.

Hàm tính toán DP

Chức năng chính của hàm này là cập nhật bảng truy xuất khả năng cho một khối tác vụ cụ thể.

void tinh_duyet(int so_buoc_hien_tai, int block_size, vector<long long> thoi_gian_tasks) {
    // Khởi tạo mảng visited cho khối mới
    for (int i = 0; i < block_limit; ++i) 
        visited[0][i].reset();
    
    visited[0][0] = true; // Trạng thái gốc
    
    for (int idx = 0; idx < so_buoc_hien_tai; ++idx) {
        int thu_tu_buoc_truc_tiep = idx + 1;
        int trang_thai_hien_tai = idx % block_size;
        int trang_thai_ke_tiep = (idx + 1) % block_size;
        
        // Xóa dữ liệu cũ cho vòng lặp tiếp theo
        for (int j = 0; j < block_limit; ++j) {
            visited[trang_thai_ke_tiep][j].reset();
        }
        
        // Thực hiện các phép chuyển trạng thái
        for (int j = 0; j < block_limit; ++j) {
            if (!visited[trang_thai_hien_tai][j].any()) continue;
            
            // Phương án 1: Gán cho máy A (giữ nguyên j, k)
            visited[trang_thai_ke_tiep][j] |= visited[trang_thai_hien_tai][j];
            
            // Phương án 2: Gán cho máy B (tăng j)
            if (j + thoi_gian_tasks[idx] < block_limit) {
                visited[trang_thai_ke_tiep][j + thoi_gian_tasks[idx]] |= visited[trang_thai_hien_tai][j];
            }
            
            // Phương án 3: Gán cho máy C (tăng k tương ứng)
            visited[trang_thai_ke_tiep][j] |= (visited[trang_thai_hien_tai][j] << thoi_gian_tasks[idx]);
        }
    }
}

Quá trình tìm lời giải

Sau khi tính toán hết tất cả nhiệm vụ, ta quét qua các trạng thái cuối cùng để tìm sự chênh lệch nhỏ nhất giữa 3 máy chủ.

for (int tg_A = 0; tg_A < block_limit; ++tg_A) {
    for (int tg_B = 0; tg_B < block_limit; ++tg_B) {
        if (visited[n_tasks % block_size][tg_A][tg_B]) {
            int tg_C = tong_thoi_gian - tg_A - tg_B;
            int chenh_lech = max({tg_A, tg_B, tg_C}) - min({tg_A, tg_B, tg_C});
            
            if (phan_optimal_chenh_lech > chenh_lech) {
                phan_optimal_chenh_lech = chenh_lech;
                best_state_A = tg_A;
                best_state_B = tg_B;
            }
        }
    }
}

Khôi phục phân bổ tác vụ

Để in ra kết quả, ta chạy lại thuật toán từng khối một cách độc lập, bắt đầu từ trạng thái ghi nhận trước đó để xác định tác vụ cụ thể thuộc về máy nào.

// Phân tách dãy tác vụ thành các khối để quản lý bộ nhớ
vector<int> ket_qua_phan_cong[3];
int vi_tri_khoang[5];
int so_khoang = 1;

vi_tri_khoang[0] = 0;
while (vi_tri_khoang[so_khoang - 1] < n_tasks) {
    vi_tri_khoang[so_khoang] = min(vi_tri_khoang[so_khoang - 1] + block_size, n_tasks);
    so_khoang++;
}

// Duyệt ngược từ đoạn cuối về đoạn đầu để truy vết
for (int khoanh = so_khoang - 1; khoanh >= 1; --khoanh) {
    int bat_dau = vi_tri_khoang[khoanh - 1];
    int ket_thuc = vi_tri_khoang[khoanh];
    
    // Tính lại DP cho đoạn này
    tinh_duyet(ket_thuc - bat_dau, block_size); 
    
    // Quay lui tìm ra ai nhận task j
    for (int j = ket_thuc - 1; j >= bat_dau; --j) {
        int task_id = j + 1;
        int task_dur = tasks[j + 1]; // Lưu ý index
        
        if (visited[0][current_val_A][current_val_B]) {
            ket_qua_phan_cong[2].push_back(task_id); // Máy thứ 3
            continue;
        }
        
        if (current_val_A >= task_dur && visited[0][current_val_A - task_dur][current_val_B]) {
            current_val_A -= task_dur;
            ket_qua_phan_cong[0].push_back(task_id); // Máy thứ 1
            continue;
        }
        
        ket_qua_phan_cong[1].push_back(task_id); // Máy thứ 2
        current_val_B -= task_dur;
    }
}

Cuối cùng, chương trình sẽ in ra danh sách ID các tác vụ cho từng máy chủ tương ứng với phương án tối ưu đã tìm thấy.