3

一度に 1 つのタスクしか実行できない 1 人のワーカー (ただし、タスクを即座に切り替えることができます)

与えられたタスクのリスト
-- 「n 秒、m 秒ごと」 (たとえば、3600 秒ごとに 5 秒) として定義

各タスクの最適な開始時間とカウントを見つけるにはどうすればよいですか?

すべてのタスクが「1 秒、60 秒ごと」の場合、それぞれに固有の開始秒があり、カウントは無限 (定常状態) になります。
「4 秒ごとに 1 秒」と「3 秒ごとに 1 秒」の場合、結果は「0、無限、3、3 回」になります。

-- 願わくば最も単純な形式

「開始秒と回数」で詳述されたタスクのリストが既にある場合、追加の {m 秒ごとに n 秒} タスクに対して {start, count} を返す関数はどのようになりますか?

-- (もう少し複雑な形式 --
「m 秒ごとに n 秒」の代わりに
、タスクが「l..o 秒ごとに n 秒」と定義されている場合
、l - o (しかし、タスクが完了するまでその m にコミットする必要があります)、
それによりワーカーの使用率が向上しますか
?最適な 'm' をどのように選択しますか?

4

4 に答える 4

1

「最高」をどう定義するかにもよると思います。たとえば、「平均して」m 秒ごとにタスクを実行したい場合、ブレゼンハム法と同じ種類のアルゴリズムを使用して線を引く簡単な方法があります (「m 秒ごとに n 秒」のタスクは、線を描くときに、m の水平ステップの間に n の垂直ステップを分散させるようなものです)。各タスクにカウンターとステップ値を割り当てます (「3 秒ごとに 1 秒」の場合、ステップは 1/3 になります)。次に、「サイクル」ごとにカウンターにステップを追加します。カウンターがゼロを超えると、そのタスクが実行されます (カウンターから 1 が減算されます)。ゼロより大きいカウンターが複数ある場合は、最大のものを選択します。これにより、少し複雑なフォームに対しても「十分な」ソリューションが得られる場合があります。

ただし、「1/4」と「1/3」の例は、タスクを「正確に」m 秒間隔で実行する必要があるように聞こえます。リストから始めて、カウントを最大化するために新しいタスクを追加することは、難しい検索問題ではありませんが、これはあなたが必要としているものではないと思います。A(1/4) B(1/4) C(1/2) の例では、A を追加してから B を追加すると、AB xx AB xx が得られます。この場合、C を追加することはできません。

フィットネス関数には明らかな候補があると思います.n,m,startのテーブルには、タスクが1つしかスケジュールされていない時間の部分であるフィットネス関数を含めることができます. GA/アニーリングは、定常状態の解が存在する場合、それを見つける可能性が高いでしょう。しかし、(1/4)、(1/3) のように定常状態の解がないように見える場合、「最良」を定義することで、フィットネス関数も定義する必要があります。

于 2008-11-21T20:48:27.400 に答える
0

うーん、ちょっとした提案があります。m の最大公約数が n の合計以上の場合、解は定常状態です。

m の gcd がその合計以上になるように、n の合計が最大になる一連のタスクを選択します。

于 2008-10-18T19:33:52.693 に答える
0

このタイプの問題は解決が困難ですが、最適化は比較的容易です。Simulated Annealing、Great Deluge、または Genetic Algorithms をご覧ください。

于 2008-10-18T19:27:11.350 に答える
0

w:Scheduling (コンピューティング)を参照してください。リンクには、スケジューリング戦略の優れたリストが含まれています。

[スケジューリング] とは、優先度キューでプロセスに優先度を割り当てる方法を指します。この割り当ては、スケジューラと呼ばれるソフトウェアによって実行されます。スケジューラは主に次のことに関係しています。

  • CPU 使用率 - CPU を可能な限りビジー状態に保ちます。
  • スループット - 時間単位ごとに実行を完了するプロセスの数。
  • ターンアラウンド - 特定のプロセスを実行するのにかかった時間。
  • 待機時間 - プロセスが準備完了キューで待機している時間。
  • 応答時間 - 要求が送信されてから最初の応答が生成されるまでにかかる時間。
于 2008-11-28T07:32:00.997 に答える