問題タブ [resource-scheduling]

問題 ：

A から E までの 5 つのバッチ ジョブがほぼ同時にコンピューター センターに到着します。実行時間は 10 分、6 分、2 分、4 分、8 分と見積もられています。それらの (外部で決定された) 優先順位は、それぞれ 3、5、2、1、および 4 であり、5 が最高の優先順位です。プロセスの平均所要時間を決定します。プロセス切り替えのオーバーヘッドを無視します。ラウンド ロビン スケジューリングでは、システムがマルチプログラミングであり、各ジョブが CPU を公平に配分すると仮定します。すべてのジョブは完全に CPU バウンドです。

解決策 #1次の解決策は、このページからのものです。

ラウンド ロビンの場合、最初の 10 分間、各ジョブは CPU の 1/5 を取得します。10 分が経過した時点で、C が終了します。次の 8 分間、各ジョブは CPU の 1/4 を取得し、その後 D が終了します。次に、残りの 3 つのジョブのそれぞれが、B が終了するまで 6 分間、CPU の 1/3 を取得します。5 つのジョブの終了時間は 10、18、24、28、30 で、平均 22 分です。

解決策 #2次の解決策は、ここのコーネル大学から提供されていますが、これは異なります (そして、これは私にとってより理にかなっています)。

ターンアラウンド タイムとは、ジョブが到着してからジョブが完了するまでの時間です。すべてのジョブが時間 0 に到着すると想定しているため、ターンアラウンド タイムは単純にジョブが完了する時間になります。(a) ラウンド ロビン: 以下の表は、各タイム クォンタムで処理されるジョブの内訳を示しています。* は、そのクォンタム中にジョブが完了することを示します。

結果は異なります。たとえば、最初の例では C は 10 分後に終了しますが、2 番目の例では C は 8 分後に終了します。

どれが正しいのですか、なぜですか? 私は混乱しています..事前に感謝します!

最適化の問題があります。20個の部品が入った商品のことです（製作順は問いません）。20 個すべての部品を製造できる同様の機械が 3 台あります。

20 パーツを数分で表現しました (つまり、最初のパーツを作成するのに 3 分、2 番目のパーツを作成するのに 75 分かかります)。

したがって、1 つの製品を製造するには 730 分かかります。

3 台の機械に良品を割り付けることで、1 台の製品の生産量を最小化することを目的としています。

したがって、実際には 243.333 分 (730/3) に近づける必要があります。

可能性の量は巨大です 3^20

さまざまな最適解があると思います。私はRがそれらすべてを私にくれることを望みます。マシン 1 2 と 3 を必要とする合計時間を知る必要があるだけでなく、マシン 1、マシン 2、およびマシン 3 にどのアイテムを渡すかを知る必要もあります。

または、長すぎる場合は、できるだけ合理的な繰り返しのないサンプルを選択したいと思います...

R 言語で問題を解決できますか?

開発者が多数の異なるプロジェクトでチームで作業しているソフトウェア会社があるとします。プロジェクトには、割り当てられた開発者の特定のスキルが必要です。私の目的のために、私はそれをシンプルに保ち、これを 1 つのスキル、つまりプログラミング言語に限定したいと考えています。そのため、Java が必要なプロジェクトもあれば、C が必要なプロジェクトもあります。プロジェクトの期間は決まっており、各プロジェクトには 2 人の開発者を割り当てる必要があります。

いつでも、いくつかのプロジェクトが進行中で、新しいプロジェクトが入ってきて、将来のある時点で計画する必要があります。どの開発者がいつ、どのプロジェクトに取り組むべきかのスケジュールを計算したい。

私は最適な解決策を探しているわけではありません (それが可能であれば)。人間のマネージャーが作成できるスケジュールで満足しています。

Resource Constrained Scheduling Problems と Assignment Problems に関する記事を読んだことがありますが、正式な CS トレーニングはほとんど受けていないため、これらの問題のさまざまなバリエーションのすべてのニュアンスをよく理解していません。

私の問題は、ジョブがプロジェクトであり、開発者がマシンであるジョブショップスケジューリングのより単純なバリエーションであると思います。そのため、ジョブには同時に複数のマシンが必要です。実行中のプロジェクトは中止できないため、最初に終了する必要があるという先行制約が 1 つだけあります。

私が読んだすべての可能なソリューションから、私は遺伝的アルゴリズムを使用する傾向があります. 線形計画法の良い結果についても読んだことがありますが、それについてはほとんど知りません。

遺伝的アルゴリズムは、この種の問題に対する実行可能な解決策ですか? または、より良い解決策はありますか？

Ubuntu12.04で次の動作を確認しました。

24GBのRAMと24個のCPUを搭載したシステムでは、1つのプロセスが最大12GBのRAMを取得すると、高メモリプロセスの所有者に属する他のすべてのプロセスが、SIGKILLと思われるものと高メモリプロセスを使用して、警告なしに強制終了されます。終了するまで実行できます。さらに、所有者による新しいプロセスの開始の試みは失敗します。

これは少し面倒ですが、なぜそれが起こるのかについてもっと興味があります。おそらく、これはカーネルでのリソーススケジューリングの決定の結果です。これに関するドキュメントを見つけることができる場所はありますか？

次の問題があり、それを処理するためのアイデアが必要です。

1. 私は個人が所有する多数のバス (約 150 台) を持っています。各個人が自分のバスを運転します (またはバスの運転手に責任があります)。バスと運転手は同じものなので、バスの運転手を気にする必要はありません。

2. 上記のバスは、毎日 (約 200 本) バス ルートを「実行/実行」する必要があります。

3. バスは毎日 1 つ以上のルートを運行できます

4. バスは通常、週に 5 日、1 日 (または 1 か月) に一定の時間働くことができます。

5. 3 か月ごとに毎日のルートを配布する公正な方法を見つけなければなりません。Fair とは、3 か月の期間の終わりに、すべてのバスが同じキロ数を走行したことを意味します (各バス ルートには一定のキロ数が割り当てられます)。

6. 「特別なこと」は毎日起こるので、最初は3か月全体のスケジュールを立てることができません。バスに問題があるように、運転手にも問題があります..これは、今日、次の日のスケジュールを実行することを意味します.

何か案は？

非 CPU リソースのスケジューリングに関するエッセイを書かなければなりません。これが何を意味するのかについての情報を見つけることができません。

スケジューリングと負荷分散のアルゴリズムについて考えていて、面白いと思う問題を思いつきました。

N 個のケージと M 個の飼育係がいます。各ケージのサイズは S で、動物の数は A です。ケージを掃除する必要がある頻度は、A / S の関数として計算されます (動物が多く、ケージが小さいほど汚れが早くなります)。ケージの掃除の難しさは、A と S の他の関数として計算されますが、その詳細は重要ではありません (ケージのサイズが難しさのほとんどに寄与し、動物の数が少し寄与します)。3 日に 1 回、清掃が予定されているケージを清掃します (「清掃日」)。Zookeepers は完全に同一であり、交換可能です。飼育係は、清掃の日に同じ量の作業を行う必要があり、他の飼育係よりも多くの作業を行う必要はありません。ケージを掃除するのにかかる時間は問題の一部ではありません (時間は難易度によって大まかに反映されると想定されますが、

スケジューリング アルゴリズムは、次のように、清掃日にどのケージを清掃するかを各飼育係に通知する必要があります。

• 各ケージは理想的な頻度で、または可能な限り近い頻度で洗浄されます。
• 清掃日ごとに飼育係ごとに最小限の、ほぼ同数の清掃を割り当てること、
• すべての飼育係にできる限り均等な作業負荷を保証する (つまり、一定期間にわたって、各飼育係の作業負荷の総計の困難は可能な限り等しくなり、ケージは飼育係間でおよそ 1/M の確率で分散される)。

このような最適化問題の近似アルゴリズムはどのようになるのだろうかと思っています。これは、NP 困難なスケジューリング/リソース使用の問題のいくつかの異なる古典的な例に似ています。多分それはそのような問題の1つに還元可能であり、私はそれを見逃しています。タスクの頻度/周期性要素を取り除くと、従来のマルチプロセッサ スケジューリングまたは有限ビン パッキングの問題に似ています。

この問題を解決するにはあなたの助けが必要です。一連のタスクがあり、各タスクには実行時間があります。2 種類の制約があります。最初のタイプは、タスク間の優先関係です。2 番目の制約タイプでは、一連のタスクを同時に実行できます。例：6つのタスクと次のエッジ（T1、T2）、（T2、T3）、（T4、T3）、（T4、T5）、および（T6、T5）を持つグラフGがあります。T1、T4 は一緒に実行でき、T1、T6 も実行できますが、T4、T6 は実行できないとします。各タスクの実行時間を考慮します。いくつかのタスクの並列実行を考慮して、タスク間の優先関係を満たし、スケジュールの長さを最小限に抑えるスケジュールを見つける方法。

最長の重複しないシーケンスを見つけるアルゴリズムに非常に似た質問があります。

リンクされた質問との唯一の違いは、最長シーケンスを表す重複しないタプルのセットを見つける代わりに、最大カバレッジを表す重複しないタプルのセットを見つける必要があることです。タプルの長さは最大です (タプルの長さは、次の文でタプルlast - first + 1の定義が与えられています)。

リンクされた問題とは異なる方法でタプルを表現します。の代わりに(starting index, length)、タプルを(first, last);として表します。たとえば、タプル(3,7)は数値のセットを表します[3, 4, 5, 6, 7]。(エンドポイントが一致していても、タプルは別のタプルとオーバーラップします。つまり、オーバー(2,6)ラップ(6,8) するため、ソリューションに両方を表示することはできません。)

例として、 でソートされた次のタプルのセットを考えてみましょうfirst:

[(0,100), (2,50), (30,150), (60,95), (110,190), (120,150), (191,200)]

ここでの最大セットは[(0,100), (110,190), (191,200)]、 のカバレッジになり101 + 81 + 10 = 192ます。(このソリューションのタプルは重複していないことに注意してください。)

これを解決するための最も複雑でないアルゴリズムの例は何ですか?また、そのアルゴリズムの複雑さはどのくらいですか? (これが で解決できれば最高ですがO(N)、それが可能かどうかは現時点ではわかりません。)

補遺:振り返ってみると、私がここで尋ねている質問は、重み付き間隔スケジューリング問題と同等であることがわかりました。これは、間隔スケジューリング問題の特殊なケースです。

以下の@j_random_hackerの答えは、実際には、重み付けされた間隔のスケジューリング問題に対する既知の解決策であり、時間の複雑さはO(N log(N)).