(57)【要約】【課題】電力供給の制約の下で電力利用のスケジュールの決定に要する時間を短縮する。【解決手段】電力利用スケジュール調整装置は、ピーク電力及び使用電力量に上限が設けられた電力供給の制約の下に、電力を利用する複数の作業を実施するスケジュールを算出する電力利用スケジュール調整装置であって、作業を実施する要求と、当該作業の継続時間及び最大消費電力とを示す情報が入力される入力部と、入力部に入力された複数の作業に対して、当該作業の継続時間及び最大消費電力から電力供給の制約を満たして実行可能か否かを順に判定し、実施する作業の組合せを削減する分枝限定法を適用して作業を実施するスケジュールを算出するスケジュール算出部とを備える。【選択図】図１
2013066330.tif 000002
【特許請求の範囲】
【請求項１】
ピーク電力及び使用電力量に上限が設けられた電力供給の制約の下に、電力を利用する複数の作業を実施するスケジュールを算出する電力利用スケジュール調整装置であって、
前記作業を実施する要求と、当該作業の継続時間及び最大消費電力とを示す情報が入力される入力部と、
前記入力部に入力された複数の作業に対して、当該作業の継続時間及び最大消費電力から前記電力供給の制約を満たして実行可能か否かを順に判定し、実施する作業の組合せを削減する分枝限定法を適用して前記作業を実施するスケジュールを算出するスケジュール算出部と
を備えることを特徴とする電力利用スケジュール調整装置。
【請求項２】
前記作業を実施する要求に当該作業を実施すべき時間帯が制約条件として設けられている場合、
前記スケジュール算出部は、前記複数の作業に対して、前記電力供給の制約と前記制約条件とを満たして実行可能か否かを順に判定する
ことを特徴とする請求項１に記載の電力利用スケジュール調整装置。
【請求項３】
ピーク電力及び使用電力量に上限が設けられた電力供給の制約の下に、電力を利用する複数の作業を実施するスケジュールを算出する電力利用スケジュール調整装置における電力利用スケジュール調整方法であって、
前記作業を実施する要求と、当該作業の継続時間及び最大消費電力とを示す情報が入力される入力ステップと、
前記入力ステップにおいて入力された複数の作業に対して、当該作業の継続時間及び最大消費電力から前記電力供給の制約を満たして実行可能か否かを順に判定し、実施する作業の組合せを削減する分枝限定法を適用して前記作業を実施するスケジュールを算出するスケジュール算出ステップと
を有することを特徴とする電力利用スケジュール調整方法。
【請求項４】
ピーク電力及び使用電力量に上限が設けられた電力供給の制約の下に、電力を利用する複数の作業を実施するスケジュールを算出する電力利用スケジュール調整装置に備えられたコンピュータに、
前記作業を実施する要求と、当該作業の継続時間及び最大消費電力とを示す情報が入力される入力ステップと、
前記入力ステップにおいて入力された複数の作業に対して、当該作業の継続時間及び最大消費電力から前記電力供給の制約を満たして実行可能か否かを順に判定し、実施する作業の組合せを削減する分枝限定法を適用して前記作業を実施するスケジュールを算出するスケジュール算出ステップと
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電力利用スケジュール調整装置、電力利用スケジュール調整方法、及びプログラムに関する。
【背景技術】
【０００２】
研究機関や大学などでは、作業をする人員や材料の有無等に基づいて実験を実施するスケジュールを立てている。更に、電力供給の制約が加わる場合、実験において使用する電力量を考慮して、実験を実施する日時や順序などのスケジュールを決めることが必要である。このように、制約の下でスケジュールを立てることは、生産、配送、プロジェクト、要因勤務などの管理において種々の制約条件の下で実行可能な最適なスケジュールを見出すスケジューリング問題として知られている（特許文献１、２）。
スケジューリング問題は、組合せの最適化問題であり、すべての組合せを調べることで、最適解が得られる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１０−２５７３８３号公報
【特許文献２】特開２０１１−０６５４２１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、実験（作業）の組合せの総数が大きくなると、すべての実験の組合せを調べるのに要する時間は、指数関数的に増加してしまうという問題がある。このとき、実施する作業のスケジュールを決定において、制限時間が設けられていると、作業の実施スケジュールを決定できず、作業を実施することができなくなってしまう可能性がある。
【０００５】
本発明は、上記問題を解決すべくなされたもので、その目的は、電力供給の制約の下において電力を利用する作業のスケジュール決定に要する時間の指数関数的な増加を抑制して、スケジュールの決定に要する時間を短縮できる電力利用スケジュール調整装置、電力利用スケジュール調整方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【０００６】
上記問題を解決するために、本発明の電力利用スケジュール調整装置は、ピーク電力及び使用電力量に上限が設けられた電力供給の制約の下に、電力を利用する複数の作業を実施するスケジュールを算出する電力利用スケジュール調整装置であって、前記作業を実施する要求と、当該作業の継続時間及び最大消費電力とを示す情報が入力される入力部と、前記入力部に入力された複数の作業に対して、当該作業の継続時間及び最大消費電力から前記電力供給の制約を満たして実行可能か否かを順に判定し、実施する作業の組合せを削減する分枝限定法を適用して前記作業を実施するスケジュールを算出するスケジュール算出部とを備える。
【０００７】
また、本発明は、上記に記載の発明において、前記作業を実施する要求に当該作業を実施すべき時間帯が制約条件として設けられている場合、前記スケジュール算出部は、前記複数の作業に対して、前記電力供給の制約と前記制約条件とを満たして実行可能か否かを順に判定することを特徴とする。
【０００８】
また、本発明の電力利用スケジュール調整方法は、ピーク電力及び使用電力量に上限が設けられた電力供給の制約の下に、電力を利用する複数の作業を実施するスケジュールを算出する電力利用スケジュール調整装置における電力利用スケジュール調整方法であって、前記作業を実施する要求と、当該作業の継続時間及び最大消費電力とを示す情報が入力される入力ステップと、前記入力ステップにおいて入力された複数の作業に対して、当該作業の継続時間及び最大消費電力から前記電力供給の制約を満たして実行可能か否かを順に判定し、実施する作業の組合せを削減する分枝限定法を適用して前記作業を実施するスケジュールを算出するスケジュール算出ステップとを有する。
【０００９】
また、本発明のプログラムは、ピーク電力及び使用電力量に上限が設けられた電力供給の制約の下に、電力を利用する複数の作業を実施するスケジュールを算出する電力利用スケジュール調整装置に備えられたコンピュータに、前記作業を実施する要求と、当該作業の継続時間及び最大消費電力とを示す情報が入力される入力ステップと、前記入力ステップにおいて入力された複数の作業に対して、当該作業の継続時間及び最大消費電力から前記電力供給の制約を満たして実行可能か否かを順に判定し、実施する作業の組合せを削減する分枝限定法を適用して前記作業を実施するスケジュールを算出するスケジュール算出ステップとを実行させるためのプログラムである。
【発明の効果】
【００１０】
この発明によれば、電力利用する作業それぞれを、当該作業の継続時間及び最大消費電力から電力供給の制約を満たして実行可能か否かを順に判定し、実施する作業の組合せである探索領域を判定結果に応じて削減する。これにより、すべての作業の組合せを調べることなく、実施する作業のスケジュールを決定することができ、作業のスケジュール決定に要する時間を削減することができる。
【図面の簡単な説明】
【００１１】
【図１】本実施形態における電力利用スケジュール調整装置１の構成を示す概略ブロック図である。
【図２】本実施形態における実験項目を入力する画面の一例である。
【図３】本実施形態における実験電力プロファイルの一例を示す図である。
【図４】本実施形態のスケジュール算出部１３が行う分枝限定法を示す概念図である。
【図５】本実施形態における実験スケジュールの出力例を示す図である。
【図６】スケジュール算出部１３が実験スケジュールを算出する処理を示すフローチャートである。
【図７】スケジュール算出部１３が記憶部１２に記憶されている申請情報及び実験電力プロファイルから生成した実験情報を示す図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して、本発明の実施形態における電力利用スケジュール調整装置、電力利用スケジュール調整方法、及びプログラムを説明する。ここでは、電力を利用する作業として実験を例とし、ピーク電力（最大消費電力）及び使用電力量の両方に上限が設けられた電力供給の制約の下に、電力利用スケジュールとしての実験スケジュールを立案する装置等について説明する。
【００１３】
図１は、本実施形態における電力利用スケジュール調整装置１の構成を示す概略ブロック図である。同図に示すように、電力利用スケジュール調整装置１は、入力部１１と、記憶部１２と、スケジュール算出部１３と、表示部１４とを備えている。
入力部１１には、ユーザーから実験を実施する申請を受けたスケジュール立案担当者による操作に応じて、当該実験申請に係る実験項目それぞれの情報を含む申請情報が入力される。ここで、実験項目は、実験名（実験時稼動設備）、継続時間、実験回数である。図２は、本実施形態における実験項目を入力する画面の一例である。同図に示すように、実験名、継続時間、及び実験回数は、予め定められたものから選択するようにしてもよい。
【００１４】
図１に戻って、電力利用スケジュール調整装置１の説明を続ける。
記憶部１２には、入力部１１に入力された申請情報が記憶される。また、記憶部１２には、各実験におけるピーク電力が実験名に対応付けられた実験電力プロファイルが予め記憶されている。
図３は、本実施形態における実験電力プロファイルの一例を示す図である。同図に示すように、実験名にピーク電力が対応付けられている。例えば、実験名がクリーンルームの実験には、１５０［ｋＷ］のピーク電力が対応付けられている。
【００１５】
図１に戻って、電力利用スケジュール調整装置１の説明を続ける。
スケジュール算出部１３は、記憶部１２が記憶する申請情報、及び実験電力プロファイルに基づいて、各実験に対応する実験情報を生成する。例えば、実験開始時刻ｔ０から実験終了時刻ｔ１までの間に電力Ａ［ｋＷ］を消費する実験の消費電力は、次式（１）として立式される。
【００１６】
【数１】
2013066330.tif 000003
【００１７】
また、実施しているときに消費する電力が一度変化する実験の消費電力は、次式（２）として立式される。このとき、時刻ｔ１は消費電力が変化する時間であり、時刻ｔ２は実験終了時刻である。
【００１８】
【数２】
2013066330.tif 000004
【００１９】
なお、実施中に消費する電力が複数回変化する実験では、場合分けが変化の回数に応じて増加する。
また、式（１）を用いて消費電力が表される実験に対して、実施する時間帯の制約がある場合、次式（３−１）及び（３−２）として立式される。
【００２０】
【数３】
2013066330.tif 000005
【００２１】
式（３−１）及び（３−２）で消費電力が表される実験は、午前中に実施することが制約として設けられている。
また、スケジュール算出部１３は、各実験の消費電力Ｐexpk(ｔ）に基づいて、制約条件つきのスケジューリング問題を次式（４）〜（６）として立式する。
【００２２】
【数４】
2013066330.tif 000006
【００２３】
【数５】
2013066330.tif 000007
【００２４】
【数６】
2013066330.tif 000008
【００２５】
ここで、式（４）のＰtotal（ｔ）は時刻ｔにおける全実験の総電力であり、Ｐbase（ｔ）は時刻ｔにおけるベース電力（空調設備やその他の負荷）である。各時刻におけるベース電力は、過去の使用電力等に基づいた統計値を用いるようにしてもよい。この場合、記憶部１２に、各時刻におけるベース電力を予め記憶させるようにしてもよい。
また、ｎは実験総数である。Ｐwmaxは総ピーク電力の上限値としての電力制約値であり、Ｐwhmaxは使用電力量の上限値としての電力量制約値である。電力制約値Ｐwmaxと電力量制約値Ｐwhmaxとは、電力供給の制約として予め定められる。また、ｔstは実験スケジュールの調整期間の開始時刻であり、ｔfinは実験スケジュールの調整期間の終了時刻である。
【００２６】
このとき、スケジュール算出部１３は、実験スケジュールの立案を次式（７）で表されるｚ（実施する実験数）を最大化する問題とする。
【００２７】
【数７】
2013066330.tif 000009
【００２８】
式（７）において、δkは実験ｋの実施の可否（０−１）を示す変数であり、δk＝０は実験ｋの不実施を示し、δk＝１は実験ｋの実施を示す。
スケジュール算出部１３は、できるだけ多くの実験を実施する実験スケジュールを立案するため、式（４）〜（６）の制約を満たしつつ、各実験の可否を示すδkの総和を示す式（７）を最大化する実験の組合せを算出する。
【００２９】
上述の問題は、混合整数計画問題として分類される。すべての０−１変数（δk：k＝１，…，ｎ）に対し探索を行うと、探索領域は２ｎになる。スケジュールの対象になる実験の数が多くなると、探索領域は指数関数的に増加することになり、解を得ることが困難になる。
そこで、スケジュール算出部１３は、分枝限定法を用いて、探索領域を削減しつつ実験スケジュールの立案を行うようにする。
【００３０】
図４は、本実施形態のスケジュール算出部１３が行う分枝限定法を示す概念図である。スケジュール算出部１３は、０−１変数（δk）の１つである０−１変数（δ1）に対応する実験１を実行する場合に各制約を満たすことができるか否かを判定する（節点Ｎ１１）。ここで、節点Ｎ１１における状態は、各実験を実施するか否かを定めていない状態である。
【００３１】
スケジュール算出部１３は、すべての制約を満たせる場合、実験１を実施するとき（節点Ｎ２１）と、実験１を実施しないとき（節点Ｎ２２）とにおける目的関数（式（７））の上界を算出する。例えば、節点Ｎ２２の上界が節点Ｎ１１の上界より小さい場合、実験１を実施することを選択し、節点Ｎ２２以下の探索領域（節点Ｎ３３、節点Ｎ３４、…）に対する探索を行なわないことになる。
一方、スケジュール算出部１３は、満たせない制約がある場合、実験１を実施しないことを選択し探索を続ける。この場合、節点Ｎ２１以下の探索領域（節点Ｎ３１、節点Ｎ３２、…）に対する探索を行わない。
【００３２】
また、図４において、節点Ｎ２１は実験１を実施することを定め、他の実験を実施するか否かを定めていない状態である。節点Ｎ２２は実験１を実施しないことを定め、他の実験を実施するか否かを定めていない状態である。
また、節点Ｎ３１は実験１及び実験２を実施することを定め、他の実験を実施するか否かを定めていない状態である。節点Ｎ３２は実験１を実施し、実験２を実施しないことを定め、他の実験を実施するか否かを定めていない状態である。節点Ｎ３３は実験１を実施せず、実験２を実施することを定め、他の実験を実施するか否かを定めていない状態である。節点Ｎ３４は、実験１及び実験２を実施しないことを定め、他の実験を実施するか否かを定めていない状態である。
【００３３】
上述のように、スケジュール算出部１３は、探索領域を限定しながら、実験スケジュールを決定する。スケジュール算出部１３は、算出した実験スケジュールを表示部１４に出力して表示させる。
また、スケジュール算出部１３は、算出した実験スケジュールを記憶部１２に記憶させる。電力利用スケジュール調整装置１は、入力部１１に入力されるスケジュール立案担当者の操作に応じて、記憶部１２に記憶された実験スケジュールを外部に出力するようにしてもよい。
【００３４】
図５は、本実施形態における実験スケジュールの出力例を示す図である。同図において横軸は時刻を示し、縦軸は各時刻における消費電力を示している。また、各実験が実施される時刻がグラフにより示されている。ここに示した出力例では、ピーク電力の総和が１２００［ｋＷ］を以下にする電力供給の制約の下に実験のスケジュールが立案されている。図５（ａ）は、スケジュール算出部１３が算出した、電力供給の制約を満たす実験スケジュールの出力例である。図５（ｂ）は、電力供給の制約を満たさない実験スケジュールの例である。同図に示した実験スケジュールでは、各実験に対して７時から２１時までの間に実施することが制約として設けられている。
【００３５】
以下、電力利用スケジュール調整装置１による実験スケジュールを算出する処理を、図６及び図７を用いて説明する。図６は、スケジュール算出部１３が実験スケジュールを算出する処理を示すフローチャートである。図７は、スケジュール算出部１３が記憶部１２に記憶されている申請情報及び実験電力プロファイルから生成した実験情報を示す図である。
図７に示す実験情報では、各実験１〜７を実施する時間帯の希望である希望時間帯が加えられている。希望時間帯は、入力部１１を介して外部より入力され、実験スケジュールを算出する際の制約条件の一つとなる。また、各実験は、実験番号をキーにして、実験名、継続時間、ピーク電力、及び希望時間帯が対応付けられている。例えば、実験番号が実験３の実験に対して、振動台（１００％）、２［ｈ］、８００［ｋＷ］、及びＡＭ（７：００〜１２：００）が、実験名、継続時間、ピーク電力、及び希望時間帯として対応付けられている。また、実験番号は、例えば、入力部１１に入力された順に付与される。
以下、実験は７時から２０時までの正時に開始する場合について説明する。
【００３６】
実験スケジュールを算出する処理が開始されると、図６に示すように、入力部１１に申請情報が入力され、申請情報が記憶部１２に記憶される（ステップＳ１０１）。
スケジュール算出部１３は、記憶部１２に記憶されている申請情報及び実験電力プロファイルから実験情報を生成する（ステップＳ１０２）。
スケジュール算出部１３は、各実験を実施するか否かを定めていない状態を実験スケジュールとする初期化を行い、実験スケジュールを記憶部１２に記憶させる（ステップＳ１０３）。このとき、各時刻における電力としてベース電力が設定される。
【００３７】
スケジュール算出部１３は、実験番号の小さい実験から順に、ステップＳ１０４〜ステップＳ１０７の処理を繰り返して行う。スケジュール算出部１３は、記憶部１２に記憶されている実験スケジュールを読み出し（ステップＳ１０４）、読み出した実験スケジュールにおいて、判定対象の実験を実施可能な開始時刻があるか否かを判定する（ステップＳ１０５）。また、記憶部１２に複数の実験スケジュールが記憶されている場合、スケジュール算出部１３は、実験スケジュールごとに、ステップＳ１０５以降の処理を実行する。
【００３８】
図７に示された実験１が判定対象である場合、スケジュール算出部１３は、実験１の希望時間帯において、実施可能な開始時刻があるか否かを判定する。具体的には、継続時間が４時間の実験１を午前中に終了させるように、７時又は８時から開始できるか否かを判定する。このとき、実験１を実施した場合に制約条件を満たしているか否かを判定する。スケジュール算出部１３は、７、８、９、１０、１１時台に使用される電力（ベース電力や、他の実験で使用される電力）に５００［ｋＷ］を足したピーク電力が電力制約値Ｐwmaxを超えていないこと、及び、実験１を実施した場合に使用される電力量（４［ｈ］×５００［ｋＷ］）を加えた使用電力量が電力量制約値Ｐwhmaxを超えていないことを判定する。
電力制約値Ｐwmax及び電力量制約値Ｐwhmaxを超えない場合、すなわち電力供給の制約を満たす場合、実験１を実施可能な開始時刻があることになる。これに対して、電力制約値Ｐwmax又は電力量制約値Ｐwhmaxのいずれか一方、あるいは両方を超える場合、すなわち電力供給の制約を満たせない場合、実験１が実施可能な開始時刻がないことになる。
【００３９】
ステップＳ１０５において、判定対象の実験に対して実施可能な開始時刻がある場合（ステップＳ１０５：ＹＥＳ）、スケジュール算出部１３は、判定対象の実験を実施した場合の目的関数（式（７））の上界と、判定対象の実験を実施しない場合の目的関数の上界とを算出する。スケジュール算出部１３は、上界が大きくなる選択を行う。すなわち、スケジュール算出部１３は、判定対象の実験を実施する選択を行い、判定対象の実験を実施しない組合せを含む実験スケジュールの探索を行わずに探索領域を削減する。
【００４０】
スケジュール算出部１３は、実施可能と判定した開始時刻から実験を実施する実験スケジュールを生成し、生成した実験スケジュールを記憶部１２に記憶させて、実験スケジュールの更新を行う（ステップＳ１０６）。このとき、実施可能と判定された開始時刻が複数ある場合、それぞれの開始時刻から実験を実施する実験スケジュールに更新する。すなわち、複数の実験スケジュールを生成する。図７における実験１が判定対象の場合、スケジュール算出部１３は、実験１を７時から実施する実験スケジュールと、実験１を８時から実施する実験スケジュールとを生成し、生成した実験スケジュールを記憶部１２に記憶させて、実験スケジュールを更新する。
【００４１】
一方、ステップＳ１０５において、判定対象の実験に対して実施可能な開始時刻がない場合（ステップＳ１０５：ＮＯ）、スケジュール算出部１３は、判定対象の実験を実施しないことを選択し、当該実験を実施しない実験スケジュールを生成する。すなわち、スケジュール算出部１３は、判定対象の実験を実施する組合せを含む実験スケジュールの探索を行わずに探索領域を削減する。
スケジュール算出部１３は、生成した実験スケジュールを記憶部１２に記憶させて、実験スケジュールを更新する（ステップＳ１０７）。
【００４２】
スケジュール算出部１３は、実験ごとに、ステップＳ１０４〜ステップＳ１０７を繰り返して行い、目的関数（式（７））を最大にする実験スケジュールを算出する。例えば、実験情報が図７に示した実験情報である場合、午前中に実験１、実験３、実験４及び実験６を開始する実験スケジュールが目的関数を最大にする実験の組合せとなる。
スケジュール算出部１３は、実験に対して実施するか否かを示す実験スケジュールを記憶部１２から読み出し、読み出した実験スケジュールを表示部１４に出力する（ステップＳ１０８）。実験スケジュールには、上述のように、実施する実験の開始時間を示す情報が含まれている。
【００４３】
以上のように、電力利用スケジュール調整装置１は、スケジュール算出部１３が申請情報と実験電力プロファイルとに基づいて実験情報を生成する。スケジュール算出部１３は、分枝限定法を用いて、予め定められた制約を満たす実験スケジュールを算出して、記憶部１２に記憶させるとともに、表示部１４に出力する。このとき、スケジュール算出部１３は、実験情報に含まれる実験に対して順に電力供給の制約を満たして実施することができるか否かを判定することにより、探索領域を削減して申請された実験のすべての組合せを調べることなく、実験スケジュールを算出することができる。
これにより、電力利用スケジュール調整装置１は、電力供給の制約の下において電力を利用する作業のスケジュール決定に要する時間の指数関数的な増加を抑制して、スケジュールの決定に要する時間を短縮することができる。
【００４４】
なお、本実施形態では、各実験のピーク電力が実験電力プロファイルとして記憶部１２に予め記憶されている構成を説明した。しかし、これに限ることなく、ピーク電力を含む申請情報が入力部１１に入力されるようにしてもよい。
【００４５】
なお、上述の電力利用スケジュール調整装置１は内部に、コンピュータシステムを有していてもよい。その場合、上述した入力部１１、記憶部１２、スケジュール算出部１３、及び表示部１４の各機能部が行う処理の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータが読み出して実行することによって、実験スケジュールを算出する処理が行われることになる。ここでコンピュータ読み取り可能な記録媒体とは、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等をいう。また、このコンピュータプログラムを通信回線によってコンピュータに配信し、この配信を受けたコンピュータが当該プログラムを実行するようにしても良い。
【符号の説明】
【００４６】
１…電力利用スケジュール調整装置、１１…入力部、１２…記憶部、１３…スケジュール算出部、１４…表示部
【図１】
2013066330.tif 000010
【図２】
2013066330.tif 000011
【図３】
2013066330.tif 000012
【図４】
2013066330.tif 000013
【図５】
2013066330.tif 000014
【図６】
2013066330.tif 000015
【図７】
2013066330.tif 000016