勤務表作成問題

勤務表を作成するのはいつの時代も大変らしくて遺伝的プログラミングを用いた方法が良いというらしいけれども（調べた限りでは遺伝的プログラミングでは解を求めるのはあまり実際的ではないらしい…）、いくつか論文やホームページを紐解いた中では問題を一般化して解法を求めたものは少ない（フリーで手に入るものとして）。

遺伝的プログラミングはあとで勉強するとして、とりあえずは勤務表作成の方法の検討。

1. 考えられうる組み合わせを全て列挙してそれから条件に合うものをpick upする。
 13人28日間のシフト（6種類）の組み方を考える。
→13*28 = 364
364マスを埋めなくてはならない。
単純に計算すると6^364 = 1.76626206 × 10^(283)であり途方も無い数字になる。

完全にランダムにするわけにはいかない。ある程度厳しい条件をもとにしてランダム作成を擦る必要がある。

一般的な考察を用いた計算により（希望日、シフト回数の条件下で、詳細は省略）
((26 !) / ((8 !) * (3 !) * (12 !) * (3 !)))^13 = 8.4133218 × 10^(152)
まで減少したが依然として多い…。

しかし優先度の高い「ゆるい条件」（後述）を加えた計算をすれば、ある程度現実的な（数万個程度が理想）数に落とせるかもしれない。条件がなければ大変だが、そもそもそんな勤務表だったら作るのは難しくないだろう。

→ゆるい条件をいかにして取り込むかが課題。

2. 絶対に変えられない項目を埋めていき、後は制約ルールに基づいてランダムにシフトを埋めていきながら変更を加える方法
変更は殆どの場合、二箇所の変更になるから（どちらかとどちらかを入れ替える）変更後にそれぞれルールに合致するかどうかを確認する。ただ、この場合完成していない勤務表ではすべての制約の確認ができないこと（連続７日間の郎度はできない、連休が1回以上あるなど）がネックになる。

制約条件について
いくつかの研究では「絶対条件」「相対条件（であれば望ましい）」を規定している。なかには絶対条件と相対条件の中間（ゆるいけど、比較的優先的なもの）を規定しているものもある。また相対条件を重要度に比してスコアリングして総合的に満足の行くものを作ろうというものもある。
また条件も一人のシフトスケジュール間の条件と、各日のスケジュールの条件の二種類があり、都合4種類の条件に分けられそう。

まあ多くの人がいろいろ挑戦して「難しい」という結論が出ているくらいだからあれだけど、最適解かそれに近い解のプログラムは作れそうな気がする。