Tôi đang làm việc trên một chương trình đa luồng, trong đó tôi có một số chuỗi công việc thực hiện các tác vụ có độ dài không bằng nhau. Tôi muốn cân bằng tải các tác vụ để đảm bảo rằng chúng hoạt động gần như giống nhau. Đối với mỗi công việc T i Tôi có một số c i cung cấp một xấp xỉ gần đúng với số lượng công việc cần thiết cho nhiệm vụ đó.Thuật toán heuristic để cân bằng tải giữa các chủ đề
Tôi đang tìm một thuật toán hiệu quả (O (N) N = số nhiệm vụ hoặc tốt hơn) sẽ cho tôi "gần" một số dư tải tốt cho các giá trị của c i. Nó không phải là tối ưu, nhưng tôi muốn có thể có một số giới hạn lý thuyết về cách phân bổ kết quả xấu như thế nào.
Bất kỳ ý tưởng nào?
Có phải các công việc đã được biết trước hay không. Bạn có phải lo lắng về nạn đói (ví dụ, một nhiệm vụ với c_i cao không bao giờ chạy nếu các nhiệm vụ c_i thấp tiếp tục được thêm)? –
@David: Số lượng tác vụ sẽ được biết trước, cùng với ước tính thời lượng của chúng. Đói đói không phải là vấn đề ở đây. Về cơ bản, mục tiêu của tôi là giảm thiểu thời gian thực hiện –