DAA - Sắp xếp công việc với thời hạn

Báo cáo vấn đề

Trong bài toán sắp xếp công việc, mục tiêu là tìm ra một chuỗi các công việc được hoàn thành trong thời hạn và mang lại lợi nhuận tối đa.

Giải pháp

Hãy để chúng tôi xem xét, một tập hợp nđược giao những công việc gắn liền với thời hạn và thu được lợi nhuận, nếu một công việc được hoàn thành trước thời hạn. Những công việc này cần được sắp xếp theo cách có lợi nhuận tối đa.

Có thể xảy ra rằng tất cả các công việc được giao có thể không được hoàn thành trong thời hạn của chúng.

Giả sử, thời hạn của i^th việc làm J_i Là d_i và lợi nhuận nhận được từ công việc này là p_i. Do đó, giải pháp tối ưu của thuật toán này là giải pháp khả thi với lợi nhuận tối đa.

Do đó, $ D (i)> 0 $ cho $ 1 \ leqslant i \ leqslant n $.

Ban đầu, những công việc này được sắp xếp theo lợi nhuận, tức là $ p_ {1} \ geqslant p_ {2} \ geqslant p_ {3} \ geqslant \: ... \: \ geqslant p_ {n} $.

Algorithm: Job-Sequencing-With-Deadline (D, J, n, k) 
D(0) := J(0) := 0 
k := 1 
J(1) := 1   // means first job is selected 
for i = 2 … n do 
   r := k 
   while D(J(r)) > D(i) and D(J(r)) ≠ r do 
      r := r – 1 
   if D(J(r)) ≤ D(i) and D(i) > r then 
      for l = k … r + 1 by -1 do 
         J(l + 1) := J(l) 
         J(r + 1) := i 
         k := k + 1

Phân tích

Trong thuật toán này, chúng tôi đang sử dụng hai vòng lặp, một vòng lặp nằm trong một vòng lặp khác. Do đó, độ phức tạp của thuật toán này là $ O (n ^ 2) $.

Thí dụ

Chúng ta hãy xem xét một tập hợp các công việc đã cho như trong bảng sau. Chúng ta phải tìm ra một chuỗi các công việc, những công việc này sẽ được hoàn thành trong thời hạn và sẽ mang lại lợi nhuận tối đa. Mỗi công việc đều gắn liền với thời hạn và lợi nhuận.

Việc làm	J₁	J₂	J₃	J₄	J₅
Hạn chót	2	1	3	2	1
Lợi nhuận	60	100	20	40	20

Giải pháp

Để giải quyết vấn đề này, các công việc đã cho được sắp xếp theo lợi nhuận của chúng theo thứ tự giảm dần. Do đó, sau khi sắp xếp, các công việc được sắp xếp như trong bảng sau.

Việc làm	J₂	J₁	J₄	J₃	J₅
Hạn chót	1	2	2	3	1
Lợi nhuận	100	60	40	20	20

Từ nhóm công việc này, trước tiên chúng tôi chọn J₂, vì nó có thể được hoàn thành trong thời hạn và đóng góp lợi nhuận tối đa.

Kế tiếp, J₁ được chọn vì nó mang lại nhiều lợi nhuận hơn so với J₄.
Trong đồng hồ tiếp theo, J₄ không thể được chọn vì thời hạn của nó đã hết, do đó J₃ được chọn khi nó thực thi trong thời hạn của nó.
Công việc J₅ bị loại bỏ vì nó không thể được thực thi trong thời hạn của nó.

Do đó, giải pháp là chuỗi các công việc (J₂, J₁, J₃), đang được thực hiện trong thời hạn của họ và mang lại lợi nhuận tối đa.

Tổng lợi nhuận của chuỗi này là 100 + 60 + 20 = 180.