(57)【特許請求の範囲】
【請求項１】
周期的に繰り返される繰り返し期間中の曜日と週との組合せ毎に、放射線治療の各プロトコールに対して基点となる治療工程の日を示すように当該各プロトコールを割当てたスケジュールパターンを生成する繰り返し型スケジュール生成装置であって、
前記各治療工程における治療部位と照射治療工程の回数とを示す前記各プロトコールと、前記各プロトコールの患者数とを規定した割当作業情報を記憶する第１の記憶手段と、
前記各プロトコールに対する各治療工程及び当該各治療工程のうちの基点となる治療工程を規定した治療工程情報を記憶する第２の記憶手段と、
前記各治療工程間に空ける日数及び前記照射治療工程の回数に関する制約を規定した制約情報とを記憶する第３の記憶手段と、
前記各プロトコールを割当て可能な曜日と週との組合せを個別に示す割当時間情報を記憶する第４の記憶手段と、
前記割当時間情報内の曜日と週との組合せに個別に割り当てられた曜日種類を規定した割当時間種類情報を記憶する第５の記憶手段と、
前記割当時間情報及び前記割当作業情報に基づいて、当該割当時間情報に示される曜日と週との組合せを個別に示す複数の割当時間ノードと、当該割当作業情報に規定された各プロトコールを個別に示す複数のプロトコールノードと、前記各割当時間ノードと前記各プロトコールノードとの組合せを個別に示す複数の割当アークと、前記各プロトコールの患者数とを含む割当ネットワークを作成する割当ネットワーク作成手段と、
前記割当作業情報及び前記割当時間情報に基づいて、前記各割当アーク毎に、割当て可能な患者数としての流量を制限する流量制限値を算出する流量制限値算出手段と、
前記割当時間情報及び前記割当時間種類情報に基づいて、前記曜日種類を個別に示す複数の割当時間種類ノードと、前記各割当時間種類ノードのうちの有効な割当時間種類ノードを個別に示す複数の割当時間種類アークとを生成する種類要素生成手段と、
前記割当作業情報、前記割当時間情報及び前記割当時間種類情報に基づいて、前記各プロトコール毎に、前記各割当時間種類アークの使用枝数を制限する使用枝数制限値を算出する使用枝数制限値算出手段と、
前記割当ネットワーク、前記流量制限値、前記各割当時間種類ノード、前記各割当時間種類アーク及び前記使用枝数制限値を統合することにより、前記各割当時間ノードと、前記各プロトコールノードと、前記各割当アークと、前記患者数と、前記流量制限値と、前記各割当時間種類ノードと、前記各割当時間種類アークと、前記使用枝数制限値とを含む制限ネットワークを作成する制限ネットワーク作成手段と、
前記制限ネットワーク、前記治療工程情報及び前記制約情報に基づいて、前記スケジュールパターンを生成し、当該生成したスケジュールパターンをスケジュールパターン記憶手段に書込むスケジュールパターン生成手段と、
前記書込まれたスケジュールパターンを記憶する前記スケジュールパターン記憶手段と、
前記スケジュールパターン記憶手段からスケジュールパターンを読出し、当該読出したスケジュールパターンを出力するスケジュールパターン出力手段と
を備えたことを特徴とする繰り返し型スケジュール生成装置。
【請求項２】
請求項１に記載の繰り返し型スケジュール生成装置において、
前記流量制限値算出手段は、前記割当作業情報に規定された各プロトコールをｊと表し、前記繰り返し期間中の日の各プロトコールｊの患者数をｄjと表し、前記割当時間情報に示される各日の集合をＩと表し、前記集合Ｉに含まれる各日の個数を｜Ｉ｜と表し、前記流量制限値のうちの流量上限値をFLOW(j)と表すとき、下記式に示すように、前記流量上限値FLOW(j)を前記流量制限値として算出する流量上限値算出部を備え、
前記使用枝数制限値算出手段は、前記割当時間情報に示される週の種類の数をｈと表し、前記使用枝数制限値のうちの使用枝数上限値をUSE(j)と表すとき、下記式に示すように、前記使用枝数上限値USE(j)を前記使用枝数制限値として算出する使用枝数上限値算出部を備えたことを特徴とする繰り返し型スケジュール生成装置。
【数１】
0005762873.tif 000009
【請求項３】
請求項２に記載の繰り返し型スケジュール生成装置において、
前記スケジュールパターンの出力後、ユーザの操作に応じて、前記流量制限値及び前記使用枝数制限値を個別に設定する制限値設定手段と、
前記設定された流量制限値及び使用枝数制限値に基づいて、前記制限ネットワーク作成手段、前記スケジュールパターン生成手段及び前記スケジュールパターン出力手段を再実行するように制御する再実行制御手段と
を備えたことを特徴とする繰り返し型スケジュール生成装置。
【請求項４】
請求項３に記載の繰り返し型スケジュール生成装置において、
前記制限値設定手段は、
前記流量制限値のうちの流量下限値をFLOW_L(j)と表すとき、下記式に示すように、前記流量下限値FLOW_L(j)を前記流量制限値として算出し、当該算出した流量下限値FLOW_L(j)を設定する流量下限値設定部と、
前記使用枝数制限値のうちの使用枝数下限値をUSE_L(j)と表すとき、下記式に示すように、前記使用枝数下限値USE_L(j)を前記使用枝数制限値として算出し、当該算出した使用枝数下限値USE_L(j)を設定する使用枝数下限値設定部と
を備えたことを特徴とする繰り返し型スケジュール生成装置。
【数２】
0005762873.tif 000010
【請求項５】
請求項２に記載の繰り返し型スケジュール生成装置において、
立案期間Ｔを示す立案期間情報を記憶する第６の記憶手段と、
前記各治療工程の間に空ける日数種類ｌを規定した日数種類情報を記憶する第７の記憶手段と、
前記各治療工程のうちの照射治療工程を休む日のパターンｋを規定した休治療日パターン情報を記憶する第８の記憶手段と
を更に備え、
前記スケジュールパターン生成手段は、前記立案期間Ｔ中の日を｛０，…，T｝と表し、前記各治療工程をｓと表し、当該各治療工程ｓの集合をＳと表し、前記集合Ｉに含まれる各日をｉと表し、前記パターンｋの集合をＫと表し、前記各プロトコールｊの集合をＪと表し、前記日数種類ｌの集合をＬと表し、一週間中の曜日をｗと表し、当該曜日ｗの集合をＷと表し、前記繰り返し期間中の曜日ｗの日の集合をDAY(w),(w∈W)と表し、前記各日ｉと前記パターンｋと前記各プロトコールｊと前記日数種類ｌとの組合せikjlにおける患者数をｙikjlと表し、前記患者数ｙikjlのとりうる値の上界値をγと表し（但し、ｒ＝max｛FLOW(j)｜ｊ∈Ｊ｝）、
【数３】
0005762873.tif 000011
のとりうる値の上界値をυと表し（但し、υ＝max｛USE(j)｜ｊ∈Ｊ｝）、前記組合せikjlにおいて患者を一人割り当てた場合の日tにおける治療工程sの作業時間を示すコストをc’tsikjlと表し、前記組合せikjlにおいて患者を一人でも割り当てた場合を１とする０−１変数をxikjlと表し、前記曜日ｗにプロトコールｊを割り当てた場合を１とする０−１変数をuwjと表し、整数全体をＺと表し、下記式に示す混合整数線形計画問題の評価値をｚと表すとき、前記評価値ｚを最小化するように前記混合整数線形計画問題を解くことにより、前記スケジュールパターンを生成するソルバ手段を備えたことを特徴とする繰り返し型スケジュール生成装置。
【数４】
0005762873.tif 000012
【請求項６】
請求項１に記載の繰り返し型スケジュール生成装置において、
前記放射線治療に代えて、定期作業を用い、
前記各プロトコールに代えて、各作業種類を用い、
前記各治療工程に代えて、各作業工程を用い、
前記患者数に代えて、作業対象数を用い、
前記治療部位と照射治療工程の回数に代えて、点検作業又は工具の交換作業を用い、
前記各治療工程間に空ける日数及び前記照射治療工程の回数に関する制約に代えて、前記作業工程間に空ける日数に関する制約を用い、
前記曜日と週との組合せに代えて、作業点を用い、
前記割当時間情報に代えて、作業点情報を用い、
前記曜日種類に代えて、作業員を用い、
前記割当時間種類情報に代えて、作業点種類情報を用い、
前記割当時間ノードに代えて、作業点ノードを用い、
前記プロトコールノードに代えて、作業種類ノードを用い、
前記割当時間種類ノードに代えて、作業点種類ノードを用い、
前記割当時間種類アークに代えて、作業点種類アークを用いたことを特徴とする繰り返し型スケジュール生成装置。
【請求項７】
情報入力手段、第１の記憶手段、第２の記憶手段、第３の記憶手段、第４の記憶手段、第５の記憶手段、割当ネットワーク作成手段、流量制限値算出手段、種類要素生成手段、使用枝数制限値算出手段、制限ネットワーク作成手段、スケジュールパターン生成手段、スケジュールパターン記憶手段、及びスケジュールパターン出力手段を備え、周期的に繰り返される繰り返し期間中の曜日と週との組合せ毎に、放射線治療の各プロトコールに対して基点となる治療工程の日を示すように当該各プロトコールを割当てたスケジュールパターンを生成する繰り返し型スケジュール生成装置が実行する繰り返し型スケジュール生成方法であって、
前記情報入力手段が、前記各治療工程における治療部位と照射治療工程の回数とを示す前記各プロトコールと、前記各プロトコールの患者数とを規定した割当作業情報を前記第１の記憶手段に書込む工程と、
前記情報入力手段が、前記各プロトコールに対する各治療工程及び当該各治療工程のうちの基点となる治療工程を規定した治療工程情報を前記第２の記憶手段に書込む工程と、
前記情報入力手段が、前記各治療工程間に空ける日数及び前記照射治療工程の回数に関する制約を規定した制約情報を前記第３の記憶手段に書込む工程と、
前記情報入力手段が、前記各プロトコールを割当て可能な曜日と週との組合せを個別に示す割当時間情報を前記第４の記憶手段に書込む工程と、
前記情報入力手段が、前記割当時間情報内の曜日と週との組合せに個別に割り当てられた曜日種類を規定した割当時間種類情報を前記第５の記憶手段に書込む工程と、
前記割当ネットワーク作成手段が、前記割当時間情報及び前記割当作業情報に基づいて、当該割当時間情報に示される曜日と週との組合せを個別に示す複数の割当時間ノードと、当該割当作業情報に規定された各プロトコールを個別に示す複数のプロトコールノードと、前記各割当時間ノードと前記各プロトコールノードとの組合せを個別に示す複数の割当アークと、前記各プロトコールの患者数とを含む割当ネットワークを作成する割当ネットワーク作成工程と、
前記流量制限値算出手段が、前記割当作業情報及び前記割当時間情報に基づいて、前記各割当アーク毎に、割当て可能な患者数としての流量を制限する流量制限値を算出する流量制限値算出工程と、
前記種類要素生成手段が、前記割当時間情報及び前記割当時間種類情報に基づいて、前記曜日種類を個別に示す複数の割当時間種類ノードと、前記各割当時間種類ノードのうちの有効な割当時間種類ノードを個別に示す複数の割当時間種類アークとを生成する種類要素生成工程と、
前記使用枝数制限値算出手段が、前記割当作業情報、前記割当時間情報及び前記割当時間種類情報に基づいて、前記各プロトコール毎に、前記各割当時間種類アークの使用枝数を制限する使用枝数制限値を算出する使用枝数制限値算出工程と、
前記制限ネットワーク作成手段が、前記割当ネットワーク、前記流量制限値、前記各割当時間種類ノード、前記各割当時間種類アーク及び前記使用枝数制限値を統合することにより、前記各割当時間ノードと、前記各プロトコールノードと、前記各割当アークと、前記患者数と、前記流量制限値と、前記各割当時間種類ノードと、前記各割当時間種類アークと、前記使用枝数制限値とを含む制限ネットワークを作成する制限ネットワーク作成工程と、
前記スケジュールパターン生成手段が、前記制限ネットワーク、前記治療工程情報及び前記制約情報に基づいて、前記スケジュールパターンを生成するスケジュールパターン生成工程と、
前記スケジュールパターン生成手段が、前記生成したスケジュールパターンを前記スケジュールパターン記憶手段に書込むスケジュールパターン書込工程と、
前記スケジュールパターン出力手段が、前記スケジュールパターン記憶手段からスケジュールパターンを読出し、当該読出したスケジュールパターンを出力するスケジュールパターン出力工程と
を備えたことを特徴とする繰り返し型スケジュール生成方法。
【請求項８】
請求項７に記載の繰り返し型スケジュール生成方法において、
前記流量制限値算出工程は、前記割当作業情報に規定された各プロトコールをｊと表し、前記繰り返し期間中の日の各プロトコールｊの患者数をｄjと表し、前記割当時間情報に示される各日の集合をＩと表し、前記集合Ｉに含まれる各日の個数を｜Ｉ｜と表し、前記流量制限値のうちの流量上限値をFLOW(j)と表すとき、下記式に示すように、前記流量上限値FLOW(j)を前記流量制限値として算出する流量上限値算出工程を備え、
前記使用枝数制限値算出工程は、前記割当時間情報に示される週の種類の数をｈと表し、前記使用枝数制限値のうちの使用枝数上限値をUSE(j)と表すとき、下記式に示すように、前記使用枝数上限値USE(j)を前記使用枝数制限値として算出する使用枝数上限値算出工程を備えたことを特徴とする繰り返し型スケジュール生成方法。
【数５】
0005762873.tif 000013
【請求項９】
請求項８に記載の繰り返し型スケジュール生成方法において、
前記繰り返し型スケジュール生成装置は、制限値設定手段及び再実行制御手段を更に備え、
前記制限値設定手段が、前記スケジュールパターンの出力後、ユーザの操作に応じて、前記流量制限値及び前記使用枝数制限値を個別に設定する制限値設定工程と、
前記再実行制御手段が、前記設定された流量制限値及び使用枝数制限値に基づいて、前記制限ネットワーク作成工程、前記スケジュールパターン生成工程、前記スケジュールパターン書込工程及び前記スケジュールパターン出力工程を再実行するように、前記制限ネットワーク作成手段、前記スケジュールパターン生成手段及び前記スケジュールパターン出力手段を制御する再実行制御工程と
を備えたことを特徴とする繰り返し型スケジュール生成方法。
【請求項１０】
請求項９に記載の繰り返し型スケジュール生成方法において、
前記制限値設定工程は、
前記流量制限値のうちの流量下限値をFLOW_L(j)と表すとき、下記式に示すように、前記流量下限値FLOW_L(j)を前記流量制限値として算出し、当該算出した流量下限値FLOW_L(j)を設定する流量下限値設定工程と、
前記使用枝数制限値のうちの使用枝数下限値をUSE_L(j)と表すとき、下記式に示すように、前記使用枝数下限値USE_L(j)を前記使用枝数制限値として算出し、当該算出した使用枝数下限値USE_L(j)を設定する使用枝数下限値設定工程とを備えたことを特徴とする繰り返し型スケジュール生成方法。
【数６】
0005762873.tif 000014
【請求項１１】
請求項８に記載の繰り返し型スケジュール生成方法において、
前記繰り返し型スケジュール生成装置は、第６の記憶手段、第７の記憶手段及び第８の記憶手段を更に備え、
前記情報入力手段が、立案期間Ｔを示す立案期間情報を前記第６の記憶手段に書込む工程と、
前記情報入力手段が、前記各治療工程の間に空ける日数種類ｌを規定した日数種類情報を前記第７の記憶手段に書込む工程と、
前記情報入力手段が、前記各治療工程のうちの照射治療工程を休む日のパターンｋを規定した休治療日パターン情報を前記第８の記憶手段に書込む工程と
を更に備え、
前記スケジュールパターン生成工程は、前記立案期間Ｔ中の日を｛０，…，T｝と表し、前記各治療工程をｓと表し、当該各治療工程ｓの集合をＳと表し、前記集合Ｉに含まれる各日をｉと表し、前記パターンｋの集合をＫと表し、前記各プロトコールｊの集合をＪと表し、前記日数種類ｌの集合をＬと表し、一週間中の曜日をｗと表し、当該曜日ｗの集合をＷと表し、前記繰り返し期間中の曜日ｗの日の集合をDAY(w),(w∈W)と表し、前記各日ｉと前記パターンｋと前記各プロトコールｊと前記日数種類ｌとの組合せikjlにおける患者数をｙikjlと表し、前記患者数ｙikjlのとりうる値の上界値をγと表し（但し、ｒ＝max｛FLOW(j)｜ｊ∈Ｊ｝）、
【数７】
0005762873.tif 000015
のとりうる値の上界値をυと表し（但し、υ＝max｛USE(j)｜ｊ∈Ｊ｝）、前記組合せikjlにおいて患者を一人割り当てた場合の日tにおける治療工程sの作業時間を示すコストをc’tsikjlと表し、前記組合せikjlにおいて患者を一人でも割り当てた場合を１とする０−１変数をxikjlと表し、前記曜日ｗにプロトコールｊを割り当てた場合を１とする０−１変数をuwjと表し、整数全体をＺと表し、下記式に示す混合整数線形計画問題の評価値をｚと表すとき、前記評価値ｚを最小化するように前記混合整数線形計画問題を解くことにより、前記スケジュールパターンを生成するソルバ工程を備えたことを特徴とする繰り返し型スケジュール生成方法。
【数８】
0005762873.tif 000016
【請求項１２】
請求項７に記載の繰り返し型スケジュール生成方法において、
前記放射線治療に代えて、定期作業を用い、
前記各プロトコールに代えて、各作業種類を用い、
前記各治療工程に代えて、各作業工程を用い、
前記患者数に代えて、作業対象数を用い、
前記治療部位と照射治療工程の回数に代えて、点検作業又は工具の交換作業を用い、
前記各治療工程間に空ける日数及び前記照射治療工程の回数に関する制約に代えて、前記作業工程間に空ける日数に関する制約を用い、
前記曜日と週との組合せに代えて、作業点を用い、
前記割当時間情報に代えて、作業点情報を用い、
前記曜日種類に代えて、作業員を用い、
前記割当時間種類情報に代えて、作業点種類情報を用い、
前記割当時間ノードに代えて、作業点ノードを用い、
前記プロトコールノードに代えて、作業種類ノードを用い、
前記割当時間種類ノードに代えて、作業点種類ノードを用い、
前記割当時間種類アークに代えて、作業点種類アークを用いたことを特徴とする繰り返し型スケジュール生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを用いたスケジューリングにおいて、規則性のある偏らないスケジュールパターンを生成し得る繰り返し型スケジュール生成装置及び方法に関する。
【背景技術】
【０００２】
例えば、放射線治療のスケジューリングでは、安全に治療を行うため，医療スタッフが認識しやすいスケジュールを生成することが重要である。週単位で繰り返すスケジュールのように、曜日に規則性を持たせると医療スタッフが認識しやすくなる。
【０００３】
しかしながら、放射線治療では、プロトコール（病状種別）の種類数と割合によっては２〜３週間に一度だけ治療を行うプロトコールが含まれる場合がある。このため、スケジューリングの際には、必ずしも１週間の繰返しではなく、複数週の単位で繰り返すスケジュールが作成される。この複数週のスケジュールの入れ方又は入れられた結果をスケジュールパターンと呼ぶ。
【０００４】
このようなスケジュールパターンは、人が覚えやすい規則性を持たせるために、前の週と次の週を似たパターンにしたい。一方、スケジュールパターンは、使い勝手を良くするために、特定のプロトコールを特定の日にスケジューリングすることなく、偏らないパターンにしたい。
【０００５】
しかしながら、規則性のある偏らないスケジュールパターンを生成することは、困難な状況にある。この状況について、放射線治療以外のスケジューリングであるが、２つの先行技術を例に挙げて説明する（例えば、特許文献１，２参照）。
【０００６】
第１の先行技術では、月単位に集計した作業量が上限値を超える場合、超過した月に割り当てられている作業項目の中で、評価値ＳＷが低い作業順に、前月または翌月にシフト処理し、超過作業量の無いスケジュールを作成している。
【０００７】
第１の先行技術では、複数の設備の各々に設定されている点検周期を下に、一定の計画期間に含まれる各単位期間の作業スケジュールを作成するにあたって、無理や無駄の無い最適化されたスケジューリング方法を提供する。このスケジューリング方法では、日単位の計画を立てることが可能であるが、各作業員が行う作業が毎日異なるため、作業員が毎回作業項目を確認して作業に当たる必要がある。
【０００８】
しかしながら、毎回作業項目を確認する必要があることは作業員に負担を強いるものである。もし、曜日によってその日の作業が決まれば非常に覚えやすいが、作業は一週間単位で入るとは限らない。
【０００９】
このように、第１の先行技術では、作業員が認識しやすい規則性を持つスケジュールを作成することが困難である。また、第１の先行技術では、特定のスキルを有する作業員が特定の決められた曜日にしか作業できない場合に、そのような制約を満たすスケジュールを容易に生成することは難しい。
【００１０】
次に、第２の先行技術では、作業周期内の単位作業間隔毎に設定されている作業点に対して、各定期作業をそれぞれの作業間隔に従って割当てる工程を備える。その割当て工程では、各定期作業を順に割当てる。また割当て工程では、割当てる定期作業毎に、（１）当該定期作業を全ての割当てパターンのそれぞれに仮に割当てるとともに、仮に割当てられた全ての割当てパターンのそれぞれについて、作業点毎の「割当てられた定期作業群の合計作業時間」の標準偏差を算出し、（２）標準偏差が最小となる割当てパターンに当該定期作業を割当てる。
【００１１】
このような第２の先行技術では、定期作業計画を作成する作業周期を決め、割当パターンを最適化することによって、作業員が同じ工具交換作業を繰り返し実施するため、作業員のスキルが向上しやすく、作業員の作業負担が少なくなるとされている。
【００１２】
しかしながら、実際には、例えば、偶数個の作業点ごとに１回実行する作業と、奇数個又は素数個の作業点ごとに１回実行する作業とが混在すると、各作業点における交換の組合せが、定期作業計画を作成する作業周期に等しくなるため、特定のスキルを有する作業員が特定の作業を繰り返して実施するようなスケジュールを作成しにくくなる。
【００１３】
従って、第２の先行技術は、固定具作成等の特定のスキル又は作業に関する放射線治療のスケジューリングに適用することが困難である。さらに、第２の先行技術では、同じ作業員に対して、例えば偶数番目か奇数番目といった担当のさせ方しかできず、同じ作業員が担当する作業点を自由に与えることができない。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開平９−１２０４１７号公報
【特許文献２】特開２００７−１０２６８４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１５】
以上説明したように、第１の先行技術では、作業が一週間単位で入るとは限らない場合に、作業員が認識しやすい規則性を持つスケジュールを作成することが困難である。
【００１６】
また、第２の先行技術では、仮に、同じ作業員が担当する作業点を自由に与えたとしても、作業点における作業量が偏らないように平準化しつつ、規則性を持って特定の作業が集まりやすいスケジュールを、容易に作成することが困難である。
【００１７】
本発明は上記実情を考慮してなされたもので、規則性のある偏らないスケジュールパターンを生成し得る繰り返し型スケジュール生成装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明の一つの局面は、周期的に繰り返される繰り返し期間中の曜日と週との組合せ毎に、放射線治療の各プロトコールに対して基点となる治療工程の日を示すように当該各プロトコールを割当てたスケジュールパターンを生成する繰り返し型スケジュール生成装置であって、前記各治療工程における治療部位と照射治療工程の回数とを示す前記各プロトコールと、前記各プロトコールの患者数とを規定した割当作業情報を記憶する第１の記憶手段と、前記各プロトコールに対する各治療工程及び当該各治療工程のうちの基点となる治療工程を規定した治療工程情報を記憶する第２の記憶手段と、前記各治療工程間に空ける日数及び前記照射治療工程の回数に関する制約を規定した制約情報とを記憶する第３の記憶手段と、前記各プロトコールを割当て可能な曜日と週との組合せを個別に示す割当時間情報を記憶する第４の記憶手段と、前記割当時間情報内の曜日と週との組合せに個別に割り当てられた曜日種類を規定した割当時間種類情報を記憶する第５の記憶手段と、前記割当時間情報及び前記割当作業情報に基づいて、当該割当時間情報に示される曜日と週との組合せを個別に示す複数の割当時間ノードと、当該割当作業情報に規定された各プロトコールを個別に示す複数のプロトコールノードと、前記各割当時間ノードと前記各プロトコールノードとの組合せを個別に示す複数の割当アークと、前記各プロトコールの患者数とを含む割当ネットワークを作成する割当ネットワーク作成手段と、前記割当作業情報及び前記割当時間情報に基づいて、前記各割当アーク毎に、割当て可能な患者数としての流量を制限する流量制限値を算出する流量制限値算出手段と、前記割当時間情報及び前記割当時間種類情報に基づいて、前記曜日種類を個別に示す複数の割当時間種類ノードと、前記各割当時間種類ノードのうちの有効な割当時間種類ノードを個別に示す複数の割当時間種類アークとを生成する種類要素生成手段と、前記割当作業情報、前記割当時間情報及び前記割当時間種類情報に基づいて、前記各プロトコール毎に、前記各割当時間種類アークの使用枝数を制限する使用枝数制限値を算出する使用枝数制限値算出手段と、前記割当ネットワーク、前記流量制限値、前記各割当時間種類ノード、前記各割当時間種類アーク及び前記使用枝数制限値を統合することにより、前記各割当時間ノードと、前記各プロトコールノードと、前記各割当アークと、前記患者数と、前記流量制限値と、前記各割当時間種類ノードと、前記各割当時間種類アークと、前記使用枝数制限値とを含む制限ネットワークを作成する制限ネットワーク作成手段と、前記制限ネットワーク、前記治療工程情報及び前記制約情報に基づいて、前記スケジュールパターンを生成し、当該生成したスケジュールパターンをスケジュールパターン記憶手段に書込むスケジュールパターン生成手段と、前記書込まれたスケジュールパターンを記憶する前記スケジュールパターン記憶手段と、前記スケジュールパターン記憶手段からスケジュールパターンを読出し、当該読出したスケジュールパターンを出力するスケジュールパターン出力手段とを備えた繰り返し型スケジュール生成装置である。
【発明の効果】
【００１９】
以上説明したように本発明によれば、流量制限値により、特定の曜日と週との組合せに対して割り当てられる患者数を制限すると共に、使用枝数制限値により、曜日種類を制限する構成により、規則性のある偏らないスケジュールパターンを生成できる。
【図面の簡単な説明】
【００２０】
【図１】第１の実施形態に係る繰り返し型スケジュール生成装置の構成を示すブロック図である。
【図２】同実施形態におけるスケジュールパターンの一例を示す模式図である。
【図３】同実施形態における割当作業情報の一例を示す模式図である。
【図４】同実施形態における割当時間情報の一例を示す模式図である。
【図５】同実施形態における割当時間種類情報の一例を示す模式図である。
【図６】同実施形態における立案期間情報の一例を示す模式図である。
【図７】同実施形態におけるプロトコール情報の一例を示す模式図である。
【図８】同実施形態における治療工程情報の一例を示す模式図である。
【図９】同実施形態における制約情報の一例を示す模式図である。
【図１０】同実施形態における休治療日パターン情報の一例を示す模式図である。
【図１１】同実施形態における日数種類情報の一例を示す模式図である。
【図１２】同実施形態における割当ネットワークの一例を示す模式図である。
【図１３】同実施形態における割当ネットワークの他の例を示す模式図である。
【図１４】同実施形態における制限ネットワークの一例を示す模式図である。
【図１５】同実施形態における制限ネットワークの他の例を示す模式図である。
【図１６】同実施形態における動作を説明するためのフローチャートである。
【図１７】同実施形態における放射線治療の治療工程の一例を示す模式図である。
【図１８】同実施形態における日数種類と休治療日パターンとの組合せを説明するための模式図である。
【図１９】同実施形態における流量上限値の算出例を示す模式図である。
【図２０】同実施形態における使用枝数制限値の算出を説明するための模式図である。
【図２１】同実施形態における使用枝数上限値の算出例を示す模式図である。
【図２２】同実施形態における割当ネットワークの作成処理を詳細に説明するためのフローチャートである。
【図２３】同実施形態における多次元コストの算出例を示す模式図である。
【図２４】同実施形態における効果を説明するための模式図である。
【図２５】同実施形態における効果を説明するための模式図である。
【図２６】第２の実施形態に係る繰り返し型スケジュール生成装置の構成を示すブロック図である。
【図２７】同実施形態における制限値表示部の表示例を示す模式図である。
【図２８】同実施形態におけるスケジュールパターン表示部の表示例を示す模式図である。
【図２９】同実施形態における制約をゆるくした場合の設定例を示す模式図である。
【図３０】同実施形態におけるスケジュールパターン表示部の表示例を示す模式図である。
【図３１】同実施形態における制約を厳しくした場合の設定例を示す模式図である。
【図３２】同実施形態における制約を厳しくした場合のスケジュールパターン表示部の表示例を示す模式図である。
【図３３】第３の実施形態におけるスケジュールパターンの例を示す模式図である。
【図３４】同実施形態における割当ネットワークの例を示す模式図である。
【図３５】同実施形態における制限ネットワークの例を示す模式図である。
【図３６】同実施形態における使用枝数上限値の算出例を示す模式図である。
【図３７】同実施形態における制限ネットワークの変更例を示す模式図である。
【図３８】同実施形態における使用枝数上限値の変更後の算出例を示す模式図である。
【図３９】同実施形態における変更後のスケジュールパターンの例を示す模式図である。
【発明を実施するための形態】
【００２１】
以下、各実施形態について図面を用いて説明するが、その前に各実施形態の概要を述べる。
【００２２】
第１及び第２の実施形態では、放射線治療のスケジューリング問題を、ネットワークフロー問題として捉え、例えば、その割当ネットワークに割当時間の種類という特別なノードとアークを追加し、各作業種類でこのアークを使用する本数に制限をかける構成により、生成されるスケジュールパターンに規則性を与えている。本数制限は、上限だけをゆるくかけることもできるし、上下限を設けることで厳しく制約することも可能であって、容易に調節できる。使用枝数の制約は、混合整数線形計画問題の制約式として定式化できるため、最適化が可能である。
【００２３】
また、割当作業を割当時間に割り当てる割当アークを流れる流量に制限をかける流量制限値についても、制約として記述することで、目的関数（例えば、平準化）を最良化する最適化が可能となる。
【００２４】
制約に用いる上下限値の算出の仕方は、第１及び第２の実施形態で一例を示している。
【００２５】
また、第１及び第２の実施形態においては、放射線治療スケジューリングにおける最適化問題のMILP（mixed integer linier programming:混合整数線形計画法）定式化の例を述べている。
【００２６】
第３の実施形態では、第１の実施形態の変形例として、割当時間種類のグルーピングを作業員ごとに分けると、各作業員が、特定の作業種類の作業を繰返し行うスケジュールパターンを生成できることについて述べている。第３の実施形態に述べた例では、割当時間種類ノードに代えて作業点種類ノードを用い、割当時間ノードに代えて作業点ノードを用いている等の変更点がある。第３の実施形態は、情報の名称等が第１の実施形態から変更されているが、情報を加工又は演算する処理の内容については、第１の実施形態と同様となっている。
【００２７】
以上が各実施形態の概要である。続いて、各実施形態について具体的に説明する。
【００２８】
＜第１の実施形態＞
図１は第１の実施形態に係る繰り返し型スケジュール生成装置の構成を示すブロック図であり、図２はこの繰り返し型スケジュール生成装置により生成されるスケジュールパターンの一例を示す模式図である。繰り返し型スケジュール生成装置は、各部１〜１２の処理により、周期的に繰り返される繰り返し期間のスケジュールパターンを生成する。
【００２９】
繰り返し型スケジューリングにおけるスケジュールパターンとは、割当作業と割当時間を有し、所定数の各割当作業が割当時間のいずれかに割当てられたものを意味する。
【００３０】
この種のスケジュールパターンにおいては、例えば、図２に示すように、繰り返し期間中の曜日と週との組合せ（割当時間）毎に、放射線治療の各プロトコール（病状種別）に対して基点となる治療工程（割当作業）の日を示すように当該各プロトコールが割当てられている。図２中、「月１」は「第１週の月曜日」を表す略称である。「肺１」は、治療部位が「肺」であり、照射治療工程が「１回」である旨のプロトコールを表す略称である。同様に、「肝８」及び「前１６」は、それぞれ治療部位が「肝臓」及び「前立腺」であり、照射治療工程が「８回」及び「１６回」である旨の各プロトコールを表す略称である。以下の説明では、これらの略称を用いる。また、スケジュールパターンは、各プロトコールを当該各プロトコールの患者数だけ含んでいる。スケジュールパターンに１０個の「肝８」が割り当てられていることは、プロトコール“肝８”の患者数が１０人であることに対応している。
【００３１】
一方、繰り返し型スケジュール生成装置は、図１に示すように、情報入力部１、割当作業情報記憶部２、割当時間情報記憶部３、割当時間種類情報記憶部４、スケジュール情報記憶部５、割当ネットワーク作成部６、流量制限値算出部７、種類要素生成部８、使用枝数制限値算出部９、制限ネットワーク作成部１０、スケジュールパターン生成部１１及びスケジュールパターン記憶及び出力部１２を備えている。
【００３２】
情報入力部１は、ユーザと各部２〜１２との間の入力インタフェースであり、例えば、ユーザの操作に応じて、種々の情報を各記憶部２〜５に書込む機能をもっている。
【００３３】
各記憶部２〜５は、各部１，６〜１２から読出／書込可能な記憶装置又は記憶装置の記憶領域であり、例えば、情報入力部１から書込まれた情報を各部６〜１２から読出可能に記憶する。また例えば、各記憶部２〜５は、各部６〜１１の処理途中のデータを記憶してもよい。
【００３４】
具体的には、割当作業情報記憶部（第１の記憶部）２は、図３に示すように、各治療工程における治療部位と照射治療工程の回数とを示す各プロトコールｊと、各プロトコールｊの患者数ｄjとを規定した割当作業情報を記憶する。
【００３５】
割当時間情報記憶部（第４の記憶部）３は、図４に示すように、各プロトコールｊを割当て可能な曜日と週との組合せを個別に示す割当時間情報ｉを記憶する。
【００３６】
割当時間種類情報記憶部（第５の記憶手段）４は、図５に示すように、割当時間情報ｉ内の曜日と週との組合せに個別に割り当てられた曜日種類ｗを規定した割当時間種類情報を記憶する。
【００３７】
スケジュール情報記憶部（第２、第６〜第８の記憶部）５は、図６〜図１１に示すように、情報入力部１から書き込まれた立案期間情報、プロトコール情報、治療工程情報、制約情報、休治療日パターン情報及び日数種類情報を記憶する。なお、スケジュール情報記憶部５内の各情報のうち、例えば、立案期間情報、プロトコール情報、休治療日パターン情報及び日数種類情報は、スケジュールパターンを作成する観点からは、任意の付加的事項であって省略可能である。但し、立案期間情報、休治療日パターン情報及び日数種類情報は、後述する混合整数線形計画問題を定式化する観点から省略しない方が好ましい。また、各情報は、説明の便宜上、スケジュール情報記憶部５にまとめて記憶しているが、適宜、他の記憶部に記憶させるように変形してもよい。
【００３８】
立案期間情報は、図６に示すように、立案期間Ｔを示す情報である。
【００３９】
プロトコール情報は、図７に示すように、各プロトコールｊと照射治療工程の回数とを規定した情報である。
【００４０】
治療工程情報は、図８に示すように、各治療工程ｓを規定した情報であり、例えば、各プロトコールｊに対する各治療工程ｓ及び当該各治療工程ｓのうちの基点となる治療工程（以下、基準治療工程ともいう）を規定した情報である。なお、基準治療工程では、各日の基準治療工程を実施する作業時間の上限が指定可能となっている。他の治療工程は、基準治療工程からの相対位置（間に空ける日数）でスケジュールが生成されることが規則で定められている。基準治療工程としては、最初の治療工程である固定具作成に限らず、ＣＴシミュレーションや第１回照射を指定することも可能である。
【００４１】
制約情報は、図９に示すように、治療工程の制約を規定した情報であり、具体的には、各治療工程間に空ける日数及び照射治療工程の回数に関する制約を規定した情報である。
【００４２】
休治療日パターン情報は、図１０に示すように、各治療工程のうちの照射治療工程を休む日（図中、照射の休治療日）のパターンｋを規定した情報である。
【００４３】
日数種類情報は、図１１に示すように、各治療工程の間に空ける日数種類ｌを規定した情報である。
【００４４】
割当ネットワーク作成部６は、各記憶部２，３内の割当時間情報及び割当作業情報に基づいて、割当ネットワークを作成する機能をもっている。
【００４５】
割当ネットワークは、図１２に示すように、当該割当時間情報ｉに示される曜日と週との組合せを個別に示す複数の割当時間ノード“月１”，…，“金２”と、当該割当作業情報に規定された各プロトコールｊを個別に示す複数のプロトコールノード“肺１”，…，“前１６”と、各割当時間ノードと各プロトコールノードとの組合せを個別に示す複数の割当アークαと、各プロトコールｊの患者数ｄjとを含んでいる。なお、割当ネットワークは、図１３に示すように、休治療日パターンｋを個別に示す休治療日パターンノードと、間に空ける日数種類ｌを個別に示す日数種類ノードとを更に含んでもよい。本実施形態では、主に、図１３に示す割当ネットワークの場合を例に挙げて述べる。
【００４６】
流量制限値算出部７は、各記憶部３，５内の割当作業情報及び割当時間情報ｉに基づいて、各割当アークα毎に、割当て可能な患者数ｄjとしての流量を制限する流量制限値を算出する流量制限値算出機能をもっている。なお、流量制限値は、図２中、同一の日（同一の列）における同一プロトコールの個数（例、“木１”の日の“肝８”の個数は“２”）の上限値又は上下限値と解釈することも可能である。
【００４７】
ここで、流量制限値算出機能は、割当作業情報に規定された各プロトコールをｊと表し、繰り返し期間中の日の各プロトコールｊの患者数をｄjと表し、割当時間情報ｉに示される各日の集合をＩと表し、この集合Ｉに含まれる各日の個数を｜Ｉ｜と表し、流量制限値のうちの流量上限値をFLOW(j)と表すとき、下記式（１）に示すように、流量上限値FLOW(j)を流量制限値として算出する流量上限値算出機能を備えてもよい。
【数１】
0005762873.tif 000002
【００４８】
種類要素生成部８は、各記憶部３，４内の割当時間情報ｉ及び割当時間種類情報に基づいて、図１４の一部に示す如き、曜日種類ｗを個別に示す複数の割当時間種類ノード“月”，…，“金”と、各割当時間種類ノード“月”，…，“金”のうちの有効な割当時間種類ノードを個別に示す複数の割当時間種類アークβとを生成する機能をもっている。なお、「種類要素」の語は「割当時間種類ノード及び割当時間種類アーク」と読み替えてもよい。
【００４９】
使用枝数制限値算出部９は、割当作業情報、割当時間情報ｉ及び割当時間種類情報に基づいて、各プロトコールｊ毎に、各割当時間種類アークの使用枝数を制限する使用枝数制限値を算出する使用枝数制限値算出機能をもっている。なお、使用枝数制限値は、図２中、曜日及び週の組合せ“月１”，…，“金２”に関し、有効な曜日の種類（月、火、木、金）の個数（図２では“４”）の上限値又は上下限値としても解釈可能である。
【００５０】
ここで、使用枝数制限値算出機能は、割当時間情報ｉに示される週の種類の数をｈと表し、使用枝数制限値のうちの使用枝数上限値をUSE(j)と表すとき、下記式（２）に示すように、使用枝数上限値USE(j)を使用枝数制限値として算出する使用枝数上限値算出機能を備えてもよい。
【数２】
0005762873.tif 000003
【００５１】
制限ネットワーク作成部１０は、割当ネットワーク、流量制限値、各割当時間種類ノード、各割当時間種類アーク及び使用枝数制限値を統合することにより、制限ネットワークを作成する機能をもっている。制限ネットワークは、図１４に示すように、各割当時間ノード“月１”，…，“金２”と、各プロトコールノード“肺１”，…，“前１６”と、各割当アークαと、患者数ｄjと、流量制限値（図示せず）と、各割当時間種類ノード“月”，…，“金”と、各割当時間種類アークβと、使用枝数制限値（図示せず）とを含んでいる。なお、制限ネットワークは、図１５に示すように、休治療日パターンｋを個別に示す休治療日パターンノードと、間に空ける日数種類ｌを個別に示す日数種類ノードとを更に含んでもよい。本実施形態では、主に、図１５に示す制限ネットワークの場合を例に挙げて述べる。また、「制限ネットワーク」の語は、「割当時間種類をもつネットワーク」と読み替えてもよい。
【００５２】
スケジュールパターン生成部１１は、制限ネットワーク、治療工程情報及び制約情報に基づいて、スケジュールパターンを生成するスケジュールパターン生成機能と、当該生成したスケジュールパターンをスケジュールパターン記憶及び出力部１２に書込むスケジュールパターン書込機能とをもっている。
【００５３】
ここで、スケジュールパターン生成機能は、立案期間Ｔ中の日を｛０，…，T｝と表し、各治療工程をｓと表し、当該各治療工程ｓの集合をＳと表し、集合Ｉに含まれる各日をｉと表し、パターンｋの集合をＫと表し、各プロトコールｊの集合をＪと表し、日数種類ｌの集合をＬと表し、一週間中の曜日をｗと表し、当該曜日ｗの集合をＷと表し、繰り返し期間中の曜日ｗの日の集合をDAY(w),(w∈W)と表し、各日ｉとパターンｋと各プロトコールｊと日数種類ｌとの組合せikjlにおける患者数をｙikjlと表し、患者数ｙikjlのとりうる値の上界値をγと表し（但し、ｒ＝max｛FLOW(j)｜ｊ∈Ｊ｝）、
【数３】
0005762873.tif 000004
【００５４】
のとりうる値の上界値をυと表し（但し、υ＝max｛USE(j)｜ｊ∈Ｊ｝）、組合せikjlにおいて患者を一人割り当てた場合の日tにおける治療工程sの作業時間を示すコストをc’tsikjlと表し、組合せikjlにおいて患者を一人でも割り当てた場合を１とする０−１変数をxikjlと表し、曜日ｗにプロトコールｊを割り当てた場合を１とする０−１変数をuwjと表し、整数全体をＺと表し、下記式（３）に示す混合整数線形計画問題の評価値をｚと表すとき、評価値ｚを最小化するように混合整数線形計画問題を解くことにより、スケジュールパターンを生成するソルバ機能を備えてもよい。
【数４】
0005762873.tif 000005
【００５５】
スケジュールパターン記憶及び出力部１２は、スケジュールパターン生成部１１から書込まれたスケジュールパターンを記憶するスケジュールパターン記憶部（図示せず）を有し、当該スケジュールパターン記憶部からスケジュールパターンを読出し、当該読出したスケジュールパターンを出力する機能をもっている。
【００５６】
次に、以上のように構成された繰り返し型スケジュール生成装置の動作について図１６を参照しながら説明する。以下の説明は、重粒子線治療における２週間繰返しのスケジュールを作成する場合を例に挙げて述べる。
【００５７】
始めに、重粒子線におけるスケジューリングの概要について述べる。ここでのスケジューリングとは、来院患者の頻度と患者のプロトコール（病状種別）の割合から、立案期間分の予定枠を作成するものである。
【００５８】
病院では、日々の負荷を超えないように、例えば半期分の予定枠（治療枠）を予め作成しておき、新患の予約時に枠を埋めていくという方法を取る場合が多い。治療枠は、他の療法との併用で数ヶ月先に予約を入れる場合や、来院患者数を見積もる場合にも有用である。予定枠を作成して埋めていく方法は、スタッフにとって理解しやすい規則性と類似のスケジュールが、週単位や２週間単位に繰り返される性質と、負荷平準化による効率性とを同時に満たすことで、より多くの患者を安全に治療することを図っている。
【００５９】
重粒子線治療では図１７に示す治療工程があり、このうちスケジューリングを行う治療工程は、例えば固定具作成、ＣＴ(computerized tomography)シミュレーション、照射の３つとする。他に、リハーサルなどの工程をスケジューリングに含む場合もある。照射治療工程は複数回行われ、プロトコールの種類によって回数が異なる。
【００６０】
スケジューリングを行う治療工程について、患者１人分の実施日（スケジュール）がきまったものを、１つのスケジュール枠（以下、枠）と呼ぶ。半期分のすべての患者の枠の集合を、ここでは治療枠と呼ぶ。各枠はプロトコールが決まっているが、どの患者に割当てるかについては決まっていない。
【００６１】
重粒子線治療における枠作成問題（以下、枠作成問題）とは、部屋の数などの施設の規模（あるいは病院スタッフの人数）、各種スケジュールなどによって各プロトコールにおける各治療工程の実行可能な条件と最適化目的が与えられているとき、実行可能な条件を満たし最適化目的を良くする、各患者における枠の集合（治療予定枠）を得ることである。
【００６２】
安全性と利便性の観点から、治療枠には週単位の規則性を持たせることが好ましい。実際には週１回未満のプロトコールもあるため、頻度が最小のプロトコールに合わせて繰返し期間を設定し、立案期間中はこの繰返し期間のスケジュールが周期的に繰り返されることとしている。さらに、繰返し期間中のスケジュールについても、週単位の規則性及び、人数の多いプロトコールは各日でなるべく均等に割り当てる規則性が重視される。
【００６３】
一方、スタッフの負荷を軽減するためには、各日の作業時間がなるべく平準化されるのが望ましい。祝日や機器のメンテナンス等で不規則なケースが発生することから、作業時間は立案期間の全体で考慮する必要がある。立案期間中で照射の作業にかかる作業時間が最も多い日の作業時間を最小にする。または、繰り返し期間中の各日ごとに割り当てられた各治療工程の作業時間を合計した合計作業時間のうち、最大の合計作業時間を持つ日の当該合計作業時間を最小にするようにしてもよい。
【００６４】
工程間に空ける日数が与えられるため、繰返し期間中の各日に各プロトコールの治療開始（固定具作成）を１人割り当てたときの（立案期間中の）各日の照射にかかる作業時間を予め計算できる。
【００６５】
治療予定枠は、繰り返し期間中の各プロトコールの開始日の指定を含むスケジュールパターンを決定することで生成できる。
【００６６】
このようなスケジューリングを行うにあたって、情報入力部１は、ユーザの操作に応じて割当作業情報、割当時間情報ｉ及び割当時間種類情報をそれぞれ割当作業情報記憶部２、割当時間情報記憶部３及び割当時間種類情報記憶部４に書込む。
【００６７】
同様に、情報入力部１は、ユーザの操作に応じて、立案期間情報、プロトコール情報、治療工程情報、制約情報、休治療日パターン情報及び日数種類情報をスケジュール情報記憶部５に書込む。
【００６８】
続いて、割当ネットワーク作成部６は、各記憶部２，３内の割当時間情報ｉ及び割当作業情報に基づいて、当該割当時間情報ｉに示される曜日と週との組合せを個別に示す複数の割当時間ノード“月１”，…，“金２”と、当該割当作業情報に規定された各プロトコールｊを個別に示す複数のプロトコールノード“肺１”，…，“前１６”と、各割当時間ノードと各プロトコールノードとの組合せを個別に示す複数の割当アークαと、各プロトコールｊの患者数ｄjとを含む割当ネットワークを作成する（Ｓ１１）。このステップＳ１１の詳細については後述する。
【００６９】
割当ネットワークは、例えば図１２に示したように、どの割当時間にどの割当作業をいくつずつ割り当てるかを二部グラフのマッチングとして表現するもので、割当時間と割当作業間のアークである割当アークαに流れる流量の組が、ひとつのスケジュールパターン要素を表す。
【００７０】
割当ネットワークは、図１３に示したように、各割当時間と各割当作業に、それぞれ休治療日パターンｋと間に空ける日数種類ｌの選択肢を拡張したネットワークでも良い。
【００７１】
間に空ける日数種類ｌの選択肢とは、基準治療工程以外の治療工程の作業日が一意に定まらなくなる問題を解決するため、治療工程間に空ける日数種類の中で最適化により良い日数を選択可能とするものである。休治療日パターンｋの選択肢は、１週間内の照射可能日が患者一人あたりの１週間の照射回数上限よりも多い週がある場合に、複数通りの照射日の入れ方のパターンの中から最適化により良いパターンを選択可能とするものである。
【００７２】
また、日数種類ｌと休治療日パターンｋとの２点を選択可能としたことに加え、同じ開始日ｉの同じプロトコールｊの各患者に対し、図１８に示すように、治療工程間に空ける日数種類ｌと、休治療日パターンｋとの組合せを１種類にした（ノードｋとノードｌ間の割当アークαを１本だけ使用する）。これにより、基準治療工程以外の治療工程の作業日が一意に定まらなくなる問題を解決している。
【００７３】
流量制限値算出部７は、割当ネットワークの各割当アークαと各割当作業pの各組（α, p）について、流量制限値を算出する（Ｓ１２、Ｓ１３）。各割当作業pは、各プロトコールｊに相当する。
【００７４】
流量制限は、割当てが特定の割当アークαに偏らないように制限をかけるものであり、例えば、上限値が下記のように算出可能となっている。
【００７５】
すなわち、流量上限値FLOW(j)は、プロトコールｊを繰り返し期間中の日１日あたりに割り当ててよい上限を示すため、集合Iの要素数を｜I｜とすると、前述した式（１）に基づいて、プロトコールｊの患者数ｄjを繰り返し期間中の日数｜Ｉ｜で除算し、この除算結果以上の最小の整数として算出できる。なお、「除算結果以上の最小の整数」は、「除算結果を下回らない最小の整数」又は「除算結果の小数点以下を切り上げた整数」と読み替えてもよい。ここで、図３及び図４に示す情報に基づく流量上限値FLOW(j)の算出例を図１９に示す。例えば、プロトコールｊが“肝８”の場合、ｄj＝１０、｜Ｉ｜＝８、として式（１）に基づき、FLOW(j)は、ｄj／｜Ｉ｜（＝１０／８）以上の最小の整数“２”として算出される。
【００７６】
次に、種類要素生成部８は、各記憶部３，４内の割当時間情報及び割当時間種類情報に基づいて、図１５に示した如き、割当時間種類ノード“月”，…，“金”を生成すると共に（Ｓ１４）、各割当時間種類ノードとソース(source)ノード、各割当時間種類ノードと割当時間種類に対応する割当時間ノード間にアークを生成する（Ｓ１５，Ｓ１６）。
【００７７】
使用枝数制限値算出部９は、生成した各割当時間種類アークβ（図２０）と各割当作業pの各組（β，p）について、使用枝数制限値を算出する（Ｓ１７，Ｓ１８）。使用枝数制限値は、割当作業pが割り当てられる割当時間の種類数（割当時間種類アークβの本数）を制限するもので、例えば上限値が下記のように算出可能となっている。
【００７８】
すなわち、使用枝数上限値USE(j)は、繰返し期間中の週の数をhとし、前述した式（２）に基づいて、プロトコールｊの患者数ｄjを繰り返し期間中の週の数hで除算し、この除算結果以上の最小の整数として算出できる。図３〜図５に示す情報に基づく使用枝数上限値USE(j)の算出例を図２１に示す。例えば、プロトコールｊが“肝８”の場合、ｄj＝１０、ｈ＝２、として式（２）に基づき、USE(j)は、ｄj／ｈ（＝１０／２）以上の最小の整数“５”として算出されるが、割当時間種類アークβの使用枝数が最大で４本のため、算出結果を“４”としている。
【００７９】
制限ネットワーク作成部１０は、割当ネットワーク、流量上限値FLOW(j)、各割当時間種類ノード“月”，…，“金”、各割当時間種類アークβ及び使用枝数上限値USE(j)を統合することにより、図１５に示した如き、制限ネットワークを作成する（Ｓ１９）。
【００８０】
この制限ネットワークは、混合整数線形計画問題として上記式（３）に示したように定式化でき、CPLEXなどの混合整数線形計画問題を解く汎用ソルバや、厳密解法、ヒューリスティクス解法、メタヒューリスティクス解法、によって最適化できる。
【００８１】
定式化においては、入力データに関する記号を以下に定義する。
【００８２】
｛０，…，T｝：立案期間中の日。
【００８３】
S：治療工程の集合。
【００８４】
I：繰り返し期間中の日の集合。
【００８５】
K：照射パターンの集合。
【００８６】
J：プロトコールの集合。
【００８７】
L：間に空ける日数の集合。
【００８８】
W：一週間中の曜日の集合。
【００８９】
dj：繰り返し期間中の日のプロトコールjの患者数。
【００９０】
次に、入力データから算出する値に関する記号を定義する。 
DAY(w),(w∈W)：曜日がwである繰り返し期間中の日の集合を返す関数。
【００９１】
USE(j),(j∈J)：プロトコールjが取ってよい曜日の種類数の上限値を返す関数。
【００９２】
FLOW(j) ,(j∈J)：プロトコールjを繰り返し期間中の日の１日あたりに割り当ててよい上限量を返す関数。
【００９３】
γ：yikjlのとりうる値の上界値。
【数５】
0005762873.tif 000006
【００９４】
c’tsikjl：i,k,j,lに患者を一人割り当てたときの、日tにおける治療工程sのコスト
以下に、定式化中の変数に関する記号を定義する。
【００９５】
yikjl：i,k,j,lに患者を割り当てた人数を示す、整数変数。
【００９６】
xikjl：i,k,j,lに患者が１人でも割り当てられた場合に１を取る、０−１変数。
【００９７】
uwj：曜日wにプロトコールjを割り当てたときに１を取る、０−１変数。
【００９８】
ただし、Zは整数全体を示す記号とする。
【００９９】
以上のような定義を用い、制限ネットワークは、式（３）に示した如き、混合整数線形計画問題として定式化される。
【０１００】
スケジュールパターン生成部１１は、このように定式化可能な制限ネットワークと、スケジュール記憶部５内の治療工程情報及び制約情報に基づいて、前述した式（３）の評価値ｚを最小化するように混合整数線形計画問題を解くことにより、図２に示した如き、スケジュールパターンを生成する（Ｓ２０）。
【０１０１】
しかる後、スケジュールパターン生成部１１は、生成したスケジュールパターンをスケジュールパターン記憶及び出力部１２に書込む。
【０１０２】
スケジュールパターン記憶及び出力部１２は、書込まれたスケジュールパターンをスケジュールパターン記憶部（図示せず）が記憶し、当該スケジュールパターン記憶部からスケジュールパターンを読出し、当該読出したスケジュールパターンを出力する。
【０１０３】
次に、前述したステップＳ１１の割当ネットワークの作成処理について詳細に述べる。
【０１０４】
放射線治療の例では、割当時間は例えば固定具作成などの基準となる治療工程の開始日を示し、割当作業は、プロトコールの種類を示す。図１３に示した割当ネットワークは、割当作業情報記憶部２内の割当作業情報と、割当時間情報記憶部３内の割当時間情報ｉと、スケジュール情報記憶部５内の各情報とに基づいて、割当ネットワーク作成部６により作成される。このような割当ネットワークの作成処理について図２２を用いて詳細に説明する。
【０１０５】
始めに、割当ネットワーク作成部６は、シンク（sink）ノードとソース（source）ノードという、ダミーのノードを１つずつ生成する（Ｓ１１−１）。
【０１０６】
割当ネットワーク作成部６は、割当作業情報記憶部２内の割当作業情報に基づいて、各プロトコールｊの割当作業ノード“肺１”，…，“前１６”を生成する（Ｓ１１−２)。
【０１０７】
続いて、割当ネットワーク作成部６は、以下のステップＳ１１−４〜Ｓ１１−６の処理を全ての割当作業ノード“肺１”，…，“前１６”について繰り返す（Ｓ１１−３）。
【０１０８】
すなわち、割当ネットワーク作成部６は、各割当作業ノード“肺１”，…，“前１６”について、割当作業ノードとシンクノード間のアークを生成し（Ｓ１１−４）、スケジュール記憶部５内の日数種類情報に基づいて、間に空ける日数種類ノードを種類数分生成する（Ｓ１１−５）。また、割当ネットワーク作成部６は、日数種類ノードと割当作業ノード間のアークを生成する（Ｓ１１−６）。
【０１０９】
ステップＳ１１−４〜Ｓ１１−６を繰り返すステップＳ１１−３の終了後、割当ネットワーク作成部６は、割当時間情報記憶部３内の割当時間情報ｉに基づいて、割当時間ノード“月１”，…，“金２”を生成する（Ｓ１１−７）。
【０１１０】
しかる後、前述同様に、以下のステップＳ１１−９〜Ｓ１１−１１の処理を全ての割当時間ノード“月１”，…，“金２”について繰り返す（Ｓ１１−８）。
【０１１１】
すなわち、割当ネットワーク作成部６は、各割当時間ノード“月１”，…，“金２”について、割当時間ノードとソースノード間のアークを生成し（Ｓ１１−９）、スケジュール記憶部５内の休治療日パターン情報に基づいて、休治療日パターンノードを生成する（Ｓ１１−１０）。また、割当ネットワーク作成部６は、休治療日パターンノードと割当時間ノード間のアークを生成する（Ｓ１１−１１）。
【０１１２】
ステップＳ１１−９〜Ｓ１１−１１を繰り返すステップＳ１１−８の終了後、割当ネットワーク作成部６は、割当アークαを生成する（Ｓ１１−１２）。割当アークαの生成処理としては、図１３に示す割当ネットワークの場合、各割当作業に関する間に空ける日数種類ノードと、各割当時間に関する休治療日パターンノードで完全２部グラフを構成すればよい。図１２に示す割当ネットワークのように休治療日パターンノードと、間に空ける日数種類ノードとがない場合には、各割当作業ノード“肺１”，…，“前１６”と各割当時間ノード“月１”，…，“金２”で完全２部グラフを構成すればよい。割当作業に関するノードと割当時間に関するノードで完全２部グラフを構成するように生成されたアークを割当アークαと呼ぶ。
【０１１３】
割当ネットワーク作成部６は、各割当アークαについて、スケジュール記憶部５内の各情報に基づいて、図２３に示すように、多次元コストを算出し（Ｓ１１−１３，Ｓ１１−１４）、割当ネットワークを作成する。
【０１１４】
ここで、ステップＳ１１−１３の多次元コストの算出方法について詳細に説明する。
【０１１５】
繰り返し期間中の日i、プロトコールj、休治療日パターンk、間に空ける日数種類lに患者を１人割り当てた場合の、立案期間中の日tにおけるコストc’tsikjlは、次のように計算できる。
【０１１６】
始めに、繰り返し期間中の日iに対して、治療の開始日の集合Qiを以下で定義する。
【０１１７】
Qi＝｛t｜TIME(t)＝i, t∈{１,...,T}｝
次に、各開始日tで開始される１人分の枠を下記の手順［１］〜［３］で計算する。
【０１１８】
［１］開始日tに基準治療工程を設定する。
【０１１９】
［２］残りの治療工程の開始日は基準治療工程からの間に空ける日数より算出する。
【０１２０】
［３］照射治療工程の開始日から、照射回数（プロトコールjによって決まっている）分の照射治療工程を各日に設定する。
【０１２１】
照射治療工程の設定は各施設で定める照射のスケジュールの割当て方法に従って行う。例えば下記の割当て方法が使用可能である。もし、その週に照射が可能な日数が、一人当たりの週の照射回数上限値より多く、かつ、残りの照射回数が一人当たりの週の照射回数上限値以上の場合、照射治療工程は、休治療日パターンkで定められた割当て方法で設定する。それ以外の場合、照射治療工程の開始日から、翌日以降の照射可能な日に順次照射治療工程を割当てていく。
【０１２２】
各t∈Qiの開始日について、それぞれ１人分の枠を計算し、各立案期間中の日で照射治療工程が設定された人数を算出する。c’tsikjlは、コストを算出するときに固定具作成とＣＴシミュレーションについても各日の作業時間を算出した値を用い、プロトコールjの照射の作業時間をかけて計算できる（図２３）。照射等の作業が複数日にわたる治療工程の作業時間は、回数によって作業時間を変えて設定しても良く、上記の計算方法と同様にして一人当たりの多次元コストを算出できる。
【０１２３】
上述したように本実施形態によれば、割当ネットワークの各割当アークα毎に、割当て可能な患者数としての流量を制限する流量制限値を算出し、曜日種類ｗを個別に示す各割当時間種類ノード“月”，…，“金”のうちの有効な割当時間種類ノードを個別に示す各割当時間種類アークβの使用枝数を各プロトコールｊ毎に算出し、割当ネットワーク、流量制限値、各割当時間種類ノード“月”，…，“金”、各割当時間種類アークβ及び使用枝数制限値を統合することにより、制限ネットワークを作成し、制限ネットワーク、治療工程情報及び制約情報に基づいて、スケジュールパターンを生成する構成により、規則性のある偏らないスケジュールパターンを生成することができる。
【０１２４】
補足すると、本実施形態では、割当時間種類ノード“月”，…，“金”および割当時間種類アークβを生成して、各割当時間種類アークβに使用枝数制限をつけることにより、例えば数週間単位のスケジュールパターンを生成するに当たって、週単位の規則性を容易に作成できるという効果を持つ。元のスケジュールの制約から前の週と次の週は必ずしも同じにはならないが、その各週が曜日によって行う作業がなるべくそろうスケジュールが生成できれば、作業員がスケジュールパターンを覚えやすく、作業員の負担が減って安全性が増す。また、複数か月単位の大まかな計画は上記先行技術で作成し、１日、あるいは単位時間単位の詳細な計画を本実施形態の繰り返し型スケジュール生成装置により作成しても良い。
【０１２５】
また、作業が一週間単位で必ず入るわけではない場合にも、作業員が認識しやすい規則性を持つスケジュールを作成できることに加え、ユーザによる目的関数のウェイト調節などが不要であるため、規則性の持たせ方を容易に調節できる（図２４、図２５）。
【０１２６】
例えば、流量上限値FLOW(j)及び使用枝数上限値USE(j)が無い場合、スケジュールパターンは、図２４（ａ）に示すように、同一のプロトコール“０”の基準治療工程が、前の週と次の週とでは異なる曜日に割当てられており、曜日の規則性が無い。また、他の同一のプロトコール“２”又は“７”についても同様に規則性が無い。
【０１２７】
一方、流量上限値FLOW(j)及び使用枝数上限値USE(j)がある場合、スケジュールパターンは、図２４（ｂ）に示すように、同一のプロトコール“０”の基準治療工程が、前の週と次の週とで同一の曜日に割当てられており、曜日の規則性がある。他の同一のプロトコール“２”又は“７”についても同様に規則性がある。
【０１２８】
また例えば、流量上限値FLOW(j)及び使用枝数上限値USE(j)が無い場合で日によって割当て人数が異なるとき、スケジュールパターンは、図２５（ａ）に示すように、同一のプロトコール“０”，“４”（火２−木２）又は“７”の基準治療工程について、曜日の規則性が無い。但し、他の同一のプロトコール“４”（月１−月２、金１−金２）については曜日の規則性がある。
【０１２９】
また他方、流量上限値FLOW(j)及び使用枝数上限値USE(j)がある場合で日によって割当て人数が異なるとき、スケジュールパターンは、図２５（ｂ）に示すように、同一のプロトコール“０”の基準治療工程について、曜日の規則性がある。他の同一のプロトコール“４”又は“７”についても同様に規則性がある。
【０１３０】
なお、本実施形態においては、図１３に示したk,lの選択肢をもつ割当ネットワークに基づいて図１５に示した制限ネットワークを混合整数線形計画問題として定式化した場合を例に挙げて説明したが、これに限らず、図１２に示したk,lの選択肢をもたない割当ネットワークに基づいて図１４に示す制限ネットワークを混合整数線形計画問題として定式化した場合としても実施できる。この場合、休治療日パターンｋ及び日数種類ｌを予め定めておけばよい。このことは以下の各実施形態でも同様である。
【０１３１】
＜第２の実施形態＞
図２６は第２の実施形態に係る繰り返し型スケジュール生成装置の構成を示すブロック図であり、図１と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。なお、以下の各実施形態も同様にして重複した部分の説明を省略する。
【０１３２】
第２の実施形態は、第１の実施形態の変形例であり、流量制限値及び使用枝数制限値を調節可能としたものであって、図１に示した構成に比べ、制限値設定部１３、スケジュールパターン表示部１４及び制限値表示部１５を付加した構成となっている。
【０１３３】
ここで、制限値設定部１３は、スケジュールパターン記憶及び出力部１２によるスケジュールパターンの出力後、ユーザの操作に応じて、流量制限値及び使用枝数制限値を個別に設定する制限値設定機能と、当該設定された流量制限値及び使用枝数制限値に基づいて、制限ネットワーク作成部１０、スケジュールパターン生成部１１、及びスケジュールパターン記憶及び出力部１２を再実行するように制御する再実行制御機能とをもっている。
【０１３４】
また、制限値設定部１３の制限値設定機能は、流量制限値のうちの流量下限値をFLOW_L(j)と表すとき、下記式（４）に示すように、流量下限値FLOW_L(j)を流量制限値として算出し、当該算出した流量下限値FLOW_L(j)を設定する流量下限値設定機能を有していてもよい。なお、下記式（４）は、流量下限値FLOW_L(j)を算出する際に、流量上限値FLOW(j)に基づき、“FLOW(j)−１＞０”のときに“FLOW(j)−１”とし、“FLOW(j)−１≦０”のときに“０”として求める手順をも包含している。
【数６】
0005762873.tif 000007
【０１３５】
同様に、制限値設定部１３の制限値設定機能は、使用枝数制限値のうちの使用枝数下限値をUSE_L(j)と表すとき、下記式（５）に示すように、使用枝数下限値USE_L(j)を使用枝数制限値として算出し、当該算出した使用枝数下限値USE_L(j)を設定する使用枝数下限値設定機能を有していてもよい。なお、下記式（５）は、使用枝数下限値USE_L(j)を算出する際に、使用枝数上限値USE(j)に基づき、“USE(j)−１＞０”のときに“USE(j)−１”とし、“USE(j)−１≦０”のときに“０”として求める手順をも包含している。
【数７】
0005762873.tif 000008
【０１３６】
スケジュールパターン表示部１４は、現在のスケジュールパターンを表示するものであり、具体的には、スケジュールパターン記憶及び出力部１２により出力されたスケジュールパターンを表示する機能をもっている。
【０１３７】
制限値表示部１５は、現在の流量制限値及び使用枚数制限値を表示するものであり、具体的には、流量制限値算出部７に算出又は設定された流量制限値と、使用枝数制限値算出部９に算出又は設定された使用枝数制限値とを表示する機能をもっている。
【０１３８】
次に、以上のように構成された繰り返し型スケジュール生成装置の動作を説明する。
【０１３９】
いま、第１の実施形態に述べた動作が終了し、スケジュールパターン記憶及び出力部１２からスケジュールパターンが出力されたとする。
【０１４０】
このとき、制限値表示部１５は、図２７に一例を示すように、現在の制限値として、流量上限値FLOW(j)、流量下限値FLOW_L(j)、使用枝数上限値USE(j)、使用枝数下限値USE_L(j)をプロトコールｊ毎に表示する。
【０１４１】
また、スケジュールパターン表示部１４は、図２８に一例を示すように、現在のスケジュールパターンとして、当該出力されたスケジュールパターンを表示する。
【０１４２】
ここで、ユーザが規則性の制約をもっと緩くして平準化を進めたいと考えた場合、制限値設定部１３は、図２９に一例を示すように、ユーザの操作に応じて、一部の制約を、例えばプロトコールｊ“前１６”の使用枝数上限値USE(j)を３から４に緩めて設定する。
【０１４３】
しかる後、制限値設定部１３は、この使用枝数上限値USE(j)“４”を使用枝数制限値算出部９を介して制限ネットワーク作成部１０に送出することにより、制限ネットワーク作成部１０、スケジュールパターン生成部１１、及びスケジュールパターン記憶及び出力部１２を再実行するように制御する。
【０１４４】
再実行の結果、繰り返し型スケジュール生成装置は、使用枝数上限値USE(j)を緩めた設定によってスケジュールパターンのバリエーションが増えるため、もし図２８に示したスケジュールパターンよりも平準化が良い解、即ち、最大作業時間が短い解が存在すれば、図３０に一例を示すように最大作業時間が４時間の解をもつスケジュールパターンを生成する。
【０１４５】
逆に、制約を厳しくして規則性をより増したい場合、制限値設定部１３は、ユーザの操作に応じて、流量上限値FLOW(j)に加えて流量下限値FLOW_L(j)を流量制限値算出部７に設定すると共に、使用枝数上限値USE(j)に加えて使用枝数下限値USE_L(j)を使用枝数制限値算出部９に設定する。
【０１４６】
ユーザは、これら下限値FLOW_L(j)，USE_L(j)の制約を規則性を増したい特定のプロトコールｊにのみ適用する。例えば図３１に示すように、プロトコールｊ“肝８”の各下限値FLOW_L(j)，USE_L(j)の制約を適用すると、図３２に示すように、規則性を増したスケジュールパターンが得られる。
【０１４７】
なお、制限値設定部１３による設定は、ユーザが手動で数字を入力して行っても良いし、図２９及び図３１に示すように、値の増加ボタン及び減少ボタン等の入力画面を設けて、値を増加又は減少させたときに当該値を自動的に設定しても良い。
【０１４８】
また、制限値設定部１３は、ユーザの操作に応じて、増減された流量上限値FLOW(j)に対応して式（４）等から算出した流量下限値FLOW_L(j)を設定してもよく、同様に、ユーザの操作に応じて、増減された使用枝数上限値USE(j)に対応して式（５）等から算出した使用枝数下限値USE_L(j)を設定してもよい。
【０１４９】
また同様に、制限値設定部１３は、これら設定された流量下限値FLOW_L(j)及び使用枝数下限値USE_L(j)をそれぞれ流量制限値算出部７及び使用枝数制限値算出部９を介して制限ネットワーク作成部１０に送出することにより、制限ネットワーク作成部１０、スケジュールパターン生成部１１、及びスケジュールパターン記憶及び出力部１２を再実行するように制御する。
【０１５０】
これにより、流量上限値FLOW(j)及び使用枝数上限値USE(j)の増減に対応して流量下限値FLOW_L(j)及び使用枝数下限値USE_L(j)の制約を含めたスケジュールパターンを出力することができる。
【０１５１】
上述したように本実施形態によれば、スケジュールパターンの出力後、ユーザの操作に応じて、流量制限値及び使用枝数制限値を個別に設定し、当該設定された流量制限値及び使用枝数制限値に基づいて、制限ネットワーク作成部１０、スケジュールパターン生成部１１、及びスケジュールパターン記憶及び出力部１２を再実行するように制御する構成により、第１の実施形態の効果に加え、流量制限値及び使用枝数制限値による制約を調整して、スケジュールパターンにおける規則性と偏り具合を調整することができる。
【０１５２】
補足すると、本実施形態は、割当時間種類ノード“月”，…，“金”及び割当時間種類アークβを生成して、各割当時間種類アークβに使用枝数制限をつけてスケジュールパターンが取り得るパターン種類の上限値、または上限値と下限値を算出して制約をかけることで、どの程度週単位の規則性が保たれるかが保証でき、各日の患者数をなるべく一定にする（又は偏りをへらす）という目的関数については、制約を満たす範囲で最適化できる。また、ユーザが複数ある目的関数のウェイトを調節するよりも容易に操作ができるという効果がある。さらに、流量制限値及び使用枝数制限値の設定は、式（１）、式（２）、式（４）及び式（５）に示したデフォルト設定の他にユーザが個別に調節することができるため、少し制約をゆるくしたい場合などにも対応できる。
【０１５３】
＜第３の実施形態＞
次に、第３の実施形態に係る繰り返し型スケジュール生成装置について説明する。
【０１５４】
第３の実施形態は、第１又は第２の実施形態の変形例であり、前述した繰り返し型スケジュール生成装置を、放射線治療に代えて、定期作業のスケジュール立案で、作業員に分かりやすいスケジュールを立案する場合に適用した形態となっている。
【０１５５】
これに伴い、前述した繰り返し型スケジュール生成装置は、以下の点１）〜１４）が変更されている。
【０１５６】
１）放射線治療に代えて、定期作業を用いる。
【０１５７】
２）各プロトコールに代えて、各作業種類を用いる。
【０１５８】
３）各治療工程に代えて、各作業工程を用いる。
【０１５９】
４）患者数に代えて、作業対象数を用いる。
【０１６０】
５）治療部位と照射治療工程の回数に代えて、点検作業又は工具の交換作業を用いる。
【０１６１】
６）各治療工程間に空ける日数及び前記照射治療工程の回数に関する制約に代えて、作業工程間に空ける日数に関する制約を用いる。
【０１６２】
７）曜日と週との組合せに代えて、作業点を用いる。
【０１６３】
８）割当時間情報に代えて、作業点情報を用いる。
【０１６４】
９）曜日種類に代えて、作業員を用いる。
【０１６５】
１０）割当時間種類情報に代えて、作業点種類情報を用いる。
【０１６６】
１１）割当時間ノードに代えて、作業点ノードを用いる。
【０１６７】
１２）プロトコールノードに代えて、作業種類ノードを用いる。
【０１６８】
１３）割当時間種類ノードに代えて、作業点種類ノードを用いる。
【０１６９】
１４）割当時間種類アークに代えて、作業点種類アークを用いる。
【０１７０】
これらの点１）〜１４）の変更は、以下のような構成を表している。
【０１７１】
スケジュールパターンは、図３３に示すように、繰り返し期間中の作業点（割当時間）毎に、定期作業の各作業種類に対して基点となる作業工程（割当作業）の日を示すように当該各作業種類が割当てられている。スケジュールパターンは、各作業種類を当該各作業種類の作業対象数だけ含んでいる。なお、図３３では、分かりやすさのため、スケジュールパターンの表示の上部に作業員の種類を記載したが、この記載は省略してもよい。
【０１７２】
割当作業情報記憶部（第１の記憶部）２は、各作業工程における点検作業又は工具の交換作業を示す各作業種類と、各作業種類の作業対象数とを規定した割当作業情報を記憶する。
【０１７３】
作業点情報記憶部（第４の記憶部）３は、各作業種類を割当て可能な作業点を個別に示す作業点情報を記憶する。
【０１７４】
作業点種類情報記憶部（第５の記憶手段）４は、作業点情報内の作業点に個別に割り当てられた作業員を規定した作業点種類情報を記憶する。
【０１７５】
作業工程情報は、各作業工程を規定した情報であり、例えば、各作業種類に対する各作業工程及び当該各作業工程のうちの基点となる作業工程（以下、基準作業工程ともいう）を規定した情報である。なお、基準作業工程では、各日の基準作業工程を実施する作業時間の上限が指定可能となっている。他の作業工程は、基準作業工程からの相対位置（間に空ける日数）でスケジュールが生成される。
【０１７６】
制約情報は、作業工程の制約を規定した情報であり、具体的には、各作業工程間に空ける日数に関する制約を規定した情報である。
【０１７７】
割当ネットワーク作成部６は、各記憶部２，３内の作業点情報及び割当作業情報に基づいて、割当ネットワークを作成する機能をもっている。
【０１７８】
割当ネットワークは、図３４に示すように、当該作業点情報に示される作業点を個別に示す複数の作業点ノード“１”，…，“１２”と、当該割当作業情報に規定された各作業種類を個別に示す複数の作業種類ノード“Ａ”，…，“Ｄ”と、各作業点ノードと各作業種類ノードとの組合せを個別に示す複数の割当アークαと、各作業種類の作業対象数“６”，…，“１”とを含んでいる。
【０１７９】
流量制限値算出部７は、各記憶部３，５内の割当作業情報及び作業点情報に基づいて、各割当アークα毎に、割当て可能な作業対象数としての流量を制限する流量制限値を算出する流量制限値算出機能をもっている。
【０１８０】
ここで、流量制限値算出機能は、割当作業情報に規定された各作業種類をｊと表し、繰り返し期間中の日の各作業種類ｊの作業対象数をｄjと表し、作業点情報に示される各作業点の集合をＩと表し、この集合Ｉに含まれる各作業点の個数を｜Ｉ｜と表し、流量制限値のうちの流量上限値をFLOW(j)と表すとき、前述した式（１）に示すように、流量上限値FLOW(j)を流量制限値として算出する流量上限値算出機能を備えてもよい。
【０１８１】
種類要素生成部８は、各記憶部３，４内の作業点情報及び作業点種類情報に基づいて、作業員を個別に示す複数の作業点種類ノードと、各作業点種類ノードのうちの有効な作業点種類ノードを個別に示す複数の作業点種類アークとを生成する機能をもっている。なお、「種類要素」の語は「作業点種類ノード及び作業点種類アーク」と読み替えてもよい。
【０１８２】
使用枝数制限値算出部９は、割当作業情報、作業点情報及び作業点種類情報に基づいて、各作業種類毎に、各作業点種類アークの使用枝数を制限する使用枝数制限値を算出する使用枝数制限値算出機能をもっている。
【０１８３】
ここで、使用枝数制限値算出機能は、作業点情報に示される作業点の個数｜Ｉ｜を作業点種類情報に示される作業員の個数｜Ｗ｜で除した値をｈ（＝｜Ｉ｜／｜Ｗ｜）と表し、使用枝数制限値のうちの使用枝数上限値をUSE(j)と表すとき、前述した式（２）に示すように、使用枝数上限値USE(j)を使用枝数制限値として算出する使用枝数上限値算出機能を備えてもよい。
【０１８４】
制限ネットワーク作成部１０は、割当ネットワーク、流量制限値、各作業点種類ノード、各作業点種類アーク及び使用枝数制限値を統合することにより、制限ネットワークを作成する機能をもっている。制限ネットワークは、図３５に示すように、各作業点ノード“１”，…，“１２”と、各作業種類ノード“Ａ”，…，“Ｄ”と、各割当アークαと、作業対象数“６”，…，“１”と、流量制限値（図示せず）と、各作業点種類ノード（図中、作業員ノード）“ａ”，…，“ｃ”と、各作業点種類アークβと、使用枝数制限値（図示せず）とを含んでいる。なお、「制限ネットワーク」の語は、「作業点種類をもつネットワーク」と読み替えてもよい。
【０１８５】
スケジュールパターン生成部１１は、制限ネットワーク、作業工程情報及び制約情報に基づいて、図３３に示した如き、スケジュールパターンを生成するスケジュールパターン生成機能と、当該生成したスケジュールパターンをスケジュールパターン記憶及び出力部１２に書込むスケジュールパターン書込機能とをもっている。
【０１８６】
スケジュールパターン記憶及び出力部１２は、前述した機能をもっている。
【０１８７】
次に、以上のように構成された繰り返し型スケジュール生成装置の動作を説明する。
【０１８８】
例えば、定期作業の回数によって、定期的に点検や工具の取り替えが必要な作業が複数種類あり、各定期作業は作業種類に応じて取り替えのタイミングが異なる。
【０１８９】
作業点とは、定期作業毎の作業間隔の公約数である単位作業間隔で設定されている、定期作業が入る可能性のあるタイミングのことである。作業種類を作業点に割り当てることでスケジュールパターンが生成可能となっている。
【０１９０】
第２の先行技術では、定期作業が必ず一定間隔で割当てられるスケジューリングを行っている。一方、本実施形態では、定期作業を作業点の繰り返し期間ごとで繰返すスケジュールとして、繰返し期間内は、必ずしも定期作業が一定間隔でなくても良いとし、作業員が作業を行う作業点が作業員ごとに得られている場合、作業員に分かりやすいスケジュールパターンを生成できる。
【０１９１】
このようなスケジューリングを行うにあたって、情報入力部１は、ユーザの操作に応じて割当作業情報、作業点情報及び作業点種類情報をそれぞれ割当作業情報記憶部２、作業点情報記憶部３及び作業点種類情報記憶部４に書込む。
【０１９２】
同様に、情報入力部１は、ユーザの操作に応じて、作業工程情報及び制約情報をスケジュール情報記憶部５に書込む。
【０１９３】
続いて、割当ネットワーク作成部６は、各記憶部２，３内の作業点情報及び割当作業情報に基づいて、例えば、繰り返し期間における作業点が１２個、作業種類が４種類の場合、図３４に示す如き、当該作業点情報に示される作業点を個別に示す複数の作業点ノード“１”，…，“１２”と、当該割当作業情報に規定された各作業種類を個別に示す複数の作業種類ノード“Ａ”，…，“Ｄ”と、各作業点ノードと各作業種類ノードとの組合せを個別に示す複数の割当アークαと、各作業種類の作業対象数“６”，…，“１”とを含む割当ネットワークを作成する。
【０１９４】
各作業種類を各作業点に割り当てたときの多次元コストは、立案期間中に各作業が繰り返し期間における作業点数毎に繰り返すとすれば、図２３と同様に算出できるため、各日の作業時間の平準化を可能としている。
【０１９５】
ここで、前述同様に、流量制限値算出部７が流量制限値を算出する。
【０１９６】
しかる後、種類要素生成部８は、各記憶部３，４内の作業点情報及び作業点種類情報に基づいて、図３５に示す如き制限ネットワークに統合される、３つの作業点種類ノード（図中、作業員）“ａ”，…，“ｃ”を生成すると共に、各作業点種類ノードとソースノード、各作業点種類ノードと作業種類ノード間にアークを生成する。
【０１９７】
このように、３つの作業点種類ノード“ａ”，…，“ｃ”が生成された場合、使用枝数制限値算出部９は、図３６に示すように、各作業点種類アークβの使用枝数上限値USE(j)を算出することができる。
【０１９８】
例えば、作業種類Ａの場合、ｄj＝６、ｈ＝｜Ｉ｜／｜Ｗ｜＝１２／３＝４、として式（２）に基づき、USE(j)は、ｄj／ｈ（＝６／４）以上の最小の整数“２”として算出される。なお、図３６の場合、作業員ａは作業点３つ、作業員ｂは５つ、作業員ｃは４つと受け持つ作業点の数が不均等になっているので、繰り返し回数としてのｈ＝４が必ずしも好ましいわけではない。ここで述べたｈの計算の仕方は一例であり、これに限定されない。
【０１９９】
続いて、制限ネットワーク作成部１０は、割当ネットワーク、流量制限値、各作業点種類ノード“ａ”，…，“ｃ”、各作業点種類アークβ及び使用枝数制限値を統合することにより、図３５に示した如き、制限ネットワークを作成する。
【０２００】
スケジュールパターン生成部１１は、前述同様に定式化可能な制限ネットワークと、スケジュール記憶部５内の作業工程情報及び制約情報に基づいて、前述した式（３）の評価値ｚを最小化するように混合整数線形計画問題を解くことにより、図３３に示したように、スケジュールパターンを生成する。
【０２０１】
また、作業員の数及び担当作業点が図３７に示すように変更された場合にも、各作業点種類アークβの使用枝数上限値USE(j)を図３８に示すように算出でき、図３９に示す如き、スケジュールパターンを生成することができる。
【０２０２】
上述したように本実施形態によれば、第１の実施形態に比べ、曜日と週との組合せに代えて作業点を用い、割当時間情報に代えて作業点情報を用い、曜日種類に代えて作業員を用い、割当時間種類情報に代えて作業点種類情報を用いる構成により、第１の実施形態の効果に加え、作業点で作業を行う作業員を作業点種類として用いることで、その作業点に特定の作業種類が集まりやすいスケジュールパターンを作成できる。
【０２０３】
また、３つの作業点種類ノード“ａ”，…，“ｃ”に対応する３つの作業点種類アークβを生成し、これら作業点種類アークβの使用枝数制限をつける構成により、作業点における作業量を平準化してかつ、作業点種類に応じて特定の作業種類が集まりやすいスケジュールパターンを容易に作成できるため、より作業者にわかりやすい計画を作成することができる。
【０２０４】
また、同じ作業員が担当する作業点を自由に与えた場合にも同じ作業員になるべく同じ作業が当たるスケジュールを作成することができる。
【０２０５】
なお、上記の各実施形態に記載した手法は、コンピュータによって実行させることができ、また、コンピュータによって実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０２０６】
また、各実施形態に記載した装置は、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体からコンピュータにインストールされ、各実施形態に記載した装置の機能を当該コンピュータに実現させるためのプログラムが用いられる。すなわち、各実施形態に記載した装置は、コンピュータのメモリ内の当該プログラムを当該コンピュータのプロセッサが実行することにより、実施してもよい。
【０２０７】
また、本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０２０８】
１…情報入力部、２…割当作業情報記憶部、３…割当時間情報記憶部、４…割当時間種類情報記憶部、５…スケジュール情報記憶部、６…割当ネットワーク作成部、７…流量制限値算出部、８…種類要素生成部、９…使用枝数制限値算出部、１０…制限ネットワーク作成部、１１…スケジュールパターン生成部、１２…スケジュールパターン記憶及び出力部、１３…制限値設定部、１４…スケジュールパターン表示部、１５…制限値表示部、α…割当アーク、β…割当時間種類アーク。
【図１】
0005762873.tif 000017
【図２】
0005762873.tif 000018
【図３】
0005762873.tif 000019
【図４】
0005762873.tif 000020
【図５】
0005762873.tif 000021
【図６】
0005762873.tif 000022
【図７】
0005762873.tif 000023
【図８】
0005762873.tif 000024
【図９】
0005762873.tif 000025
【図１０】
0005762873.tif 000026
【図１１】
0005762873.tif 000027
【図１２】
0005762873.tif 000028
【図１３】
0005762873.tif 000029
【図１４】
0005762873.tif 000030
【図１５】
0005762873.tif 000031
【図１６】
0005762873.tif 000032
【図１７】
0005762873.tif 000033
【図１８】
0005762873.tif 000034
【図１９】
0005762873.tif 000035
【図２０】
0005762873.tif 000036
【図２１】
0005762873.tif 000037
【図２２】
0005762873.tif 000038
【図２３】
0005762873.tif 000039
【図２４】
0005762873.tif 000040
【図２５】
0005762873.tif 000041
【図２６】
0005762873.tif 000042
【図２７】
0005762873.tif 000043
【図２８】
0005762873.tif 000044
【図２９】
0005762873.tif 000045
【図３０】
0005762873.tif 000046
【図３１】
0005762873.tif 000047
【図３２】
0005762873.tif 000048
【図３３】
0005762873.tif 000049
【図３４】
0005762873.tif 000050
【図３５】
0005762873.tif 000051
【図３６】
0005762873.tif 000052
【図３７】
0005762873.tif 000053
【図３８】
0005762873.tif 000054
【図３９】
0005762873.tif 000055