ジョブシーケンス問題では、期限内に完了し、最大の利益を与えるジョブのシーケンスを見つけることが目的です。
期限に関連付けられたn個のジョブのセットが与えられ、利益が獲得され、その期限までにジョブが完了した場合。 これらの仕事は、最大の利益があるように注文する必要があります。
一例を挙げてみましょう。 図1.1に示すように、すべてのジョブに期限があり、期限前にジョブが終了した場合に関連する利益があるジョブの配列が与えられます。 また、すべてのジョブには単一の単位時間がかかるため、任意のジョブの可能な最小期限は1です。 一度に1つのジョブのみをスケジュールできる場合、総利益を最大化する方法。
簡単な解決策は、与えられたジョブセットのすべてのサブセットを生成し、そのサブセット内のジョブの実現可能性を個々のサブセットでチェッ すべての実行可能なサブセットの中で最大の利益を追跡します。 この解の時間の複雑さは指数関数的です。また、単純な解よりも最適な貪欲な方法を使用してこの問題を解決することもできます。だから貪欲な方法でこの問題を解決することができます。
貪欲な方法でジョブシーケンシングの問題を解決するには、次の手順に従います:
- すべてのジョブを利益の少ない順に並べ替えます。
- ソートされたジョブの最初のジョブとして結果シーケンスを初期化します。
- 残りのn-1ジョブについては以下を実行してください。
- 現在のジョブが期限を逃さずに現在の結果シーケンスに収まる場合は、現在のジョブを結果に追加します。 それ以外の場合は、現在のジョブを無視します。
あなたが図1.1で見ることができるように、ジョブはすでに利益の減少順になっています。ここでは、ジョブ1は最高の利益を持ち、期限は3なので、図1.2に示すように2-3の間でそのジョブを設定します。ジョブ2は二番目に高い利益を持っており、期限は4なので、3-4の間でそのジョブを設定し、すべてに同じことを行いますjobs.So 最後のシーケンスはJ4-J3-J1-J2であり、総利益は110です。
このアルゴリズムのコードはhttps://www.geeksforgeeks.org/job-sequencing-problemで指定できます。
この解の時間の複雑さはO(n2)です。
