2011-08-16 55 views
5

Tôi gặp vấn đề về lập kế hoạch trong đó các công việc mới (tập hợp các tác vụ có thực hiện được kết nối tuần tự) đến sau mỗi vài giây hoặc lâu hơn.
Mỗi công việc yêu cầu một số tài nguyên được phân bổ trong khoảng thời gian đã biết.
Ví dụ:
Job j1 là một tập hợp các nhiệm vụ mà chúng tôi bảo lưu nguồn {r1, r2, r3} trên một mẫu lịch nổi tiếng:Thuật toán lập lịch biểu

r1:[t0 .. t1=t0+td1], 
r2:[t2=t1+td2+i2 .. t3=t2+td3] 
  • t0 là thời gian bắt đầu thực hiện
  • TD1 là chiều dài phân bổ tài nguyên cho r1
  • t1 là thời gian kết thúc phân bổ nguồn lực cho r1
  • i1 là độ dài của chờ đợi perioid giữa r1, r2 và như vậy.

schedule example
Trong ví dụ, một j2 công việc mới đang được lên kế hoạch ngay sau khi thực hiện j1 đã bắt đầu. Thời gian bắt đầu sớm nhất cho j2 là t1. Một công việc có thể mất vài phút thực hiện hầu hết trong số đó bao gồm chờ đợi.

Tôi có bộ lập lịch xem bảng đặt chỗ hiện tại và quyết định thời điểm bắt đầu sớm nhất có thể cho công việc mới với thời gian phân bổ cố định và thời gian chờ và đặt chỗ tương ứng.

(Nhưng trong thực tế, thời gian chờ đợi không thực sự cần phải cố định - nhưng trong một số tỷ lệ phần trăm (có thể 5%) và có thể có lựa chọn thay thế cho việc sử dụng tài nguyên, ví dụ, nếu tài nguyên r3.1 được đặt trước, sau đó 3.2 có thể được sử dụng để đạt được điều tương tự.)

Tuy nhiên, nếu cần có lịch biểu (có, được đề xuất) có thể điều chỉnh động tất cả phân bổ lịch biểu khi công việc mới đến để tối đa hóa tổng số công việc được thực hiện (trong một ngày) bằng cách tận dụng thực tế là thời gian chờ đợi không chính xác như được đưa ra và khả năng thực hiện song song với một số bản sao (3.1/3.2), sau đó tôi sẽ xem xét một cách hoàn toàn khác lược đồ lập kế hoạch (so với phương pháp bắt đầu hiện tại càng sớm càng tốt của tôi).

  1. Bạn sẽ gọi chương trình lập lịch biểu nào?
  2. Bất kỳ đề xuất nào về việc tiếp cận vấn đề (mới)?

Trả lời

1

Đối với câu hỏi của bạn liên quan đến "thay thế cho nguồn lực sử dụng":

Các mô hình phổ biến nhất được thực hiện để giải quyết rằng loại vấn đề là Object Pool Pattern
Ví dụ biết đến rộng rãi nhất cho điều này có lẽ là ThreadPool

Tôi khuyên bạn nên triển khai lớp ResourcePool với phương thức int GetResource(ResourceType type, int durationInSeconds). Giá trị trả lại cho biết khi tài nguyên tiếp theo của ResourceType nhất định sẽ có sẵn

0

Bạn có thể xử lý RCPSP (Vấn đề lập kế hoạch dự án tài nguyên ràng buộc). Các kỹ thuật giải pháp bao gồm lập trình số nguyên và lập trình ràng buộc cho các chẩn đoán khác nhau.Kỹ thuật này phụ thuộc các chi tiết như đường chân trời lên kế hoạch, làm thế nào nhiệm vụ/công việc sử dụng tài nguyên/cổ phiếu, nhanh như thế nào bạn cần một kế hoạch giải pháp vv

see:

https://developers.google.com/optimization/scheduling/job_shop

http://www.laas.fr/files/ROC/2014-Presentations/MILP-RCPSP-PMS2014.pdf

Các vấn đề liên quan