□投稿者/ ONnoji -(2010/09/16(Thu) 11:56:24)
| さらに蛇足です。
いろいろググッてみましたが…
どうやら、勤務表を最適化するアルゴリズムのひとつは、「遺伝的アルゴリズム」と呼ばれるもののようですよ。
【引用】システムバンク株式会社 |システムバンクからのお知らせ | 当社の新しい取り組み http://www.sbn.co.jp/0600news/0630torikumi/ 汎用GAエンジンと勤務表作成エンジンGA(Genetic Algorithm)=遺伝的アルゴリズムはメタヒューリスティック(メタヒューリスティクスとは特定の問題に限定されず、どのような問題に対しても汎用的に対応できるように設計された、アルゴリズムの基本的な枠組み)の一部でデータ(解の候補)を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する方法です。 一般的なアルゴリズムを用いたプログラミング、例えば近似アルゴリズムのように厳密な解法による計算方法は、正確な答えをいきなり求めようとするあまり、計算時間が爆発的に増加してしまいます。 ところが答えの範囲をなるべく「答えに近い」まで拡大すると、 計算時間は飛躍的に短縮させることができます。 ただし、 一般的にGAのようなメタヒューリスティクスは特定の問題専用のヒューリスティクスより平均的な解の精度が劣ります。これは汎用的な探索をするためには問題に対する事前知識を必要とせずに実装しなければならないので、それらを有効に使用することで解の探索を行う方法に対してどうしても不利な立場で探索を進める必要があるからです。 当社では、このメタヒューリスティックスの弱点を克服するため、問題専用ヒューリスティックスの組み合わせで「勤務表作成エンジン」を開発し、短時間で正確な「解」を導き出すことに成功しました。 その1つの成果が勤務表作成システム「セルヴィス」です。一般的に看護師の勤務表作成はNSP(ナーススケジューリングプロブレム)として昔から議論されるように、 2次元解の中で最も複雑(勤務表の中で最も作成するのが難しい)と言われています。 当社では上記「勤務表作成エンジン」を組み込んだ「セルヴィス」を普及価格のプロダクトとして流通させています。 この実績は汎用的なGAエンジンをベースに、様々な業種専用のヒューリスティック(セルヴィスは看護師専用のヒューリスティックを実装)を開発することで、あらゆる業種の勤務表作成ソリューションとなり得ることを示しています。 例として、当社の保有する汎用に使えるGAエンジンを現在構築している勤務表作成アプリケーションやシステムに組み込み、専用のヒューリスティックを開発することで、大人数のパートやアルバイト人員を抱える各種工場や、何百の店舗の人員のスケジューリングに最適なシステムを構築することができます。
|
|