私は医師のスケジューリング アプリケーションに取り組んでいます。線形計画法と cplex/lindo などのソルバーを使用してモデルを解決しています。いくつかのモデリングの制限により、夜勤のみのバイナリ パターンを生成する必要があります。
通常、1 か月のスケジュールを生成するため、夜勤の 30 日間のパターンを生成する必要があると考えてみましょう。
夜勤には、人が連続して夜勤に来る場合、医師は次の 5 日間働くことができないなど、いくつかの制約があります。以下は制約の例です。
111000001111100000111110000011 Valid
111000001100000000111110000011 Valid
111010001111101000111110000011 Invalid
また、パターン内の 1 の数が定義された値より少なくなければならない、連続する 1 の数が定義された値より少なくなければならないなど、他の制約もあります。
最初に、0から開始し、ビット単位の演算子を使用して1つ追加して次の順列を取得し、有効でない場合はすべての制約に対して次の順列をチェックする単純なアルゴリズムを試しました。次の順列を取得し、無効なパターンを無視します。このパターンの長さは 30 ビット (2 30 = 1073741824) であるため、チェックするパターンの数が非常に多くなり、単純なアルゴリズムに進みます。すべての有効なパターンを見つけるには、24 時間以上かかると思います。
今私の質問は
時間効率の良い方法で制約が適用されたすべての順列を見つける特定の問題にどのアルゴリズムを使用する必要がありますか?
この問題は正確なカバーの問題ですか? 直面している問題にリンクを踊るようなアルゴリズムを適用できますか?
この問題に対して提案する解決策について読むためのリンクをいくつか提供してください。