Lập lịch máy song song

Lập lịch máy song song là gì?

Lập lịch máy song song phân bổ một tập công việc cho nhiều máy giống hệt nhau nhằm tối ưu các mục tiêu như cực tiểu hóa makespan (tổng thời gian hoàn thành) hoặc tổng độ trễ hạn. Đây là sự mở rộng của lập lịch một máy sang môi trường nhiều máy, vốn phổ biến trong sản xuất, tính toán và hậu cần.

Quy tắc LPT (Longest Processing Time — ưu tiên công việc có thời gian gia công dài nhất) là thuật giải gần đúng (heuristic) nổi tiếng để cực tiểu hóa makespan trên các máy song song: sắp xếp công việc theo thời gian gia công giảm dần rồi gán mỗi công việc cho máy rảnh sớm nhất. LPT bảo đảm makespan không vượt quá 4/3 lần giá trị tối ưu đối với các máy giống hệt nhau. Những quy tắc khác (SPT, EDD, WSPT) tối ưu các mục tiêu khác.

Hệ số sử dụng máy — tỷ lệ thời gian mỗi máy ở trạng thái bận trên tổng thời gian — cho thấy chất lượng cân bằng tải. Hệ số sử dụng đồng đều giữa các máy cho thấy tải được cân bằng tốt. Biểu đồ Gantt thể hiện dòng thời gian lịch trình của từng máy, làm cho thời gian rảnh và tình trạng mất cân bằng tải hiện ra ngay lập tức.

Formula: Makespan = max(Completion Time of all machines) Utilization = Σ Processing Time / (Makespan x m) Tardiness = max(0, Completion - Due Date) LPT: Assign longest job to earliest available machine SPT: Assign shortest job to earliest available machine

Ví dụ tính toán

4 công việc (p=8,6,5,3) trên 2 máy theo quy tắc LPT. Gán Công việc 1(8)→M1, Công việc 2(6)→M2, Công việc 3(5)→M2 (tải 6→11), Công việc 4(3)→M1 (tải 8→11). Makespan = 11. Hệ số sử dụng: M1=11/11=100%, M2=11/11=100%. Cân bằng hoàn hảo. Nếu không dùng LPT (theo FCFS): có thể nhận makespan=14 với mức cân bằng kém.

Khi nào sử dụng máy tính này

• Khi lập lịch lô công việc trên nhiều máy giống nhau và cần giảm thiểu makespan hoặc tổng trễ
• Trong lập kế hoạch công suất để đánh giá liệu thêm máy có giảm đáng kể makespan cho khối lượng công việc hiện tại
• Khi so sánh quy tắc điều phối cho hỗn hợp công việc cụ thể — quy tắc khác nhau tối ưu mục tiêu khác nhau và lựa chọn tốt nhất phụ thuộc ưu tiên
• Sau khi máy hỏng để nhanh chóng lập lại lịch công việc còn lại trên máy khả dụng và đánh giá tác động giao hàng
• Khi cân bằng tải giữa các máy để giảm thiểu thời gian nhàn rỗi và đảm bảo tất cả máy đóng góp đều cho lịch sản xuất

Những sai lầm thường gặp

• Sử dụng SPT cho giảm thiểu makespan — SPT giảm thiểu thời gian lưu trung bình, không phải makespan; cho makespan trên máy song song, sử dụng LPT phân công việc dài nhất trước
• Giả định thêm máy luôn giảm makespan tỷ lệ — cải thiện theo quy luật lợi nhuận giảm dần; với kích thước công việc rất không đều, thêm máy có thể hầu như không giảm makespan
• Không xem xét thời gian phát hành khi công việc đến vào thời điểm khác nhau — quy tắc điều phối tĩnh giả định tất cả công việc có sẵn tại thời điểm 0; sử dụng điều phối động khi thời gian đến khác nhau
• Bỏ qua cân bằng hiệu suất sử dụng máy — lịch makespan tối thiểu có thể để một số máy nhàn rỗi lâu; kiểm tra hiệu suất sử dụng tất cả máy cho công bằng và cân bằng mài mòn

Cách diễn giải kết quả

• Hiệu suất sử dụng đều trên tất cả máy (>90% mỗi máy) — tải được cân bằng tốt; quy tắc điều phối hoạt động hiệu quả
• Một máy 100% hiệu suất trong khi các máy khác thấp đáng kể — máy đó là tắc nghẽn; công việc dài nhất có thể quyết định makespan
• Tổng trễ = 0 — tất cả công việc hoàn thành trước hạn; lịch đáp ứng tất cả cam kết giao hàng
• Tổng trễ cao với nhiều công việc trễ — khối lượng công việc vượt công suất trong khung thời gian hạn; xem xét làm thêm, thêm máy hoặc đàm phán kéo dài hạn
• LPT và SPT cho makespan rất tương tự — thời gian xử lý công việc tương đối đồng đều; lựa chọn quy tắc ít quan trọng khi công việc có kích thước tương tự

Tiêu chuẩn & Tài liệu tham khảo liên quan

• APICS CPIM Body of Knowledge — Bao gồm khái niệm lập lịch máy song song trong mô-đun kiểm soát hoạt động sản xuất
• ISA-95 (IEC 62264) — Tiêu chuẩn tích hợp hệ thống doanh nghiệp-kiểm soát định nghĩa các cấp lập lịch bao gồm lập lịch chi tiết cấp máy

Câu hỏi thường gặp

Quy tắc điều độ nào cực tiểu hóa makespan trên các máy song song?

LPT (ưu tiên công việc có thời gian gia công dài nhất) là thuật giải gần đúng tốt nhất để cực tiểu hóa makespan. Nhờ gán các công việc dài trước, quy tắc này bảo đảm những công việc lớn không tạo ra nút thắt cổ chai ở cuối lịch trình. LPT bảo đảm nghiệm nằm trong khoảng 4/3 - 1/(3m) lần giá trị tối ưu, với m là số máy. Với 2 máy, con số này là 7/6 (≈17%) so với giá trị tối ưu.

Tôi nên xử lý các công việc có thời điểm sẵn sàng hoặc hạn hoàn thành khác nhau như thế nào?

Khi có thời điểm sẵn sàng, công việc chỉ có thể bắt đầu sau thời điểm đó — hãy dùng cách điều độ động, tức đánh giá lại mức ưu tiên mỗi khi một máy trở nên rảnh. Khi có hạn hoàn thành, các quy tắc EDD hoặc CR giúp cực tiểu hóa độ trễ hạn. Với những bài toán phức tạp có cả hai ràng buộc, hãy mô phỏng nhiều quy tắc rồi so sánh các chỉ số hiệu quả. Quy tắc tốt nhất phụ thuộc vào tổ hợp công việc cụ thể và mục tiêu đặt ra.