5

問題:各ジョブ i が処理時間 p iを持ち、時間 t までに完了した場合に利益 g i (t)を与える、M 台のマシン上の n 個のジョブのスケジューリング問題を考えます。すべてのジョブは時間 0 で解放されます。すべての g i (t) は非増加関数です。簡単にするために、マシンはプリエンプティブではないと仮定できます。

M=1 で直線的に減少する利益関数の場合。この問題は、欲張りアルゴリズムを使用して O(n) で解決できます。しかし、一般的な関数の場合、NP 完全です。

私は一般的なケースに興味があります。問題に関する論文またはリソース資料のリンクを教えてください。インターネットで検索しましたが、M>1 について興味深いものは見つかりませんでしたが、M=1 の境界の近似に関する以前の研究があります。

私はあなたがこれを解決することを期待していませんが、もしあれば同様の問題に関する以前の作業が必要であることに注意してください. そして、役立つアイデアがあれば、遠慮なく共有してください。

同じリリース日と一般的な非増加利益関数を持つ m 台のマシンと n 個のジョブで、この問題の限界を知りたいです。その方向への紙を見つけた

http://arxiv.org/pdf/1008.4889v1.pdf

すべてのジョブのリリース時間が同じ場合、彼らは O(1) 近似を与えました。私は、この問題に関する同様の種類の文献と、その問題を解決するために彼らがどのようなアイデアを使用したかを見つけたいと考えています。

4

1 に答える 1

2

たとえば最小化するディスパッチルールを使用して、「貪欲なソリューション」から始めることができます

g i (t 0 +p i )/p i

最初の空のマシンで (i はまだスケジュールされていないすべてのジョブを実行します。t 0は最初のマシンが空の時間です)。

次に、シミュレーテッド アニーリングなどのメタヒューリスティックを使用して、このソリューションを改善できます。ソリューションは、ジョブ シーケンスのタプル (マシンごとに 1 つのジョブ シーケンス) として表すことができます。重要な点は、ソリューションを変更できるのは「移動」することです。おそらく、この問題については、次の 2 つの基本的な動きで既に適切な解決策を見つけることができます。

  • 1 台のマシンから 1 つのジョブを取得し、それを挿入する新しい場所を見つけます。
  • マシンのジョブ シーケンスで 2 つのジョブを交換します。
于 2015-10-02T10:36:12.113 に答える