スケジューリング問題とは？数理最適化によるシフト作成などの問題解決事例

スケジューリングとは人や機械の日程や順序を組むことです。業務で表れるスケジューリングでは大勢の人の予定が絡み合ったり、機械の稼働状況も考えなければいけない、といった要因により非常に複雑になります。

人の手でスケジューリングを行う場合、規模の小さなものでも現場のノウハウのあるベテランがかかりきりになって数時間かけて計画を立てるのが典型的で、規模の大きなものになると計画を立てるのに数日かけることもあります。しかし、数理最適化という技術を活用すれば複雑なスケジューリングも自動で数分から数十分で組むことができるようになります。この記事では人のスケジューリングであるシフトスケジューリングと機械のスケジューリングである生産スケジューリングについてご紹介します。

シフトスケジューリング

シフトスケジューリングとは、シフト勤務を採用している現場における、ある一定の期間（例えば1ヶ月）のシフトを作成する問題のことです。数理最適化の視点から見ると、勤務表の各マス目にシフトを割り当てる問題ということで、割当問題の一種と言うことができます。

シフト作成の際、法令の遵守や必要人数の充足は当然考慮しなければなりません。しかし、それだけでは満足度の低いシフトとなってしまう可能性が高いです。満足度の高いシフトを作成するためには、以下のような各企業・現場に固有の制約を考慮することになります。

「夜勤」の取り扱い（病院の看護師のシフト作成（ナーススケジューリング問題）においては非常に重要）
就業開始・終了時間や休憩のタイミング
時間帯ごとに業務を割り当てる（午前と午後という分け方が多いですが、細かい場合は15分単位

数理計画法パッケージ Nuorium Optimizer では問題構造に応じた数理モデルを構築することで、上記のような制約を考慮することができます。また Nuorium Optimizer を利用したシフト作成は、次のように様々な場面で実際に活用されています。

JRシステム様：働き方改革の時代の、最適な勤務シフト作成「勤務シフト作成お助けマン」
TMJ様：オペレーター300人の勤務シフト作成を「最適化」の視点で革新
大阪ガス様：当直シフト編成ツール
社団法人日本将棋連盟様：関東奨励会における対戦表自動作成システム
東日本旅客鉄道株式会社様：JINJRE（勤務）

生産スケジューリング

生産スケジューリングとは、工場などの現場における作業計画を決定する問題のことです。

例えばジョブショップスケジューリングのように資源制約（機械の台数や性能等）を気にしながら、納期遅れを最小にする機械の稼働計画を決定する問題が挙げられます。また、在庫を気にしながら数カ月の生産計画を立てる問題もあります。この場合、製品の生産順序によっては段取り替えが発生して生産能力が落ちることもあるため、順序を決めるスケジューリングの要素を含むこともあります。また、少し特殊な例としては資材切り出し問題もあります。

このように、生産スケジューリングといっても様々な種類の問題があり、生産方法、製造方法に依存して考慮すべき制約条件も異なります。非常に難しい問題であるように聞こえますが Nuorium Optimizer を用いるとご自身の現場特有の制約条件を考慮した計画を立てることができます。

問題解決までのプロセス

以下は問題解決のための一般的な流れになります。

現実の課題の整理
数理モデルの構築
プロトタイプ作成（数理モデルの検証）
システム化

ここではシフトスケジューリングを例にもう少し具体的にご紹介します。なお、株式会社NTTデータ数理システムはこちらのプロセスのどの部分からでもお手伝いさせて頂きますのでご相談ください。

1. 現実の課題の整理

シフト作成の担当者にヒアリングしながら、現状考慮しているルール（制約条件）の洗い出しを行います。例えば、以下の様なルールを洗い出します。

ある時間帯はリーダーが必ずいなければいけない
ある作業の後は45分以上空けなければいけない
一週間で○○時間以上△△時間以下の勤務時間でなければいけない

2. 数理モデルの構築

1.で洗い出したルールを数理モデルの形で表現します。

Nuorium Optimizer を用いる場合は、モデリング言語 SIMPLE、または Pythonインターフェースの PySIMPLE を用いて数理モデルを表現します。「表現した数理モデルから最適解を求めるためにどのような（数学的な）処理をするのか」というアルゴリズムの部分はユーザーの方は意識する必要はありません。従ってユーザーは数理モデルの構築に注力できます。一方で数理モデルの表現方法にはある程度自由度があります。

数理モデルの "変数" を何にするか、"変数" を用いて "制約式" を数式としてどのように表現するかで計算速度に影響もあるため、モデル作成者の腕の見せ所と言えるでしょう。類似問題の研究であったり、自身の実際の経験から適切な数理モデルを構築します。また、シフトスケジューリングに限ってはスタッフの要望によっては「制約条件を満たす計画が存在しない」という状況に良く陥ります。その場合のケアや運用方法などを整理しておくことがプロジェクト成功のカギです。

不安な方、あるいはいろいろと試したけど上手くいかなかったという方は、株式会社NTTデータ数理システムにお任せください。

3. プロトタイプ作成（数理モデルの検証）

1.の作業のみではたいていの場合全てのルールを洗い出すことは不可能です。そもそも人間の頭は非常によくできていて、特に熟練のシフト作成者は、自分でも意識していない様々なルールを考慮しながらシフト作成をしているものです。このため、シフト作成者が最初にプロトタイプで得られたシフトを見た際に、無意識の内に考慮している要素が反映されていないため「何かおかしい」と感じられるケースが多いようです。ここでは、ヒアリング等を通して「何かおかしい」と感じた理由から無意識に考慮していたルールを洗い出すことになります。そして、新たに洗い出されたルールを数理モデルに反映させ、より現実に近いシフトの作成を目指します。

また、計算時間に関する評価もここの段階でしておきましょう。制約を全て満たせているけど計算に1日かかる数理モデルでは運用できないかもしれません。計算速度を改善するためにどういったモデルを構築すべきか2.に戻って考え直します。

このように数理最適化を用いたシステム構築をする際はプロトタイプ作成をいち早く行い、どういった課題が残っているのか、残された課題は技術的あるいは運用面で解決できるのかを見極めることが重要です。ここをクリアした段階で4.に進みます。

4. システム化

Nuorium Optimizer は構築した数理モデルを簡単に実行形式のロードモジュール（exeファイルや DLLファイル）にすることができます。

このロードモジュールは Excel からの呼び出しや現在ご利用のシステムへの組み込み等が可能です。例えば現在担当者の方が利用している Excel があれば、そこに「シフト自動作成ボタン」を1個追加することで、これまでの運用とほぼ変わらない状態で自動化することができます。

おわりに

本記事では、数理最適化という技術でシフトや生産計画のスケジュールを行う方法についてご紹介しました。数理最適化についてさらに詳しく知りたいという方は、下記のコンテンツもぜひご覧ください。

スケジューリングの具体的な課題をお持ちの方は、ぜひNTTデータ数理システムにご相談ください。

数理最適化、AI活用などのご相談はこちら

監修：株式会社NTTデータ数理システム機械学習、統計解析、数理計画、シミュレーションなどの数理科学を背景とした技術を活用し、業種・テーマを問わず幅広く仕事をしています。
http://www.msi.co.jp NTTデータ数理システムができること