開発スケジュール変更

大規模な手持ちプロジェクトが、未だコンパイル出来ていません。
ソフト制約の実装が予想外に難しく、設計開発に手間取っているためです。

ソフト制約の実装は、例えば、Smetさんの論文のような手法があるのですが、
これを、任意のパターンに適用するのは、かなり難しいです。

https://people.cs.kuleuven.be/~pieter.smet/

例えば、5日連続勤務禁止は、
W=勤務として、次のように制約できます。

!(WWWWW)

これをDAGで表現するには、前のステートを覚えておく必要があります。単純にW→Wとするグラフでは、表現できません。一方で、夜勤集中禁止
のように夜勤＝N、N=S|Jとして、

!(N*N)
!(N**N)
!(N***N)

という制約も同時に満たさなければいけません。さらに、それに対してソフト制約も加わる..
となると、大変なState数になりそうだ、ということが分かると思います。特にシフト数が大きいインスタンスでは、指数関数的にステート数が増えてしまいます。これがシフト数が大きいと探索に時間のかかる理由です。Smetさんの論文では、「連続勤務制約の影響が大きい」と言及されていますが、それは、DAGのステート数が直接に影響していると考えます。　ナーススケジューリング問題の多くは、NP-Hardであるとされていて、問題の規模が少し大きくなると、現実的な時間では解けない種類の問題と認識されています。勿論、解ける・解けないの境界は、計算機やアルゴリズムの進歩で変わってきます。アルゴリズムの改良によって解ける範囲を少しでも広げようと努力しているのが現在の研究動向です。

アカデミックベンチマークと勤務表ソフトとの違いは、「任意のシフトパターンを定義できるか否か」です。インスタンスがStaticに決まっているアカデミックベンチマークと違い、ユーザは任意のシフト、任意のシフトシーケンスを定義でき、さらにソフト制約まであるので、そのどれにも対応できる能力が求められます。（それが、現実に出来ているScNurseが素晴らしいということでしょう。）

実は、ソフト制約によって、探索空間は一挙に大きくなります。この辺りの理論的な解析は、あまりみかけたことがありません。こちらは、実プロジェクトに基づいた知見と、今回の成果がありますので、まとめ後に報告したいと思います。

ようやく、実装に目処がついたので、次のようにスケジュールを変更します。

１）手持ちベンチマークで検証　 12月
２）NS2ベンチマークで検証　　　1月
３）NS1ベンチマークで検証   　　1月    
４）まとめ　　　　　　　　　　　　　　 2月
５）実装ベータ版公開　　　　　　　2月
６）英語サイト公開　　　　　　　　　　3月
７）DSL作成～　　　　　　　　　　　　4月