Tag: scheduling

Analytics
0
電力平準化問題に対するSASのアプローチ(2)

はじめに 前回のブログでは、電力平準化問題が数理最適化のスケジューリング問題として扱えること、SASのCLP Procedureで簡単にモデリング可能であることを紹介しました。今回は具体的にサンプル問題でCLP Procedureの使い方を見ていきます(ブログ末尾にサンプルコード記載)。 CLP Procedureの使い方 ここではプロシジャの使い方を分かりやすく示すため、図1のような3タスク、2設備の簡略化された問題のスケジューリングを例として説明します。タスクの詳細な設定は表1の通りとします。   中身の詳しい説明に入る前に、一つだけ最適化の処理で理解しておくべき概念として、Resourceというものを紹介します。Resourceとはタスクを実行するために必要な何かしらの資源で、CLP Procedureによるスケジューリングでは「ある時間帯の使用電力がXである=電力という資源をX占有する」のように読み替えることがポイントです。図1を例にとると、全体のResourceとしては電力設備M1とM2が1つずつ、電力は設定した電力上限分が用意されており、タスクA実行中は電力設備M1というResourceを1つ、電力というResourceを電力波形で表される分だけ各時間で占有する、と見なすことができます。最終的に実行可能なスケジュール(同じ時間帯に複数のタスクが同じ設備で実行されない、電力上限を超過しない)を作成することは、各タスクが上限の範囲内で上手くResourceを分け合うような割り当てを作成することに置き換えられます。 では、実際にSASコードでCLP Procedureを呼び出してスケジューリングを行う部分ですが、必要なのは以下のコードだけです。 proc clp actdata=act resdata=res schedtime=outtime schedres=outres; run; “schedtime”と”schedres”は出力先データセットの指定なので、ユーザーが用意する必要があるのは入力データの”actdata”と”resdata”のみです。では、それぞれのデータセットの内容を確認してみましょう。 “resdata”ではResourceの設定を行います。上での説明の通り、電力設備M1とM2が1つずつで、使用可能な電力総量の上限が“12”であることを表現しており非常に簡潔な設定です。 “actdata”はスケジューリングの対象となる最小要素であるActivityの設定を行います。今回の例では、タスクを図1のように分割したフェーズそれぞれを一つのActivityと考えます。こちらのデータセットは様々な要素が一行に並んでいるのでやや複雑ですが、設定項目は大まかに5種類の系統に分かれます。 まず_ACTIVITY_列では、各Activityにそれぞれ固有のIDを設定します。タスクAを例にとると、各フェーズの電力使用に当たるA01~A05と、タスク全体として設備M1を使用することを表すA00を設定しています。今回の問題では「設備M1を使用している間電力を使用する」という前提なので、A00の_DURATION_とA01~A05の合計が一致していることが確認できます。問題によっては「待ち時間などで使用電力0だが設備は占有したまま」のような状況で、両者の_DURATION_が異なる設定もあり得ます。 _SUCCESSOR_は前後関係を設定する対象のActivityを示しており、前後関係の種類と程度は_LAG_と_LAGDUR_で指定します。例えばFSは、「当該ActivityのFinishと_SUCCESSOR_で指定するActivityのStartの差が_LAGDUR_で指定する値以上」を示しています。今回の例では一つのタスクを分割したフェーズに相当するActivityは常に間を空けることなく実行されるため、_LAG_=FSE(FinishとStartが_LAGDUR_にEqual)、_LAGDUR_=0と設定しています。6行目のように、「タスクAの後3時間単位空けてタスクBを開始する」という業務的な意味での前後関係を表すのにも使用できます。また1行目のA00では、_LAG_=SSE(StartとStartが_LAGDUR_にEqual)でA01と開始が一致するように設定されていることにも注意が必要です。設定の詳細はマニュアルをご覧ください。 _ALIGNDATE_と_ALIGNTYPE_の組み合わせは_SUCCESSOR_と_LAG_の関係に似ていて、当該Activityと_ALIGNDATE_で指定した期日の間に_ALIGNTYPE_で指定する前後関係を設定します。例えば作業に着手可能になる時期や納期を表すのに使用でき、12行目では_ALIGNTYPE_=FEQ(Finishが_ALIGNDATE_=24にEqual)で「タスクB(のフェーズ5)が時刻24丁度に終了すること」を指定しています。 この設定でCLP Procedureを実行すると以下のような結果が得られ、時間に関する結果の”schedtime”とResourceに関する結果の”schedres”が出力されます。”schedtime”は各Activityをどの時間枠に割り当てるかという関心のある結果そのもの、”schedres”には例えば(今回の問題とは異なり)タスクを実行する設備にも選択肢がある場合のResourceの割り当てが出力されています。 最後に少しデータの加工が必要ですが、以下のようにガントチャートや電力波形に可視化して、諸々の条件が満たされたスケジュールになっていることが確認できます。図2 では"resdata"(表2)で指定した、「使用可能な電力総量の上限が“12”」を下回っていることが確認できます。 なお前回も記載しましたが、「ピーク値をどこまで下げることができるか?」を知りたい場合は、「使用可能な電力総量の上限」の指定値を下げて計算し、その条件を満たすスケジュールが作成可能かを調べることで下限を得ることができます。 まとめ 本ブログでは電力平準化問題を例として、CLP Procedureの使い方を見てきました。手順の中心となる入力データ準備の部分は、他のプログラミング言語で用意したものを読み込ませても良いですし、規模が小さければExcel上で作成してしまうことも可能です。SAS言語の知識も最適化の知識も最小限で、便利にスケジューリング機能が使えると感じていただけたなら幸いです。(反響があれば、設備の割り当ても考える場合など、より高度なモデリング方法についても取り上げます) サンプルコード 入力データは全てdataステップで作成しています。ganttプロシジャはclpプロシジャの結果である"schedtime"をほとんどそのまま使用できます(今回はグループ化の処理だけ追加しています)。使用電力の棒グラフについては、今回説明していないデータ加工が多少必要になるため、ソースコードからは割愛しています。 data res; input _RESOURCE_ $ _CAPACITY_; datalines; M1 1 M2 1 El 12 ;  

Analytics
0
電力平準化問題に対するSASのアプローチ(1)

はじめに 2022年も半ばを過ぎましたが、今年は何かと電力需給関係の話題を耳にすることが多くなっています。まず3月下旬には、直前に発生した福島県沖地震の影響で火力発電所が停止したことと寒波が重なり、東京電力と東北電力の管内で電力需給ひっ迫警報(予備率3%以下)が発令されました。そして6月下旬にも想定外の猛暑により、東京電力管内で電力需給ひっ迫注意報(予備率5%以下)が発令されています。事業者の皆様にとっても、政府からの節電要請など対応の必要な課題の一つではないでしょうか。 さて、本ブログでは製造業のスケジューリングを例にとって、使用電力の平準化(ピーク時間帯をシフトする、またピークそのものを下げる)問題に対するSASのアプローチをご紹介します。そもそも一般的なスケジューリング問題は数理最適化問題として扱えることが知られていますが、電力平準化問題も同様の枠組みで解決可能です。数理最適化によるスケジューリングは事例も豊富で歴史もある分野なのですが、通常の最適化エンジンを使用したスケジューリング問題のモデリングには背景にある数理最適化の理解が必要不可欠で、経験の無い方にとっては中々手を出しにくい代物というのが実情です。一方SAS Optimization(またはSAS/OR)にはスケジューリング問題専用の機能があり、CLP Procedureにフォーマットに従ったデータを与えるだけで、ほとんど数理最適化の理論を意識することなく簡単にモデリングすることができます。SASにはあまり最適化のイメージは無いかもしれませんが、本ブログをきっかけに意外と便利な機能が揃っていることを知っていただけたら幸いです。 問題設定 本ブログのスケジューリングで対象にするタスクとは、製造業における一連の生産プロセスのように、一度開始すると所定時間まで途中で中断することのできない作業のまとまりを指し、その間継続的に電力を使用するものとします(タスクごとに使用電力の推移がどうなるかは、過去の実績や予測としてデータ化されている必要があります)。 そして「使用電力を平準化する」とは、非常に単純に表現すると図1のように、使用電力の大きいタスクの時間的重なりをできるだけ解消してピークを下げることです。もちろん現実の問題では、設備の数や納期など様々な制約が存在するので、それらを考慮したスケジュールを作成する必要があります。 では次に、スケジューリング問題として扱いやすくするため現実の問題に対して行う、二つの側面からの近似を説明します。一つ目は時間軸に関する近似で、最小の時間単位を決めてその単位に粒度を丸めます。例えば30分単位で1日分のスケジュールを立てる場合、各タスクの所要時間も30分単位に切り上げて丸めて、「1日分48個の時間枠のどこからどこに割り当てるか」という処理を行うようにします。もう一つは電力波形に関する近似で、もとの波形を階段状に近似します。階段状の近似では、実際の電力波形の傾向が変わるなどキリの良い時点で分割して(フェーズに分割)、各フェーズの使用電力は常に期間中の最大値と同じとみなすような近似を行います。30分単位のスケジューリングを行う場合は、フェーズの所要時間も30分単位になるよう切り分けます。ここでは実際の電力波形を四角いブロックで覆うように近似していますが、もとの波形から多めに余裕を見て使用電力を設定している状況に該当しますので、このシミュレーションで電力ピークを削減できれば、実際にはもっと大きく削減できる可能性があるということになります。「時間軸はどれくらい細かく設定するか」や「タスクを何フェーズに分割するか」は、最終的なスケジュールの精度に影響しますので、問題の設定者が処理時間(細かくすればするほど計算の処理時間は伸びる)との兼ね合いで決定していく要素になります。電力に限定すると、電力会社の集計が30分単位なので、30分単位のスケジューリングには妥当性があります。 このような設定のタスクが複数存在してそれぞれのタスクを実行可能な設備が決まっている場合に、「各タスクをいつ開始するか」を上手く調節して、使用電力合計のピークが所定の上限を超えないようなスケジュールを作成することが今回の目的です。 本手法で行うのは与えた使用電力の上限を超えないスケジュールを作成することなので、いくらまでピーク値を下げられるかは自動的には求められません。通常は業務的に意味のある目標値を指定しますが、「ピーク値をどこまで下げることができるか?」を知りたい場合は、電力上限の指定値を変えて複数回実行することで求められます。指定値が厳しすぎて実行可能なスケジュールが無い場合は解なしと出るので、そこに至るまで少しずつ指定値を下げて再実行する、もしくはそのような処理を自動で行うシステムを実装します。 以下はある程度複雑な問題(30分単位1週間分、10設備、20タスク、上限10kW)を解いた時の結果イメージです。弊社では実際のプロジェクトでも使用電力平準化の問題に取り組んだ事例があり、階段状近似によって実際より各タスクの使用電力を過大評価している分を加味しても、最適化によって作成したスケジュールの方が実績よりピークが低くなることを示せました。 次回はサンプル問題でCLP Procedureの使い方を詳しく説明します! まとめ 最後に電力平準化問題のビジネスインパクトについてですが、この問題で行っているのは使用電力のピーク値の削減で、使用量そのものを削減している訳ではない(合計すると同じ)ことに注意が必要です。電力会社との契約はピーク値に基づいて決まるため、それを小さくすることができれば一定のコスト削減効果はあります。また契約によっては時間帯によって料金が異なるため、高い時間帯からピークをずらせればその分だけのコスト削減も見込めます。ただし事業規模にもよりますが、この両者を総合しても、電力平準化だけで十分な投資対効果を得るのは難しい可能性もあります。一方、節電要請への対応はコストだけに還元できない社会的意義もあり、今後のディマンドレスポンス進展や、既に今冬にも予想されている電力ひっ迫への対応など、昨今の不安定な情勢へのBCPの一つとして十分に検討に値するテーマであるとも考えています。また同じような考え方で、より利益に直結するスケジューリングを検討することも可能です。 SASでは既存のユーザー様に対するライセンス追加や活用方法のアドバイス、既存・新規関わらずドメイン知識の豊富なコンサルタントによるプロジェクト化の支援など幅広く受け付けておりますので、ご興味を持たれた方は是非ご連絡ください。

Advanced Analytics
Subramanian Pazhani 0
Back to School Optimization

Public and private schools are struggling to figure out how to bring face-to-face instruction to students during this pandemic. Health risks to students and teachers, parents struggling with child-care options and/or support for virtual learning, and schools’ capacities and budget limitations make this problem a severe logistical challenge. Schools need

Advanced Analytics
0
Detecting Anomalies in the NFL Schedule

Super Bowl 50 (L?) is this Sunday, so it's time for another (American) football-related post. Steven Miller, a mathematics professor at Rutgers University, recently noted that the 2015 NFL schedule allowed a competitive advantage for some teams (including the Carolina Panthers). This figure he generated displays the 2015 regular season

Advanced Analytics
Emily Lada 0
Simulate to validate

The primary objective of many discrete-event simulation projects is system investigation.  Output data from the simulation model are used to better understand the operation of the system (whether that system is real or theoretical), as well as to conduct various "what-if"-type analyses.   However, I recently worked on another model