2010年7月30日金曜日

勤務表作成問題について

まだ自分の中で答えは出ていないけれども勤務表作成問題について適当に調べた結果。

・遺伝的アルゴリズムを使用した場合はなかなか解にたどり着くのが難しい
・制約プログラミングを使用した例ではまずまずうまく行っているみたい
・解を求めることができるとしているソフトが市販されている(結構高いしtuningが必要らしいけど)

自分の課題。

・制約プログラミングを使って解を求める
・いろいろな論文を探したが、ほとんどは「ある特定の」条件下で実験であり(まあアルゴリズムの懸賞だからそれでいいのだろうけど)、普遍的に通用するルールに付いてはまだ規定されていない

まだ自分の中でどういうアルゴリズムを持ってすれば現実的な時間で現実的な解を求められるかは分からない。しかし、これからいろいろ考えていく上で、まずは検証を行うソフトの開発、そのためにそもそも勤務表を作成する段階でどのようなパターンが考えうるか、突き詰めていけば複数のパターンで説明が可能なはずでそれを追求すべし。

個人的には何万枚か(ゆるい制約のもと)ランダムに勤務表を作ってそれから合致するモノを選び出したらいいんじゃないかなと思っているが、そう簡単には行かないのだろう。

2010年7月27日火曜日

勤務表作成問題

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

遺伝的プログラミングはあとで勉強するとして、とりあえずは勤務表作成の方法の検討。
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. 絶対に変えられない項目を埋めていき、後は制約ルールに基づいてランダムにシフトを埋めていきながら変更を加える方法
変更は殆どの場合、二箇所の変更になるから(どちらかとどちらかを入れ替える)変更後にそれぞれルールに合致するかどうかを確認する。ただ、この場合完成していない勤務表ではすべての制約の確認ができないこと(連続7日間の郎度はできない、連休が1回以上あるなど)がネックになる。
制約条件について
いくつかの研究では「絶対条件」「相対条件(であれば望ましい)」を規定している。なかには絶対条件と相対条件の中間(ゆるいけど、比較的優先的なもの)を規定しているものもある。また相対条件を重要度に比してスコアリングして総合的に満足の行くものを作ろうというものもある。
また条件も一人のシフトスケジュール間の条件と、各日のスケジュールの条件の二種類があり、都合4種類の条件に分けられそう。

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

2010年7月22日木曜日

Something new

結局なんだかんだ言って今月も無事に終わろうとしている。

ちょっと早いって?

来年の就職先探しの話題が(といってもどこにしようかという話題だけが)よく出るけど、今日ひとつの会社に応募してみた。

ソフトウェア(電子カルテ?オーダリングシステム?の受注をしている)会社らしい。

もちろんそこに決めたわけじゃないし、そもそも自分のような人材を民間の一企業が必要としているのか定かではなくて、それが知りたくて応募した、というのもある。

条件が良ければ入社する可能性もあるしもしかしたら、話をする前に門前払いかもしれない。

どちらにしろ、自分にとってはchallengingでbrandnewなeventには違いない。

面接に来いといわれたらどうしようか…。来月は忙しいので無理ですなんて言えるかなぁ。。

まぁ最悪落ちたとしても普通に病院に就職すればいいだし、今の自分にとって失うものは(ちょっとした自尊心以外)ないのであまり問題ないか。

とある産婦人科医の奥さんの占いで「あなたは20代は民間企業で働いた方がいいわよ。その後大学に行ったらいいわ」なんて言われたからそういうふうに動いてみたけど、果たして吉と出るか凶とでるか。

「新しい」にはnew, brandnew, epoch-making, innovativeなどなどいろいろ言えるけど、brandnewという単語が好き。

さて、救急で来た人の結果が揃ったらしいので行くか。

2010年7月13日火曜日

Outline processor

最近は勉強したことをアウトラインプロセッサ(Story Editorというもの)に書くようにした。

昔自分が勉強したこと、例えばプログラミング、語学なども少しずつではあるけれども、まとめなおしている。

これまではパソコンの何処かに保存しておけば、なくなることはないし、google desktopなんかはそんな発想。だからとりあえず保存しておけばいいじゃん。

それが多分今の時代かと思っていた。

でも実際はなかなかうまくいくことはなくて、自分が欲しい情報は「これとその周辺」みたいなかなり曖昧な求め方だったりするしやっぱりなぜかなくなってたりする。

下手にいろいろファイルを作ると細切れの多数のファイルが出てきて整理したくなる。

というわけでアウトラインプロセッサなのだけれども、今のところ非常に使いやすい。

ふと語学関連の項目を作ってもさっと作成ができるし、これはこっちかなと思っても直ぐに移動ができる。

テーマが段々大きくなってきたら、ひとつずつ階層を上げていけばいいし、アクティブな項目は一番上にあげてある程度落ち着いたら下に下ろせばいい。

そしていざ必要になればその項目だけ、出力すればいい。

画像が貼り付けられないのが玉に瑕だけど、それはそれでいい。あまりファイルサイズが大きくなりすぎるとかえって読み込みが遅くなったりするので。

最近京大生が読んでいる?なんて帯がついた思考の整理学という本を半分くらいまで読んだけど、趣旨自体は結構近い気がする。

2010年7月7日水曜日

Pediatrics and motivation.

今月から小児科。でもって一週間程度で早速不登校児になる。

月末に興味を持ったことの発表があるらしく、先月にサボった(はみられた)人は不登校にしたとのことでじゃあ「小児の適応障害」をテーマに選ぶことにした。いや、でも不登校とかぶるなぁ。どうしよう。

せっかくだから、その領域に近いものをテーマとして選びたい、というのはある。

それとは別にこれから先の就職先探しその2。

小児科の先生が病理の先生と仲をとりもってくれると言ってくれたが、残念ながらその頃私は小児科にいません。

なのでその話も流れることでしょう、たぶん。