1

Django を使用して、人々が上司と会うために特定の時間を割り当てられる小さなスケジューリング Web アプリケーションを開発します。従業員はモデルとして保存され、時間範囲と従業員が空いている曜日を表すモデルとの OneToMany 関係があります。例えば：

Bob: (W 9:00, 9:15), (W 9:15, 9:30), ... (W 15:00, 15:20)
Sarah: (Th 9:05, 9:20), (F 9:20, 9:30), ... (Th 16:00, 16:05)
...
Mary: (W 8:55, 9:00), (F 13:00, 13:35), ... etc

私のプログラムでは、基本的なスケジュール設定が可能です。雇用主は、その週にすべての従業員に少なくとも 1 回会うという条件の下で、会議間のギャップを最小限に抑えて最初の N 個の可能なスケジュールを表示することを選択できます。私は現在、会議のすべての可能な順列を生成し、会議時間に重複があるスケジュールを除外しています。M 個の可能性をすべて経由せずに、M 個の可能なものから最初の N 個のスケジュールを生成する方法はありますか?

明確化: 私たちは、すべての日にわたって合計された、任意の日のギャップの最小合計を取得しようとしています。

4

2 に答える 2

0

一般に、スケジューリング問題は NP 困難であり、この問題を証明するための縮約を見つけることはできませんが、他の多くの有名な NP 完全問題と非常によく似ています。1日の最小ギャップを見つけるための多項式時間の解決策があるかもしれませんが（私もそれを手に負えませんが）、複数日にわたってそれを解決する必要があるという希望はあまりありません。残念ながら、これは複雑な問題であり、完全にエレガントな答えは存在しない可能性があります。(または、後で誰かが投稿したときに自分を蹴るつもりです。)

まず、データセットがかなり小さく、考えられるすべてのスケジュールをかなり迅速に計算できた場合は、そのソリューションに固執することをお勧めします。他のすべては概算であり、最終的には実行時間の定数係数が大きい場合、実行速度が遅くなります。(つまり、データセットのサイズに合わせて大きくならないため、大規模なデータセットでは比較的小さくなります。)

最も単純な近似は、貪欲なヒューリスティックを使用することです。ほとんどの場合、最適なスケジュールを見つけることはできず、ほとんどのスケジュールが重複している場合、解決策を見つけるのに長い時間がかかる可能性があり、有効な解決策でさえあるのはごくわずかですが、これは従業員の時間には当てはまりません。

従業員ごとに 1 つのタイムスロットを無作為に選択して、任意のスケジュールから始めます。反復ごとに、1 人の従業員を選び、現在のスケジュールの残りの部分に関して、そのタイムスロットを可能な限り最適な時間に変更します。結果に満足するまで、このプロセスを繰り返します。このプロセスはほとんどのデータに対してループする可能性が高いため、スケジュールを改善する変更をこれ以上行うことができなくなるまで、おそらく繰り返したくないでしょう。

これは優れたヒューリスティックではありませんが、合理的なスケジュールを生成する必要があり、調整の余地がたくさんあります。重複する時間帯を他の時間帯よりも先に切り替えたり、現在最大のギャップに貢献している従業員を反転させたり、すでに試した特定の時間枠を削除したりすることができます。極小値に達し、そこから抜け出したいという期待を込めて、最適ではない解への移行を許可したい場合があるかもしれません - いくらかのランダム性もこれに役立ちます。これまでに見た最適なソリューションを常に追跡するようにしてください。

より多くのスケジュールを生成するには、別のランダムなスケジュールでプロセスを最初からやり直すことが最も明白です。または、以前に見つけた解決策から任意の回数反転して、そこから繰り返すこともできます。

編集：これはすべて遺伝的アルゴリズムにかなり関連しており、ここで提示したアイデアのいくつかをGAで使用したい場合があります。

于 2013-01-02T04:24:31.163 に答える
0

これを行うには、 A-starなどの検索アルゴリズムを使用します。グラフの各ノードは、個人の利用可能なタイム スロットを表し、あるノードから別のノードへのパスは、部分スケジュールにあることnode_aを意味します。node_b

もう 1 つの解決策は、ノードが各人の空き時間であり、node_a に関連付けられた人物が node_b に関連付けられた人物と同じでない場合、node_a から node_b へのエッジがあるグラフを作成することです。各ノードの重みは、2 つのノードに関連付けられた時間の間の時間です。

このグラフを作成した後、グラフから最小スパニング ツリーのバリアントを生成できます。このバリアントは、次の点で MST とは異なります。

  1. ノードに関連付けられている人がまだ MST にいない場合にのみ、ノードを MST に追加します。
  2. すべての人が MST にいるときに、MST の作成を終了します。

生成される最小スパニング ツリーは、1 つのスケジュールを表します。

他のスケジュールを生成するには、作成したばかりのスケジュールで見つかったすべてのエッジをグラフから削除し、削除したエッジを使用してグラフから新しい最小スパニング ツリーを作成します。

于 2013-01-02T03:17:57.410 に答える