Thuật toán nào cho chương trình lập lịch biểu

Question

Tôi gặp vấn đề về lập kế hoạch nhiệm vụ. Mỗi tác vụ có thời gian bắt đầu đề xuất T (cần bắt đầu tại [T-10, T + 10]), mất L phút để hoàn thành và sử dụng một số tài nguyên [R1, R2, ...]. Khi một tài nguyên đang được sử dụng, không có nhiệm vụ nào khác có thể sử dụng nó. Cho rằng chỉ có thời gian bắt đầu là linh hoạt, mục tiêu của tôi là lên lịch các tác vụ để họ có thể truy cập bất kỳ tài nguyên nào họ cần hoặc chỉ ra tất cả các xung đột cần giải quyết.

Tôi có thể sử dụng thuật toán nào cho mục đích này? Cảm ơn bạn.

Answer 1

Vì bạn đã gắn thẻ này như prolog, tôi khuyên bạn nên thực hiện nó trong constraint logic programming (CLP) và sử dụng các thuật toán xây dựng vào thực hiện CLP của bạn. Ví dụ một phần:

:- use_module(library(clpfd)). 

on_time([]). 
on_time([Task|Tasks]) :- 
    Task = task(TSuggested,TActual,L,Rs), 
    TActual #>= TSuggested - 10, 
    TActual #=< TSuggested + 10, 
    on_time(Tasks). 

vị khác sẽ kiểm tra rằng không có hai nhiệm vụ sử dụng tài nguyên cùng đồng thời:

nonoverlap(R,Task1,Task2) :- 
    Task1 = task(_,T1,L1,Rs2), 
    Task2 = task(_,T2,L2,Rs2), 
    ((member(R,Rs1), member(R,Rs2)) -> 
     T2 #> T1+L1  % start Task2 after Task1 has finished 
     #\/    % OR 
     T1 #> T2+L2  % start Task1 after Task2 has finished 
    ; 
     true   % non-conflicting, do nothing 
    ). 

Cuối cùng, hãy gọi labeling trên tất cả các biến chế để cung cấp cho họ những giá trị phù hợp. Điều này sử dụng CLP(fd), hoạt động cho các đơn vị thời gian nguyên. CLP(R) thực hiện tương tự với giá trị thực nhưng nó hơi phức tạp hơn. Các liên kết dành cho SWI-Prolog nhưng SICStus và ECLiPSe có các thư viện tương tự.

Answer 2

Các vấn đề lập kế hoạch như thế này thường được giải quyết tốt nhất bằng cách sử dụng hoặc lập trình ràng buộc CP hoặc lập trình số nguyên hỗn hợp (MIP). Cả hai đều là phương pháp khai báo, vì vậy bạn chỉ cần tập trung vào các thuộc tính của vấn đề của bạn và để cho một công cụ chuyên dụng xử lý thuật toán cơ bản. Thông tin chi tiết có thể được tìm thấy trên wikipedia:

http://en.wikipedia.org/wiki/Constraint_programming

http://en.wikipedia.org/wiki/Linear_programming

Answer 3

Nếu bạn đang khó khăn, lĩnh vực vấn đề của bạn sẽ mở rộng ra, bạn cũng nên xem xét các thuật toán không hoàn hảo, chẳng hạn như:

• Metaheuristics như tìm kiếm Tabu và mô phỏng ủ. Có một vài triển khai nguồn mở ngoài đó, chẳng hạn như Drools Planner.

• Thuật toán di truyền, chẳng hạn như JGap.