(57)【要約】【課題】計画作成装置において、従来に比べて少ないリソースで計画を作成し、且つ条件の変更に対して柔軟に対応することを課題とする。【解決手段】計画作成装置によって計画を作成するにあたって、計画を部分計画に分割して所定の順序で作成することとし、部分計画の作成にあたって考慮すべき複数の制約を種類毎に各次元に割り当てた多次元配列を生成し、多次元配列において制約を満たす位置に所定のフラグを記録することで部分計画を作成し、一の部分計画の作成に関連して派生し他の部分計画に対する制約となる派生制約を抽出し、後から作成される部分計画の作成を行う場合に、先に作成された部分計画に関連して派生した派生制約を満たすよう部分計画を作成することとした。【選択図】図３
2010218045.tif 000002
【特許請求の範囲】
【請求項１】
記憶装置に接続され、
作成される計画を構成する複数の部分計画毎に、部分計画の作成にあたって考慮すべき複数の制約が、制約の種類毎に各次元に割り当てられた多次元配列を、前記記憶装置上に生成する多次元配列生成手段と、
前記部分計画に係る多次元配列において、各次元に割り当てられた制約を満たす位置を探索する探索手段と、
前記探索手段によって探索された位置に所定のフラグを記録することで、前記部分計画を作成するフラグ記録手段と、
一の部分計画の作成に関連して派生し、他の部分計画に対する前記制約となる派生制約を抽出する制約抽出手段と、を備え、
前記複数の部分計画は、所定の順序で作成され、
前記探索手段は、前記所定の順序においてより後に作成される部分計画に係る探索を行う場合に、前記多次元配列において、該部分計画に関して予め設定されている初期制約、および該部分計画より先に作成される部分計画に関連して派生した前記派生制約を満たす位置を探索する、
計画作成装置。
【請求項２】
前記複数の制約は、前記部分計画の作成にあたって考慮すべき複数の条件を夫々数式化することで作成されたものであり、
前記探索手段は、前記数式化された複数の制約の解を求めることで、前記多次元配列において、各次元に割り当てられた制約を満たす位置を探索する、
請求項１に記載の計画作成装置。
【請求項３】
前記探索手段は、前記部分計画の作成に際して、前記派生制約の解を先行して求める、
請求項２に記載の計画作成装置。
【請求項４】
前記制約抽出手段は、前記一の部分計画の作成において記録されたフラグの位置関係に基づいて、前記他の部分計画の作成にあたって考慮すべき条件を数式化することで前記派生制約を抽出する、
請求項１から３の何れか一項に記載の計画作成装置。
【請求項５】
作成される前記計画は、人員配置スケジュールであり、
前記多次元配列生成手段は、勤務形態に関連する制約が割り当てられる次元と、日時に関連する制約が割り当てられる次元と、要員に関連する制約が割り当てられる次元と、を有する多次元配列を生成する、
請求項１から４の何れか一項に記載の計画作成装置。
【請求項６】
記憶装置に接続されたコンピュータが、
作成される計画を構成する複数の部分計画毎に、部分計画の作成にあたって考慮すべき複数の制約が、制約の種類毎に各次元に割り当てられた多次元配列を、前記記憶装置上に生成する多次元配列生成ステップと、
前記部分計画に係る多次元配列において、各次元に割り当てられた制約を満たす位置を探索する探索ステップと、
前記探索ステップで探索された位置に所定のフラグを記録することで、前記部分計画を作成するフラグ記録ステップと、
一の部分計画の作成に関連して派生し、他の部分計画に対する前記制約となる派生制約を抽出する制約抽出ステップと、を実行し、
前記複数の部分計画は、所定の順序で作成され、
前記探索ステップでは、前記所定の順序においてより後に作成される部分計画に係る探索を行う場合に、前記多次元配列において、該部分計画に関して予め設定されている初期制約、および該部分計画より先に作成される部分計画に関連して派生した前記派生制約を満たす位置が探索される、
計画作成方法。
【請求項７】
記憶装置に接続されたコンピュータを、
作成される計画を構成する複数の部分計画毎に、部分計画の作成にあたって考慮すべき複数の制約が、制約の種類毎に各次元に割り当てられた多次元配列を、前記記憶装置上に生成する多次元配列生成手段と、
前記部分計画に係る多次元配列において、各次元に割り当てられた制約を満たす位置を探索する探索手段と、
前記探索手段によって探索された位置に所定のフラグを記録することで、前記部分計画を作成するフラグ記録手段と、
一の部分計画の作成に関連して派生し、他の部分計画に対する前記制約となる派生制約を抽出する制約抽出手段と、として機能させ、
前記複数の部分計画は、所定の順序で作成され、
前記探索手段は、前記所定の順序においてより後に作成される部分計画に係る探索を行う場合に、前記多次元配列において、該部分計画に関して予め設定されている初期制約、および該部分計画より先に作成される部分計画に関連して派生した前記派生制約を満たす位置を探索する、
計画作成用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計画作成装置、計画作成方法およびプログラムに関する。
【背景技術】
【０００２】
従来、スケジュール等の計画作成を支援するために、与えられた条件を満たすようにスケジュールにスタッフ等を割り当てる技術がある（特許文献１から５を参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００６−２７７０６０号公報
【特許文献２】特開２００６−３３８３９６号公報
【特許文献３】特開２００２−２０３０８５号公報
【特許文献４】特開２００５−８５２０４号公報
【特許文献５】特開２００７−１５６９９０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来、計画業務を支援するために、制約プログラミングを用いた計画作成支援システムが用いられている。このような計画作成支援システムでは、計画が満たすべき複数の条件を、制約プログラミングによって「制約」としてモデル化し、この「制約」を満たす解を、制約に合わない計画を取り除きながら解を探索する（換言すれば、再帰的な探索を行う）制約伝播手法を用いて探索することで、計画を作成する。
【０００５】
しかし、従来の計画作成支援システムでは、全ての条件を満足する計画を一括して導き出すため、計算量が膨大となり、処理時間が長くなる、解が見つからない、条件の変更へ柔軟に対応できない、等の問題がある。
【０００６】
本発明は、上記した問題に鑑み、計画作成装置において、従来に比べて少ないリソースで計画を作成し、且つ条件の変更に対して柔軟に対応することを課題とする。
【課題を解決するための手段】
【０００７】
本発明は、作成される計画を、階層関係を有する複数の部分計画に分け、各部分計画に割り当てられる制約を多次元配列で表現して求解することで、計画作成装置において、従来に比べて少ないリソースで計画を作成し、且つ条件の変更に対して柔軟に対応することを可能にした。
【０００８】
詳細には、本発明は、記憶装置に接続され、作成される計画を構成する複数の部分計画毎に、部分計画の作成にあたって考慮すべき複数の制約が、制約の種類毎に各次元に割り当てられた多次元配列を、前記記憶装置上に生成する多次元配列生成手段と、前記部分計画に係る多次元配列において、各次元に割り当てられた制約を満たす位置を探索する探索手段と、前記探索手段によって探索された位置に所定のフラグを記録することで、前記部分計画を作成するフラグ記録手段と、一の部分計画の作成に関連して派生し、他の部分計画に対する前記制約となる派生制約を抽出する制約抽出手段と、を備え、前記複数の部分計画は、所定の順序で作成され、前記探索手段は、前記所定の順序においてより後に作成される部分計画に係る探索を行う場合に、前記多次元配列において、該部分計画に関して予め設定されている初期制約、および該部分計画より先に作成される部分計画に関連して派生した前記派生制約を満たす位置を探索する、計画作成装置である。
【０００９】
本発明に係る計画作成装置によって作成が支援される計画には、例えば、人員配置スケジュール等があるが、作成される計画は、与えられた条件を満たすように作成されるべき計画であればどのようなものであってもよい。例えば、「列車等のダイヤ」、「宅配便等の集配スケジュール」および「大学等の時間割・教室割スケジュール」等の計画を作成する場合にも、本発明を用いることが出来る。本発明では、このような計画を複数の部分計画で構成されるものとし、部分計画に階層関係を定義して、階層の上位に位置する部分計画から下位に位置する部分計画に向けて、順に部分計画を作成することとしている。本発明では、このような階層構造を用いることで、条件を満たす計画を作成するための計算が極端に複雑化することを避け、大規模な計画の作成においても、少ないリソースで計画作成を完了させることを可能としている。
【００１０】
本発明では、部分計画を作成するにあたって考慮されるべき複数の条件は、夫々「制約」として表現される。そして、計画作成装置は、これら複数の制約を満たすように部分計画を作成する。部分計画の作成に際して、本発明に係る計画作成装置は、上記複数の制約を種類毎に各次元に割り当てた多次元配列を生成する。そして、本発明に係る探索手段は、多次元配列において、各次元に割り当てられた制約を満たす位置を探索する。
【００１１】
ここで、前記複数の制約は、前記部分計画の作成にあたって考慮すべき複数の条件を夫々数式化することで作成されたものであり、前記探索手段は、前記数式化された複数の制約の解を求めることで、前記多次元配列において、各次元に割り当てられた制約を満たす位置を探索してもよい。
【００１２】
なお、多次元配列における位置とは、例えば、記憶装置上に生成された多次元配列に含まれる変数記録領域である。探索手段によって複数の制約を満たす位置が探索されると、フラグ記録手段は、この位置にフラグを記録する（例えば、変数記録領域に所定の値を書き込む）。全ての制約を満たすように探索およびフラグ記録が完了すると、部分計画の作成が完了する。
【００１３】
ここで、本発明に係る部分計画は、上述の通り階層関係を有しており、各部分計画の作成に際して考慮される制約には、初期制約と派生制約とが含まれる。派生制約は、一の部分計画の作成に関連して派生する、階層構造において下位に位置する他の部分計画に対する制約である。また、初期制約は、派生制約以外の制約であり、例えば、前記探索手段による探索の対象となる部分計画において、他の部分計画とは関係なく設定されている制約である。
【００１４】
即ち、本発明に係る計画作成装置は、上位階層の部分計画から順に作成していくにあたって、上位の部分計画が作成された際に、この部分計画の作成結果および計画作成上の他の条件との関係で矛盾が生じないように、下位階層の部分計画に割り当てられる派生制約を抽出する。このため、部分計画の階層関係は、より強い条件（換言すると、計画作成にあたって遵守されるべき優先度が高い条件）が割り当てられた部分計画がより上位の階層となるように、定められることが好ましい。
【００１５】
なお、本発明において、前記制約抽出手段は、前記一の部分計画の作成において記録されたフラグの位置関係に基づいて、前記他の部分計画の作成にあたって考慮すべき条件を数式化することで前記派生制約を抽出してもよい。
【００１６】
本発明に係る計画作成装置によれば、計画の全体を構成する複数の部分計画が夫々独立して作成され、下位の階層は自身の初期制約の他に、上位の階層からの派生制約を受けるため、数学的な処理およびシステム構成が簡素化される。また、計画に課される制約（条
件）の重要度を考慮した階層分けが可能であり、現場の実態に応じて部分計画の分割基準および階層順序を変更することも可能である。
【００１７】
なお、派生制約は、既に作成された部分計画に基づいて派生するものである。このため、一般に、派生制約の方が初期制約に比べてより限定的な条件を表現したものであることが多い。このため、本発明において、前記探索手段は、前記部分計画の作成に際して、前記派生制約の解を先行して求めるものであってもよい。即ち、より限定的な（解が見つかり難い）制約から先に求解し、より限定的でない（解が見つかり易い）制約を後から求解することで、全ての制約を満たす部分計画が作成される確率を向上させようというものである。
【００１８】
なお、本発明において、作成される前記計画が、人員配置スケジュールである場合、前記多次元配列生成手段は、勤務形態に関連する制約が割り当てられる次元と、日時に関連する制約が割り当てられる次元と、要員に関連する制約が割り当てられる次元と、を有する３次元配列を生成してもよい。人員配置スケジュールを作成する場合、多次元配列を構成する各次元に、勤務形態に関連する制約と、日時に関連する制約と、要員に関連する制約と、を割り当てることで、異なる部分計画に係る多次元配列においても、各次元に割り当てられる制約種別を共通化させることが出来る。このようにすることで、上位階層において派生した制約を下位階層に適用することが容易となる。
【００１９】
また、本発明は、計画作成方法、計画作成用プログラム、およびこの計画作成用プログラムが記録されたコンピュータ読み取り可能な記録媒体の発明としても把握することが可能である。
【発明の効果】
【００２０】
本発明によれば、計画作成装置において、従来に比べて少ないリソースで計画を作成し、且つ条件の変更に対して柔軟に対応することが可能となる。
【図面の簡単な説明】
【００２１】
【図１】実施形態に係るスケジューリングシステムの構成の概略を示す図である。
【図２】実施形態において、結果表示装置のディスプレイに表示される画面（インタフェース）の遷移を示す図である。
【図３】実施形態において、作成されるスケジュールを構成する部分スケジュールの、階層構造を示す図である。
【図４】実施形態における部分スケジュールを３次元配列モデルで表現した場合の一例を示す図である。
【図５】実施形態における、スケジュール作成処理の全体の流れを示すフローチャートである。
【図６】実施形態において、作成された「全ての対象日における宿直勤務」の部分スケジュールから抽出された派生制約を用いて、「平日におけるチーム別勤務」の部分スケジュールを作成する方法を示す概念図である。
【図７】実施形態において、派生制約伝播装置によって派生制約が伝播し、伝播した制約に従って部分スケジュールが作成される様子を示す図である。
【発明を実施するための形態】
【００２２】
以下、本発明に係る計画作成装置の実施の形態について、図面に基づいて説明する。大規模なコールセンターでは、年間総コール数は１２００万本にのぼり、その応答には最大で約２０００名のオペレータが必要となる。そして、オペレータの勤務形態には、通常勤務の他に、シフト勤務、休日勤務、宿直勤務（夜勤）等の形態があり、その他にも有給休暇や指定休日、休日出勤の回数制限があり、また、一日の勤務時間内にも１時間の昼休み
の他１時間あたり１０分間の休憩が義務付けられている等、多岐に渡る制約がある。
【００２３】
より詳細には、宿直勤務は、所謂夜勤であるため、２４時間体制のコールセンターでは、全ての曜日において宿直勤務を割り当てる必要がある。なお、宿直勤務に割り当てられる要員の単位は、個人である。また、本実施形態に係るコールセンターでは、平日の日勤（夜勤以外の時間帯）を、チーム別勤務で割り当てている。例えば、本実施形態では、平日日勤にシフトＡ、Ｂ、Ｃがあり、これら３つのシフトの夫々に対して、チーム１、２、３の何れかが割り当てられる。なお、宿直勤務に割り当てられる個人は、平日日勤のチームの何れかに所属していることがある。また、本実施形態に係るコールセンターでは、日曜祝日の日勤（夜間以外の時間帯）を、個人単位で割り当てている。このため、コールセンターにおける人員配置スケジュールの計画には、人手による場合には多大な労力が必要となり、また、従来の計画作成支援システムを用いる場合にも、膨大なリソースが必要となる。
【００２４】
このような事情に鑑み、本実施形態では、本発明に係る階層型のスケジューリングシステム１を構築して、コールセンターの勤務スケジューリングにおいて最適な人員配置を行うこととしている。なお、以下に説明する実施形態では、最終的にコールセンターのオペレータについての１月分のスケジュールを作成する場合について説明する。
【００２５】
＜システムの構成＞
図１は、本実施形態に係るスケジューリングシステム１の構成の概略を示す図である。本実施形態に係るスケジューリングシステム１は、カレンダー発生装置１１、チーム編成作成装置１２、制約条件初期値指定装置１３、計算条件パラメータ設定装置１４、宿直勤務割初期制約発生装置１５ａ、チーム別勤務割初期制約発生装置１５ｂ、個人別勤務割初期制約発生装置１５ｃ、個人別休憩割初期制約発生装置１５ｄ、宿直勤務割求解装置１６ａ、チーム別勤務割求解装置１６ｂ、個人別勤務割求解装置１６ｃ、個人別休憩割求解装置１６ｄ、派生制約伝播装置１７ａ−１７ｄ、コールセンター呼量実績データが記録されたデータベース１８、呼量予測装置１９、コールセンター呼量予測データが記録されたデータベース２０、呼量分布曲線発生装置２１、全体結果集計装置２２、および結果表示装置２３を備える。上記各装置は、ネットワークで接続されたコンピュータであり、これらの装置に設けられたプロセッサがメモリ上に展開されたプログラムを実行し、ネットワークを介して互いにデータを送受信しながら必要な処理を行うことで、スケジューリングシステム１によるスケジューリングが行われる。
【００２６】
カレンダー発生装置１１は、スケジューリングに用いられる基本カレンダー設定情報を生成し、スケジューリングシステム１を構成する各装置に供給する。ここで、基本カレンダー設定情報は、平日、土曜、日曜、休日の設定の他、ゴールデンウィークや年末年始、特別休日等の設定情報を含む。
【００２７】
チーム編成作成装置１２は、スケジューリングにおいて配置される要員の基本データ、およびこれら要員を含むチームの基本データを生成し、スケジューリングシステム１を構成する各装置に供給する。ここで、要員の基本データには、要員の氏名、ＩＤ、性別、職位、職種、時給単価、勤務可能形態等が含まれ、チームの基本データには、チーム名、ＩＤ、チーム構成（要員指定）、勤務可能形態等が含まれる。
【００２８】
制約条件初期値指定装置１３は、作成対象のスケジュールを構成する複数の部分スケジュール（子スケジュール）毎に基本制約（時間別の制約、要員別の制約、勤務別の制約）を指定し、また、各部分スケジュールの特別制約（男女、職級、所属チーム、職種等による論理積、論理和、排他的論理和等の制約を含む）を指定する。これらの基本制約および特別制約は、本実施形態では、何れも初期制約として扱われる。また、計算条件パラメー
タ設定装置１４は、例えば、勤務形態に関して、勤務形態名、ＩＤ、勤務開始／終了時間、合計勤務時間、時給割増、対象勤務日（平日、土曜日、日曜・休日）、チーム構成（要員指定）、勤務可能形態、等のパラメータを設定し、また、勤務期間に関して、勤務割の可能な対象期間（年、月、週、日、時間等）、各可能期間の開始時間、等のパラメータを設定する。
【００２９】
ここで、初期制約とは、部分スケジュールを作成するにあたって考慮されるべき複数の条件を数式化して表現した制約のうち、他の部分スケジュールが作成されたことによって後発的に発生する派生制約を除くものである。本実施形態において、部分スケジュールは、該当する部分スケジュールに割り当てられた全ての制約を満たす解を求めることで作成される。
【００３０】
宿直勤務割初期制約発生装置１５ａ、チーム別勤務割初期制約発生装置１５ｂ、個人別勤務割初期制約発生装置１５ｃ、および個人別休憩割初期制約発生装置１５ｄは、作成されるスケジュールを構成する部分スケジュール毎に、適用される初期制約を生成する。本実施形態に係るコールセンターでは、作成されるスケジュールは、コールセンター内の業務形態に応じて、「全ての対象日における宿直勤務」、「平日におけるチーム別勤務」、「日曜祝日における個人別勤務」、および「全ての対象時間における個人別休憩」の４つの部分スケジュールに大別される。宿直勤務割初期制約発生装置１５ａは、「全ての対象日における宿直勤務」の部分スケジュールに適用される初期制約を生成し、チーム別勤務割初期制約発生装置１５ｂは、「平日におけるチーム別勤務」の部分スケジュールに適用される初期制約を生成し、個人別勤務割初期制約発生装置１５ｃは、「日曜祝日における個人別勤務」の部分スケジュールに適用される初期制約を生成し、個人別休憩割初期制約発生装置１５ｄは、「全ての対象時間における個人別休憩」の部分スケジュールに適用される初期制約を生成する。
【００３１】
なお、本実施形態では、スケジューリングの対象となる日時と割り当てられる要員種別との組み合わせに基づいて、コールセンター内の業務形態を分け、分けられた業務形態毎に部分スケジュールを作成することとしているが、スケジュールを部分スケジュールに分割する基準には、実施の形態に応じて適宜最適なものが採用されることが好ましい。
【００３２】
宿直勤務割求解装置１６ａ、チーム別勤務割求解装置１６ｂ、個人別勤務割求解装置１６ｃ、および個人別休憩割求解装置１６ｄ、は、各部分スケジュールに割り当てられた初期制約および派生制約を満たす部分スケジュールを作成する。宿直勤務割求解装置１６ａは、「全ての対象日における宿直勤務」の部分スケジュールを作成し、チーム別勤務割求解装置１６ｂは、「平日におけるチーム別勤務」の部分スケジュールを作成し、個人別勤務割求解装置１６ｃは、「日曜祝日における個人別勤務」の部分スケジュールを作成し、個人別休憩割求解装置１６ｄは、「全ての対象時間における個人別休憩」の部分スケジュールを作成する。
【００３３】
本システムは、各部分スケジュールの問題（複数の条件）に対して制約プログラミングを適用し、該当する部分スケジュールの勤務割求解装置（宿直勤務割求解装置１６ａ、チーム別勤務割求解装置１６ｂ、個人別勤務割求解装置１６ｃ、および個人別休憩割求解装置１６ｄの何れか）によって個別に部分スケジュールを作成する。実際の求解装置１６ａ−１６ｄは、各部分スケジュールに割り当てられた条件を制約プログラミングによって実装する。具体的には、解くべき対象を、「取り得る値の範囲（ドメイン）」を持つ変数の組で、制約（条件）をそれら変数間の関係式で表現する。その上で、この関係式の計算中に明らかになる個々の変数の変化を、制約を介して関係する変数に伝えることで、探索空間を小さくし、解探索の高速化を実現する。
【００３４】
換言すると、本実施形態に示したスケジューリングシステム１では、全体の人員配置スケジュールを部分スケジュールに分割する際に変数を決定し、初期制約発生装置および派生制約伝播装置１７ａ−１７ｃによって、記述された制約を生成し、その後、従来の制約プログラミング技術を用いて、記述された制約を満たす解を探索することにより、最終的な人員配置スケジュールを作成する。
【００３５】
なお、各求解装置１６ａ−１６ｄは、部分スケジュールの探索方法として、順探索、逆探索等から適宜実施の形態に適したものを採用することが好ましい。また、求解方法としても、一つの解だけを求める、Ｎ個の解を求める、最適解を求める等の求解方法から、適宜実施の形態に適したものが採用されることが好ましい。更に、より適した解を求める方法として、コスト最小化、要員負荷平準化、目標応答率最大化等のための目標関数を指定する方法や、分枝限定法、他のヒューリスティック法などの最適求解方法を指定する方法が採用され得る。
【００３６】
派生制約伝播装置１７ａ−１７ｃは、上記した各求解装置１６ａ−１６ｄによって作成された部分スケジュールに従って発生する派生制約を抽出し、部分スケジュールの階層（部分スケジュールの階層構造については後述する）において下位にあたる部分スケジュールを作成する求解装置に派生制約を伝える。派生制約伝播装置１７ａは、宿直勤務割求解装置１６ａによって作成された部分スケジュールに従って発生する派生制約を抽出してチーム別勤務割求解装置１６ｂに送信し、派生制約伝播装置１７ｂは、チーム別勤務割求解装置１６ｂによって作成された部分スケジュールに従って発生する派生制約を抽出して個人別勤務割求解装置１６ｃに送信し、派生制約伝播装置１７ｃは、個人別勤務割求解装置１６ｃによって作成された部分スケジュールに従って発生する派生制約を抽出して個人別休憩割求解装置１６ｄに送信する。このようにして派生制約が伝播することで、各求解装置は、上位階層で発生した派生制約を満たす部分スケジュールを作成すること、換言すると、他の部分スケジュールと矛盾や齟齬のない部分スケジュールを作成することが可能となる。
【００３７】
呼量予測装置１９は、接続されたデータベース１８からコールセンター呼量実績データを受けて、スケジュール作成対象の月における呼量を予測し、曜日別、日付別、および時間帯別の呼量予測結果を含むコールセンター呼量予測データを生成する。呼量の予測に用いられる処理の詳細な説明は省略する。実施にあたっては、従来用いられている呼量予測技術から、実施の形態に適したものが適宜採用されることが好ましい。呼量予測装置１９は、生成したコールセンター呼量予測データを、接続されたデータベース２０に保存させる。
【００３８】
呼量分布曲線発生装置２１は、接続されたデータベース２０から、呼量予測装置１９によって生成されたコールセンター呼量予測データを取得して、呼量分布曲線を生成する。生成された呼量分布曲線は、個人別休憩割求解装置１６ｄに出力されて、「全ての対象時間における個人別休憩」の部分スケジュールの作成に用いられる。即ち、個人別休憩割求解装置１６ｄは、初期制約および派生制約に加えて、呼量分布曲線を考慮することで、各要員の１時間あたり１０分間の休憩スケジュールを作成する。但し、呼量分布曲線は、呼量が比較的多い時間帯に休憩をとる要員の数を所定以下とし、呼量が比較的少ない時間帯に休憩をとる要員の数を所定以上とするような条件を定めた制約として、個人別休憩割求解装置１６ｄに処理されてもよい。
【００３９】
全体結果集計装置２２は、宿直勤務割求解装置１６ａ、チーム別勤務割求解装置１６ｂ、個人別勤務割求解装置１６ｃ、および個人別休憩割求解装置１６ｄの各求解装置によって作成された部分スケジュールを集計し、対象月の、コールセンター全体のスケジュールを作成する。作成された全体のスケジュールは、結果表示装置２３に出力され、結果表示
装置２３によってディスプレイ表示や帳票出力（印刷出力）されることで、ユーザに通知される。なお、出力のためのディスプレイやプリンタ等については、図示を省略する。また、作成された全体のスケジュールは、特に次回の勤務割のために必要な情報として、記憶装置に保存される。
【００４０】
また、全体結果集計装置２２は、指定された条件（制約）と最終結果の確認、作成された部分スケジュールを修正する場合、修正した部分スケジュールの他の部分スケジュールへの影響の確認、および影響がある場合の、求解装置１６ａ−１６ｄに対する再計算の指示（何れの階層から再計算するかの情報提供）、を行うことで、最終結果の確認を行い、各階層を協調させる。
【００４１】
なお、結果表示装置２３は、ディスプレイの他にキーボードやマウス等の入力装置（図示は省略する）を備えることで、ユーザに対してシステム管理機能を提供してもよい。システム管理機能としては、例えば、権限設定機能（作成ユーザ、承認ユーザ、閲覧ユーザ）、ログインＩＤとパスワードの設定機能、作成ユーザ／承認ユーザ／閲覧ユーザ別の権限管理機能、利用履歴管理機能（必要なログの記録、検索等）、期間管理機能（ツールの対応可能期間−開始日付と終了日付）等がある。図２は、本実施形態において、結果表示装置２３のディスプレイに表示される画面（インタフェース）の遷移を示す図である。
【００４２】
＜部分スケジュールの階層構造＞
図３は、本実施形態において、作成されるスケジュールを構成する部分スケジュールの、階層構造を示す図である。本実施形態に係るスケジューリングシステム１では、全体のスケジュールを構成する複数の部分スケジュールを階層構造に当てはめ、上位の階層から順に部分スケジュールを作成していくことで、全体のスケジューリング問題を求解する。
【００４３】
本実施形態では、「全ての対象日における宿直勤務」の部分スケジュールを第一の階層とし、「平日におけるチーム別勤務」の部分スケジュールを第二の階層とし、「日曜祝日における個人別勤務」の部分スケジュールを第三の階層とし、「全ての対象時間における個人別休憩」の部分スケジュールを第四の階層としている。また、第一の階層が最も上位の階層であり、以下、第二の階層、第三の階層、第四の階層、の順に下位の階層となる。部分スケジュールは、上位の階層から順に作成されるため、本実施形態では、「全ての対象日における宿直勤務」の部分スケジュール、「平日におけるチーム別勤務」の部分スケジュール、「日曜祝日における個人別勤務」の部分スケジュール、「全ての対象時間における個人別休憩」の部分スケジュールの順に作成される。
【００４４】
各部分スケジュールは、「オペレータに課せられる条件」、「勤務希望」、「必要な人員」等の複数の条件を夫々数式化した複数の「制約」として表現し、全ての制約を満たす解を求めることで、作成される。なお、本実施形態で用いられる制約には、全体のスケジュール作成を開始する時点において予め設定される初期制約の他に、他の部分スケジュールが作成されたことで、作成された部分スケジュールの内容に従って派生する派生制約がある。
【００４５】
スケジュール全体が対象としているコールセンターは一つのコールセンターであり、各部分スケジュールにおいて割り当てられる要員についても、複数の異なる部分スケジュールにおいて割り当ての対象となる個人がいる等の理由で、部分スケジュール間で連関している。このため、全体のスケジュールを部分スケジュールに分割した場合、部分スケジュール間で調整を行う必要が発生する。
【００４６】
本実施形態では、部分スケジュールを、処理順序を定めるための階層に割り当て、上位の階層に属する部分スケジュール（先にスケジュールが作成される部分スケジュール）か
ら、より下位の階層に属する部分スケジュール（後からスケジュールが作成される部分スケジュール）に対して、上位階層から派生した制約を付加することで、このような部分スケジュール間で必要となる調整を行う。例えば、「全ての対象日における宿直勤務」の部分スケジュールが作成されると、作成された内容（個別の要員の割り当て結果等）に応じて、より下位階層に属する「平日におけるチーム別勤務」の部分スケジュールの作成において考慮すべき派生制約が生成され、「平日におけるチーム別勤務」の部分スケジュールの作成の際に考慮すべき制約となる。
【００４７】
＜部分スケジュールを表現する３次元モデル＞
本実施形態に係るスケジューリングシステム１では、各部分スケジュールの作成のために、３次元配列モデル（実際には、メモリ上に確保された３次元配列の変数領域）が生成される。
【００４８】
図４は、本実施形態における部分スケジュールを３次元配列モデルで表現した場合の一例を示す図である。図４に示した「平日におけるチーム別勤務」の部分スケジュールでは、「日時別」の次元において、スケジューリング対象となる月の平日の日付が表され、「要員別」の次元において、スケジューリング対象となるチーム１−３が表され、「勤務別」の次元において、スケジューリング対象となるシフトＡ−Ｃが表される。
【００４９】
３次元配列は、「日時別」を表す次元、「要員別」を表す次元、および「勤務別」を表す次元を有する。部分スケジュールに割り当てられた制約は、種類別にこれらの各次元に対する制約となり、スケジューリングシステム１は、この３次元配列モデル内に、部分スケジュールに割り当てられた制約を満たすセル（３次元配列中の変数）を求め、求められたセルにフラグ（具体的には、値「１」）を記録することで、スケジュールを作成する。即ち、本実施形態において、フラグが記録されたセルは、人員が配置されたスケジュール枠を示す。なお、人員が配置されないスケジュール枠を表すセル（３次元配列中の変数）には、値「０」が記録される。
【００５０】
なお、３次元配列モデルは、本実施形態におけるスケジュールを構成する４つの部分スケジュールの夫々について生成されるが、これら複数の３次元配列モデルの各次元に割り当てられる制約の種別は、異なる部分スケジュールにおいても同一（日時別、要員別、勤務別）である。このようにすることで、上位階層において派生した制約を下位階層に適用することが容易となる。換言すれば、ある次元に関連して派生した制約は、下位階層においても同じ次元への制約となるため、上位から与えられた派生制約を下位の形式に変換する手間がかからないか、少なくて済む。
【００５１】
＜処理の流れ＞
図５は、本実施形態における、スケジュール作成処理の全体の流れを示すフローチャートである。本フローチャートに示された処理は、ユーザが、所定の入力装置（例えば、結果表示装置２３）を介して、スケジュール作成対象の月指定、初期制約として設定される個別の条件指定を入力して、スケジュール作成開始の指示を入力したことを契機として開始される。なお、本フローチャートに示された処理の詳細な内容および順序は一例であり、処理の詳細および順序は実施の形態に応じて適宜最適なものが採用されることが好ましい。
【００５２】
ステップＳ１０１およびステップＳ１０２では、「全ての対象日における宿直勤務」の部分スケジュールが作成され、派生制約が抽出される。宿直勤務割求解装置１６ａは、宿直勤務割初期制約発生装置１５ａによって生成された初期制約を受けて、この初期制約を満たす部分スケジュール（宿直勤務割結果）を作成し、作成した部分スケジュールを全体結果集計装置２２に対して出力する（ステップＳ１０１）。そして、派生制約伝播装置１
７ａは、作成された部分スケジュールに基づいて派生制約を抽出し、チーム別勤務割求解装置１６ｂに対して出力する（ステップＳ１０２）。その後、処理はステップＳ１０３へ進む。
【００５３】
ステップＳ１０３およびステップＳ１０４では、「平日におけるチーム別勤務」の部分スケジュールが作成され、派生制約が抽出される。チーム別勤務割求解装置１６ｂは、チーム別勤務割初期制約発生装置１５ｂによって生成された初期制約、および派生制約伝播装置１７ａによって抽出された派生制約を受けて、この初期制約および派生制約を満たす部分スケジュール（チーム別勤務割結果）を作成し、作成した部分スケジュールを全体結果集計装置２２に対して出力する（ステップＳ１０３）。そして、派生制約伝播装置１７ｂは、作成された部分スケジュールに基づいて派生制約を抽出し、上位階層から引き受けた他の派生制約と共に個人別勤務割求解装置１６ｃに対して出力する（ステップＳ１０４）。その後、処理はステップＳ１０５へ進む。
【００５４】
ステップＳ１０５およびステップＳ１０６では、「日曜祝日における個人別勤務」の部分スケジュールが作成され、派生制約が抽出される。個人別勤務割求解装置１６ｃは、個人別勤務割初期制約発生装置１５ｃによって生成された初期制約、および派生制約伝播装置１７ｂによって抽出された派生制約を受けて、この初期制約および派生制約を満たす部分スケジュール（個人別勤務割結果）を作成し、作成した部分スケジュールを全体結果集計装置２２に対して出力する（ステップＳ１０５）。そして、派生制約伝播装置１７ｃは、作成された部分スケジュールに基づいて派生制約を抽出し、上位階層から引き受けた他の派生制約と共に個人別休憩割求解装置１６ｄに対して出力する（ステップＳ１０６）。その後、処理はステップＳ１０７へ進む。
【００５５】
ステップＳ１０７では、「全ての対象時間における個人別休憩」の部分スケジュールが作成される。個人別休憩割求解装置１６ｄは、個人別休憩割初期制約発生装置１５ｄによって生成された初期制約、および派生制約伝播装置１７ｃによって抽出された派生制約を受けて、この初期制約および派生制約を満たす部分スケジュール（個人別休憩割結果）を作成し、作成した部分スケジュールを全体結果集計装置２２に対して出力する。その後、処理はステップＳ１０８へ進む。
【００５６】
ステップＳ１０８では、全体スケジュールが作成、出力される。全体結果集計装置２２は、ステップＳ１０７までに受け付けた部分スケジュールを集計して全体のスケジュールを作成し、結果表示装置２３は、作成された全体スケジュールを出力する。その後、本フローチャートに示された処理は終了する。
【００５７】
＜派生制約の伝播の具体例＞
図６は、本実施形態において、作成された「全ての対象日における宿直勤務」の部分スケジュールから抽出された派生制約を用いて、「平日におけるチーム別勤務」の部分スケジュールを作成する方法を示す概念図である。以下、図６を用いて、「平日におけるチーム別勤務」の部分スケジュールの作成を実例に、３次元配列を用いた具体的なスケジュール作成の方法について説明する。
【００５８】
第二の階層（「平日におけるチーム別勤務」の部分スケジュール）は、３次元配列の縦、横および奥行に係る各次元について、以下の表１に示す制約が割り当てられている。この部分スケジューリング問題は、３次元配列の中の各セルにフラグを示す所定の値を記録することによって解決される。なお、図中では、値１が代入されることで記録されるフラグを黒いボールで表す。
【００５９】
各次元の制約種別／取り扱う対象
【表１】
2010218045.tif 000003
【００６０】
「平日におけるチーム別勤務」の部分スケジュールに対する初期制約としては、例えば、「各チームが各平日のシフトＡ、Ｂ、Ｃ勤務の１勤務のみ担当する」という初期制約や、「各平日の休日明けの平日に対し必ずＢ勤務を１チームより担当する」という初期制約、「各平日の休日明け以外の平日に対し必ずＣ勤務を１チームより担当する」という初期制約、「各チームの一ヶ月内のＢ勤務は一回以内とする」という初期制約、「各チームが各平日にＡ勤務以外の勤務は２日以上連続しない」という初期制約がある。
【００６１】
ここで、「各チームが各平日のシフトＡ、Ｂ、Ｃ勤務の１勤務のみ担当する」という初期制約は、勤務別の軸方向（図中の縦方向）に並んだセルの値の合計（縦に並んだセル内の黒いボールの総数）が１となることを示す数式で表現される。また、「各チームの一ヶ月内のＢ勤務は一回以内とする」という初期制約は、日時別の軸方向（図中の横方向）に並んだセルの値の合計（横に並んだセル内の黒いボールの総数）が１以下となることを示す数式で表現される。また、「各平日の休日明け以外の平日に対し必ずＣ勤務を１チームより担当する」という初期制約は、休日明け以外の平日において、要員別の軸方向（図中の奥行方向）に並んだセルの値の合計（奥行方向に並んだセル内の黒いボールの総数）が１となることを示す数式で表現される。
【００６２】
「平日におけるチーム別勤務」の部分スケジュールに対する派生制約としては、例えば、「第一の階層のスケジューリング結果から、個人ＰがＮの日に宿直を担当したら、この個人Ｐの所属するチームＴについては、その日（Ｎ）、その前日（Ｎ−１）と次の日（Ｎ＋１）にシフトＡ勤務指定とする」という派生制約がある。図６には、「全ての対象日における宿直勤務」の部分スケジュールを作成する第一の階層において個人Ｐの宿直が決定したことにより、上記説明したような派生制約が伝播し、「平日におけるチーム別勤務」の部分スケジュールを作成する第二の階層において、個人Ｐが属するチームが、個人Ｐの宿直当日とその前後の日においてシフトＡとなるスケジュールが作成されたこと（換言すると、Ｎ、Ｎ−１、Ｎ＋１の日において、個人Ｐが属するチーム且つシフトＡに該当するセルにフラグが記録されたこと）が示されている。
【００６３】
また、図７は、本実施形態において、派生制約伝播装置１７ａによって第一の階層から第二の階層へ派生制約が伝播し、伝播した制約に従って第二の階層に係る部分スケジュールが作成される様子を示す図である。なお、ここでは、平日の１０日間において、３チームで昼間のシフトＡ、Ｂ、Ｃを担当する場合について説明する。
【００６４】
チーム別勤務割求解装置１６ｂは、派生制約伝播装置１７ａによって伝播された派生制約と、第二の階層の部分スケジュールに割り当てられた初期制約と、を同時に考慮して、図７に黒いボールで示された位置を、派生制約等を満たすセルとして索出し、このセルに所定のフラグを記録する。派生制約に係るスケジュールが作成されると、チーム別勤務割求解装置１６ｂは、初期制約のみに基づいて制約を満たすセルを索出し、このセルに所定
のフラグ（ここでは、白いボールで示される）を記録する。
【００６５】
表２は、このようにして作成された、「平日におけるチーム別勤務」の部分スケジュールを示す表である。なお、下記の結果では、太枠Ａ、Ｂ、Ｃは上位層からの派生制約および初期制約に基づいて得られた解であり、それ以外は初期制約のみに基づいてチーム別勤務割求解装置１６ｂにより得られた解である。
【００６６】
平日勤務チーム割結果例
【表２】
2010218045.tif 000004
【００６７】
＜制約のモデリングの具体例＞
以下に、本実施形態に係るスケジューリングシステム１で用いられる制約のモデリングについて説明する。制約は作成対象となるスケジュールやセンターによって異なり、また、制約形態も様々であるため、ここではごく一部の制約を例にモデリングの方法を示す。
【００６８】
はじめに、本実施形態における制約モデリングに用いられる記号を示す。
Ｍ＝｛１，  ２，  ．．．，  ｉ，  ．．．，  ｍ｝は、要員番号の集合である。例えば、ｉは要員ｉを指す。
Ｎ＝｛１，  ２，  ．．．，  ｊ，  ．．．，  ｔ｝は、スケジューリング対象日の集合である。例えば、ｊは対象日ｊを指す。
Ｗ＝｛ｓｈｉｆｔ１，  ｓｈｉｆｔ２，  ．．．，  ｓｈｉｆｔｋ，  ．．．，  ｓｈｉｆｔｗ｝は、勤務シフトの集合である。例えば、シフト集合は（日勤、夜勤、休み）の場合は、ｓｈｉｆｔ１＝日勤、ｓｈｉｆｔ２＝夜勤、ｓｈｉｆｔ３＝休み、となる。
Ｒ＝｛ｒ１，  ｒ２，  ．．．，  ｒｇ｝は、ある指標（例えばスキル）またはニーズ（例えばチーム編成）に分けられたグループの集合である。例えば、ｒ２は第２グループを指す。
ａｒ，ｊ，ｋ：ｒ∈Ｒ，  ｊ∈Ｎ、ｋ∈Ｗは、ｊ日のシフトｋに対するグループｒからの人数の下限値である。即ち、ｊ日のシフトｋに対しては、グループｒからａｒ，ｊ，ｋ以上の要員を配置しなければならない。
ｂｒ，ｊ，ｋ：ｒ∈Ｒ，  ｊ∈Ｎ、ｋ∈Ｗは、ｊ日のシフトｋに対するグループｒからの人数の上限値である。即ち、ｊ日のシフトｋに対しては、グループｒからの要員配置をｂｒ，ｊ，ｋ以下にしなければならない。
Ｐｉは、要員ｉのｎ日分（スケジュール対象期間分）の実行可能シフトパターン（スケジュール割り当て）の集合である。なお、各パターンはδｉ，ｑ，ｊ，ｋで表現される。δｉ，ｑ，ｊ，ｋ＝１は、パターンｑのｊ日にシフトｋが割り当てられていることを示し、δｉ，ｑ，ｊ，ｋ＝０は、パターンｑのｊ日にシフトｋが割り当てられていないことを示す。
ｘｉ，ｊ，ｋは、各要員（ｉ）の各日（ｊ）の勤務シフト（ｋ）を表現する意思決定変数である。ｘｉ，ｊ，ｋ＝１は当該するスケジュール（要員ｉが日ｊの勤務シフトｋ）に割り当てられる。ｘｉ，ｊ，ｋ＝０は当該するスケジュール（要員ｉが日ｊの勤務シフトｋ
）に割り当てられないことになる。
【００６９】
続いて、本実施形態に係るスケジューリングシステム１において用いられる制約の例を示す。以下に示す制約の例には、上述した記号が用いられている。
【００７０】
数１は、各グループ各日各シフトの人数の上下限を示す制約である。ここで、ＧＳはグループＳの集合を示し、ａｊ，ｋ，ｓはグループＳに対してｊ日ｋシフトの必要な人数下限を示す。なお、人数下限制限なしの場合はａｊ，ｋ，ｓ＝０とする。また、ｂｊ，ｋ，ｓはグループＳに対してｊ日ｋシフトの必要な人数上限である。人数上限制限なしの場合はｂｊ，ｋ，ｓ＝∞とする。
【００７１】
【数１】
2010218045.tif 000005
【００７２】
また、数２は、１要員が１日に最大１つのシフトしか割り当てられないことを示す制約である。
【００７３】
【数２】
2010218045.tif 000006
【００７４】
また、数３は、要員シフト指定を示す制約である。数３において、Ｆ１＝｛（ｉ，  ｊ，  ｋ）｝は、要員ｉのｊ日のシフトｋに固定することを示す。また、Ｆ１＝｛（ｉ，  ｊ，  ｋ）｝は予め指定する必要がある。
【００７５】
【数３】
2010218045.tif 000007
【００７６】
また、数４は、要員シフト不可を示す制約である。数４において、Ｆ０＝｛（ｉ，  ｊ，  ｋ）｝は、要員ｉのｊ日のシフトｋが不可であることを示す。また、Ｆ０＝｛（ｉ，
ｊ，  ｋ）｝は予め指定する必要がある。
【００７７】
【数４】
2010218045.tif 000008
【００７８】
また、数５は、シフト勤務連続禁止を示す制約である。
【００７９】
【数５】
2010218045.tif 000009
ただし、
2010218045.tif 000010
2010218045.tif 000011
【００８０】
また、数６は、シフト３勤務が月間１回以内ことを示す制約である。但し、１∈Ｍ（全ての要員に対して）であり、ｋ∈ｓｈｉｆｔ３（ｓｈｉｆｔ３はシフト３勤務を示す）である。
【００８１】
【数６】
2010218045.tif 000012
【００８２】
また、数７は、シフト３の勤務者が、明けの翌日が休日となるように指定する制約である。なお、ここでｋ１はシフト３勤務を示し、ｋ２はシフトの明け休みを示し、ｋ３はシフトの休日を示す。
【００８３】
【数７】
2010218045.tif 000013
【００８４】
また、月単位で土曜日の３勤務を連続しないようにする制約において、例えば、要員Ｓが７月に土曜日の３勤務を担当した場合に、翌月（８月）の土曜日３勤務を担当させない制約は、以下の数８で表わせる。但し、ｉ∈Ｓ（Ｓは先月で土曜日の３勤務を担当した要員の集合）であり、ｊ∈Ｎ（Ｎはスケジューリング対象日の集合）であり、ｋ＝ｓｈｉｆｔｓ（ｓｈｉｆｔｓは土曜日のシフト３を示す）である。
【００８５】
【数８】
2010218045.tif 000014
【００８６】
また、数９は、土曜日、日曜日および祝日の日数分は休む制約、換言すると、休日に１日出勤したら、指定休日を必ず１日入れる制約を表す。但し、Ｂはスケジューリング対象日集合の中の土曜日、日曜日、祝日の子集合であり、Ａはスケジューリング対象日集合の中の土曜日、日曜日、祝日以外の日の子集合である。即ち、Ｂ＝Ｎ−Ａである。
【００８７】
【数９】
2010218045.tif 000015
【００８８】
また、数１０は、指定勤務が最大で月３回までとなる制約を示す。但し、ｉ∈Ｍ（全ての要員に対して）であり、ｊ∈Ｎ（Ｎはスケジューリング対象日の集合）であり、ｋ＝ｓｈｉｆｔｓ（ｓｈｉｆｔｓは指定勤務を示す）である。
【００８９】
【数１０】
2010218045.tif 000016
【００９０】
＜効果＞
本実施形態に係るスケジューリングシステム１によれば、各階層が夫々独立したスケジュール問題として扱われ、下位の階層は自身の初期制約の他に、上位の階層からの派生制約を受けるため、数学的な処理およびシステム構成が簡素化される。また、人手による勤務割作成業務の実体を考慮した階層分けが可能であり、現場の実態に応じて部分スケジュールの分割基準および階層順序を変更することも可能である。以上のような特徴により、本実施形態に係るスケジューリングシステム１によれば、処理の高速化、条件（制約）の変更に対する柔軟な対応が可能となる。
【符号の説明】
【００９１】
１  スケジューリングシステム
１５ａ、１５ｂ、１５ｃ、１５ｄ・・・初期制約発生装置
１６ａ、１６ｂ、１６ｃ、１６ｄ・・・求解装置
１７ａ、１７ｂ、１７ｃ・・・派生制約伝播装置
【図１】
2010218045.tif 000017
【図２】
2010218045.tif 000018
【図３】
2010218045.tif 000019
【図４】
2010218045.tif 000020
【図５】
2010218045.tif 000021
【図６】
2010218045.tif 000022
【図７】
2010218045.tif 000023