組み合わせ最適化エンジン Redhat JBoss BRMS 「Business Resource Planner」

組合せ最適化による業務効率化

シフトスケジューリングや、配送問題など、誰に、何を、どの順番でといった組み合わせで表現される問題を、組合せ最適化問題といいます。組み合わせ最適化問題を解くのには、非常に膨大な繰り返し演算を行う必要があり、最近までPCでは許容時間内に計算を終了させることができませんでした。しかし、近年、PCの処理性能向上とともに計算アルゴリズムの進歩により、日常的に業務で問題にしている組合せ最適化問題が許容時間内に計算できるケースが増えています。
オープンソースである最適化エンジン「Business Resource Planner」では、初期コストを抑えて、組合せ最適化問題を自動化することが可能になります。より短期間により良い組み合わせを探し出すことができるようになります。これにより組合せ最適化問題であるシフトスケジューリングや配送問題にかける労力を軽減します。

組合せ最適化エンジンによる業務効率化

組合せ最適化とは

業務の中でも、誰にどの仕事をやってもらうかといった組み合わせで表現されるものを組み合わせ問題といい、以下のような問題が存在します。
・シフトスケジューリング(ナーススケジューリング)
・配送問題(TSP、VRP)
・時間割作成
・席決め
・PJの最短工期と作業順の算出

最適化エンジンでは、上記のような組み合わせ問題をPCで計算してより良い解を試行錯誤しながら算出します。


最適化問題

このようなお悩みをお持ちではないでしょうか?

実際に組合せ最適化問題を解く場合には、色々な制約を考慮する必要があります。
・勤務の制約
 勤務希望日/時間帯、連続勤務日数、最低/最高出勤日数/時間など。
・公平性の考慮
 過去の業務負荷を加味しながら、今後の業務割を決めるなど。
・スキルの制約
 国語と英語は教えられる(優先)。数学は資格はあるが専門でない(劣後)など。
・組み合わせの制約
 熱いものと冷たい物を同時に運ばないなど。

 

これらの組み合わせに関する制約を加味しながら問題を解くには、非常に大変な作業となります。そのため、組み合わせ最適問題を解く場合、現状は、以下のようになってはいないでしょうか?
・試行錯誤を繰り返すため、非常に時間と手間がかかる(月の労働時間の5割など)
・業務時間中に問題が解けず、家に持ち帰って作業をしている
・組み合わせ問題の業務を憂鬱に感じている

最適化エンジン「Business Resource Planner」を利用するメリット

組合せ最適化問題は、全通りの組み合わせの中からBestなものを探す問題です。しかし、実際には全通りの組み合わせを列挙することは不可能です。たとえば、10人の従業員の1か月間のシフト(朝、昼、晩、休みの4種類)を割り当てる組み合わせでも4^(10人*30日)通りの組み合わせが存在します。1秒間に10000通り列挙しても、宇宙の寿命を超える時間がかかる計算です。人間は、勘と経験を生かすことで、このような問題を解いているのです。
PCには勘や経験はありません。そこで最適化エンジン「Business Resource Planner」はメタヒューリスティックと呼ばれる手法を利用することで、より良いパターンを発見します。そして、組合せ最適化問題を作業者からPCに移管することで、作業者はより付加価値の高い仕事に専念できるようになります。

ページトップへ戻る

組合せ最適化問題

ペナルティ

PCが組合せ最適化問題を解くとき、組合せの制約と、違反した場合のペナルティを設定します。ペナルティにも種類があり、違反したら業務が成り立たないようなペナルティ(たとえば、積載量を超える荷物の割り当て)をハードペナルティ、違反しても業務は可能だがなるべく満たしてほしい制約(たとえば、8時間以内に終わる業務量の割り当て)はソフトペナルティといいます。ソフトペナルティも、制約の重要度によって1違反あたりのペナルティ量を設定できます。PCは、このペナルティが最小(もしくは最大)になるように組み合わせの入れ替えを行っていきます。

ページトップへ戻る

Business Resource Planner基本機能

Business Resource Plannerとは

JBoss Communityで開発されているメタヒューリスティックな解法を用いた最適化エンジンで、シフトスケジューリングやビンパッキング問題など、様々な最適化問題に対応することが可能となっています。

・Javaのオープンソースライブラリとして提供
・比較的軽量な実装で、他のアプリケーションへの組込みも可能
・割当ルールはルール記述言語「Drools Rule Language」にて記述し、柔軟な割当ルールの変更も可能
・複数のメタヒューリスティックな解法を実装

記述可能なルール

業務仕様に合わせてルールを記述していきます。ルールの優先順位だけでなく、そのインパクトを定量的にペナルティとして記述する必要があります。そのため、技術的な内容に加えて、業務の重要度をお客様と分析する必要があります。

 

 

『Opta Planner』は、Redhat JBoss BRMS『Business Resource Planner』のコミュニティ版です。

 

ページトップへ戻る

組み合わせ最適化エンジン Redhat JBoss BRMS 「Business Resource Planner」関連資料ダウンロード

お問い合わせ・見積のご相談

お問い合わせ

当製品・ソリューションに関するお問い合わせはこちら

見積のご相談

当製品・ソリューションについての簡易見積が可能です