việc lập kế hoạch hiệu quả với giảm lợi nhuận trên nhiều máy tính

Question

Vấn đề: Xét bài toán lập lịch trình của n công việc trên máy M trong đó mỗi công việc tôi có một thời gian xử lý p _i và đưa ra một lợi nhuận g _i (t) nếu hoàn thành theo thời gian t. Tất cả các công việc được giải phóng tại thời điểm 0. Tất cả g _i (t) là các chức năng không tăng. Để đơn giản, chúng ta có thể giả định rằng các máy không được ưu tiên.

Đối với M = 1 và chức năng lợi nhuận giảm tuyến tính. vấn đề này có thể được giải quyết trong O (n) bằng cách sử dụng thuật toán tham lam. Nhưng đối với các chức năng chung, nó là NP-complete.

Tôi quan tâm đến trường hợp chung. Xin vui lòng cho tôi bất kỳ liên kết của các giấy tờ hoặc tài liệu tài nguyên cho vấn đề này. Tôi tìm kiếm trên internet nhưng không tìm thấy bất cứ điều gì thú vị cho M> 1, mặc dù có công việc trước đó trên xấp xỉ các giới hạn cho M = 1.

Xin lưu ý rằng tôi không mong bạn giải quyết vấn đề này nhưng chỉ cần thực hiện công việc trước đó về các vấn đề tương tự, nếu có. Và nếu bạn có bất kỳ ý tưởng nào có thể giúp vui lòng chia sẻ.

Tôi muốn biết những giới hạn nào được biết cho vấn đề này với máy móc và công việc n với cùng ngày phát hành và chức năng lợi nhuận không tăng chung. Tôi tìm thấy một giấy về phía hướng đó

http://arxiv.org/pdf/1008.4889v1.pdf

Họ đưa ra một O (1) xấp xỉ khi tất cả các công việc có thời gian phát hành giống hệt nhau. Tôi muốn tìm những tài liệu tương tự về vấn đề và ý tưởng họ sử dụng để giải quyết vấn đề.

Answer 1

Bạn có thể bắt đầu bằng "giải pháp tham lam" bằng cách sử dụng quy tắc công văn, ví dụ: giảm thiểu

g _i (t + p _i)/p _i

trên máy trống đầu tiên (i chạy việc làm khắp nơi vẫn chưa lên kế hoạch, t là thời gian, nơi máy đầu tiên trống).

Sau đó, giải pháp này có thể được cải thiện bằng cách sử dụng Meta-Heuristics như Simulated Annealing. Một giải pháp có thể được biểu diễn dưới dạng một chuỗi các chuỗi công việc (một chuỗi công việc cho mỗi máy). Một điểm quan trọng là, những gì "di chuyển" được phép thay đổi một giải pháp. Có thể cho vấn đề này người ta có thể tìm thấy các giải pháp tốt với hai bước cơ bản:

• Lấy một công việc từ một máy và tìm một vị trí mới để chèn nó.
• Trao đổi hai công việc trong chuỗi công việc của máy móc.