(57)【要約】【課題】制約スケジューリングシステムにおいて最適解の探索速度を向上させる。【解決手段】各スタッフのスケジュールをCNFにエンコードする手段と制約エラーの部分和１１１を得る手段と前記部分和に対して許容最大値１１２を設定する手段１１３と前記部分和と制約エラーに対する総和をカウントする手段１１４と前記総和に対して許容最大値１１５を設定する手段１１６と前記ＣＮＦに対する充足判定を行うSATソルバを具備したことを特徴とする前記コンピュータを機能させるプログラム。【選択図】図１１
2015172794.tif 000002
【特許請求の範囲】
【請求項１】
所定の集団に属するスタッフの
スケジューリング制約に対する解をコンピュータを用いて解くためのプログラムであって、
各スタッフのスケジュールをCNFにエンコードする手段と
制約エラーの部分和を得る手段と
前記部分和に対して許容最大値を設定する手段と
前記部分和と制約エラーに対する総和をカウントする手段と
前記総和に対して許容最大値を設定する手段と
前記ＣＮＦに対する充足判定を行うSATソルバを具備したことを特徴とする
前記コンピュータを機能させるプログラム。
【請求項２】
複数回、SATソルバの充足判定結果得る機構を有した請求項１に記載のプログラム
【請求項３】
予め定められた制限時間内にSATソルバの充足判定結果が得られないとき、充足不能の判断を行う請求項１に記載のプログラム。
【請求項４】
優先度付きの制約に対する制約エラーの部分和をカウントする手段を有した請求項１に記載のプログラム。
【請求項５】
充足解の否定をSATソルバに追加する機講を有した請求項2に記載のプログラム。
【請求項６】
充足解の解の一部をハード制約としてSATソルバに入力する機構を有した請求項１に記載のプログラム。
【請求項７】
充足不能の原因となる制約を指摘する手段を有した請求項2に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム、スケジューリング方法及びスケジューリング装置に関し、特に解探索の高速化に寄与する。
【背景技術】
【０００２】
従来より、所定の集団に属するスタッフのスケジュールを最適化するナーススケジューリング問題が一般的に知られている。この種のスケジューリング問題に対する解法として、特許文献２に開示されているように遺伝的アルゴリズムがある。また、非特許文献１にあるように、混合線形計画問題（MILP)や、充足可能性判定問題（SAT)による解法が提案されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許4398672
【特許文献２】特許4467286
【非特許文献】
【０００４】
【非特許文献１】SATを用いたナーススケジューリング問題の厳密解法の評価(スケジューリング)日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集 2010, 120-121, 2010-03-04
【非特許文献２】ナーススケジューリング問題における混合整数線形計画問題と充足可能性判定問題による厳密解法の比較  オペレーションズ・リサーチ : 経営の科学 55(11), 706-712, 2010-11-01
【非特許文献３】システムＬＳＩ設計自動化技術の基礎  ９７−１１０p 培風館
【非特許文献４】C. Sinz, "Towards an Optimal CNF Encoding of Boolean Cardinality Constraints", in International Conference on Principles and Practices of Constraint Programming , 2005
【発明の概要】
【発明が解決しようとする課題】
【０００５】
前記特許文献１では、仮割付によるヒューリスティクスによる方法、特許文献２で開示されたスケジューリング方法では、遺伝的アルゴリズムにより解の探索が行われ準最適解が得られる。しかしながら、解は準最適解であり常に最適解であるとは限らないという問題がある。非特許文献１では、MILPまたは、SATソルバを用いることにより最適解が得られることが示されている。非特許文献2ではSATソルバは、制約エラーの数が少ない問題ではMILPより性能的に優秀であることが示されているが、制約エラーが多い問題では、解の探索速度が遅くなる問題を指摘している。本発明は、この課題を解消するためになされたものである。
【課題を解決するための手段】
【０００６】
所定の集団に属するスタッフのスケジューリング制約に対する解をコンピュータを用いて解くためのプログラムは、各スタッフのスケジュールをCNFにエンコードする手段と制約エラーの部分和を得る手段と前記部分和に対して許容最大値を設定する手段と
前記部分和と制約エラーに対する総和をカウントする手段と前記総和に対して許容最大値を設定する手段と前記ＣＮＦに対する充足判定を行うSATソルバを有する。
【発明の効果】
【０００７】
本発明によれば、スケジュール制約の最適解を迅速に探索できる。
【図面の簡単な説明】
【０００８】
【図１】本発明によって得られた解の一出力例である。
【図２】本発明の係わるシステムの一部で、本発明からみると入力の一部になる。
【図３】本発明の係わるシステムの一部で、本発明からみると入力の一部になる。
【図４】本発明の係わるシステムの一部で、本発明からみると入力の一部になる。
【図５】本発明に係わるシステムのブロック図である。
【図６】ＣＮＦフォーマットの一例（Dimacsフォーマット）である。
【図７】制約の説明図である。
【図８】ソフト制約の実現方法の説明図である
【図９】ＳＡＴソルバを用いたソフト制約をエラーの最小値を求めるフローチャートである。
【図１０】従来方法によるソフト制約エラーの計算部ブロック図である
【図１１】本発明によるソフト制約エラーの計算ブロック図である。
【図１２】従来と本発明のＣＮＦ節数の比較である。
【図１３】タイムアウトを附加した本発明の実施例である。
【図１４】本発明による優先度付きソフト制約の実行を方法を示すフローチャートである。
【図１５】本発明による複数の解を得るフローチャートである。
【図１６】本発明による出力を入力に戻して編集を行う方式のフローチャートである。
【図１７】出力を入力に戻した後、ユーザが編集を行った後の画面の一例である。
【図１８】ＵＮＳＡＴの原因を解析する手順を示したフローチャートである。
【発明を実施するための形態】
【０００９】
以下、本発明の実施の形態を図面に基づいて説明する。
【００１０】
図１は、本発明によって得られた解をコンピュータの表示部に表示された出力例である。この勤務表の例では、病院の特定病棟に勤務する看護師（スタッフ）について勤務スケジュールを割り当てた結果が表示されている。各セルには、勤務形態（シフト）を示すシンボルが記入されている。各スタッフのスケジュールは、１日毎になんらかのシフトが割り当てられており、この例では、３７日分のシフトが割りあてられている。
【００１１】
解を得るには、スケジュールの制約を入力することが必要である。図２は、制約の一つである初期条件の入力画面の例である。予め決まったスケジュールや、スタッフの希望勤務・休み等を入力する。
【００１２】
図３は、スタッフの勤務パターン（行制約）に関する制約例である。図４は、毎日のシフトに関する制約（列制約）である。図１、図２、図３、図４の関係をまとめたものが、図５である。すなわち、本発明による方法では、スケジュールに関する制約をＣＮＦで表現し、ＳＡＴソルバへの入力とする。
【００１３】
図６は、図２、図３、図４の制約をＣＮＦで現した一部である。この例の場合、本発明を実施した結果、ＣＮＦ変数の数が10103、ＣＮＦ節数が、46155となった。ＣＮＦ変数数とＣＮＦ節数は問題の規模と相関があるとされている。より大規模な問題またはより複雑な制約程、ＣＮＦ変数数とＣＮＦ節数が大きくなる傾向にある。従って、同じ問題に対して、より小さなＣＮＦ変数数・ＣＮＦ節数で表現できれば、よりＳＡＴソルバの求解高速化を期待できる。
【００１４】
制約は、図７のように必ず満たさなければいけないハード制約とソフト制約（必ずしも満たさなくてもよいができるだけ満たしたい制約）に分けられる。法令遵守や予め決まったスケジュール等はハード制約になる。ソフト制約は、できれば避けたい勤務パターン、例えば、スタッフにとって負荷の高い2連続深夜等がこれに該当する。
【００１５】
ＳＡＴソルバ単体には、ソフト制約に対するハンドリング機構はない。ＳＡＴソルバは、与えられたＣＮＦに対して充足可能ならば、充足可能な１解を示すのみである。図８に示すように、ソフト制約の「できれば」は、ソフト制約エラーの総数を最小にすることに他ならない。
すなわち、スケジュール制約における最適化とは、ハード制約を全て満たした上で、ソフト制約エラー数（制約を遵守できない数）の総和を最小にすることである。ソフト制約エラーの最小解を求めるには、図９に示すように、ソフト制約エラーの総和が許容エラー値以下であるという制約を附加しそれに対して充足可能かどうかを見る、という探索操作を複数回行えば可能である。この探索手法としては、バイナリサーチやリニアサーチ等がある。
【００１６】
図１０は、ソフト制約総数の計算構造を示した従来技術の実施例である。  全制約エラー総数は、各スタッフのスケジュール期間中のエラー数和と各日（列）に対する制約エラーの和になる。ソフト制約を実現するには、制約エラーを現す変数(x1,x2,..xn)がのうち真になる変数数が、ある許容設定値Ｋ以下であるときに、充足解が得られればよい。これを一般化すると数1式になる。
【数１】
2015172794.tif 000003
【００１７】
数1式を実現するＣＮＦ記述は、いくつか公知のものが知られている。例えば、非特許文献４に記載の方法によれば、そのＣＮＦ節数は、次のオーダになる。
【数２】
2015172794.tif 000004
【００１８】
図１１は、本発明の根幹の構造図である。従来実施例に対して、制約エラーの部分和に対する制約を追加している。数2式により、従来実施方法と、本発明とで、ＣＮＦ節数の比較を行ったものが、表１である。
【表１】
2015172794.tif 000005
【００１９】
表1から本発明では、従来技術に比べＣＮＦ節数が大幅に減少していることが分かる。表1の従来技術と本発明によるＣＮＦ節数の比をプロットしたのが、図１２である。特に本発明による効果が、各スタッフの制約エラー数が少ないときに顕著であることを示している。ＣＮＦ節数の大幅な減少は、所要メモリの減少、アクセス帯域の増加、キャッシュヒット率の向上が期待でき、求解速度の高速化が期待できる。この例では、スタッフ毎の制約エラー数の和を制約としたが、本発明はこれに限定するものではない。
【００２０】
尚、本発明は、前記実施形態について、以下のような構成としてもよい。
【００２１】
最適解ではなくとも、より迅速に準最適解を得たい場合がある。そのような場合に好適な構成を図１３に示した。前記実施形態において、ＳＡＴソルバ起動時にタイマーを設け、予め決められた時間内にＳＡＴソルバの解が得られなければ充足不能と判断し、次の許容エラー数Ｋについて探索を行う。
【００２２】
前記実施形態を複数回呼び出す構成（図１４）としてもよい。図３のソフト制約レベル３1が、ソフト制約のレベルの例である。この場合、まずソフト制約４について、最小値の探索が行われ、続いて３、２についても同様に行われる。つまり、ソフト制約４を優先的に最小値が求められたことになる。ソフトレベル３は、ソフトレベル２よりも優先的に最小値が求められる。
【００２３】
前記実施形態において、複数の解を得たい場合がある。そのような場合に、好適な構成を図１５に示した。複数回、ＳＡＴソルバを呼べばよいが、それでは同じ解が出力されてしまう場合がある。これを避けるためには、現在の解の否定を制約として入力すればよい。例えば、解の集合が{1 2 -3 4 5 }である場合には、{-1 -2 3 -4 -5} というＣＮＦ節をＳＡＴソルバに追加すればよい。こうすれば、現在の解があってはならないという制約になるので別解が得られることになる。
【００２４】
前記実施形態において、解の一部を編集して新たな解を得たい場合がある。そのような場合に好適な構成を図１６に示す。解を得た後に、図17に示すようにユーザは、解を得たあとに必要な部分をブランクにする。その後、ブランク以外の箇所はハード制約としてＣＮＦを生成するようにすれば、より探索空間を狭めることができ、必要な複数解を高速に得ることが出来る。
【００２５】
解は、常に充足可能（ＳＡＴ）であるとは限らない。ユーザが入力するスケジュール制約に対して充分な人的資源が与えられない場合があるからである。ＳＡＴソルバーは、このときＵＮＳＡＴ（充足不能）を示すだけであって、充足不能の原因がどこにあるかは分からない。しかしながら、図１８の構成を取れば、ＵＮＳＡＴの原因となる制約箇所を示すことが出来る。ＣＮＦ生成時に個々の制約と対応するＣＮＦ集合とをテーブルに格納しておく。このテーブルに対して、解の結果がＵＮＳＡＴだった場合、例えば、バイナリサーチ、リニアサーチ等の探索によりＵＮＳＡＴとＳＡＴの境界を得る。ＳＡＴからＵＮＳＡＴに変ったところの制約１８１が、ＵＮＳＡＴの原因である。
このようにして、ユーザは、ＵＮＳＡＴの原因を知ることが出来、制約を修正して速やかに、前記実施形態により解を得ることが可能になる。
【実施例】
【００２６】
図１、図２、図3、図4の形態において、従来技術による方法と本発明による方法とで比較を行った。
本実施例は、ある病棟のスタッフ数26名の勤務シフト休み希望（図２）と制約（図３、図４）を使って行ったものである。
結果を表２に示す。本発明の適用によりＣＮＦ変数数および節数が従来技術による方法に比べ大幅に削減されている。その結果、本発明は、約4倍高速であり本発明の有効性を確認できる。
【表２】
2015172794.tif 000006
【符号の説明】
【００２７】
３１ ソフト制約レベル  
１１１  制約エラーの部分和  １１２  部分和に対する最大許容エラー数  １１３  部分和に対して最大許容エラー数を制約する手段  １１４  制約エラーの総和  １１５  全体の許容エラー数設定  １１６  総和に対して最大許容エラー数を制約する手段  
１８１  ＵＮＳＡＴの原因制約
【図１】
2015172794.tif 000007
【図２】
2015172794.tif 000008
【図３】
2015172794.tif 000009
【図４】
2015172794.tif 000010
【図５】
2015172794.tif 000011
【図６】
2015172794.tif 000012
【図７】
2015172794.tif 000013
【図８】
2015172794.tif 000014
【図９】
2015172794.tif 000015
【図１０】
2015172794.tif 000016
【図１１】
2015172794.tif 000017
【図１２】
2015172794.tif 000018
【図１３】
2015172794.tif 000019
【図１４】
2015172794.tif 000020
【図１５】
2015172794.tif 000021
【図１６】
2015172794.tif 000022
【図１７】
2015172794.tif 000023
【図１８】
2015172794.tif 000024
【手続補正書】
【提出日】平成26年10月8日(2014.10.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
所定の集団に属するスタッフのスケジュールを構成するシフトとスケジュール制約をＣＮＦにエンコードし、前記ＣＮＦを用いて充足可能解を得ることによってスケジュールの最適化を行う方法をコンピュータに実行させるためのプログラムであって、
前記スケジュール制約は、必ず守るべき制約であるハード制約と、必ずしも満たす必要はないができれば満たしたい制約であるソフト制約とから成り、
前記ソフト制約のエラー数の和がＫ以下となる不等式を前記ＣＮＦにエンコードするエンコード手段、
前記ＣＮＦに対する複数の充足可能または充足不能の結果を用いて、前記Ｋの最小値を、バイナリサーチまたはリニアサーチに基づいて探索する探索手段、
として前記コンピュータを機能させるためのプログラム。
【請求項２】
請求項１に記載したプログラムであって、
前記エンコード手段が、各スタッフ毎に前記不等式を前記ＣＮＦにエンコードするように前記コンピュータを機能させるためのプログラム。
【請求項３】
請求項１又は２に記載したプログラムであって、
前記探索手段による探索の開始時にタイマを起動させるタイマ起動手段、
前記タイマ起動手段により前記タイマを起動させてから予め決められた時間内に充足判定結果が得られない場合に、充足不能の判断を行う充足不能判断手段、
として前記コンピュータをさらに機能させるためのプログラム。
【請求項４】
請求項３に記載したプログラムであって、
前記エンコード手段が、前記充足不能判断手段によって充足不能と判断された場合に、前記Ｋの値を更新して、前記不等式を前記ＣＮＦにエンコードし直し、
前記探索手段が、前記充足不能判断手段によって充足不能と判断されなくなるまでの間、前記Ｋの最小値の探索を繰り返し実行するように前記コンピュータを機能させるためのプログラム。
【手続補正書】
【提出日】平成27年4月27日(2015.4.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
所定の集団に属するスタッフのスケジュールを構成するシフトとスケジュール制約をＣＮＦにエンコードし、前記ＣＮＦを用いて充足可能解を得ることによってスケジュールの最適化を行う方法をコンピュータに実行させるためのプログラムであって、
前記スケジュール制約は、必ず守るべき制約であるハード制約と、必ずしも満たす必要はないができれば満たしたい制約であるソフト制約とから成り、
前記ソフト制約のエラー数の和がＫ以下となる不等式を前記ＣＮＦにエンコードするエンコード手段、
前記ＣＮＦに対する複数の充足可能または充足不能の結果を用いて、前記Ｋの最小値を、バイナリサーチまたはリニアサーチに基づいて探索する探索手段、
前記探索手段による探索の開始時にタイマを起動させるタイマ起動手段、
前記タイマ起動手段により前記タイマを起動させてから予め決められた時間内に充足判定結果が得られない場合に、充足不能の判断を行う充足不能判断手段、
として前記コンピュータを機能させ、
前記エンコード手段が、前記充足不能判断手段によって充足不能と判断された場合に、前記Ｋの値を更新して、前記不等式を前記ＣＮＦにエンコードし直し、
前記探索手段が、前記充足不能判断手段によって充足不能と判断されなくなるまでの間、前記Ｋの最小値の探索を繰り返し実行するように前記コンピュータを機能させるためのプログラム。
【請求項２】
請求項１に記載したプログラムであって、
前記エンコード手段が、各スタッフ毎に前記不等式を前記ＣＮＦにエンコードするように前記コンピュータを機能させるためのプログラム。