2019年4月27日土曜日

PHS所持待機問題の構想

訪問看護の現場で、PHS所持待機の日数を等分に割り振りたいという問題があります。
(こちらは、通常のシフトスケジューリング問題とは異なる対応が必要になりますが、そのことについては、別の機会に。)

その等分というのは、長期休暇が入る3ヶ月、もしくは、1年で見て、各スタッフ等分に、という意味です。そうなると、月々の設定だけではなくて、長期休暇予定を見据えて月々に目標値を配分するという管理が必要になってきます。まず管理シートが必要となります。これを自前で持つのも一案ですが、Excelを直に読み書きした方がベターと判断しました。GUIは、C#なので、Excelを操作できるC#ライブラリをSurveyしてみました。ClosedXMLがよさそうですので試してみることにしました。

これとは別に、スタッフ数100人を超える職場で、各スタッフのシフト、タスク、年間予定シフトを手入力するのも大変です。なので、Excelシートを指定してインポートできるようにします。

2019年4月26日金曜日

数独をPython制約で解く

import sc3
for day in 全日: #列制約
 for シフト in 全シフト:
  V=[]
  for 人 in 全スタッフ:
   V.append(sc3.GetShiftVar(人,day,シフト))
  sc3.AddHard(sc3.SeqLE(1,1,V),'')
for 人 in 全スタッフ: #行制約
 for  シフト in 全シフト:
  V=[]
  for  day in 全日:
   V.append(sc3.GetShiftVar(人,day,シフト))
  sc3.AddHard(sc3.SeqLE(1,1,V),'')
for 人 in スタッフブロックトップ: #ブロック制約
 for シフト in 全シフト:
  for  day in ブロックトップ日集合:
   V=[]
   for  i  in range(3):
    for  j in range(3):
     V.append(sc3.GetShiftVar(人+i,day+j,シフト))
   sc3.AddHard(sc3.SeqLE(1,1,V),'')
  
僅か21行で数独が記述出来ています。神戸大学のCoprisには 及びませんがそれなりに簡潔に記述出来ているのではないと思います。SeqLEの書式は、(min,max,List)で、ハード制約専用です。
min==max==1なので、LeastOne&&MostOneつまり、OnlyOneということです。

Pythonの制約ステートメント

import sc3

v1=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-27  ', '  オンコール ')
sc3.AddHard(v1,' 川畑拓也2017-05-27    オンコール')


制約するには、シフト変数v1を取り出します。シフト変数は、3次元で、Person、Day,Shiftの順にGetShiftVar関数で取り出します。 引き数は、GUIで定義した文字列、もしくは、配列Indexです。または、任意の組合せ(文字列/配列Index)になります。どちらもPropertyファイルを参照して、Validな名前、範囲を確認することが出来ます。文字列の場合、空白はあっても構いません。(Trimされます。) で、取り出した変数をアサートするには、AdddHard関数を呼び出します。AddHard関数は、1番目に変数、2番目にコメントになっています。上記は、川畑拓也の2017-5-27の勤務はオンコールであること、というハード制約になります。 下が実行結果です。確かに、オンコールのラベルであるになっています。

同様にして、日付を追加したソースが次です。
import sc3

v1=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-27  ', '  オンコール ')
sc3.AddHard(v1,' 川畑拓也2017-05-27    オンコール')

v2=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-28  ', '  オンコール ')
sc3.AddHard(v2,' 川畑拓也2017-05-28    オンコール')

v3=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-29  ', '  オンコール ')
sc3.AddHard(v3,' 川畑拓也2017-05-29    オンコール')

v4=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-30  ', '  訪問看護 ')
sc3.AddHard(v4,' 川畑拓也2017-05-30    オンコール')
実行結果は次です。
 

次は、Andに関するどれもValidな構文です。And()関数の引き数は、4個までサポートしています。2項演算子&を使えばその制限はありませんが、3個以上の演算については、リストを使うことを推奨します。
import sc3

v1=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-27  ', '  オンコール ')
v2=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-28  ', '  オンコール ')
v3=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-29  ', '  オンコール ')
v4=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-30  ', '  訪問看護 ')
sc3.AddHard(v1&v2&v3&v4,' 川畑拓也2017-05-30パターン    オンコール')

vlist=[v1,v2,v3,v4]#3個以上はリストを推奨
sc3.AddHard(sc3.And(vlist),' 川畑拓也2017-05-30Vlistパターン    オンコール')

v5=sc3.And(v1,v2,v3,v4)#引き数は4個まで
sc3.AddHard(v5,' 川畑拓也2017-05-30Andパターン    オンコール')
ハード制約にはコメントをつける
コメントは、空白でSPLITされる任意の文字列とします。 上の記述は、3つのANDの制約は、お互いが等価な制約です。感心しない記述ですが、お互い矛盾しないのでエラーは出ません。 ここで意図的にエラーを作ってどのような 事象になるかを見てみます。具体的には、v4をInvert(Not)してみます。制約BC間は、矛盾しませんが、制約AB,AC間では矛盾が起こります。
import sc3

v1=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-27  ', '  オンコール ')
v2=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-28  ', '  オンコール ')
v3=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-29  ', '  オンコール ')
v4=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-30  ', '  訪問看護 ')
sc3.AddHard(v1&v2&v3&~v4,' 川畑拓也2017-05-30パターン    オンコール')#制約A)故意にエラーを生成

vlist=[v1,v2,v3,v4]
sc3.AddHard(sc3.And(vlist),' 川畑拓也2017-05-30Vlistパターン    オンコール')#制約B

v5=sc3.And(v1,v2,v3,v4)
sc3.AddHard(v5,' 川畑拓也2017-05-30Andパターン    オンコール')#制約C
コンパイルの準備中ソルバを呼び出し中です。
 python propertyファイル生成を開始します。
 python propertyファイル生成が終了しました。
 満たしていないハード制約の集約化を行います。
 o=11 Time=3.153(CPU秒)
 o=10 Time=3.183(CPU秒)
 o=9 Time=3.245(CPU秒)
 o=8 Time=3.362(CPU秒)
 o=7 Time=3.425(CPU秒)
 o=6 Time=3.516(CPU秒)
 o=5 Time=3.593(CPU秒)
 o=4 Time=3.666(CPU秒)
 o=3 Time=3.773(CPU秒)
 o=2 Time=3.805(CPU秒)
 o=1 Time=3.907(CPU秒)
 f=0 Time=3.969(CPU秒)
 Optimum ConUB found
 b=1 Time=4.039(CPU秒)
 以下に矛盾または満たしていない可能性がある制約を示します。
  ● 川畑拓也2017-05-30パターン
解探索が終了しました。 4 (秒)
解を見つけることが出来ませんでした。
上記は、ソルバーが充足解を見つけられないと判断し、充足しない原因を探すために、どの制約を外せば、充足するようになるかという エラーの最小化アルゴリズムが実施された結果です。結果、一つの制約を外せば、全て満たされることが示されています。 制約の開発・設計過程においては、上記のようなことが割りに頻繁に起きます。そのとき、コメントがブランクだったらどうなるでしょう? 矛盾している制約の数が1個であることは分かりますが、コメントがブランクだと、それがどこなのかは、知ることができません。ナーススケジューリングの場合、制約の数は、数万を越えることは普通にあります。面倒でも、ハード制約には他の制約と区別するコメントをつけておくことを強くお勧めしたい理由がここにあります。SC3は、数理最適化系のソルバーも搭載しますが、こちらの場合は、運がよければ目的関数値が妙にでかくなる、大抵の場合は、線形制約ソルバーが充足しないので手も足も出ません。結果、どこが問題かは、見当をつけることさえ困難です。厳密解を目指す場合、数理最適化系が有利になる場合がありそちらのソルバーを最終的に使う場合でも、制約記述の開発・設計には、こちらのモードで行うのがよいでしょう。
import sc3

v1=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-27  ', '  オンコール ')
v2=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-28  ', '  オンコール ')
v3=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-29  ', '  オンコール ')
v4=sc3.GetShiftVar(' 川畑拓也 ',  ' 2017-05-30  ', '  訪問看護 ')
sc3.AddSoft(v1&v2&v3&~v4,' 川畑拓也2017-05-30パターン    オンコール',  1  )#制約A)故意にエラーを生成レベル1でソフト制約

vlist=[v1,v2,v3,v4]
sc3.AddHard(sc3.And(vlist),' 川畑拓也2017-05-30Vlistパターン    オンコール')#制約B

v5=sc3.And(v1,v2,v3,v4)
sc3.AddHard(v5,' 川畑拓也2017-05-30Andパターン    オンコール')#制約C

制約Aをソフト制約化するには、AddHardをAddSoftに置き換え、最後にレベルを加えます。上では、レベル1に設定しました。 SC2では、エラーをカウントするという意味で、INV化(Not化)する必要がありましたが、SC3では、必要なく、上記変更だけで事足ります。 ソフト制約化することにより下のように充足することになります。

python propertyファイル生成を開始します。
 python propertyファイル生成が終了しました。
 解探索を開始します。2.370(CPU秒)

 User Soft Constraint Level 1
 o=1 Time=2.454(CPU秒)
 f=0 Time=2.484(CPU秒)
 Optimum ConUB found
 o=1 Time=2.563(CPU秒)
 o=1 Time=2.587(CPU秒)
 b=1 Time=2.603(CPU秒)
 充足解を書き込み中です。


SC3、Pythonによる言語制約について概観しました。Python言語制約の公式Tutorialは、6月にリリース予定です。SC3で追加した、Phase/Task機能、さらにPythonによる言語制約により、 およそ勤務表と名のつくスケジューリング問題で出来ない勤務表はないと思います。SC2は、元々他の勤務表ソフトでは記述不能な、複雑で込み入った仕様の勤務表について、トップを独走中でした。今回の機能強化により、工場の工程管理、コールセンター等、大規模な勤務表分野にも参入します。さらに、SC2では、基本1ヶ月単位でしたが、3ヶ月・1年といった単位での管理のご要望がありまして、そちらについても対応予定です。

2019年4月25日木曜日

python集合ファイル

GUIで記述した集合をpythonソースにしたものです。ファイル名は、プロジェクト名+_property.pyで、プロジェクトファイルと同じフォルダに出力されます。

#staffdef
staffdef=['川畑拓也','中田拓実','高橋真央','友安美琴','降矢悠司','横山加奈','渡邊夏希']
#daydef
制約開始日=5
制約終了日=34
表示開始日=0
daydef=['2017-05-27','2017-05-28','2017-05-29','2017-05-30','2017-05-31','2017-06-01','2017-06-02','2017-06-03','2017-06-04','2017-06-05','2017-06-06','2017-06-07','2017-06-08','2017-06-09','2017-06-10','2017-06-11','2017-06-12','2017-06-13','2017-06-14','2017-06-15','2017-06-16','2017-06-17','2017-06-18','2017-06-19','2017-06-20','2017-06-21','2017-06-22','2017-06-23','2017-06-24','2017-06-25','2017-06-26','2017-06-27','2017-06-28','2017-06-29','2017-06-30']
#shiftdef
オンコール=0
代休=1
休み=2
半日代休=3
外来勤務=4
希半=5
希望休み=6
訪問看護=7

#staffcollection
全スタッフ=[0,1,2,3,4,5,6]
常勤=[0,1,2,3,4,5]
パート=[6]
常時オンコールしない=[6]
月曜オンコールしない=[5]
火曜オンコールしない=[]
水曜オンコールしない=[]
木曜オンコールしない=[]
金曜オンコールしない=[]
訪看しない=[5,6]
水曜休み=[5]
木曜休み=[]
金曜休み=[]
土曜休み=[]
月曜休み=[]
火曜休み=[]
オンコール可能=[0,1,2,3,4,5]
訪問看護可能=[0,1,2,3,4]
定期休みあり=[5]
定期休みなし=[0,1,2,3,4,6]

#daycollection
今月=[5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34]
日=[1,8,15,22,29]
月=[2,9,16,23,30]
火=[3,10,17,24,31]
水=[4,11,18,25,32]
木=[5,12,19,26,33]
金=[6,13,20,27,34]
土=[0,7,14,21,28]
全日=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34]
平日=[2,3,4,5,6,9,10,11,12,13,16,17,18,19,20,23,24,25,26,27,30,31,32,33,34]
週末=[1,8,15,22,29]
休日=[1,8,15,22,29]
稼働日=[0,2,3,4,5,6,7,9,10,11,12,13,14,16,17,18,19,20,21,23,24,25,26,27,28,30,31,32,33,34]
制約開始日一日前=[4]
制約開始日二日前=[3]
制約開始日三日前=[2]
制約開始日四日前=[1]
制約開始日五日前=[0]
制約開始日一日後=[6]
制約開始日二日後=[7]
制約開始日三日後=[8]
制約開始日四日後=[9]
制約開始日五日後=[10]
制約開始日六日後=[11]
第一週=[5,6,7,8,9,10,11]
第二週=[12,13,14,15,16,17,18]
第三週=[19,20,21,22,23,24,25]
第四週=[26,27,28,29,30,31,32]
第五週=[33,34]
制約開始日1日前から=[4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34]
制約開始日2日前から=[3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34]
制約開始日3日前から=[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34]
制約開始日4日前から=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34]
制約開始日5日前から=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34]
制約開始日6日前から=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34]
制約終了日六日前=[28]
制約終了日五日前=[29]
制約終了日四日前=[30]
制約終了日三日前=[31]
制約終了日二日前=[32]
制約終了日一日前=[33]
金土日=[0,1,6,7,8,13,14,15,20,21,22,27,28,29,34]
金土日月=[0,1,2,6,7,8,9,13,14,15,16,20,21,22,23,27,28,29,30,34]
外来休診日=[1,8,15,22,29]
訪問休診日=[1,8,15,22,29]
訪問診療日=[0,2,3,4,5,6,7,9,10,11,12,13,14,16,17,18,19,20,21,23,24,25,26,27,28,30,31,32,33,34]
外来診療日=[0,2,3,4,5,6,7,9,10,11,12,13,14,16,17,18,19,20,21,23,24,25,26,27,28,30,31,32,33,34]
月火水土=[0,2,3,4,7,9,10,11,14,16,17,18,21,23,24,25,28,30,31,32]
木金=[5,6,12,13,19,20,26,27,33,34]
水土=[0,4,7,11,14,18,21,25,28,32]
訪問月火水土=[0,2,3,4,7,9,10,11,14,16,17,18,21,23,24,25,28,30,31,32]
訪問木金=[5,6,12,13,19,20,26,27,33,34]
水曜休み者の休み=[1,4,8,11,15,18,22,25,29,32]
木曜休み者の休み=[1,5,8,12,15,19,22,26,29,33]
水曜休み者の出勤日=[0,2,3,5,6,7,9,10,12,13,14,16,17,19,20,21,23,24,26,27,28,30,31,33,34]
木曜休み者の出勤日=[0,2,3,4,6,7,9,10,11,13,14,16,17,18,20,21,23,24,25,27,28,30,31,32,34]
水土訪問休診日=[0,1,4,7,8,11,14,15,18,21,22,25,28,29,32]

#shiftcollection
オンコール否=[1,2,3,4,5,6,7]

#classcollection
全スタッフ属性=[全スタッフ]
勤務形態=[常勤,パート]
オンコール=[常時オンコールしない,月曜オンコールしない,火曜オンコールしない,水曜オンコールしない,木曜オンコールしない,金曜オンコールしない]
訪看=[訪看しない]
休み=[水曜休み,木曜休み,金曜休み,土曜休み,月曜休み,火曜休み]
上記ファイルは、インタープリタ起動時に、読み込み済みです。 Pythonで、プログラムするにしても、折角GUIで集合を定義済みなので、それを利用しない手はありません。
import sc3
for 人 in staffdef:
 sc3.print(人+'\n')

for 人 in 全スタッフ:
 sc3.print(str(人)+'\n')
 
pythonインタープリタは、これに対して以下のように出力します。
 
コンパイルの準備中ソルバを呼び出し中です。
 python propertyファイル生成を開始します。
 python propertyファイル生成が終了しました。
川畑拓也
中田拓実
高橋真央
友安美琴
降矢悠司
横山加奈
渡邊夏希
0
1
2
3
4
5
6
 充足解を書き込み中です。

次のソースでは、月曜オンコールしない人を選んで、制約開始日以降の月曜日になにか処理する場合の記述です。 このように、制約開始日基準で、記述すれば、毎月同じpythonソースで対応が可能です。 SC2と雰囲気が似ていますが、こちらは真性のpythonソースです。

import sc3

for 人 in 全スタッフ:
 #sc3.print(str(人)+'\n') #人は数字なので、str()で文字に変換しないとエラーになる
 if 人 in 月曜オンコールしない:
  sc3.print(staffdef[人]+'\n') 
  for day in 全日:
   if  day >=制約開始日 and day in 月:
    sc3.print(daydef[day]+'\n')

出力は、以下のようになります。propertyファイルと見比べるとプログラムの流れが理解できると思います。

コンパイルの準備中ソルバを呼び出し中です。
 python propertyファイル生成を開始します。
 python propertyファイル生成が終了しました。
横山加奈
2017-06-05
2017-06-12
2017-06-19
2017-06-26
 充足解を書き込み中です。

このようにして、任意の人、任意のDay、任意のシフトにアクセスすることが出来ます。ところで、未だ制約は一行も 書いていません。上のプログラムは、制約ではなく、制約するための前段階、本丸である制約へ行くためのアクセス手段に過ぎません。 アクセスさえ出来れば、どんな言語を用いてもよいのですが、昨今の流行と実装の容易性を鑑み、Pythonインタープリタという 選択になりました。

2019年4月24日水曜日

Pythonによる制約記述

下図のようにメニューに追加しました。
SC2との互換を取るために前の言語制約はそのまま残しています(deprecated)が、SC3では、Pythonによる言語制約を使ってください。

Pythonの日本語変数
日本語の全てが使える訳ではないようです

とりあえず、不具合が出ると分かっているものは、次のようにプロジェクト読み込み時に修正するようにしました。

SC2SC3 Replaced
制約開始日ー1制約開始日一日前
制約開始日ー2制約開始日二日前
制約開始日ー3制約開始日三日前
制約開始日ー4制約開始日四日前
制約開始日ー5制約開始日五日前
制約開始日ー6制約開始日六日前
制約開始日ー7制約開始日七日前
制約開始日+1制約開始日一日後
制約開始日+2制約開始日二日後
制約開始日+3制約開始日三日後
制約開始日+4制約開始日四日後
制約開始日+5制約開始日五日後
制約開始日+6制約開始日六日後
制約終了日ー1制約終了日一日前
制約終了日ー2制約終了日二日前
制約終了日ー3制約終了日三日前
制約終了日ー4制約終了日四日前
制約終了日ー5制約終了日五日前
制約終了日ー6制約終了日六日前



お決まりのHello World!からです。
import sc3
sc3.print("Hi\n")
<Pythonインタープリタは?>
pythonインタープリタは、制約ソルバ上に組み込まれて(embedded)います。インタープリタのpathは、制約ソルバーと同じパス上にあります。プロジェクトファイル上にはないのでご注意ください。

<制約ソルバーとのインターフェースは?>
python上からは、全てsc3を介してインターフェースされます。sc3は、暗黙moduleでありユーザは実体を見ることはできません。 sc3は、pybind11でバインドしたc++moduleです。
sc3がないと、何もすることは出来ません。従い、まずプログラムの最初に、
import sc3
と書く必要があります。

<コンソールの出力方法は?>
ありません。GUIへの出力は、sc3.print(string,string...) としてください。


実行の様子です。 コンパイルの最初の方で、GUIが設定した集合情報ファイルを生成しています。
(後述)その後、インタープリタの実行に移り、Hiが出力されています。その後、制約の最終コンパイル経てソルバーの実行に移って行きます。



<Pythonの役目>
Pythonの役目は、集合情報ファイルを利用して、ソルバー内の変数に自由にアクセスし、制約を付加することです。GUI設定で、行き届かない部分について、Pythonでプログラムすることになります。

SC2言語とあまり変わるところはないのですが、SC3では、公式にPythonによる制約をサポートします。ハード制約のみならず、ソフト制約もサポートします。一般のユーザが使うことは想定していません。十分にGUIによる制約について慣れている方々を想定します。(プログラム上級の方でも、制約プログラムには、慣れが必要だと思います。)
GUIの全てを置き換えることも理論的には可能ですが、Pythonを使っても骨が折れる作業ですので、小さなシステムを除いてあまり現実的ではないと思います。総じて、GUI制約を補間することが、Pythonの役目になります。

2019年4月22日月曜日

C++から、Pythonを実行する実験

C++からpythonのインタープリタを起動させたい。そのような要求には、pybind11が良いです。

#include "pch.h"
#include 
namespace py = pybind11;
using namespace py::literals;

int main()
{
 py::scoped_interpreter guard{}; // start the interpreter and keep it alive
 py::print("Hello, World!"); // use the Python API
    
}
実行環境は以下です。

2019年4月20日土曜日

Pythonで言語制約構想

PhaseとTaskの実装が大分進んだので、言語化にも手をつけようと思ったのですが、この際、こちらも大変更し、一気にPythonでの言語制約にしようという話です。 現在言語制約は、自作のインタープリタで制約していますが、Pythonで制約を記述できればそれがベストです。また、結果もPythonで処理すれば、制約の検証というステージでも一貫した処理系になります。自作インタープリタへの実装が面倒になった、というのが実態ではありますが、こういう機会を捉えて機能拡張してメンテナンスを容易にしていくというは、良い開発の方向性であると、長年の経験から言えます。

今までLARKを使ったDSL in Pythonをイメージしていたのですが、DSL構想は止めます。
上記は、現在のスタイルですが、言語記述は、自作インタープリタが行っています。これを
Pythonによるものに置き換えます。
Pythonで言語制約するには、Person、Day,Shift、Phase, Taskといった集合情報を入力する必要があります。これらは、一度RUNすれば、Pythonソースファイルとしてソルバが出力することは出来ます。GUIに吐かせることも設計可能です。とりあえずは、ソースファイルを利用して記述するものとします。

Pythonでは、任意の制約オブジェクトを外部関数(C/C++で記述、ソルバーの制約関数を呼び出す)を呼び出せれば、Pythonで言語制約が出来ることになります。

さらなる構想としては、ソルバ自身もDLL化すれば、ソルバのSolveをループでき、パラメータの最適化チューニング、データを積み重ねての機械学習も可能になります。
最近のVisualStudioは、Python処理系も装備しているようです。これを用いれば、Print文が不要でスマートにデバッグできるようになります。これは、将来的な構想です。

言語制約を使ったSC2プロジェクトでは、SC3プロジェクトと互換がなくなってしまいます。(言語制約を書き換える必要が生じます。)

今日サーベイして言語化方針を定めました。


2019年4月13日土曜日

SC3への拡張

INRC2のインスタンスをSC3GUIで記述しました。


予定入力では、シフトとタスクの記述は分離しています。シフトは従来と同じです。タスクは、上部になりますが、最初に記述したフェーズで、一日が分割(薄緑→緑)されています。解画面では、シフト・タスクが統合した画面となります。

スタッフプロパティの記述です。SC2であったプロパティが下のタスクに移動しています。

各スタッフはありえるタスクリストを定義します。


タスクの定義です。タスクとフェーズを記述しなければ、SC2と同じ機能となります。
 
フェーズは、時刻概念で一日のSPLITです。1フェーズ中、最大1タスクまでです。(一人が同時にできる仕事は、一つまで) フェーズはExclusiveな性質をもち、フェーズ同士はオーバラップしません。
それに対してシフトは、時間帯です。一日にできるのは、これまで通り1シフトのみです。

<利点>
フェーズとタスクの機能追加によって、柔軟にシフト勤務を記述できます。これまでもシフトの種類を増やすことで、同様の機能を記述することは可能でした。従って、SC2の記述のままで特に問題はありません。

利用の場面としては、タスクを導入することで、シフト数を大幅に削減できる場合、あるいは、一日に複数の仕事を定義したい場合になるかと思います。
技術的な問題として、SC3では、複数のソルバを搭載しますが、シフト数が多いとソルバが利用可能なソルバ種類が限定される方向になります。
 いずれにしても、この機能追加によって、さらに記述自由度が上がります。どんなに複雑な制約を持つシフト勤務でも記述可能となるでしょう。

Task変数Yは、次のように4次元に修正しました。Dayの次にフェーズが来ます。フェーズは、便宜的にシフト分割で定義されますが、絶対時刻なのでシフトの集合要素ではなく、Dayを構成する集合要素です。あまりないかと思いますが、同じ時刻を共有する別なシフト記述は許すものとします。その場合、同じ時刻なので、同時に可能なTaskは、一つのみです。つまり同じフェーズを共有すると考えた方が自然な解釈になります。

Taskは、縦方向の制約記述(Ex. X日の午前はZ人以上)に使い、シフトは、横方向のシーケンス記述に特化すると、記述の柔軟性が高まります。SC2の記述だと、Taskが増えた場合は、シフト記号を増やさざるえません。本来Day方向のシーケンスが変わらないならば、シフト記述は変えない方が分かりやすいでしょう。



$Y_p_d_u_t$. または $ Y[p][d][u][t]$
ここで、
$p \in Persons$
$d \in Days$
$u \in Phases$
$t \in Tasks$
です。4次元でアクセス可能です。
最も基本的な制約は、
$\sum_{t\in Tasks}Y_p_d_u_t=1  \ \ \  \forall u \in Phases$
subject to active shift
$\sum_{s\in Shifts}X_p_d_s=1  \ \ \  \forall p \in Persons, \forall d \in Days$

です。




2019年4月5日金曜日

ラグランジェ緩和問題

ラグランジェ緩和の説明は、こちらが分かりやすいです。
https://www.jstage.jst.go.jp/article/bjsiam/23/3/23_KJ00008829092/_pdf/-char/en

双対問題との関連はこちら。
http://tomomi.my.coocan.jp/text/relax1.pdf

ナーススケジューリングでも一定の試みがなされています。
https://thesis.eur.nl/pub/45916/Dopheide.pdf

私もトライしてみたのですが、期待したほどよい下界値は得られませんでした。なので別な方法を採っています。 こちらは、簡単で近い上界値が得られます。

2019年4月2日火曜日

PhaseとTaskの追加検討

3直4交代の勤務表作成依頼がありました。
この機会に勤務表の対応可能範囲を広げることにしました。GUI含めて大変な変更なので現状のSC2に悪影響が懸念されます。そこで、SC3として、リリースすることを目標にしますが、当面3直4交代用のGUI/Solvertとして別リリースします。

今回の変更を説明する前に、現在の基本的な概念を記しておきます。

今までシフトは、次の式で表しておりました。あるシフト変数Xは、シフトの状態を表し2値です。
個々の状態にアクセスするには、次の形態をとります。

$X_p_d_s$. または $ X[p][d][s]$
ここで、
$p \in Persons$
$d \in Days$
$s \in Shifts$
です。3次元でアクセス可能です。
最も基本的な制約は、
$\sum_{s\in Shifts}X_p_d_s=1  \ \ \  \forall p \in Persons, \forall d \in Days$
です。

今回の変更は、上式を維持したまま、Shiftの時間分割であるPhaseを追加します。Shiftは、24時間の環を表しますが、一つのShiftが8時間だとすると、さらに4時間で分けて前後という風に二つに分けます。これを称して2Phaseと呼びます。 ですから、3Shift、2Phaseであれば、一日あたりの6Phaseをもつことになります。Phaseは、オプションとしてAliasの概念が持ちます。Aliasとは別名のことで実態は別なところにあるリンクみたいなものです。早出と残業は、Aliasです。



さらに、概念の追加をします。Taskです。Taskの概念は、INRC2でも出てきました。各シフトは、各Taskを持つという概念でした。ここでは、より広く対応するために、ShiftではなくPhase毎にTaskを持つという風に拡張します。つまり、Phase時間毎にTaskを決められるという関係になります。新たにTask変数Yを定義し、個々の変数には、以下でアクセスします。

$Y_p_d_s_u_t$. または $ Y[p][d][s][u][t]$
ここで、
$p \in Persons$
$d \in Days$
$s \in Shifts$
$u \in Phases$
$t \in Tasks$
です。5次元でアクセス可能です。
最も基本的な制約は、
$\sum_{t\in Tasks}Y_p_d_s_u_t=1  \ \ \  \forall u \in Phases$
subject to active shift
$\sum_{s\in Shifts}X_p_d_s=1  \ \ \  \forall p \in Persons, \forall d \in Days$

です。



 Primary PhaseAlias Phase
呼称
 DayAlias DayAlias
勤務1S1ES1L-1S3L0S2E
勤務2S2ES2L0S1L0S3E
勤務3S3ES3L0S2L1S1E

例えば、勤務1早 というフェーズの実態は、S3Lですから、前の日の勤務3後になります。
このようにして、二人の早出・残業をセットにすることで、1人分のシフトリソース不足を補償することが可能になります。スケジュールナースは、登録してある工程技能者の中から、不足している(自・他工程)リソースを自動的に補償するプログラムです。これを100人単位で配置するとなると、結構な手間になると思います。

働き方改革で年休取得も必要ですし、工程の欠員をどうするか、多能化だけでは、難しい場面もあると思います。そこを優先度つきで、個々の要望を満足させながら、複雑多岐に渡る最適化してくれるのがスケジュールナース3になります。 今までのように、一度作った勤務表で終わりではありません。条件を変えながら、難しく時間がかかる部分は機械がやってくれます。そうしていくつかの解の様子をみながら、調整して得た解こそ、本当の人間の欲しい最適化した解なのです。

変数量の計算
100人スタッフ
(5シフト(3Shift+休み+常日勤勤務))
6Phases
31+1日(前月1日)
32Tasks
=60万変数

かなり大規模ですが、なんとかできるでしょう。

今回Latexを使って数式を記述してみました。下記のYoutubeを見てGoogleBloggerを設定しました。
http://latex.codecogs.com/