(57)【要約】 【課題】作業列に含まれる複数の作業を、できるだけ少ない資源数で効率よく実施する。【解決手段】資源スケジューリング装置は、スケジューリング対象の作業の作業時間と、前記作業を実施するのに必要な資源の数とを含む作業情報を入力する作業情報入力部と、複数の作業を含む作業列における各作業の実施順序及び間隔を含む作業列情報を入力する作業列情報入力部と、前記資源の割当禁止期間を含む資源情報を入力する資源情報入力部と、前記作業列情報に含まれる前記実施順序及び前記間隔を遵守するように、作業情報、作業列情報および資源情報に基づいて作業列における各作業を割り当てることが可能な割当可能期間を出力する期間割当出力部と、作業情報、作業列情報および資源情報に基づいて割当可能期間に割り当てられ割当先資源を含む資源割当情報を出力する資源割当出力部と、を備える。【選択図】図１
2020113007.tif 000002
【特許請求の範囲】
【請求項１】
スケジューリング対象の作業の作業時間と、前記作業を実施するのに必要な資源の数とを含む作業情報を入力する作業情報入力部と、
複数の作業を含む作業列における各作業の実施順序及び間隔を含む作業列情報を入力する作業列情報入力部と、
前記資源の割当禁止期間を含む資源情報を入力する資源情報入力部と、
前記作業列情報に含まれる前記実施順序及び前記間隔を遵守するように、前記作業情報、前記作業列情報および前記資源情報に基づいて前記作業列における各作業を割り当てることが可能な割当可能期間を出力する期間割当出力部と、
前記作業情報、前記作業列情報および前記資源情報に基づいて、前記割当可能期間に割り当てられ割当先資源を含む資源割当情報を出力する資源割当出力部と、を備える、資源スケジューリング装置。
【請求項２】
前記割当可能期間及び前記資源割当情報に基づいて、前記複数の作業の実施タイミングと各作業に用いられる資源とを制御する、制御部を備える、請求項１に記載の資源スケジューリング装置。
【請求項３】
前記制御部は、前記作業列に含まれる前記複数の作業が最小の資源数で実施されるように、前記複数の作業の実施タイミングと各作業に用いられる資源とを制御する、請求項２に記載の資源スケジューリング装置。
【請求項４】
前記制御部は、
前記作業列に含まれる前記複数の作業のそれぞれを、単一の資源で実施される単一資源作業に分割する作業分割部と、
前記作業分割部で分割された前記単一資源作業に対し、資源ごとに資源割当可能期間を算出する単一資源作業割当部と、
前記単一資源作業ごとにすべての資源に対する前記資源割当可能期間を統合することにより、前記作業列を開始することが可能な単一資源作業割当可能期間と、前記単一資源作業割当可能期間にて単一資源作業を割当可能な単一資源作業割当先候補とを前記単一資源作業ごとに算出する単一資源作業統合部と、
前記単一資源作業割当可能期間及び前記単一資源作業割当先候補に基づいて、前記割当可能期間を算出するとともに、前記割当可能期間にて前記単一資源作業のそれぞれに割り当てられる前記資源割当情報を算出する割当統合部と、を有する、請求項２又は３に記載の資源スケジューリング装置。
【請求項５】
前記割当統合部は、
前記単一資源作業に基づいて、作業列を単一資源作業列に分割する単一資源作業列接続部と、
前記単一資源作業列ごとに、前記単一資源作業列を割当可能な単一資源作業列割当可能期間と、前記単一資源作業列割当可能期間にて割当可能な単一資源作業列割当先候補とを算出する単一資源作業列割当部と、
前記単一資源作業列割当可能期間および前記単一資源作業列割当先候補に基づいて、前記割当可能期間を算出するとともに、前記割当可能期間にて前記単一資源作業列のそれぞれに割り当てられる前記資源割当情報を算出する作業列割当統合部と、を有する、請求項４に記載の資源スケジューリング装置。
【請求項６】
前記割当統合部は、
前記単一資源作業割当可能期間の候補となる検査期間を算出する検査期間分割部と、
前記検査期間ごとに、前記単一資源作業割当先候補と、作業に必要な資源数とに基づいて、使用する資源数が最小になるように資源被覆問題を解く被覆問題演算部と、
前記資源被覆問題を解いた結果に基づいて、前記割当可能期間にて前記単一資源作業のそれぞれに割り当てられる前記資源割当情報を算出する作業割当統合部と、を有する、請求項４に記載の資源スケジューリング装置。
【請求項７】
前記割当可能期間と、対応する前記資源割当情報と、を表示可能な表示部を備える、請求項１乃至６のいずれか一項に記載の資源スケジューリング装置。
【請求項８】
前記作業列の開始時刻を決定する開始時刻決定部と、
前記開始時刻決定部で決定された開始時刻を起点として割り当てられた前記資源割当情報に基づいて、前記割当禁止期間を含む前記資源情報を更新する資源情報更新部と、を備える、請求項１乃至７のいずれか一項に記載の資源スケジューリング装置。
【請求項９】
前記開始時刻決定部は、前記割当可能期間における最先の時刻を前記開始時刻として決定する、請求項８に記載の資源スケジューリング装置。
【請求項１０】
前記割当可能期間中の任意の時刻を前記開始時刻として選択する選択部を備え、
前記開始時刻決定部は、前記選択部で選択された時刻を前記開始時刻として決定する、請求項８に記載の資源スケジューリング装置。
【請求項１１】
スケジューリング対象の作業の作業時間と、前記作業を実施するのに必要な資源の数とを含む作業情報を入力する工程と、
複数の作業を含む作業列における各作業の実施順序及び間隔を含む作業列情報を入力する工程と、
前記資源の割当禁止期間を含む資源情報を入力する工程と、
前記作業列情報に含まれる前記実施順序及び前記間隔を遵守するように、前記作業情報、前記作業列情報および前記資源情報に基づいて前記作業列における各作業を割り当てることが可能な割当可能期間を出力する工程と、
前記作業情報、前記作業列情報および前記資源情報に基づいて前記割当可能期間に割り当てられ割当先資源を含む資源割当情報を出力する工程と、を備える、資源スケジューリング方法。
【請求項１２】
コンピュータに、
スケジューリング対象の作業の作業時間と、前記作業を実施するのに必要な資源の数とを含む作業情報を入力する手順と、
複数の作業を含む作業列における各作業の実施順序及び間隔を含む作業列情報を入力する手順と、
前記資源の割当禁止期間を含む資源情報を入力する手順と、
前記作業列情報に含まれる前記実施順序及び前記間隔を遵守するように、前記作業情報、前記作業列情報および前記資源情報に基づいて前記作業列における各作業を割り当てることが可能な割当可能期間を出力する手順と、
前記作業情報、前記作業列情報および前記資源情報に基づいて前記割当可能期間に割り当てられ割当先資源を含む資源割当情報を出力する手順と、を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、資源スケジューリング装置、資源スケジューリング方法及びプログラムに関する。
【背景技術】
【０００２】
作業に対し、その実施期間およびそれを実行する資源を割り当てる資源スケジューリングは、生産設備を資源とする生産工程や、人員を資源とする業務指示などの分野をはじめとして、広く行われている。資源スケジューリングにおける主な制約条件として、期日までに作業を完了するための期限制約や、作業中に専有される必要数の資源を確保するための資源制約、作業間の実施順序を守るための順序制約などが挙げられる。また、順序制約の拡張として、前後の作業間の間隔を守ることが要求される場合もある。例えば、人員を資源とする装置保守作業では、装置が自動実行する工程が含まれる場合がある。このような作業は、資源から見たときに、自動実行の前後の２つの作業が一定の間隔を空けて実施されるものと見なすことができる。
【０００３】
また、順序付けられた一連の作業を同じ資源に割り当てることが要求される場合もある。例えば、前出の装置保守作業において、重量物の運搬を伴う場合など２名の人員を要する第１の作業の後に、１名で行われる第２の作業が続く場合を考える。このとき、作業指示を煩雑にしないことや不要な引継ぎを省くため、第１の作業に割り当てる人員のうち１名を、引き続き第２の作業に割り当てることが求められる場合がある。このとき第１の作業と第２の作業からなる一連の作業、すなわち作業列に割り当てる資源数は、必要資源数が最も多い第１の作業の資源数と一致する。このことを作業列に対する最小資源数と呼ぶ。
【０００４】
複数の作業からなる作業列には、実施順序や間隔を遵守することが求められる一方で、できるだけ少ない資源数で各作業を実施する効率性が求められる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１７−２１１９２１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の一態様は、作業列に含まれる複数の作業を、できるだけ少ない資源数で効率よく実施できる資源スケジューリング装置、資源スケジューリング方法及びプログラムを提供するものである。
【課題を解決するための手段】
【０００７】
本実施形態によれば、スケジューリング対象の作業の作業時間と、前記作業を実施するのに必要な資源の数とを含む作業情報を入力する作業情報入力部と、
複数の作業を含む作業列における各作業の実施順序及び間隔を含む作業列情報を入力する作業列情報入力部と、
前記資源の割当禁止期間を含む資源情報を入力する資源情報入力部と、
前記作業列情報に含まれる前記実施順序及び前記間隔を遵守するように、前記作業情報、前記作業列情報および前記資源情報に基づいて前記作業列における各作業を割り当てることが可能な割当可能期間を出力する期間割当出力部と、
前記作業情報、前記作業列情報および前記資源情報に基づいて、前記割当可能期間に割り当てられ割当先資源を含む資源割当情報を出力する資源割当出力部と、を備える、資源スケジューリング装置が提供される。
【図面の簡単な説明】
【０００８】
【図１】一実施形態による資源スケジューリング装置の概略構成を示すブロック図。
【図２】作業列の一例を示す図。
【図３】資源情報の一例を示す図。
【図４】出力部の出力形態の一例を示す図。
【図５】作業分割部が行う作業分割の一例を示す図。
【図６】単一資源作業割当部の処理動作を示すフローチャート。
【図７】資源割当可能期間を示す図。
【図８】単一資源作業統合部の処理動作を示すフローチャート。
【図９】単一資源作業統合部の処理動作を示す図。
【図１０】図１の資源スケジューリング装置の処理動作を示すフローチャート。
【図１１】第１手法を行う割当統合部の内部構成を示すブロック図。
【図１２】作業列を単一資源作業列に分割した例を示す図。
【図１３】単一資源作業列割当部の処理動作を説明する図。
【図１４】（ａ）と（ｂ）は作業列割当統合部の処理動作を説明する図。
【図１５】割当統合部が行う第１手法の処理動作を示すフローチャート。
【図１６】第２手法を行う割当統合部の内部構成を示すブロック図。
【図１７】割当統合部が行う第２手法の処理動作を示すフローチャート。
【図１８】作業群の一例を示す図。
【発明を実施するための形態】
【０００９】
以下、図面を参照して本発明の実施形態を説明する。以下の実施形態では、資源スケジューリング装置内の特徴的な構成および動作を主に説明するが、資源スケジューリング装置には以下の説明で省略した構成および動作が存在しうる。
【００１０】
図１は一実施形態による資源スケジューリング装置１の概略構成を示すブロック図である。図１の資源スケジューリング装置１は、入力部２と、記憶部３と、出力部４と、制御部５とを備えている。
【００１１】
入力部２は、作業情報入力部２１と、作業列情報入力部２２と、資源情報入力部２３とを有する。入力部２は、図１の資源スケジューリング装置１の使用者が各種情報を入力してもよいし、他の装置から出力された情報を入力してもよい。
【００１２】
作業情報入力部２１は、スケジューリング対象の作業の作業時間と、作業を実施するための必要な資源数とを含む作業情報を入力する。本実施形態による資源スケジューリング装置１は、スケジューリング対象の各作業が少なくとも一つの資源を利用することを前提としている。各作業を並行して行う場合には、別々の資源を用いて実施される。
【００１３】
作業列情報入力部２２は、複数の作業を含む作業列における各作業の実施順序及び間隔を含む作業列情報を入力する。間隔は、連続した各作業間の間隔であり、間隔は０又は正の時間である。すなわち、複数の作業が間隔なしで連続して繋がっていてもよい。複数の作業列が並行して行われてもよい。この場合、各作業列は同一時刻では別々の資源を用いて実施される。
【００１４】
図２は作業列の一例を示す図である。図２の作業列は間隔Ｇを挟んで作業Ａ１と作業Ａ２を有する例を示している。作業Ａ１は実施に一つの資源を要し作業時間がＬ１の例を示し、作業Ａ２は実施に二つの資源を要し作業時間がＬ２の例を示している。このように、作業によって、必要とする資源数や作業時間が異なることがありうる。
【００１５】
資源情報入力部２３は、各資源についての割当禁止期間を含む資源情報を入力する。本実施形態では、各資源は、同一時刻では、一つの作業にしか使えないものとしており、ある時間帯にある資源をある作業に割り当てた場合は、その資源は、その時間帯が割当禁止期間になり、他の作業に割り当てることができなくなる。資源スケジューリングでは、割当先資源の割当禁止期間と重ならないように、作業の実施期間を決める必要がある。
【００１６】
図３は資源情報の一例を示す図である。図３の横軸は時間である。図３は、３つの資源Ｒ１，Ｒ２，Ｒ３の資源情報を示している。資源情報は、各資源Ｒ１〜Ｒ３の割当禁止期間Ｃ１〜Ｃ３を含んでいる。割当禁止期間Ｃ１〜Ｃ３には、対応する資源を作業に割り当てることができない。
【００１７】
記憶部３は、入力部２を介して入力された各種の情報と、制御部５にて算出される各種の情報を記憶する。なお、記憶部３は、図１の資源スケジューリング装置１における必須構成部ではない。例えば、記憶部３は、図１の資源スケジューリング装置１の外部に設けられてもよい。
【００１８】
出力部４は、期間割当出力部４１と資源割当出力部４２を有する。
【００１９】
期間割当出力部４１は、作業列情報に含まれる実施順序及び間隔を遵守するように、作業情報、作業列情報および資源情報に基づいて作業列における各作業を割当可能な割当可能期間を出力する。本実施形態では、作業時間および作業の間隔は不変であり、そのため作業列の開始時刻を定めることでその作業列における各作業の実施期間も定まり、ゆえに作業列の開始時刻の期間を割当可能期間とする。なお、作業列の開始時刻からその作業列における各作業の開始時刻を計算し、その各作業の開始時刻の期間を割当可能期間として出力してもよい。
【００２０】
資源割当出力部４２は、作業情報、作業列情報および資源情報に基づいて、上述した割当可能期間に割り当てられ割当先資源を含む資源割当情報を出力する。
【００２１】
図４は出力部４の出力形態の一例を示す図である。図４の出力形態は、図３の資源情報に対応するものである。図４は、４つの割当可能期間Ｔ１〜Ｔ２、Ｔ２〜Ｔ３、Ｔ３〜Ｔ４、Ｔ４〜Ｔ５において作業Ａ１とＡ２の資源を割り当てる例を示している。
【００２２】
図４の表のＤ１行は割当可能期間を示し、Ｄ２行は資源割当情報を示している。より具体的には、図４の表は、図２の作業列の割当結果を出力部４が出力する例を示している。割当可能期間Ｔ１からＴ２までにおいて、作業Ａ１には資源Ｒ１を割当可能で、作業Ａ２にはＲ１およびＲ２を割当可能である。なお、作業Ａ２は、図２に示すように、作業Ａ１が終わった後に行われるため、資源Ｒ２が期間Ｔ１〜Ｔ２において割当禁止であっても、作業Ａ１をＴ１〜Ｔ２の間に開始すれば、資源Ｒ１又はＲ２を用いて作業Ａ２を実施できる。
【００２３】
同様に、図４の表によれば、割当可能期間Ｔ２からＴ３までにおいて、作業Ａ１には資源Ｒ２を割当可能で、作業Ａ２にはＲ２およびＲ３を割当可能である。割当可能期間Ｔ４からＴ５までにおいて、作業Ａ１には資源Ｒ３を割当可能で、作業Ａ２には資源Ｒ１およびＲ３を割当可能である。なお、本明細書及び図面では、時刻ＸからＹまでの期間を、［Ｘ，Ｙ）と表記する。ただし期間［Ｘ，Ｙ）は時刻Ｘを含み、時刻Ｙを含まない。
【００２４】
制御部５は、作業列に含まれる複数の作業が最小資源数で実施されるように、複数の作業の実施タイミングと各作業を実施するのに用いられる資源を制御する。
【００２５】
制御部５は、図１に示すように、作業分割部５１と、単一資源作業割当部５２と、単一資源作業統合部５３と、割当統合部５４とを有する。
【００２６】
作業分割部５１は、作業列に含まれる複数の作業のそれぞれを、単一の資源が割り当てられる単一資源作業に分割する。単一資源作業とは、単一の資源を用いて行われる作業を指す。単一資源作業の作業時間は、元の作業の作業時間と一致する。このように、各作業は、必要資源数と同じ数の単一資源作業に分割される。
【００２７】
図５は作業分割部５１が行う作業分割の一例を示す図である。必要資源数が１の作業Ａ１は単一資源作業Ｅ１１に分割される。必要資源数が２の作業Ａ２は、単一資源作業Ｅ２１とＥ２２に分割される。なお、図５では、便宜上、作業Ａ１，Ａ２を表す枠の内側に、単一資源作業Ｅ１１、Ｅ２１、Ｅ２２を図示しているが、単一資源作業Ｅ１１の作業時間は作業Ａ１の作業時間に等しく、単一資源作業Ｅ２１、Ｅ２２の作業時間は作業Ａ２の作業時間に等しい。
【００２８】
単一資源作業割当部５２は、作業分割部５１で分割された単一資源作業に対し、資源ごとに資源割当可能期間を算出する。例えば、単一資源作業がｎ個、資源がＭ個ある場合、単一資源作業割当部５２は、単一資源作業と資源の全組合せｎ×Ｍ通りに対して資源割当可能期間を算出する。ある単一資源作業とある資源との組み合わせについての資源割当可能期間は、２つ以上存在する場合もありうる。資源割当可能期間は、単一資源作業が含まれる作業列の開始時刻がこの期間内にあるとき、単一資源作業の実施期間が資源の割当禁止期間と重ならないように定められる。
【００２９】
単一資源作業割当部５２は、以下の手法で、資源割当可能期間を算出できる。まず、割当禁止期間に含まれない期間［Ｓ，Ｔ）を見つける。この期間の長さＴ−Ｓが単一資源作業の作業時間Ｌ以上であるとき、対応する資源割当可能期間を算出する。例えば、単一資源作業と、この単一資源作業が含まれる作業列の開始時刻との差分をΔで表すと、資源割当可能期間は、［Ｓ−Δ，Ｔ−Ｌ−Δ）となる。なお、Δは、単一資源作業と同じ作業列に含まれる、先行するすべての作業の作業時間と間隔を合計した時間である。
【００３０】
図６は単一資源作業割当部５２の処理動作を示すフローチャート、図７は資源割当可能期間を示す図である。図６と図７は、図５に示す作業Ａ１とＡ２を有する作業列における資源割当可能期間を算出する例を示している。
【００３１】
図６に示すように、単一資源作業割当部５２は、まず、割当禁止期間に含まれない期間［Ｔ１１，Ｔ１５）を算出する（ステップＳ１）。図５の作業列の場合、ステップＳ１の期間は単一資源作業Ｅ２１を割り当てるための期間である。
【００３２】
次に、ステップＳ１で算出した期間の終了時刻Ｔ１５から、作業時間Ｌだけ前倒しすることによりＴ１３＝Ｔ１５−Ｌを得て、単一資源作業Ｅ２１を開始できる期間［Ｔ１１，Ｔ１３）を算出する（ステップＳ２）。図７のＴ１１〜Ｔ１３の矢印区間が単一資源作業Ｅ２１を開始できる期間である。
【００３３】
次に、単一資源作業Ｅ２１の元の作業Ａ２に対するΔを算出する（ステップＳ３）。Δは、図５の作業列の開始時刻と単一資源作業Ｅ２１の開始時刻との時間差である。
【００３４】
次に、ステップＳ２で算出した期間に基づいて、この期間の開始時刻と終了時刻をΔだけ前倒しすることにより、作業列を開始できる期間を算出する（ステップＳ４）。例えば、［Ｔ１１−Δ，Ｔ１２＝Ｔ１３−Δ）。ここで、Ｔ１１がスケジューリング期間の開始である場合、Ｔ１１よりも前の作業列を開始することはできないため、上記の例では、Ｔ１１以前の期間［Ｔ１１−Δ，Ｔ１１）が除かれることにより、作業列を開始できる期間は［Ｔ１１，Ｔ１２）となる。作業列の先頭には、単一資源作業Ｅ１１が含まれるため、この単一資源作業Ｅ１１の資源割当可能期間は、Ｔ１１〜Ｔ１２になる。
【００３５】
なお、作業列を開始する時刻は、図７の［Ｔ１３，Ｔ１４）の期間内でもよい。この場合、単一資源作業Ｅ２１の開始時刻は［Ｔ１６，Ｔ１７）の期間内になる。
【００３６】
このように、単一資源作業割当部５２は、各資源の割当禁止期間を考慮に入れて、作業列内の各単一資源作業について、資源割当可能期間を算出する。
【００３７】
単一資源作業統合部５３は、単一資源作業ごとにすべての資源に対する資源割当可能期間を統合することにより、作業列を開始することが可能な単一資源作業割当可能期間と、単一資源作業割当可能期間にて単一資源作業を割当可能な単一資源作業割当先候補とを単一資源作業ごとに算出する。単一資源作業割当可能期間は、単一資源作業が含まれる作業列の開始時刻がこの期間内にあるとき、単一資源作業割当先候補に含まれるいずれの資源にも単一資源作業の割当が可能なように定められる。このように、単一資源作業統合部５３は、単一資源作業ごとに、単一資源作業割当部５２で算出した、単一資源作業に対応するすべての資源に対する資源割当可能期間を入力とし、この単一資源作業に対する単一資源作業割当可能期間と単一資源作業割当先候補の組（複数ありうる）を算出する。
【００３８】
単一資源作業割当可能期間と単一資源作業割当先候補は、単一資源作業ごとに、以下の手法で算出することができる。資源Ｒに対する資源割当可能期間［Ｕ，Ｖ）に対して、期間の端点Ｕ又はＶ、資源Ｒ及び記号＋又は記号−の３要素からなる２つのタプル（Ｕ，Ｒ，＋）及び（Ｖ，Ｒ，−）を定める。すべての資源割当可能期間に対してタプルを生成し、生成したタプルのリストを、タプルの第１要素である時刻順にソートする。リストの末尾にタプルの第１要素をスケジューリング期間の終了時刻、第２要素を空、第３要素を−とするタプルを追加する。
【００３９】
図８は単一資源作業統合部５３の処理動作を示すフローチャートである。単一資源作業割当可能期間の開始時刻に当たるＰをスケジューリング期間の開始時刻、単一資源作業割当先候補を空集合として初期化する（ステップＳ１１）。リストの先頭から順にタプル（Ｑ，Ｒ，＊）を取り出す（ステップＳ１２）。タプルの第３要素の＊には＋または−のいずれかの記号が入る。タプルの第３要素の記号が＋か否かを判定し（ステップＳ１３）、タプルの第３要素の記号が＋のとき、第２要素である資源Ｒを単一資源作業割当先候補に追加し（ステップＳ１４）、記号が−のとき、単一資源作業割当先候補から取り除く（ステップＳ１５）。また、Ｐ＜Ｑか否かを判定し（ステップＳ１６）、タプルの第１要素である時刻Ｑの値がＰより大きい場合、［Ｐ，Ｑ）を単一資源作業割当可能期間として（ステップＳ１７）、このときの単一資源作業割当先候補と対応付ける（ステップＳ１８）。さらに時刻Ｐの値をＱに更新する（ステップＳ１９）。ステップＳ１６でＰ＜Ｑでないと判定された場合、又はステップＳ１９の処理が終了した場合、リストが空になったか否かを判定する（ステップＳ２０）。リストがまだ空でなければステップＳ１２以降の処理を行い、リストが空であれば、図８の処理を終了する。
【００４０】
図９は単一資源作業統合部５３の処理動作を示す図である。図９では、資源Ｒ１に対する資源割当可能期間が［Ｔ２１，Ｔ２３）および［Ｔ２５，Ｔ２６）、資源Ｒ２およびＲ３に対する資源割当可能期間がそれぞれ［Ｔ２２，Ｔ２４）および［Ｔ２３，Ｔ２６）であるとき、Ｔ２１〜Ｔ２６を区切りとする単一資源作業割当可能期間と、それぞれに対応する単一資源作業割当先候補を算出する例を示している。
【００４１】
［Ｔ２１，Ｔ２３）は、資源Ｒ１を用いて単一資源作業Ｅ１１を開始できる期間である。［Ｔ２１，Ｔ２２）は、資源Ｒ２，Ｒ３の割当禁止期間であり、かつ資源Ｒ１の資源割当可能期間であるため、資源Ｒ１が割当可能である。［Ｔ２２，Ｔ２３）は、資源Ｒ３の割当禁止期間であり、かつ資源Ｒ１，Ｒ２の資源割当可能期間であるため、資源Ｒ１又はＲ２が割当可能である。［Ｔ２３，Ｔ２４）は、資源Ｒ１の資源割当可能期間ではなく、かつ資源Ｒ２，Ｒ３の資源割当可能期間であるため、資源Ｒ２又はＲ３が割当可能である。［Ｔ２４，Ｔ２５）は、資源Ｒ１，Ｒ２の資源割当可能期間ではなく、かつ資源Ｒ３の単一資源割当可能期間であるため、資源Ｒ３が割当可能である。［Ｔ２５，Ｔ２６）は、資源Ｒ２の資源割当可能期間ではなく、かつ資源Ｒ１，Ｒ３の資源割当可能期間であるため、資源Ｒ１又はＲ３が割当可能である。
【００４２】
図９には、［Ｔ２１，Ｔ２２）の間に図５の作業列を開始する例と、［Ｔ２２，Ｔ２３）の間に図５の作業列を開始する例を示している。［Ｔ２１，Ｔ２２）の間に図５の作業列を開始する場合、単一資源作業Ｅ１１は資源Ｒ１で実施可能である。［Ｔ２２，Ｔ２３）の間に図５の作業列を開始する場合、単一資源作業Ｅ１１は資源Ｒ１又はＲ２で実施可能である。ただし、図９は単一資源作業Ｅ１１に対する単一資源作業統合部５３の処理動作を示しており、各単一資源作業割当可能期間において単一資源作業Ｅ１１以外の割当可否は考慮されていない。
【００４３】
割当統合部５４は、単一資源作業割当可能期間と単一資源作業割当先候補に基づいて、割当可能期間を算出するとともに、割当可能期間にて単一資源作業のそれぞれに割り当てられる資源割当情報を算出する。割当統合部５４は、割当可能期間内に作業列の開始時刻がある場合、作業列に含まれる各作業に資源を割り当てられるようにする。割当可能期間への資源の割当は、後述する第１手法又は第２手法で行うことができる。より具体的には、割当統合部５４は、作業列に対する資源の割当を行う。すなわち、割当統合部５４は、単一資源作業統合部５３で算出した、この作業列に含まれるすべての作業に対する単一資源作業割当可能期間および単一資源作業割当先候補を入力とし、この作業列に対する割当可能期間（複数ありうる）を算出するとともに、その割当可能期間において、この作業列に含まれるすべての単一資源作業に対し資源を割り当てる。
【００４４】
図１０は図１の資源スケジューリング装置１の処理動作を示すフローチャートである。まず、作業分割部５１にて、作業を単一資源作業に分割する（ステップＳ２１）。次に、単一資源作業割当部５２にて、単一資源作業ごと及び資源ごとに、資源割当可能期間を算出する（ステップＳ２２）。次に、単一資源作業統合部５３にて、単一資源作業ごとに単一資源作業割当可能期間と単一資源作業割当先候補を算出する（ステップＳ２３）。次に、割当統合部５４にて、作業列ごとにすべての割当可能期間に資源を割り当てる（ステップＳ２４）。
【００４５】
以下、割当統合部５４が割当可能期間への資源の割当のために行う第１手法と第２手法を順に説明する。
【００４６】
（第１手法）
図１１は第１手法を行う割当統合部５４の内部構成を示すブロック図である。図１１の割当統合部５４は、単一資源作業列接続部５４ａと、単一資源作業列割当部５４ｂと、作業列割当統合部５４ｃとを有する。
【００４７】
単一資源作業列接続部５４ａは、単一資源作業に基づいて、作業列を単一資源作業列に分割する。単一資源作業列は、同一資源を割り当てようとする単一資源作業を、元の作業の実施順序及び間隔を保って前後（時系列）に繋げたものである。ただし、単一資源作業列の開始時刻は、元の作業列の開始時刻と一致するものと定める。作業列は、最小資源数と等しい数の単一資源作業列に分割される。
【００４８】
図１２は作業列を単一資源作業列に分割した例を示す図である。図１２は、図５のように作業Ａ１とＡ２を有し、作業Ａ１は単一資源作業Ｅ１１を有し、作業Ａ２は単一資源作業Ｅ２１とＥ２２を有する場合の分割例である。図１２の作業列は、単一資源作業列Ｆ１とＦ２に分割される。単一資源作業列Ｆ１は、単一資源作業Ｅ１１とＥ２１を、間隔Ｇを挟んで繋げたものであり、例えば資源Ｒ１を用いて各単一資源作業Ｅ１１，Ｅ２１が行われる。また、単一資源作業列Ｆ２は、単一資源作業Ｅ２２のみを有し、例えば資源Ｒ２を用いて単一資源作業Ｅ２２が行われる。
【００４９】
単一資源作業列割当部５４ｂは、単一資源作業列ごとに、単一資源作業列を割当可能な単一資源作業列割当可能期間と、単一資源作業列割当可能期間にて割当可能な単一資源作業列割当先候補とを算出する。単一資源作業列割当可能期間は、単一資源作業列の開始時刻がこの期間内にあるとき、単一資源作業列割当先候補に含まれるいずれの資源にも単一資源作業列の割当が可能なように定められる。単一資源作業列割当可能期間と単一資源作業列割当先候補は、例えば以下の手法で算出することができる。
【００５０】
単一資源作業列を構成する単一資源作業の単一資源作業割当可能期間の開始時刻および終了時刻をすべて収集し、順序付集合にまとめる。すなわち、重複する時刻は省き、時刻順にソートする。スケジューリング期間の開始時刻が順序付集合に含まれない場合は追加する（先頭に加わる）。同様に、スケジューリング期間の終了時刻が順序付集合に含まれない場合は追加する（末尾に加わる）。順序付集合の連続する２つの時刻Ｓ、Ｔによる期間［Ｓ，Ｔ）を算出する。単一資源作業列を構成するすべての単一資源作業に対し、［Ｓ，Ｔ）を含む単一資源作業割当可能期間が存在する場合、それらの単一資源作業割当可能期間と対応する単一資源作業割当先候補の積集合を算出する。積集合が空でない場合、［Ｓ，Ｔ）を単一資源作業列割当可能期間とし、積集合を単一資源作業列割当先候補とし、それらを対応づける。
【００５１】
図１３は単一資源作業列割当部５４ｂの処理動作を説明する図である。図１３は、２つの単一資源作業Ｅ１１、Ｅ２１に対する単一資源作業割当可能期間と単一資源作業割当先候補を示している。図１３の期間Ｔ３０〜Ｔ３１、Ｔ３１〜Ｔ３２、Ｔ３２〜Ｔ３３、Ｔ３３〜Ｔ３４、Ｔ３４〜Ｔ３５、Ｔ３５〜Ｔ３６は単一資源作業列割当可能期間になりうる期間である。図１３では、各単一資源作業割当可能期間を示す矢印線の上に、単一資源作業割当先候補が表示されている。
【００５２】
なお、図１３の単一資源作業Ｅ１１とＥ２１は、開始時刻がΔだけずれている。しかし、図７に示したように、単一資源作業Ｅ１１とＥ２１のいずれの単一資源作業割当可能期間も、単一資源作業Ｅ１１とＥ２１がともに含まれる作業列の開始時刻が取り得る期間である。そのため、ここであらためて単一資源作業の開始時刻のずれを考慮することなしで、単一資源作業割当可能期間を比較（統合）することができる。
【００５３】
単一資源作業列割当部５４ｂは、単一資源作業割当可能期間ごとに、単一資源作業割当先候補の積集合を算出する。例えば、単一資源作業割当可能期間Ｔ３０〜Ｔ３１では、単一資源作業列割当部５４ｂは、単一資源作業Ｅ１１の単一資源作業割当先候補｛Ｒ１｝と、単一資源作業Ｅ２１の単一資源作業割当先候補｛Ｒ１，Ｒ２｝との積集合である｛Ｒ１｝を算出する。
【００５４】
作業列割当統合部５４ｃは、単一資源作業列割当可能期間および単一資源作業列割当先候補に基づいて、割当可能期間を算出するとともに、単一資源作業列のそれぞれに割り当てられる資源割当情報を算出する。より具体的には、作業列割当統合部５４ｃは、まず割当可能期間の候補となる検査期間を算出する。検査期間は以下の手法で算出することができる。作業列を構成する単一資源作業列の単一資源作業列割当可能期間の開始時刻および終了時刻をすべて収集し、順序付集合にまとめる。すなわち、重複する時刻は省き、時刻順にソートする。スケジューリング期間の開始時刻が順序付集合に含まれない場合は追加する（先頭に加わる）。同様に、スケジューリング期間の終了時刻が順序付集合に含まれない場合は追加する（末尾に加わる）。順序付集合の連続する２つの時刻Ｐ、Ｑに対し、検査期間［Ｐ，Ｑ）を算出する。
【００５５】
続いて、検査期間［Ｐ，Ｑ）ごとに割当グラフ（（Ｕ，Ｖ），Ｅ）を生成する。割当グラフは一方の頂点集合Ｕを単一資源作業列と対応付け、他方の頂点集合Ｖを資源と対応付けた２部グラフであり、以下の手法で生成することができる。作業列を構成する単一資源作業列に対し、［Ｐ，Ｑ）を含む単一資源作業列割当可能期間が存在する場合、単一資源作業列に対応付けられた頂点Ｘを集合Ｕに追加する。また、この単一資源作業列割当可能期間に対応する単一資源作業列割当先候補に含まれる資源と対応付けられた頂点Ｙが集合Ｖに含まれていない場合は追加する。また、辺集合Ｅに２点Ｘ、Ｙをつなぐ無向辺（Ｘ，Ｙ）を追加する。
【００５６】
作業列を構成するすべての単一資源作業列と対応する頂点が、生成した割当グラフの頂点集合Ｕに含まれる場合、割当グラフ上の最大マッチングを算出する。最大マッチングの算出には公知の手法を用いればよい。最大マッチングのサイズが頂点集合Ｕのサイズと等しい場合、［Ｐ，Ｑ）を割当可能期間とし、最大マッチングから資源割当を作成して対応付ける。すなわち資源割当では、最大マッチングに含まれる辺（Ｘ，Ｙ）に対し、頂点Ｘに対応する単一資源作業列を構成する単一資源作業の元の作業を、頂点Ｙに対応する資源に割り当てる。
【００５７】
図１４は作業列割当統合部５４ｃの処理動作を説明する図である。図１４（ａ）は、単一資源作業列Ｆ１およびＦ２について、単一資源作業列割当可能期間と、対応する単一作業列割当先候補を示している。図１４（ｂ）は、Ｔ４１〜Ｔ４５を区切りとする検査期間を算出し、各検査期間で割当グラフを生成し、単一資源作業列と資源とのマッチングを算出する例を示している。図１４（ｂ）では、［Ｔ４１，Ｔ４２）において生成される、単一資源作業列Ｆ１およびＦ２にそれぞれ対応付けられた頂点Ｆ１およびＦ２と、資源Ｒ１〜Ｒ３にそれぞれ対応付けられた頂点Ｒ１〜Ｒ３と、無向辺（Ｆ１，Ｒ１）、（Ｆ２，Ｒ１）および（Ｆ２，Ｒ２）からなる割当グラフを示している。図１４（ｂ）では、［Ｔ４１，Ｔ４２）において、単一資源作業列Ｆ１は資源Ｒ１に割り当てられ、単一資源作業列Ｆ２は資源Ｒ２に割り当てられる例を示している。
【００５８】
図１５は割当統合部５４が行う第１手法の処理動作を示すフローチャートである。まず、単一資源作業列接続部５４ａにて、作業列を単一資源作業列に分割する（ステップＳ３１）。次に、単一資源作業列割当部５４ｂにて、単一資源作業列ごとに、単一資源作業列割当可能期間と単一資源作業列割当先候補とを算出する（ステップＳ３２）。次に、作業列割当統合部５４ｃにて、割当可能期間を算出し、単一資源作業列ごとに資源を割り当てる（ステップＳ３３）。
【００５９】
作業スケジューリングの制約条件として、資源の組合せに対する割当可否制約が加えられる場合もある。例えば人員を資源とする業務指示では、必要人数が２名の作業に対して、少なくとも１名が熟練者となる割当が要求される場合がある。
【００６０】
このとき、熟練者のみで構成される第１の集合と、他の人員も加えた第２の集合を構成し、作業分割部５１で作成される２つの単一資源作業のうち、一方を第１の集合に含まれる資源と、他方を第２の集合に含まれる資源とに、それぞれ対応付ける。そして、単一資源作業割当部５２において、各単一資源作業と対応付けられた資源に対してのみ資源割当可能期間を算出し、その他の資源では資源割当可能期間なしとすることで、割当可否制約を守った割当可能期間および資源割当を算出することができる。
【００６１】
また、例えば必要人数が２名の作業に対し２つの班から各１名ずつとなる割当が要求された場合、一方の班の人員で第１の集合を構成し、他方の班の人員で第２の集合を構成し、同様の方法を行えばよい。なお、必要資源数が２以外の場合や、資源集合を３つ以上に分割する場合も同様である。
【００６２】
一方、割当可否制約などが課されておらず、作業を構成する単一資源作業の単一資源作業割当可能期間および単一資源作業割当先候補がすべて共通している場合、割当統合部５４において、割当可能期間および資源割当は以下の第２手法で算出することもできる。
【００６３】
（第２手法）
図１６は第２手法を行う割当統合部５４の内部構成を示すブロック図である。図１６の割当統合部５４は、検査期間分割部５４ｅと、被覆問題演算部５４ｆと、作業割当統合部５４ｇとを有する。
【００６４】
検査期間分割部５４ｅは、単一資源作業割当可能期間の候補となる検査期間を算出する。検査期間は、例えば以下の手法で算出することができる。作業列を構成する単一資源作業の単一資源作業割当可能期間の開始時刻および終了時刻をすべて収集し、順序付集合にまとめる。すなわち、重複する時刻は省き、時刻順にソートする。スケジューリング期間の開始時刻が順序付集合に含まれない場合は追加する（先頭に加わる）。同様に、スケジューリング期間の終了時刻が順序付集合に含まれない場合は追加する（末尾に加わる）。順序付集合の連続する２つの時刻Ｐ、Ｑに対し、検査期間［Ｐ，Ｑ）を算出する。
【００６５】
被覆問題演算部５４ｆは、個々の検査期間ごとに、単一資源作業割当先候補と作業に必要な資源数とに基づいて、使用する資源数が最小になるように資源被覆問題を解く。
【００６６】
資源被覆問題は、資源Ｒに対応する０−１決定変数をＸ［Ｒ］として、以下の（１）式で定式化される最小化問題である。
【数１】
2020113007.tif 000003
【００６７】
ただし、Ｎは資源の総数、Ｍは作業列を構成する作業の数を表す。定数Ａ［Ｔ，Ｒ］は、作業Ｔを構成する単一資源作業の単一資源作業割当可能期間のうち［Ｐ，Ｑ）を含むものが存在するとき、それと対応する単一資源作業割当先候補に資源Ｒが含まれている場合１とする。それ以外の場合は０とする。また定数Ｋ［Ｔ］は作業Ｔの必要資源数を表す。
【００６８】
被覆問題演算部５４ｆは、（１）式の資源被覆問題を解く。求解には、数理最適化の公知の手法を用いればよい。作業割当統合部５４ｇは、資源被覆問題を解いた結果に基づいて、単一資源作業割当可能期間に資源を割り当てる。作業割当統合部５４ｇは、資源被覆問題を解いた結果、目的関数値が作業列の最小資源数と一致する場合、［Ｐ，Ｑ）を割当可能期間とし、最大マッチングから資源割当を生成して対応付ける。すなわち、資源割当では、資源被覆問題の解において変数Ｘ［Ｒ］の値が１であるとき、定数Ａ［Ｔ，Ｒ］の値が１である作業Ｔを資源Ｒに割り当てると定める。
【００６９】
図１７は割当統合部５４が行う第２手法の処理動作を示すフローチャートである。まず、検査期間分割部５４ｅにて、検査期間を算出する（ステップＳ４１）。次に、被覆問題演算部５４ｆにて、検査期間ごとに、使用する資源数が最小になるように資源被覆問題を解く（ステップＳ４２）。次に、作業割当統合部５４ｇは、資源被覆問題の解に基づいて、割当可能期間にて単一資源作業のそれぞれに割り当てられる資源割当情報を算出する（ステップＳ４３）。
【００７０】
スケジューリング対象の作業列は、複数の作業列が開始間隔を守りながら期間が重なるように実施される作業群に拡張してもよい。この場合、作業列情報入力部２２に入力される作業列情報は、作業群に含まれる各作業列およびそれらの開始間隔に関する情報を含むことになる。ただし、開始間隔は０または正値の時間であり、作業群を構成する作業列のうち少なくとも１つに対して０、すなわちこの作業列と作業群の開始時刻は一致するものとする。なお、作業群の最小資源数は、これを構成する作業列の最小資源数の総和である。
【００７１】
図１８は作業群の一例を示す図である。図１８は、必要資源数１の作業Ａ１と必要資源数２の作業Ａ２が間隔Ｇを空けて連続する作業列Ｂ１と、必要資源数２の作業Ａ３のみで構成される作業列Ｂ２とが、開始間隔Ｈを維持しながら期間が重なるように実施される作業群を示している。なお作業列Ｂ１、Ｂ２の最小資源数の合計４が、この作業群の最小資源数となる。
【００７２】
例えば、人員を資源とする装置保守作業では、装置を止めている間に、同時に実施することが可能な複数の作業をまとめて行うことが望ましい場合がある。このとき、開始間隔を０として複数の作業からなる作業群を構成し、作業の実施期間が重なるように割当可能期間および資源割当を算出すればよい。
【００７３】
作業群の割当を行う制御部５における、作業分割部５１、単一資源作業割当部５２および単一資源作業統合部５３の処理動作は上述した通りである。第１手法を実施する場合、割当統合部５４内の単一資源作業列接続部５４ａおよび単一資源作業列割当部５４ｂの処理動作は上述した通りである。作業列割当統合部５４ｃは、作業群を構成するすべての作業列を対象とすることにより、作業群に対する割当可能期間および資源割当を算出する。
【００７４】
また、第２手法を実施する場合、割当統合部５４内の検査期間分割部５４ｅは、作業群を構成するすべての作業を対象として検査期間を算出し、被覆問題演算部５４ｆおよび作業割当統合部５４ｇは作業列ごとに順に資源被覆問題を解き、すべての作業列に対して資源割当が存在する場合、検査期間を割当可能期間とし、算出された資源割当と対応付ける。このとき、被覆問題演算部５４ｆで作成する資源被覆問題は、既に他の作業列の資源被覆問題で変数Ｘ［Ｒ］の値が１となった資源Ｒに対し、この問題における定数Ａ［Ｔ，Ｒ］の値を０にする。
【００７５】
さらに、制御部５は、資源情報更新部５５を備えていてもよい。資源情報更新部５５は、開始時刻決定部５６で決定された開始時刻を起点として、開始時刻を含む割当可能期間と対応付けられた資源割当情報に基づいて、割当禁止期間を含む資源情報を更新する。資源情報更新部５５は、開始時刻が含まれる開始可能期間と対応する資源割当を算出し、作業列を構成する作業の割当先資源に対し、割り当てられた作業の実施期間を割当禁止期間とすることにより資源情報を更新する。開始時刻決定部５６は、割当可能期間に基づき特定の方法で開始時刻を算出する構成としてもよい。例えば割当可能期間に含まれる最も早い時刻を開始時刻としてもよい。もしくは、資源スケジューリング装置１の利用者が、期間割当出力部４１で出力される割当可能期間から開始時刻を選択するために、入力部２は開始時刻選択部２４を備えてもよい。
【００７６】
図１の資源スケジューリング装置１は、割当可能期間と、対応する資源割当情報とを表示可能な表示部６を備えていてもよい。
【００７７】
このように、本実施形態では、作業列を構成する各作業の実施順序及び間隔を遵守できるように、各作業の割当可能期間と資源割当情報を出力するため、作業列に最小資源数の資源を割り当てることが可能となり、効率よく作業を行うことができる。
【００７８】
上述した実施形態で説明した資源スケジューリング装置１の少なくとも一部は、ハードウェアで構成してもよいし、ソフトウェアで構成してもよい。ソフトウェアで構成する場合には、資源スケジューリング装置１の少なくとも一部の機能を実現するプログラムをフレキシブルディスクやＣＤ−ＲＯＭ等の記録媒体に収納し、コンピュータに読み込ませて実行させてもよい。記録媒体は、磁気ディスクや光ディスク等の着脱可能なものに限定されず、ハードディスク装置やメモリなどの固定型の記録媒体でもよい。
【００７９】
また、資源スケジューリング装置１の少なくとも一部の機能を実現するプログラムを、インターネット等の通信回線（無線通信も含む）を介して頒布してもよい。さらに、同プログラムを暗号化したり、変調をかけたり、圧縮した状態で、インターネット等の有線回線や無線回線を介して、あるいは記録媒体に収納して頒布してもよい。
【００８０】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００８１】
１  資源スケジューリング装置、２  入力部、３  記憶部、４  出力部、５  制御部、２１  作業情報入力部、２２  作業列情報入力部、２３  資源情報入力部、４１  期間割当出力部、４２  資源割当出力部、５１  作業分割部、５２  単一資源作業割当部、５３  単一資源作業統合部、５４  割当統合部、５４ａ  単一資源作業列接続部、５４ｂ  単一資源作業列割当部、５４ｃ  作業列割当統合部、５４ｅ  検査期間分割部、５４ｆ  被覆問題演算部、５４ｇ  作業割当統合部
【図１】
2020113007.tif 000004
【図２】
2020113007.tif 000005
【図３】
2020113007.tif 000006
【図４】
2020113007.tif 000007
【図５】
2020113007.tif 000008
【図６】
2020113007.tif 000009
【図７】
2020113007.tif 000010
【図８】
2020113007.tif 000011
【図９】
2020113007.tif 000012
【図１０】
2020113007.tif 000013
【図１１】
2020113007.tif 000014
【図１２】
2020113007.tif 000015
【図１３】
2020113007.tif 000016
【図１４】
2020113007.tif 000017
【図１５】
2020113007.tif 000018
【図１６】
2020113007.tif 000019
【図１７】
2020113007.tif 000020
【図１８】
2020113007.tif 000021