Thuật toán để chuyển đổi một luồng công việc DAG thành phân bổ tài nguyên song song?

Question

Giả sử tôi có biểu đồ nơi các nút là khối lượng công việc của các loại và cạnh khác nhau là các phụ thuộc giữa các tải công việc. (Đây là một DAG vì phụ thuộc chu kỳ không được tồn tại.)

Tôi cũng có một tập hợp nhiều tác nhân có thể thực hiện công việc.

Một số giống tải công việc có thể được trao cho bất kỳ đại lý nào, các loại khác phải được trao cho một đại lý cụ thể và một số khác phải được trao cho một đại lý trong một nhóm đại lý cụ thể.

Làm thế nào để tôi chỉ định khối lượng công việc như vậy:

• Không khối lượng công việc được trao cho một đại lý cho đến khi tất cả các khối lượng công việc ngăn chặn nó được hoàn thành

• Thời gian ngắn nhất có thể được yêu cầu phải hoàn thành việc tổng graph khối lượng công việc . (Lưu ý rằng thời gian nhàn rỗi của đại lý thường tốt, nhưng không phải là yêu cầu cơ bản - có thể có các tình huống theo đó một tác nhân cụ thể không hoạt động lâu hơn nhưng tổng thời gian để hoàn thành tất cả công việc trên tất cả các đại lý ở mức tối thiểu.)

Tải công việc có ước tính thời gian, nhưng giả sử vì mục đích đơn giản là mỗi khối lượng công việc đều tính thời gian bằng nhau để tính toán. (Chỉ cần chia nhỏ khối lượng công việc thành nhiều khối lượng công việc phụ thuộc vào serially cho đến khi mọi tải công việc là hoạt động liên tục.)

Tôi biết phân loại DAG tôpô. Tôi có nhiều tác nhân hoạt động song song, và các mối quan hệ là như vậy mà tối ưu hóa thời gian có khả năng lớn có thể được thực hiện bằng cách sắp xếp lại các nhiệm vụ không rõ ràng.

Kết quả của điều này sẽ được hiển thị tốt nhất dưới dạng biểu đồ Gantt có thời lượng tối thiểu tổng thể. Trong thực tế, nếu bạn nghĩ về vấn đề như việc phân bổ vé lỗi trong một cột mốc quan trọng cho các kỹ sư trong một nhóm, với mục tiêu đạt được mốc quan trọng được thực hiện càng sớm càng tốt, thì bạn sẽ có được ý tưởng. (Không ... xin đừng nói với tôi để nhập đồ thị của tôi vào MS Project và sau đó xuất nó :) - Tôi quan tâm đến thuật toán đằng sau nó!)

Con trỏ đến thuật toán nổi tiếng, thư viện phần mềm, hoặc các vấn đề chung và các nguyên tắc được đánh giá cao!

Answer 1

Trừ khi bạn có số lượng đại lý vô hạn sao cho một tác nhân tương thích có sẵn ngay khi tất cả các nhiệm vụ trước của công việc được thực hiện, đây là vấn đề NP-hard.

< shameless plug>

Một vấn đề rất giống nhau là có trong cuốn sách của tôi "Algorithms For Interviews"

</shameless plug>

Đây là vấn đề và giải pháp từ cuốn sách:

Chúng tôi cần lên lịch cho N bài giảng trong lớp M. Một số trong những bài giảng đó là điều kiện tiên quyết cho người khác. Làm thế nào bạn sẽ chọn khi nào và ở đâu để tổ chức các bài giảng để hoàn thành tất cả các bài giảng càng sớm càng tốt?

Giải pháp: Chúng tôi có một tập hợp các bài giảng về thời lượng đơn vị N và các lớp học M. Các bài giảng có thể được tổ chức đồng thời miễn là không có hai bài giảng cần phải xảy ra trong cùng một lớp học cùng một lúc và tất cả các ràng buộc ưu tiên được đáp ứng. Vấn đề lập kế hoạch các bài giảng này để giảm thiểu thời gian hoàn thành được biết là NP-complete. Vấn đề này được mô hình hóa tự nhiên bằng cách sử dụng biểu đồ. Chúng tôi mô hình các bài giảng như đỉnh, với một cạnh từ đỉnh u đến đỉnh v nếu u là điều kiện tiên quyết cho v. Rõ ràng, đồ thị phải được tuần hoàn cho các ràng buộc ưu tiên được thỏa mãn. Nếu chỉ có một phòng thuyết trình, chúng ta có thể chỉ đơn giản là giữ các bài giảng theo thứ tự topo và hoàn thành N bài giảng trong thời gian N (giả sử mỗi bài giảng là thời gian đơn vị). Chúng ta có thể phát triển các chẩn đoán bằng cách quan sát những điều sau đây: bất cứ lúc nào, có một tập các bài giảng có các ràng buộc ưu tiên đã được thỏa mãn. Nếu bộ này nhỏ hơn M, chúng ta có thể lên lịch cho tất cả chúng; nếu không, chúng ta cần phải chọn một tập hợp con để lên lịch. Lựa chọn tập hợp con có thể dựa trên một số chỉ số:

• Thứ tự bài giảng dựa trên độ dài của chuỗi phụ thuộc dài nhất mà chúng bắt đầu.
• Xếp hạng thứ tự bài giảng dựa trên số lượng bài giảng mà chúng là điều kiện tiên quyết ngay lập tức cho.
• Xếp hạng thứ tự bài giảng dựa trên tổng số bài giảng mà họ là điều kiện tiên quyết trực tiếp hoặc gián tiếp.

Chúng tôi cũng có thể sử dụng kết hợp các tiêu chí này để đặt hàng các bài giảng hiện có thể lên lịch. Ví dụ, đối với mỗi đỉnh, chúng tôi xác định mức độ quan trọng của nó là chiều dài của một con đường dài nhất từ ​​nó đến bồn rửa. Chúng tôi lên lịch các bài giảng bằng cách xử lý các đỉnh theo thứ tự topo. Tại bất kỳ điểm nào trong thuật toán của chúng tôi, chúng tôi có một tập hợp các bài giảng ứng cử viên - đây là những bài giảng có điều kiện tiên quyết đã được lên lịch. Nếu tập hợp ứng viên nhỏ hơn M, chúng tôi lên lịch cho tất cả các bài giảng; nếu không, chúng tôi chọn M bài giảng quan trọng nhất và lên lịch cho những ý tưởng đó là chúng nên được lên kế hoạch sớm hơn vì chúng bắt đầu từ các chuỗi phụ thuộc dài hơn. Tiêu chí là heuristic và có thể không dẫn đến lịch trình tối ưu - điều này được mong đợi vì vấn đề là NP-complete. Các chẩn đoán khác có thể được sử dụng, ví dụ: chúng tôi có thể sử dụng số lượng bài giảng phụ thuộc vào bài giảng L là mức độ quan trọng của bài giảng L hoặc một số kết hợp của tiêu chí.

Answer 2

Bài viết trên Wikipedia về PERT có thể là một nơi hữu ích để bắt đầu.