0

以下の問題に適したアルゴリズムを教えてください。

特定の 3 か月間に有限数のプロジェクトがあります (通常は 50 未満)。各プロジェクトには時間数があります。

同じ 3 か月間に有限数のリソース (通常は 100 未満) があります。

各リソースは、1 か月あたり固有の時間数を消費できます (休日、個人的な休暇などを考慮して、この 1 か月あたりの時間数はリソースごとに事前に計算されており、利用可能です)。

1 つのリソースを複数のプロジェクトに割り当てることができます。

これは、プロジェクトをビン、リソースをオブジェクト、時間をオブジェクト ボリュームと見なすと、ビン パッキングの問題がひっくり返ったようなものだと思います。少なくとも 2 つのことが、正式なビン パッキングの問題から逸脱しています。

  1. リソースは流動的なオブジェクトであり、あるビンに数時間、別のビンに数時間滴下する可能性があります。
  2. 最適な解決策は、使用されるビン (プロジェクト) の数を最小限に抑えることではなく、リソースがプロジェクト間で自分自身を分割しなければならない回数を最小限に抑え、すべてのプロジェクトが確実に使用されるようにすることです。

ビンパッキングアングルでガチョウを追いかけているような気がします。これにもっと適したアルゴリズムはありますか？

4

1 に答える 1

1

あなたが描いたように世界が本当にシンプルなら、単純なキューで制約が満たされるように思えます。プロジェクトが到着したら、それらをキューに入れます。開発者が利用可能になると、キューの先頭から取得します。この方法で完了できないほど大きなプロジェクトがある場合にのみ、複数の開発者を割り当てる必要があり、これを検出してバックトラックして 2 人の開発者を割り当てることができます。

しかし、これらはすべて、開発者間の調整、ハンドオフ、依存関係 (他の何かを行う前に最初に行う必要があること)、有能な開発者は異なるスキルと経験を持っているという事実を無視しています。最大 10 倍の速度差があります。

于 2012-04-12T20:01:41.200 に答える