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

問題文

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

解決

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

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

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

したがって、$ 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

分析

このアルゴリズムでは、2つのループを使用しています。1つは別のループ内にあります。したがって、このアルゴリズムの複雑さは$ O(n ^ 2)$です。

次の表に示すように、与えられたジョブのセットを考えてみましょう。期限内に完了し、最大の利益をもたらす一連の仕事を見つける必要があります。各仕事は締め切りと利益に関連付けられています。

ジョブ J1 J2 J3 J4 J5
締め切り 2 1 3 2 1
利益 60 100 20 40 20

解決

この問題を解決するために、指定されたジョブは、利益に従って降順で並べ替えられます。したがって、ソート後、ジョブは次の表に示すように順序付けられます。

ジョブ J2 J1 J4 J3 J5
締め切り 1 2 2 3 1
利益 100 60 40 20 20

この一連のジョブから、最初に選択します J2、期限内に完了することができ、最大の利益に貢献するため。

  • 次、 J1 に比べて利益が大きいため、 J4

  • 次の時計では、 J4 締め切りが過ぎたため選択できません。 J3 期限内に実行されるときに選択されます。

  • 仕事 J5 期限内に実行できないため、破棄されます。

したがって、解決策は一連のジョブです(J2, J1, J3)、期限内に実行され、最大の利益をもたらします。

このシーケンスの総利益は 100 + 60 + 20 = 180