DAA-期限付きのジョブシーケンス

問題文

ジョブシーケンス問題では、目的は、期限内に完了し、最大の利益をもたらす一連のジョブを見つけることです。

解決

考えてみましょう、のセット n仕事がその期限までに完了した場合、締め切りと利益に関連付けられている特定の仕事が獲得されます。これらの仕事は、最大の利益が得られるような方法で注文する必要があります。

指定されたすべてのジョブが期限内に完了しない場合があります。

仮定、締め切り i^th ジョブ J_i です d_i そしてこの仕事から受け取った利益は p_i。したがって、このアルゴリズムの最適解は、最大の利益を伴う実行可能解です。

したがって、$ 1 \ leqslant i \ leqslant n $に対して$ D（i）> 0 $です。

最初、これらのジョブは利益に従って順序付けられます。つまり、$ 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