21

病院の看護師にシフトを最適に割り当てるアプリケーションを開発しています。これは離散変数を使用した線形計画法の問題であり、したがっておそらく NP 困難であると思います。

  • 毎日、各看護師 (約 15 ～ 20 歳) にシフトが割り当てられます。
  • 少数 (約 6) の異なるシフトがあります。
  • 1 日に関して、または従業員に関して、かなりの数の制約と最適化基準があります。
    • 毎日、各シフトに割り当てられる最小人数が必要です
    • 一部のシフトは重複しているため、中間シフトを行っている人がいる場合は、早いシフトの人が 1 人少なくても問題ありません。
    • 早いシフトを好む人もいれば、遅いシフトを好む人もいますが、より高いシフト勤務賃金を得るには、最小限のシフト変更が必要です。
    • ある日は遅番、翌日は早番で働くことは認められていません（最低休憩時間の規定による）。
    • 割り当てられた週の勤務時間のミーティング (人によって異なります)
    • ...

したがって、基本的に、それぞれが少数の離散値を取ることができる多数の (aout 20*30 = 600) 変数があります。

現在、私の計画は、修正されたMin-conflicts アルゴリズムを使用することです

  • ランダムな割り当てから始める
  • 一人一人、毎日のためのフィットネス機能を持っています
  • 最悪のフィットネス値を持つ人または日を選択します
  • その日/人の割り当ての 1 つをランダムに選択し、最適なフィットネス値をもたらす値に設定します
  • 繰り返しの最大回数に達するか、選択した日/人に改善が見られなくなるまで繰り返します

より良いアイデアはありますか？局所最適に陥ってしまうのではないかと少し心配です。何らかの形式のシミュレーテッド アニーリングを使用する必要がありますか? それとも、一度に 1 つの変数を変更するだけでなく、具体的には 2 人の間でシフトを切り替えること (現在の手動アルゴリズムの主要コンポーネント) を検討しますか? 変更される可能性があるため、現在の制約に合わせてアルゴリズムを調整することは避けたいと思います。

編集:厳密に最適なソリューションを見つける必要はありません。名簿は現在手動で作成されており、ほとんどの場合、結果はかなり最適化されていないと確信しています-それを打ち負かすのは難しいことではありません. 短期的な調整と手動によるオーバーライドも間違いなく必要ですが、これが問題になるとは思いません。過去の割り当てと手動割り当てを「修正済み」としてマークすると、実際には、ソリューション スペースが減り、タスクが単純化されます。

4

9 に答える 9

12

これはうまく解決するのが難しい問題です。特にオペレーションズリサーチの分野では、このテーマに関する多くの学術論文があります。たとえば、2007年から2008年のナース名簿作成論文、または単にグーグルの「ナース名簿作成オペレーションズリサーチ」を参照してください。複雑さは、次のような側面にも依存します。解決する日数。看護師はどのような種類の「要求」を行うことができますか。名簿の「循環」です。それは長期的な計画ですか、それとも病気や交換などの短期的な名簿の「修理」を処理する必要がありますか。

説明するアルゴリズムは、ヒューリスティックなアプローチです。問題の特定のインスタンスに対してうまく機能するように調整できる場合がありますが、「何か」が変更されるとすぐにうまく機能しない場合があります（たとえば、局所最適、収束不良）。

ただし、そのようなアプローチは、特定のビジネスニーズに応じて適切な場合があります。たとえば、最適なソリューションを取得することの重要性、同じままであると予想される問題の概要、潜在的な節約（お金とリソース）、重要性などです。名簿の質に対する看護師の認識、この仕事の予算などです。

于 2009-02-21T21:05:49.180 に答える
4

うーん、ILPソルバーの中にはかなり良い仕事をしている人がいることをご存知ですか？AIMMS、Mathematica、またはGNUプログラミングキットをお試しください！600変数はもちろん、Lenstraの定理が簡単に解くよりもはるかに多くなりますが、これらのILPソルバーはうまく処理できる場合があり、AIMMSでは分岐戦略を少し変更できます。さらに、ILPには非常に高速な100％近似があります。

于 2009-02-21T20:57:39.387 に答える
3

最近、大規模な製造工場のシフト割り当ての問題を解決しました。最初に、純粋にランダムなスケジュールを生成し、is_schedule_validテストに合格したスケジュールを返すことを試みました - フォールバック アルゴリズム。もちろん、これは遅く、不確定でした。

次に、遺伝的アルゴリズムを試しましたが（あなたが提案したように）、実行可能な解決策を閉じる適切なフィットネス関数を見つけることができませんでした（最小の変更により、スケジュール全体が正しいか間違っている可能性があるため、ほとんどポイントはありません）。

最後に、次の方法を選択しました (うまくいきました!)。

  1. 入力セット (ジョブ、シフト、スタッフなど) をランダム化します。
  2. 有効なタプルを作成し、暫定スケジュールに追加します。
  3. 有効なタプルを作成できない場合は、最後に追加されたタプルをロールバック (およびインクリメント) します。
  4. 部分的なスケジュールをテストする関数に渡しますcould_schedule_be_valid。つまり、残りのタプルが可能な方法で満たされている場合、このスケジュールが有効であるかどうかをテストします。
  5. の場合!could_schedule_be_valid、(2) で追加されたタプルを単純にロールバック (およびインクリメント) します。
  6. もしschedule_is_complete、return schedule
  7. 後藤 (2)

このようにして部分的なシフトを段階的に構築します。利点は、有効なスケジュールの一部のテストはステップ 2 (事前テスト) で簡単に実行でき、他のテストはステップ 5 (事後テスト) に残す必要があることです。

幸運を。最初の 2 つのアルゴリズムを試すのに何日も費やしましたが、5 時間以内の開発で有効なスケジュールを即座に生成する推奨アルゴリズムを取得しました。

また、アルゴリズムが尊重する割り当ての事前修正と事後修正をサポートしました。ステップ 1 でこれらのスロットをランダム化しないだけです。ソリューションが最適に近い場所である必要はないことがわかります。私たちのソリューションは最低でも O(N*M) ですが、PHP(!) では製造プラント全体で 0.5 秒未満で実行されます。could_schedule_be_valid優れたテストを使用して、悪いスケジュールを迅速に除外できる点が優れています。

手動で行うことに慣れている人は、1 時間かかっても気にしません。もう手動で行う必要がないことを知っているだけです。

于 2009-02-21T21:52:20.940 に答える
2

マイク、

これに対する良い答えが得られたかどうかはわかりませんが、制約プログラミングがチケットであると確信しています。GA は答えを与えるかもしれませんが、CP は多くの答えを与えたり、実行可能な解決策がないかどうかを教えたりするように設計されています。「制約プログラミング」とスケジューリングで検索すると、多くの情報が表示されます。これは比較的新しい分野であり、CP 法は、従来の最適化法が行き詰まる多くの種類の問題でうまく機能します。

于 2010-01-28T20:54:42.533 に答える
0

あなたができることの一つは、問題の対称性を探すことです。たとえば、問題の目的のために、すべての看護師を同等として扱うことができますか？もしそうなら、あなたは任意の順序で看護師を考慮する必要があるだけです-あなたはi > jである看護師jの前に看護師iがスケジュールされるような解決策を考慮することを避けることができます。（あなたは、個々の看護師がシフト時間を好むと言っていましたが、これはこの例と矛盾しますが、おそらくそれはそれほど重要な目標ではありませんか？）

于 2009-02-21T21:05:29.833 に答える
0

動的プログラミング風？部分問題の重複、最適な部分構造など、そのための場所があるように思えます。

于 2009-02-21T20:41:36.460 に答える
0

次の理由から、遺伝的アルゴリズムを使用する必要があると思います。

も見てください：同様の質問と別の質問

于 2011-01-04T14:46:19.003 に答える