DAA - Urutan Pekerjaan dengan Batas Waktu

Pernyataan masalah

Dalam masalah job sequencing, tujuannya adalah untuk menemukan urutan pekerjaan yang diselesaikan sesuai tenggat waktunya dan memberikan keuntungan yang maksimal.

Larutan

Mari kita pertimbangkan, satu set ndiberikan pekerjaan yang terkait dengan tenggat waktu dan keuntungan diperoleh, jika pekerjaan diselesaikan sesuai dengan tenggat waktunya. Pekerjaan ini perlu diatur sedemikian rupa agar ada keuntungan yang maksimal.

Mungkin saja semua pekerjaan yang diberikan mungkin tidak selesai dalam tenggat waktu mereka.

Asumsikan, tenggat waktu i^th pekerjaan J_i adalah d_i dan keuntungan yang didapat dari pekerjaan ini adalah p_i. Oleh karena itu, solusi optimal dari algoritma ini adalah solusi yang layak dengan keuntungan maksimum.

Jadi, $ D (i)> 0 $ untuk $ 1 \ leqslant i \ leqslant n $.

Awalnya, pekerjaan ini diurutkan menurut keuntungan, yaitu $ 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

Analisis

Dalam algoritma ini, kami menggunakan dua loop, satu di dalam yang lain. Oleh karena itu, kompleksitas algoritma ini adalah $ O (n ^ 2) $.

Contoh

Mari kita pertimbangkan satu set pekerjaan tertentu seperti yang ditunjukkan pada tabel berikut. Kami harus menemukan urutan pekerjaan, yang akan diselesaikan dalam tenggat waktu mereka dan akan memberikan keuntungan maksimal. Setiap pekerjaan dikaitkan dengan tenggat waktu dan keuntungan.

Pekerjaan	J₁	J₂	J₃	J₄	J₅
Tenggat waktu	2	1	3	2	1
Keuntungan	60	100	20	40	20

Larutan

Untuk mengatasi masalah ini, pekerjaan yang diberikan diurutkan menurut profitnya dalam urutan menurun. Karenanya, setelah pengurutan, pekerjaan akan diurutkan seperti yang ditunjukkan pada tabel berikut.

Pekerjaan	J₂	J₁	J₄	J₃	J₅
Tenggat waktu	1	2	2	3	1
Keuntungan	100	60	40	20	20

Dari rangkaian pekerjaan ini, pertama kita pilih J₂, karena dapat diselesaikan dalam tenggat waktu dan memberikan keuntungan maksimal.

Lanjut, J₁ dipilih karena memberikan keuntungan lebih dibandingkan J₄.
Di jam berikutnya, J₄ tidak dapat dipilih karena tenggat waktunya telah berakhir J₃ dipilih saat dijalankan dalam tenggat waktu.
Pekerjaan J₅ dibuang karena tidak dapat dijalankan dalam tenggat waktu.

Jadi, solusinya adalah urutan pekerjaan (J₂, J₁, J₃), yang dieksekusi dalam batas waktu dan memberikan keuntungan maksimal.

Total profit dari urutan ini adalah 100 + 60 + 20 = 180.