2020年8月7日金曜日

2020年8月6日木曜日

Algorithm4のRefactoring

以前頓挫した、ペア制約のLP化を再考してみました。

A:f1(x0,x1,x2...)≤b1;
B:f2(x0,x1,x2...)≤b2;

Implication A→Bは、
!A+B
そのソフト化は、Binary Variable Cを追加して
!A+B+C >=1;-----(1)

Minimize:  ...+C*Cweight;

とします。ここで、Cは、0になるように作用することに注意します。すると(1)式より
!Aもしくは、Bが1になるように作用することが分かります。なので、
!A:  f1(x0,x1,x2...)+M(1-A) ≧b1+1;
   B:  f2(x0,x1,x2...) -M(1-B) ≤b2;
とすれば、A==1、B==1側に自然に作用します。(Mは、BigMです。)

上のように定式化すれば、ペア制約ImplicationもLP化(Linear Programming)出来そうです。



2020年8月4日火曜日

130Aをリリースしました

メジャーバージョンアップです。

今後(8月)の実装予定としては、
1)Algorithm4の一般化
2)祝日の国際化
3)マニュアル類の英語化
4)Dockerの構築

です。

2020年7月31日金曜日

ユーザマニュアル作成

作成しました。

PowerPoint→PDF→しおり作成→htmlで、しおり作成を手動で行うのがどうにも面倒だったので、PowerPointからタイトルを抽出するpython codeを書きました。

PowerPointからタイトルを取り出したつもりですが、なぜかページNoを拾ってしまうことがありました。良く分かっていません。htmlにしたときページが1ページずれるのも謎です。
import pptx
from pptx import Presentation
prs = Presentation("schedule_nurse3_user_manual.pptx") # load the ppt
slide_titles = [] # container foe slide titles
page=1
file = open('user_manual.txt', 'w')

for slide in prs.slides: # iterate over each slide
  count=0
  for shape in slide.shapes:
    if shape.has_text_frame:
      count+=1
      if not shape.text.isdecimal():
        if page !=1:
          file.write(shape.text+'/'+str(page-1)+',Black,notBold,notItalic,closed,FitPage\n') 
        print(page,shape.text)
        break
      if count>=2:
        break 
  page+=1    
file.close()
#print(slide_titles)

2020年7月30日木曜日

Excel予定シフト読み込みの変更

Excel Importの整理をしました。
ExcelImportのインポートを行う場合は、稼働日とスタッフ属性は、必須としました。
また、予定シフトの読み込みも、変更を行いました。従い、常に制約期間は変更禁止となり予定シフトで、制約期間が変更することは出来なくなります。

2020年7月29日水曜日

シフト型勤務表とタスク型勤務表

2日以上のシーケンスが発生するものをシフト型と分類しています。それ以外をタスク型としています。ナーススケジューリング問題は、シフト型です。

で、経験的な難易度でいうと、

タスク型 フェーズ数3以下 容易
シフト型 行制約でソフト制約がないもの 容易

それ以外は、難しい分類に入ります。中でも難問は、断トツにINRC2の問題です。行制約のソフト化がほぼ全制約に渡り、なおかつ複数のタスクがあります。行制約のソフト項がない、ScehdulingBenchmarkは、現在では、MIPソルバにより、殆どの問題は解くことができますが、INRC2の問題は、MIPソルバでは殆ど歯がたちません。敢えてそういう問題にしている意図があると思います。(作成者に聞いてみたことはありません。) 池上先生のベンチマークは、実現場での制約をヒアリングした実務問題で、実は、INRC2のソフト制約以上にソフト制約が入っています。というより全てがソフト制約で記述されています。通常制約により探索空間は減少しますが、全てがソフト制約で記述されているために、探索空間の減少はありません。その意味で難問の部類に入り、実際、数理的ソルバーでは梃子摺ります。しかし、解空間が広いので、数理的手段を用いない別なアプローチで難しくはありません。が、パラメータをちょっといじるだけで、最高難度の問題にもなりえます。つまり、実務上の問題も、容易に高難度問題になり得るということです。それには、探索空間と解空間の大きさが関係しています。探索空間が大きくても解空間が大きければ、解は容易に見つかります。一般に、探索空間が大きく解空間が狭い問題が難問です。

2020年7月28日火曜日

シフト型勤務表をタスク型にする


■シフト型勤務表に複数のタスクを定義したくなった場合は、シフト型勤務表をタスク型変更にする必要があります。(外来応援等、別なシフトとするよりも日勤の中でタスクを増減するほうがメンテしやすい、行制約はいじる必要がないので。)

■下のように実フェーズ列挿入で、フェーズ数分、列を挿入します。

■タスクは、タスク名を新しくするのが簡単です。(
既存のままだと、スタッフ毎のタスクにチェックが入りません。)
■こうしてみると、正循環シフトが、確かに 等間隔に近いですね。
 
 
 



 

2020年7月27日月曜日

タスク勤務表のチュートリアル

作成しました。

作成の流れは、
1)PowerPointで作成
2)PDF ExchangeでText抽出
3)2)のページタイトルをText編集 ShiftJIS(1ページずらす)
4)pdfbookmarksで3)text import
5)pdf2htmlex --dest-dir out8 --embed-css 0 --split-pages 1 schedule_nurse3_tutorial_for_task.pdf

2020年7月26日日曜日

アルバイト勤務表のチュートリアル動画

を作成しました。Videoの早回しや切り貼りを行うのにDemocreatorの新しいバージョンを使いました。古い方は、もうないのですが、これはこれで、重宝しています。今回も作成は、古い方で行い、新しい方は、切り貼り用で使いました。動画はこちら

2020年7月23日木曜日

タスク勤務表 多数のタスクの例

これは、看護師の応援勤務割り当て問題から取ってきたのですが、同様の職場は多いかもしれません。
とりあえず、Excelシートを作ります。



多数のタスクの場合、そのタスクを実行できるスタッフは限られることが多いので、タスクスキル属性で記述します。
読み込むプロジェクトは、以下で読み込んでください。
後は、いつものように、Excelファイルを読み込みます。
求解して解を確認、終了です。

2020年7月22日水曜日

アルバイトのシフト最適化その2

行制約については、自動生成されません。ユーザが必要な制約を記述します。パートナ問題の場合、その制約グループは、以下のスタッフプロパティ、日勤禁止ー休み曜日属性です。
これらは、各スタッフ事に異なる仕様です。行制約で記述できます。
さらに、パートナ問題より、希望予定を入力します。
これで求解すると以下の通り6連勤禁止制約に違反して解がありません。
そこで予定入力は、全てソフト制約化して解を求めることにします。

全体のエラーの様子を見るには、Excelの方が分かり易いです。行制約では、エラーがないものの、列制約では、満たしていない箇所(黄色部)が沢山あります。
実は、ソフト制約化するときにその重みを以下のように設定しています。
 
 予定入力の重みが一番重い設定になっています。試しに、予定を外すと
行制約・列制約共にエラーが消失します。このとき、求解設定は、
です。
 
 重み設定を
としても、エラーはありません。

 

 
 
行制約・列制約共にエラーはありません。以上、これらの結果をどう捉えればよいでしょうか?

そもそも行制約は、個人の希望を制約化したものです。なので、考えようによっては、予定入力は、必要ない、上の解だけで十分だ、ということが言えます。一方、個人の希望として全日をハード予定入力としてしまうと解の自由度は、0です。つまり、必要なスタッフ数を調整する遊びがないことになります。潤沢なリソースを持つ職場では、多くのスタッフの希望をカットすることで、必要なスタッフ数を得ることが出来ますが、そう出ない場合、スタッフの必要数が得られるとは限りません。必要数より多い場合は、希望をカットすればよいのですが、不足する場合、スタッフに掛け合って調整する作業が必要となります。

<行制約を持たない場合の問題>

予定希望を入力するしかなく、その場合解空間が極めて小さくなり、必要なスタッフ数が得られない、という事態が発生する確率が高いという問題があります。

一方、行制約を持つ場合は、予め、個人毎の許容範囲を決めて解を求めるので、最低限のスタッフの希望を適えていることになります。解空間が広いので、雇用者にとって、必要なリソースを自動で得ることができ、スタッフに連絡してその可否を問う調整作業そのものが不要になる確率が高くなります。

以上の考察から、行制約を持つと、雇用者にとっても調整という手間がかからず(ソフトが最適化の調整をしてくれるので)、スタッフにとっても希望通りに働き易くなるという良い側面を期待できます。

<さらに精度を上げるには>
行制約と予定制約の併用、予定の希望ではなく、禁止の入力、スタッフ・Day毎の重み細分化等、必要に応じて適用が可能です。

これらのテクニックを駆使して雇用者とスタッフのミスマッチをさらに少なくすることが可能です。

以上は、ナーススケジューリングで得られた知見をアルバイトシフトに取り入れただけで目新しいものではありません。今までも記述しようと思えば記述できましたが、

■Excelからインポートすることで、GUI設定を容易にした
■シフトをフェーズオブジェクトに拡張し、統一的にシフト・タスク勤務表を扱えるようにした

ということが新しいです。


<予定入力はどうなっている?>
入力との比較で、判明します。18個あります。これは、最適解なので、これより少ない数の変更で済ますことはできません。(列制約を全て満たす解では、)


<シフト形の解は?>
以上の解を再び、シフト形に戻すには、ExcelでFormatted出力を行います。


<解をさらにアレンジするには?>
タスク型勤務表では、シフト情報の他、タスク情報も含んでいるので、フォーマットを個別にアレンジしたい場合があると思います。その場合、Pythonでポスト処理を行います。
テンプレートプロジェクトには、CSV出力するPython記述が添付されているので、それをアレンジするのが早いです。

2020年7月21日火曜日

アルバイトシフト最適化その1

必要なものは、Excelファイルです。パートナシフト問題を参照して、必要な人員数をまとめます。


これをインポートします。
フェーズを見ると次のようになっています。
 3フェーズであり得る全てのシフトパターンが表示されていますが、必要なものだけ残して削除します。パートナ問題では、PH23とPH1が不要ですので、これらを削除します。
削除したシフトも不要なので、シフトのチェックを外します。
これで、とりあえず求解して解の様子を見てみます。
1は、仕事1というタスクがActiveであることを表しています。
しかし、このままでは、分かりづらいので、タスクの定義を次のようにします。
フェーズ数と別名数が同じときに、Enableされるオプションを使用して
Ph0:default label
Ph1:別名1
ph2:別名2
が適用されます。
ついでに、シフトのラベルも分かり易いものに変えます。
解が見易くなりました。
タスクの予定を見てみると、
上のExcel工程人数で読み込んだ値が表示されていることが分かります。
実際列制約は、

と自動生成しています。最大・最小は、タスク予定下部の対応するプロパティを呼んでいます。
記載のない値の箇所では、制約が生成されません。ところで、解のチェックをするために、
項目を追加するのですが、「全て挿入」が便利になりました。記載されている項目は、そのままに、
全項目が追加されます。

このように、工程人数のインポートは、シフトとタスクの自動生成、列制約自動生成を行います。
上の最大最小のベクトル制約化も自動生成を記述し易くする目的です。

ちなみに、昨日書いた、曜日集合も、下のように
自動生成されています。名前は、月曜日が最初となるような名前になります。
(Ex 日月 →月日になります。)

まとめると、
1)Excelテンプレートに必要なフェーズ数、各フェーズ毎の必要なスタッフ人数を記載
2)インポート
3)フェーズ編集、シフト編集
4)求解

するだけで、解が生成されました。簡単ですね。同じ原理で、保育勤務表もできると思います。

このように、簡単生成できるのは一重に、タスク型勤務表では行制約がない、という背景があります。しかし、本当に、行制約は不要でよいかというと、これについては、議論の余地があります。  明日へ続く。



2020年7月20日月曜日

休み曜日属性の実装

スタッフプロパティでの定型記述ですが、その度に、曜日集合をメンテするのも面倒なので、自動化を検討します。

DayElements:
月 Mon
火 Tue
水 Wed
木 Thu
金 Fri
土 Sat
日 Sun

例えば、プロジェクト上では、月水金(MonWedFri) とか、土日(SatSun)とか、グループ集合に記述するだけで、Day集合の記述が済むと便利です。また、Excel Import時には、Excel
スタッフプロパティに記述するだけで済みます。

 スタッフ名コメント全スタッフ属性1シフト禁止属性2シフト禁止属性週当たりの休み数属性休み曜日属性
 A1 全スタッフ   2 
 A2 全スタッフ 1シフト禁止  2 
 A3 全スタッフ  2シフト禁止  土日
 A4 全スタッフ    火
 A5 全スタッフ    日水金土
 A6 全スタッフ    
 A7 全スタッフ    月火金土
 A8 全スタッフ    木土
 A9 全スタッフ    水木
 A10 全スタッフ    土日
 
実装は、
1)グループ属性設定ボタンクリック時
2)要素が、全てDayElementsのみから成るならば、Day・Day集合で同名をチェック
3)定義されていなければ、Day集合定義追加


これであれば、既存のプロジェクトにも悪影響はないと思います。ソルバーには無関係でGUIC#のみで実装できます。7C2=21 7C3=35、 7C4,,なので、Dynamicに生成した方がよさそうです。

これで、アルバイトシフト作成チュートリアルの記述は、簡単になります。

2020年7月18日土曜日

シフト勤務表とタスク勤務表

今まで、色々な勤務表を見てきたのですが、大別すると、シフト勤務表とタスク勤務表に分類されます。

 今まで手がけてきた勤務表は、以下になります。
メインは、2交代3交代勤務表ですが、夜勤シフトが入らない勤務表も求められるようになりました。

そこで、登場したのが、タスクという概念です。これは、INRC2での記述をするときに導入したものです。シフトとタスクの混在でしたが、DayObjectという統一概念までには、至っていませんでした。

そこで、Refactoring を行い、今回、新たにDayObjectという概念を作りました。1日のDayは、Shift
とTaskで記述され、DayObject上で、結びつけられ、統一的に記述できます。なので、DayObjectは、Shiftの集合でもあり、Taskの集合でもあります。シフトの概念を拡張したものと考えてもよいです。

ただし、Algorithm4は、根底から構築しなおした方がよいとの結論に達しました。今のところ、Algorithm4の優位性は、コンペティション以外にはないのですが、必要になる可能性は、否定できないので、今回のRefactoringがまとまった後に再構築することにしました。

いずれにしても、今回のRefactoringにより、タスク勤務表が容易に記述できる効果の他に、シフト勤務表を拡張することも容易になります。シフトもタスクもどちらもDayObject上にあるので、相互の拡張が容易になります。多分、このShiftとTaskをDayObjectに融合するフレームワークは、学会でも報告がなく新しいと思います。このフレームワークにより、全ての勤務表を記述出来ると思います。



タスク勤務表シフト勤務表
訪問診療2交代勤務表(病棟・介護) 
訪問介護3交代勤務表(正循環・逆循環)
保育勤務表SchedulingBenchmark
アルバイト勤務表放送局
看護師応援割り当て派遣業務
3直4交代工場
INRC2 Benchmarks
TaskShift
DayObject
 PhaseObject Aggregates
 PhaseObjectTaskTaskAggregates
Shift
Shift Aggregates

2020年7月17日金曜日

アルバイトシフト問題の最適化

Tutorial用に何か良い例題がないか探しまして、ありました。
http://www.bunkyo.ac.jp/~nemoto/lecture/seminar2/98/katoh/sotsu-ron/main.htm

ここでいうパートナとは、恋愛の相手ではなくて、アルバイトする人のことです。OR上の基本的な定式化が述べられています。スケジュールナースⅢは、この問題で式を用いることがなく、Excelから必要人員をインポートして、全てGUIだけで記述し、最適化解を数秒で得ることが出来ます。

何を持って最適化とするかが、最も重要ですが、一つのアプローチとして、スタッフ毎に制約を追加することを提案しています。スケジュールナース上では、スタッフプロパティにあたります。

http://www.bunkyo.ac.jp/~nemoto/lecture/seminar2/98/katoh/sotsu-ron/jikken/7days.htm

アルバイトのシフト希望そのままではなく、制約を付加することで、経営的視点と勤務負担の平準化を狙っている訳です。

このようなプログラミングを、IntegerProgrammingといい、モデリング・記述・デバッグが必要で、ORの教育を受けた人しか出来ません。また、初期プログラミングの他に、実務的には、月々のメンテナンスが必要です。常に、専門家が在籍していればよいのですが、そうでない場合、制約変更記述の手間を考えると実用的ではなくなってしまうという問題があります。

「自動化と最適化を誰でも使えるようにすること、with どんなに細かい制約でも」、これがスケジュールナースの設計コンセプトで、まさにこの種の問題の解決手段となります。

とりあえず、上記をベースにタスク勤務表として、チュートリアルを作成してみることにします。














2020年7月11日土曜日

アルバイトのシフトテンプレート

フェーズ数が1から8まで作成しました。Excelをインポートするだけです。初心者が、フェーズ、シフト、タスクという概念を理解し、列制約を一から作り上げるのは、実のところ容易ではないのですが、こういったテンプレートからスタートすると、視覚的に理解しやすいガントチャート部とシフトをいじくるだけで、実務のシフトにマッチさせることができるので、有効ではないかと思いました。







2020年7月10日金曜日

アルバイトのシフト問題

Excelテンプレートから、SC3にインポートする実装を行いました。
下のフォーマットをインポートします。

そうすると、次のようなプロジェクトが自動で構築されます。
いくつかポイントがありますが、フェーズは、右上のようにシフトをガントチャートっぽく実装しています。例えば、Wというシフトは、フルタイムで働くシフト。PH12は、フェーズ01帯で働くシフトになります。タスクは、仕事1というタスクのみです。上の仕事1に対するスタッフ要求は、前回見たスタッフプロパティの縦要求と見ることもできます。なので、どこかにそのGUIを追加する必要があったのですが、タスクの予定と連動したほうが見易いと思い、右下のように実装しています。
3番目のポイントは、それらのDay毎に異なるMaxMin要求を左下で制約しています。MaxMinは、
右下を参照しているVectored Max/Minになります。

ということで、アルバイトのシフト問題を記述するのに多くの機能追加を行っています。
アルバイトの場合は、予定制約として、勤務希望を入れれば、他の制約は、殆どないのでナーススケジューリングに比べれば容易い問題です。ほぼ、Excelテンプレートさえあれば、簡単にSC3プロジェクトにインポートすることが出来、そのまま希望入力を打ち込んで任意の重みで最適解を得ることが可能です。

また、今回実装した機能を使うことにより、既存のナーススケジューリングも容易に拡張できるようになるます。また、AM/PM単位の訪問診療・訪問看護・保育勤務シフト等にも応用が出来ます。

2020年7月9日木曜日

vectored max/min 

上青部の最大最小は、マクロではありません。スタッフプロパティのグループ属性での値です。
スタッフ毎にMax/Minは、変えたい、それでいて制約名は同じとしたい、ということが出来るようになりました。Pythonでは、既に可能ですが、GUI上でも可能になりました。Pythonでは、浮動小数もサポートしますが、GUIでは、整数のみのサポートです。グループ属性で整数のみを記述すると選択できるようになります。

2020年7月8日水曜日

シフト整数計数のサポート

フェーズオブジェクトのみならず、シフトにも整数計数を実装しました。これにより、時間制約を使う必要がなくなりソフト制約化が可能になります。ソフト制約の単位は1(半日単位)です。上の場合、AMのみの場合が1、PMのみの場合が1、日勤(AM・PM両方)の場合2に設定しています。WAPは、これらのOR集合です。WAPに対する基数制約になります。このとき、シフト集合は、常に排他論理を満足するので、チェックはしていません。(Activeになるシフトは常に一つ/Day) 通常22日制約ですが、1日出勤すると2となるので、全体を44で制約しています。
 

2020年7月7日火曜日

世界記録更新

ナーススケジューリング業界で有名なTim Curtoisさんから返事を頂きました。光栄です。(ちょっと上から目線が感じられますが) ノッティンガム大学かと思ったのですが、所属は、商売敵のstaffrostersolutionsでした。やはりスピンアウトカンパニーのようです。HiGHsにしてもエジンバラ大学のJulian教授が率いてますし、基礎分野はイギリスが強い印象です。

Thank you very much for updating me with the new result. I have just
updated the website with the new information. It is nice work. Well done.
Please let me know if you have any new results and I will update the
website.
ということで、こちらプレスリリースをご覧ください。

2020年7月4日土曜日

Benchmark Result更新

WEBページを更新しました。LBは世界記録をとっくに突破していたのですが、思わぬ難敵が現れてUBが更新されてしまっていたので、とりあえずタイ記録を確認するまで、報告していませんでした。が、今回、UBのタイ記録を確認したので、schedulingbenchmarks.orgに報告しました。
(LBの証明は、難しく信じてもらうしかありません。)

付録として、こぷと1.2を含めたLP Solversの評価結果を添付しています。こぷと1.03と比較して、若干改善が見られましたが、CLPと比較して見るべきものはありませんした。 

2020年7月2日木曜日

アルバイトの勤務表ソフト構想

<折角の能力を範疇を広げてもっと使ってもらえるようにするには?>

ナーススケジューリングの場合は、シフトがKeyでした。一方、アルバイトの場合は、時間毎の場合が殆どで、シフトという明確な概念がない場合もあります。この対応をどうするかということを解決する必要があります。

で、シフトとフェーズの対応を考えたのが次です。フェーズとシフトは無数とも言える対応が可能ですが、予めフェーズ数に応じてシフトとの対応を定義しておきます。こうすると、これをベースに考えるように自然に誘導出来ます。(シフトとフェーズの対応は意外に難しく、何かテンプレートがあった方がよいようです。私自身、記述してみてシフトを使わずにフェース変数で記述してみたのですが、
シフトを使った方が自然な考え方のような気がしています。制約のデザインパターンと言うべきかもしれません。)

こうしたテンプレートを用意しておくことで、見かけ上記述が
簡単にでき、Excel上で、日毎のスタッフ要求数の表を用意するだけで、そのまま使えるようになります。(実際は、制約があって、自動割り当てとするには、あれこもこれもは..後から行制約として記述しないといけないのですが。それは、ユーザが追加することになります。シフトとして行制約として記述してもよいし、それでも足りなければフェーズ変数を定義することもでき,さらに、それでも足りなければPython..と無限の拡張記述能力を持つことががSC3の特徴です。)


1Phases 
1
2 
2Phases  
1
2 
3 
4  
3Phases   
1
2 
3 
4  
5  
6  
7    
    
4Phases    
1
2 
3 
4 
5  
6  
7  
8  
9   
10  
11    
5Phases     
1
2 
3 
4  
5  
6  
7  
8   
9   
10  
11     
6Phases      
1
2 
3 
4 
5  
6  
7  
8  
9   
10  
11  
12   
13   
14   
15   
16