8

私は以前働いていたプールのスケジューリングの問題を解決しようとしばらく試みてきました。この問題は次のように...

プールで働く監視員は X 人いて、それぞれが働きたい特定の時間数を持っています。私たちは、各ライフガードが希望する時間数から平均時間をできるだけ短くし、すべての人にできるだけ公平に保つことを望んでいます. 各ライフガードも大学生であるため、対応可能なスケジュールが異なります。

毎週、プールのイベント スケジュールは前回とは異なるため、毎週新しいスケジュールを作成する必要があります。

毎日、特定の時間間隔で非常に多くの監視員が必要になります (例: 午前 8 時から午前 10 時までは警備員 3 名、午前 10 時から午後 3 時までは警備員 4 名、午後 3 時から午後 10 時までは警備員 2 名)。ここが難しい部分です。ライフガードのそれぞれを配置するための明確に定義されたシフト (スロット) はありません (ライフガードの可用性に加えて、毎週プールのスケジュールが変更される場合、スケジュールを作成できない可能性があるため)イベントの）。

したがって、スケジュールは、提供された白紙の状態から作成する必要があります...

  • ライフガードとその情報 (希望時間数、空き状況)
  • プールのイベントのスケジュールと、常時勤務が必要な警備員の数

この問題は、「必要な数の警備員を毎日常にカバーする可能なスケジュールを作成し、スケジューリングにおいてすべてのライフガードに対して可能な限り公平にする」と明確に定義できるようになりました。

曜日ごとに必要な数の警備員を常にカバーする可能なスケジュールを作成することは、必要であり、完全に解決されなければならない問題の一部です。すべてのライフガードに対して可能な限り公平であることに関する後半は、問題を大幅に複雑にし、概算アプローチが必要になると私に信じ込ませます。公平を期すために、可能なスケジュールのみがばかげている場合があります。

編集：私が見つけた最も一般的に提案されているアルゴリズムの1つは「病院/居住者の問題」ですが、労働者を配置するための明確に定義されたスロットがないため、これが適用されるとは思いません.

4

2 に答える 2

9

これを解決する 1 つの方法は、制約プログラミングを使用することです。ウィキペディアの記事には、いくつかの制約プログラミング言語とライブラリへのリンクが記載されています。 これは、スケジューリングの問題を解決するために制約プログラミングを使用する方法を説明する論文です。

別のオプションは、貪欲なアルゴリズムを使用して (おそらく無効な) ソリューションを見つけ、次にローカル検索を使用して無効なソリューションを有効にするか、最適ではない貪欲なソリューションを改善することです。たとえば、各ライフガードに優先時間を割り当てることから始めます。これにより、一部のスロットに非常に多くのガードがスケジュールされ、一部のガードにばかげた時間数が割り当てられることになります。次に、ローカル検索を使用して、割り当てられた警備員が多すぎるスロットから、時間数が最も多い警備員の割り当てを解除します。

于 2013-06-17T04:14:57.727 に答える
4

公平性の基準を目的関数に変換する必要があります。次に、任意の数の職場スケジューリング ツールから選択できます。たとえば、希望する時間と割り当てられた時間の平均差を最小限に抑えたいと説明します。ただし、最大の差を最小限に抑えることを検討することをお勧めします。これは（私には）より公平に思え、通常は別のスケジュールになります。

ただし、問題はもう少し複雑です。たとえば、1 人の警備員が常に不足しているのに、他の全員が希望する勤務時間を確保している場合、それも不公平です。そのため、前の週からの各ガードの累積不一致を表す変数を公平性モデルに導入することをお勧めします。また、週に 4 時間働きたい警備員の 1 時間の不一致は、20 時間働きたい警備員よりも不公平かもしれません。そのようなことを処理するには、不一致に重みを付けることができます。

特定の時間数を超える警備員が割り当てられていない、すべての警備員がシフト間に一定の時間を持っている、または週に 1 人の警備員に割り当てられるスロット数が必要であるなどの制約を導入する必要がある場合があります。ある閾値を超えないこと。多くのスケジューリング ツールには、この種の制約を処理する機能がありますが、それらをモデルに追加する必要があります。

于 2013-06-17T04:13:48.670 に答える