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

分析

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

例

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

Job	J₁	J₂	J₃	J₄	J₅
Deadline	2	1	3	2	1
Profit	60	100	20	40	20

溶液

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

Job	J₂	J₁	J₄	J₃	J₅
Deadline	1	2	2	3	1
Profit	100	60	40	20	20

この一連のジョブから、最初に J〜2〜 を選択します。これは、期限内に完了することができ、最大の利益をもたらすためです。

次に、 _ J〜4〜' と比較してより多くの利益が得られるため、 ' J〜1〜_ が選択されます。
次のクロックでは、期限が過ぎているため、 _ J〜4〜' を選択できません。したがって、 ' J〜3〜_ は、期限内に実行されるときに選択されます。
ジョブ J〜5〜 は、期限内に実行できないため破棄されます。

したがって、ソリューションはジョブのシーケンス（ J〜2〜、J〜1〜、J〜3〜 ）であり、期限内に実行され、最大の利益をもたらします。

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

Design-and-analysis-of-algorithms-job-sequencing-with-deadline

目次

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

問題文

溶液

分析

例

溶液