看護実習科目の年間スケジュール表の作成 - シフト連問題

 看護学部の実習先を割り当てる問題です。実習先を一つのシフトとして表現します。

シフト定義としては、

成人1

成人2

老年

地域

精神

小児

母性

統合

があります。期間60日内に上記シフトを割り当てます。シフトは、連続的であり、期間内に一回です。例えば、上の解では、成人１が3日、成人2が3日になっていますが、これらは、期間内に一回となっています。こういった連続シフト島をシフト連と呼称し、シフト連毎に順番の制約がある問題をシフト連問題と呼ぶことにします。

＜シフト連問題は、何が問題か？＞

シフト連毎に順番があることが問題です。看護師である妻に聞いたところ、たとえば、「成人1の前に、成人2は、有り得ない」、「統合は、まあ最後かな。　」という具合に、シフト連毎にハード制約とソフト制約が存在するようです。Day単位ならば、GUIでシフトパターンとして記述が可能ですが、不定長の連なので、GUIでは記述が困難です。

＜難易度＞

Pythonで制約を記述しますので、上級です。私も数十分悩んだのでアルゴリズムの難易度は高いです。加えて、GUIで操作インターフェースをどのようにPythonで記述するか？という問題もあります。やはり難易度が高いです。

＜アルゴリズム＞

便宜的にA>BをAは、Bに先行すると表記します。シフトA、BがあったときA>Bを実現するには、次のように、簡単な2日間から出発し、n日間では、どういう制約が必要になるかを考えてみます。

すると、期間をありえる全ての2つに分けて禁止パターンを記述していけばよいことに気づきます。ちなみに一つの連の長さは不定で、期間内に1個のみという仕様です。禁止パターンで記述しておけば、連が存在しないときでも悪さはしません。あくまで全てのB>Aを禁止するだけです。60日期間であれば、59個の禁止パターンを制約することになります。

＜連の記述＞

連は、期間内に1個なので、各Person,各DayでORを取れば十分です。

まずは、成人１＞成人２　制約を記述してみます。

僅か24行です。

import sc3

def 順序():

    first_day=今月[0] #期間初日
    last_day=今月[len(今月)-1] #期間最終日
    for person in 全グループ:#全ての人について　
        st=staffdef[person]+' 順序制約'
        sc3.print(st+'します。\n')
        for day in 今月:#全期間あらゆる分割を行う
            vlist2=[]
            vlist1=[]
            for d in range(first_day,day+1):#初日からday日まで
                v2=sc3.GetShiftVar(person,d,'成人2')#person day shiftで状態取得　Binary 0/1
                vlist2.append(v2)
            for d in range(day+1,last_day+1):#day+1日から最終日まで
                v1=sc3.GetShiftVar(person,d,'成人1')#person day shiftで状態取得　Binary 0/1
                vlist1.append(v1)
            V2=sc3.Or(vlist2)#成人2連を求める
            V1=sc3.Or(vlist1)#成人1連を求める
            st_day=st+' '+ str(day)
            sc3.AddHard(~(V2&V1),st_day) #成人2>成人1 を禁止する。ハード制約する

順序()

これを打ち込んで、走らせてみます。最初の解で見られた、成人２>成人１　箇所は、無くなり全スタッフで、成人1>成人2　になりました。

成功です！

＜Pythonを書くときの注意点＞

■いつものように設定ボタンを押すのを忘れずに。また、前のソースに戻ってしまう現象が起こることがあります。RUNする前に保存も行ってください。

■インデント自体に意味があります。インデントを揃えてください。下記は、インデントエラーの例です。赤いところをダブルクリックします。

すると、ソース全体に飛んでいきます。インデントが揃っていないことがわかります。

ソース全体は、ReadOnlyです。Editするには、ソースタブで元のソースを開いてください。

＜一見宣言されていないような変数はどこにある？＞

一回RUNして、ソース全体でご確認ください。例えば、”全グループ”は、ソース全体の最小の方で記述されています。配列になっていますが、これは、personを0から振った番号が収められています。for person in 全グループでは、person に0,1,2,3...とループします。動作が軽くなるように、person,day共、基数化しています。(最終的には、AddHardで、person,dayの数字を渡すので。）

＜動作確認＞

設計時は、頻繁にRUN-Editを繰り返すので、動作は軽い方が吉です。列制約をオフにして、ターゲット動作確認だけに注力するとよいでしょう。いきなりGUI部から記述するのではなく、上のように、アルゴリズム本質部の確認から行うのが吉です。

＜汎用化＞

成人１＞成人２は、上記で確認出来ました。GUIで任意のシフト連の順序を記述できるようになると、より使い易いと思います。次回は、GUIインタフェースについて考えてみます。