8

メンバーのジョブをローテーションスケジュールで自動的にスケジュールする必要があるアプリケーションに取り組んでいます。私はルールを説明するのがあまり得意ではないので、ここに役立ついくつかのデータがあります：

役職：毎週月曜日や水曜日などのルールを持つ役職。
カテゴリ：ポジションのセット
グループ：別のポジションのセット。同じグループのポジションを同じ日に割り当てることはできません
メンバー：特定の日にポジションに割り当てられたユーザー。

その月の各日付について、メンバーはポジションに割り当てられます（両方とも昇順）。メンバーが1つのカテゴリの位置に割り当てられている場合、次に同じカテゴリの位置が表示されると、アルファベット順（またはリストの先頭）に次のメンバーが割り当てられます。

メンバー：M1、M2、M3、M4
カテゴリーC1のポジション：P1、P2、P3
ポジションP1のメンバー：M1、M2、M3、M4
ポジションP2のメンバー：M1、M2、M3
ポジションP2のメンバー：M1、M3、 M4

M1がP1に割り当てられている場合、次にP2が来ると、M2が割り当てられます。代わりにP3が次に来る場合、M3が割り当てられる、複雑さの追加レイヤーが導入されます。システムは、M2が「スキップされた」という事実を追跡し、利用可能な場合は次にM2を割り当て、次にM4を割り当てるか、M2が利用可能な位置に到達するまで待機する必要があります（スキップされた数が多い場合、これはさらに複雑になります） 'メンバー）。

メンバーは、その日に利用できないことを示した場合もスキップされます。システムは、スキップされたメンバーを優先し、メンバーが現れたときに何らかの方法でそれらを識別してから、リスト内の次の論理的な人物にジャンプする必要があります。日付の衝突によるグループにもスキップが適用されます。

各ステップを説明するコメントがたくさんあるのに、私はすでに一時的な[そして厄介な]解決策を持っていますが、それはもはや理解できません。その弱点は、スキップされたメンバーに対処することです。

これをコーディングする場合、どのようにコーディングしますか？私はこれをPHPで実装していますが、擬似コードも同様に機能します。

4

3 に答える 3

6

私の解決策: PriorityQueue が必要です (これは PHP の SplPriorityQueue で利用できます)。PriorityQueue は、降順の優先度を持つ要素を提供します (値でソートされ、最小値が最高の優先度になります)。

各メンバーは割り当てられた値を取得します。この値は、n 桁 (便宜上 8 桁を使用できます) の ASCII 数値であり、n 桁までゼロで埋められます。その後、名前を追加します。また、各メンバーに利用可能なポジションを追加します

したがって (n=5):

  • M1 値: 99999Albert P1、P2、P3
  • M2 値: 99999Susi P1,P2
  • M3 値: 99999ボブ P1、P3

これにより、メンバーを優先順位と名前で簡単に並べ替えることができます。

準備：

晴れの日。特定の日の割り当てられた位置とカテゴリを取得しています。各メンバーは長いリストにロードされます。仕事に出ていない各メンバーはロードされませんが、値がマイナス 2 減少します。Bob はここにいないため、新しい値は 99997Bob になります。つまり、次回は Bob が自動的に選択されます。他のすべてのメンバーの値はマイナス 1 減らされます。

特定の日に割り当てられた位置がマップされます (SplObjectStorage を使用):

P1->M1、M2、M3、M4など P2->など

マップには、その日に割り当てる必要のある位置のみが含まれています。後に

フィルター: グループを検索し、その日に割り当てることができないマップ上の位置を削除する必要があります。あなたのグループの説明は少し不明確です。

割当：

  • 配属先は自分で選ぶ
  • ポジションを埋めることができるメンバーのリストを取得する
  • 利用可能なメンバーをリストから削除し、それらを PriorityQueue に入れます
  • PriorityQueue から extract() によって位置を割り当てます (正しい割り当ては自動的に行われます)。割り当てられた各メンバーは、その値が 1 増加します (したがって、ここにいて作業している場合、減少と増加は横ばいになります)。あなたがここにいて、何らかの理由で役職に割り当てられていない場合、1の小さなペナルティを受けます. ここにいない場合は、2 のペナルティを受けます。
  • 完了後、残りのメンバーを再びリストに追加し、PQueue をクリアして、次の割り当てに進みます。

警告:

  • ポジションに常に十分な人数がいるように注意する必要があります。
于 2010-01-02T15:10:45.320 に答える
1

うーん。私はあなたの説明には従いませんが、同様の状況で、SQLを使用してこの種の問題を解決しました。PHP を使用している場合は、SQL を使用できると思います。

私がお勧めするのは、この情報を一連のテーブルに格納する方法を見つけてから、どの SQL クエリで必要な答えが得られるかを調べることです。多くの場合、手続き型言語よりも SQL の方がはるかに簡単です。

たとえば、スキップされた部分については、誰かが最後に割り当てられた日時を記録する列があり、それによって並べ替えることができます (長い間割り当てられていない人を選択するため)。または、スキップされた回数を列として並べて並べることもできます。

于 2009-12-19T12:09:45.323 に答える
0

私が理解しているのは、「m」人のメンバーと「n」人のポジションがあるということです。

カテゴリ: 役職のグループ -- カテゴリ内のある役職を割り当てられたメンバーは、別の役職を持つことはできませんか?

グループ: ポジションのグループ -- 同じグループ内のポジションは、別の日に割り当てる必要があります。

最後に、Position には、それを埋めることができるメンバーのリストがあります。

これをデータ構造の観点から見ると、メンバーをリンクされたリストに入れます。各メンバーには、最終的に割り当てられる [位置、日] の追加リストが必要です。次に、ポジションごとに、そのポジションを埋めることができるメンバーへの参照のリストを作成します。カテゴリを、そのポジションがどのカテゴリに属しているかについての参照の別のリストとして実装します。

実際の割り当て: 日カウンター = 0 を持ち、位置を繰り返します。位置 P ごとに、それを埋めることができるメンバーを反復処理します。メンバー M は、次の場合にそのポジションを埋めることができます。

  • 彼が P2 に就いたポジションは、P とカテゴリを共有しません。
  • 彼が P2 を day = daycounter で満たしたポジションは、P とグループを共有しません。

彼がポジションを埋めることができる場合、[ポジション、日] ペアがメンバーに追加され、メンバーのノードがリストの END に移動されます (これが参照が必要な理由です。ノードが移動しました)。これにより、「スキップされた」メンバーに最高の優先度が与えられ、到達しなかったメンバーには次に高い優先度が与えられます。

ポジションが満たされたら、次のポジションに移動します。ポジションがすでに割り当てられているポジションとグループを共有している場合は、それをスキップし、1 日目にできるだけ多くのポジションを割り当てることができるまで、すべてのポジションを繰り返します。次に、デイ カウンターをインクリメントし、2 日目も繰り返します。すべてのジョブに対する最大の割り当て (最大については不明)。

ヒント: メンバーをメンバー リストの最後に移動するときは、リストをトラバースする必要がないように、最後への参照を保持します。全部。

于 2010-01-02T17:16:29.177 に答える