(57)【要約】【課題】変更前後で切替えコストの変化量を小さくしつつ、作業計画に新たな作業を追加する。【解決手段】本発明の一態様としての作業計画スケジューリング装置は、作業計画と、切替えコスト情報と、追加作業の情報と、を読み込む読込部と、前記作業主体に割り当てられた作業間の区間を区間頂点とし、入力頂点、区間頂点、出口頂点間を辺で張り、前記辺に重み変数を設定してグラフネットワークを作成するグラフネットワーク作成部と、前記グラフネットワークの前記入口頂点から出口頂点へ至る各経路のそれぞれの辺重み総和に基づいて経路を選択する経路選択部と、前記選択された経路に従って前記作業主体間で作業を交換し、当該交換によって創出した区間に前記追加作業を割り当てる作業計画作成部と、を備える。【選択図】図１
2015060566.tif 000002
【特許請求の範囲】
【請求項１】
複数の作業を複数の作業主体に割り当てた作業計画と、前記作業主体が作業を切り換える場合に切り替え前後の作業に応じて発生する切替えコストを定めた切替えコスト情報と、開始時刻と処理時間または終了時刻とが定められた追加作業の情報と、を読み込む読込部と、
前記作業主体に割り当てられた作業間の時間の区間を区間頂点とし、作業主体間で前記区間が時間的に交わりをもちかつ、一方の区間の終了時刻が他方の終了時刻より早いとき、前記一方の区間の区間頂点から他方の区間の区間頂点へ辺を張り、前記追加作業の開始時刻が前記区間に含まれる場合に入口頂点から当該区間の区間頂点へ辺を張り、前記追加作業の終了時刻を含む区間か、あるいはそれより後の区間の区間頂点から、出口頂点へ辺を張り、
前記辺の始点側の区間の前後の作業間と、前記辺の終点側の区間の前後の作業間と、前記終点側の区間の前の作業と前記始点側の区間の後の作業間との切替えコストに基づく辺重みを前記辺に設定し、前記入口頂点から前記区間頂点に張った辺に対し、前記区間頂点に対応する区間の前後の作業間および前記区間の前の作業と前記追加作業間との切替コストに基づく辺重みを設定し、前記区間頂点から前記出口頂点に張った辺に対して、前記区間頂点の区間の前後の作業間および前記追加作業と前記区間の後の作業間との切替えコストに基づく辺重みを設定することにより、
グラフネットワークを作成するグラフネットワーク作成部と、
前記グラフネットワークの前記入口頂点から出口頂点へ至る各経路のそれぞれの辺重み総和に基づいて経路を選択する経路選択部と、
前記選択された経路における前記入口頂点の次の区間頂点に対応する区間より後のすべての作業を、前記次の区間頂点より後の区間頂点を辿るごとに、辿った区間頂点に対応する区間より後のすべての作業と交換することを繰り返すことで、前記入口頂点の次の区間頂点に対応する区間に属する作業主体に前記追加作業の処理時間以上の長さの区間を生成し、前記区間に前記追加作業を割り当てるように前記作業計画を更新する作業計画作成部と、
を備えた作業計画スケジューリング装置。
【請求項２】
前記経路選択部は、前記辺重み総和が最小または閾値以下の経路を選択する
請求項２に記載の作業計画スケジューリング装置。
【請求項３】
前記開始時刻は複数の候補が存在し、
前記グラフネットワーク作成部は、前記追加作業の処理を開始させる区間の候補ごとに、前記グラフネットワークを作成し、前記候補となる区間は、前記開始時刻の候補の少なくともいずれかを含み、前記グラフネットワークごとに前記入口頂点からは前記候補となる区間の区間頂点にのみ辺を設定し、
前記経路選択部は、前記グラフネットワークごとに前記経路を選択し、各グラフネットワークから選択した経路の中から１つの経路を決定する
請求項１または２に記載の作業計画スケジューリング装置。
【請求項４】
前記経路選択部は、前記切替えコストの総和の比較、前記候補の開始時刻の比較の少なくとも一方に基づいて前記経路を決定する
請求項３に記載の作業計画スケジューリング装置。
【請求項５】
複数の作業を複数の作業主体に割り当てた作業計画と、前記作業主体が作業を切り換える場合に切り替え前後の作業に応じて発生する切替えコストを定めた切替えコスト情報と、開始時刻と処理時間または終了時刻とが定められた追加作業の情報と、を読み込む読込ステップと、
前記作業主体に割り当てられた作業間の時間の区間を区間頂点とし、作業主体間で前記区間が時間的に交わりをもちかつ、一方の区間の終了時刻が他方の終了時刻より早いとき、前記一方の区間の区間頂点から他方の区間の区間頂点へ辺を張り、前記追加作業の開始時刻が前記区間に含まれる場合に入口頂点から当該区間の区間頂点へ辺を張り、前記追加作業の終了時刻を含む区間か、あるいはそれより後の区間の区間頂点から、出口頂点へ辺を張り、
前記辺の始点側の区間の前後の作業間と、前記辺の終点側の区間の前後の作業間と、前記終点側の区間の前の作業と前記始点側の区間の後の作業間との切替えコストに基づく辺重みを前記辺に設定し、前記入口頂点から前記区間頂点に張った辺に対し、前記区間頂点に対応する区間の前後の作業間および前記区間の前の作業と前記追加作業間との切替コストに基づく辺重みを設定し、前記区間頂点から前記出口頂点に張った辺に対して、前記区間頂点の区間の前後の作業間および前記追加作業と前記区間の後の作業間との切替えコストに基づく辺重みを設定することにより、
グラフネットワークを作成するグラフネットワーク作成ステップと、
前記グラフネットワークの前記入口頂点から出口頂点へ至る各経路のそれぞれの辺重み総和に基づいて経路を選択する経路選択ステップと、
前記選択された経路における前記入口頂点の次の区間頂点に対応する区間より後のすべての作業を、前記次の区間頂点より後の区間頂点を辿るごとに、辿った区間頂点に対応する区間より後のすべての作業と交換することを繰り返すことで、前記入口頂点の次の区間頂点に対応する区間に属する作業主体に前記追加作業の処理時間以上の長さの区間を生成し、前記区間に前記追加作業を割り当てるように前記作業計画を更新する作業計画作成ステップと、
をコンピュータが実行する作業計画スケジューリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、工場や配送、サービス提供などにおける、作業計画スケジューリング装置およびその方法に関する。
【背景技術】
【０００２】
作業数の多い作業計画のスケジューリングは、スケジューリングするのにかけてよい計算時間の制約から、いわゆる貪欲算法を利用して行われていた。たとえば、納期の厳しいもの順などの単純な指標で作業を取り出し、既に割り当たっている作業を避けながら、最も早く作業を終了できる作業主体に割り付けることによってスケジューリングを行っていた。
【０００３】
一方、スケジュールの性能評価としては、納期の遵守、全体における作業間の切換えコストの最小化、作業主体の稼働率（作業の密度）の最大化、作業工期（Turn Around Time）の最小化など、複数の指標を同時によくすることが求めらてきた。
【０００４】
しかし、上記貪欲算法程度の算法では、これらの指標を十分考慮して良くすることは困難である。たとえば納期の厳しいもの順に作業を作業主体に割り付けていくとき、一度割り付けた作業を変更しない方針を取ると、作業主体の中に、作業しない時間がまだら模様のように残ってしまい、作業主体の稼働率を上げられない。これから割り付ける作業を、既に割り付けた他の作業の後にしか割り付けられないということになれば、不必要な作業遅れが発生する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開2002−157012号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の実施形態は、切替えコスト総和の変動量（増加量）を小さくしつつ、作業計画に新たな作業を追加することを可能にした作業計画スケジューリング装置およびその方法を提供する。
【課題を解決するための手段】
【０００７】
本発明の一態様としての作業計画スケジューリング装置は、読込部と、グラフネットワーク作成部と、経路選択部と、作業計画作成部を備える。
【０００８】
前記読込部は、複数の作業を複数の作業主体に割り当てた作業計画と、前記作業主体が作業を切り換える場合に切り替え前後の作業に応じて発生する切替えコストを定めた切替えコスト情報と、開始時刻と処理時間または終了時刻とが定められた追加作業の情報と、を読み込む。
【０００９】
前記グラフネットワーク作成部は、前記作業主体に割り当てられた作業間の時間の区間を区間頂点とし、作業主体間で前記区間が時間的に交わりをもちかつ、一方の区間の終了時刻が他方の終了時刻より早いとき、前記一方の区間の区間頂点から他方の区間の区間頂点へ辺を張り、前記追加作業の開始時刻が前記区間に含まれる場合に入口頂点から当該区間の区間頂点へ辺を張り、前記追加作業の終了時刻を含む区間か、あるいはそれより後の区間の区間頂点から、出口頂点へ辺を張り、
前記辺の始点側の区間の前後の作業間と、前記辺の終点側の区間の前後の作業間と、前記終点側の区間の前の作業と前記始点側の区間の後の作業間との切替えコストに基づく辺重みを前記辺に設定し、前記入口頂点から前記区間頂点に張った辺に対し、前記区間頂点に対応する区間の前後の作業間および前記区間の前の作業と前記追加作業間との切替コストに基づく辺重みを設定し、前記区間頂点から前記出口頂点に張った辺に対して、前記区間頂点の区間の前後の作業間および前記追加作業と前記区間の後の作業間との切替えコストに基づく辺重みを設定することにより、グラフネットワークを作成する。
【００１０】
前記経路選択部は、前記グラフネットワークの前記入口頂点から出口頂点へ至る各経路のそれぞれの辺重み総和に基づいて経路を選択する。
【００１１】
前記作業計画作成部は、前記選択された経路における前記入口頂点の次の区間頂点に対応する区間より後のすべての作業を、前記次の区間頂点より後の区間頂点を辿るごとに、辿った区間頂点に対応する区間より後のすべての作業と交換することを繰り返すことで、前記入口頂点の次の区間頂点に対応する区間に属する作業主体に前記追加作業の処理時間以上の長さの区間を生成し、前記区間に前記追加作業を割り当てるように前記作業計画を更新する。
【図面の簡単な説明】
【００１２】
【図１】第1の実施形態に係る作業計画スケジューリング装置のブロック図である。
【図２】第1の実施形態に係るデータ格納部の例を示す図である。
【図３】第1の実施形態に係るグラフネットワークの構成要素を示す図である。
【図４】第1の実施形態に係る作業計画の例を示す図である。
【図５】第1の実施形態に係るグラフネットワークの例を示す図である。
【図６】第1の実施形態に係る作業計画作成部の動作の説明図。
【図７】第1の実施形態に係る動作のフローチャートである。
【図８】第2の実施形態に係る作業計画スケジューリング装置のブロック図である。
【図９】第2の実施形態に係るデータ格納部の例を示す図である。
【図１０】第2の実施形態に係る作業計画の例を示す図である。
【図１１】第2の実施形態に係るグラフネットワークの例を示す図である。
【図１２】第2の実施形態に係る動作のフローチャートである。
【図１３】第3の実施形態の説明図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照しながら、本発明の実施形態について説明する。
【００１４】
（第1の実施形態）
本実施形態は、作業計画のスケジューリングとして、工場の生産計画スケジュールを作成する例で説明する。この場合、「作業主体」は装置であり、「作業」はロットなどの、作業を分割せずに装置へ割り当てたい単位とする。「作業」は、以下、Workと呼ぶことにする。装置はWorkを同時に1個しか処理できないものとする。装置は複数台存在するものとする。
【００１５】
図1は、本発明の実施形態に係る作業計画スケジューリング装置のブロック図である。
【００１６】
図1の作業計画スケジューリング装置は、データ格納部1と、作業抽出部2と、グラフネットワーク作成部3と、経路選択部4と、作業計画作成部6と、作業計画記憶部7と、出力部8を備える。
【００１７】
データ格納部1は、装置台数、作業リスト、切替えコスト表を記憶している。図2にデータ格納部1の例を示す。装置台数は、作業を処理出来る装置の台数であり、図示の例では3台である。作業リストは、作業計画の対象となるWorkのリストである。各Workの処理開始時刻および処理終了時刻が定まっている。Work w1〜w6まではすでに作業計画が作成済みであり、この作成済みの作業計画にWork wを追加する状況を想定する。割り当て済みのWorkには割り当て済みのフラグを付けてもよい。図示のWork wは、任意の1つの未割当のWorkを示したものである。Work wは、処理開始時刻に作業を開始して、処理終了時刻に終了する必要がある。各装置は同じ性能を有し、各装置はwを処理開始時刻から処理開始すれば、図示の処理終了時刻に終了することができる。すなわち、各装置は、それぞれwを時間（処理終了時刻−処理開始時刻）で処理可能である。切替えコストは、Workを切り換えるのに要するコストである。wiからwjへの切換えコストをc(wi, wj)と記述する。ある装置がWork w1を処理した後、次にw2を処理する場合は、図示のw1からw2への切り換えコストc(w1, w2)が1かかり、w1をw6に切り換える場合のコストc(w1, w6)は30である。またw1をwに切り換える場合のコストc(w1, w)は0である。コストとは、一例として、費用または時間等に換算できる値である。図示のφ（空集合）とは、Workがないことを示す。
【００１８】
作業計画記憶部7は、完成した作業計画または作成途中の作業計画を記憶している。作成途中の作業計画とは、まだ割り当てていない作業が残っている状態の計画であり、完成した作業計画は、すべての作業を割り当てた状態の作業計画である。作業計画は、すでに割り当たっているWorkの処理開始時刻、処理終了時刻および割当て先の装置の情報を含んでいる。
【００１９】
装置m1, m2, m3があり、Work w1, w2, w3, w4, w5, w6を割り当てた状態の作業計画の例を図4に示す。図4の作業計画は作成途中の作業計画である。すでに割り当たっているWorkw1〜w6の処理開始時刻、処理終了時刻および割当て先の装置の情報が含まれる。本実施形態ではこの作業計画に、新しくWork w（図2参照）を割り当てる場合を想定する。
【００２０】
作業抽出部2は、データ格納部1から、次に割り当てるべきWork（追加作業）を何らかの方法で選ぶ。以後の説明では、この選ばれたWorkをwと呼ぶ。前述したように、データ格納部1では、wに関して、処理開始時刻と処理終了時刻を保持している。処理開始時刻と処理終了時刻の間でwを処理できる装置を見つけて、割り当てなければならない。
【００２１】
グラフネットワーク作成部3が、Work wの情報と、作業計画記憶部7に格納されている既存の作業計画と、データ格納部1に格納されている切替えコスト表を読み込み、グラフネットワークを作成する。グラフネットワーク作成部3は、これらのデータを読み込む読込部を備える。図5に、図4の作業計画と、図2のWork wおよび切替えコスト表から作成されたグラフネットワークの例を示す。
【００２２】
グラフネットワークは、図3に示すように、頂点集合と、辺集合と、辺重み関数の値（辺重み）を含む。なお、頂点集合と、辺集合のみからなるものも、グラフネットワークと呼ぶことがある。
【００２３】
頂点集合は、既存の作業計画におけるWork間の区間に対応する頂点（区間頂点と呼ぶ）、および、区間頂点とは異なる特別な入口頂点aと出口頂点bとを含む。
【００２４】
区間頂点viに対応する区間riと、区間頂点vjに対応する区間rj同士が、区間として交わりを持ち、かつriの終了時刻がrjの終了時刻より小さいという条件（区間条件）が満たされるとき、viからvjへ辺を張る。
【００２５】
区間riとrjとが区間として交わりを持つとは、［riの終了時刻≧rjの開始時刻］かつ［riの開始時刻≦rjの終了時刻］を満たすことである。
【００２６】
図4に示した作業計画の例では、区間頂点v1に対応する区間r1と、区間頂点v2に対応する区間r2同士が、区間として交わりを持ち、かつr1の終了時刻がr2の終了時刻より小さいため、v1からv2へ辺を張る。
【００２７】
入口頂点aから、割り当て対象となるwの処理開始時刻が含まれる区間に対応する区間頂点に対して辺を張る。図4の例では、aからv1とv2にそれぞれ辺を張る。
【００２８】
また、割り当て対象となるwの処理終了時刻を含むか、あるいはそれ以降の区間に対応する区間頂点から、出口頂点へ辺を張る。図4の例では、v3、v4、v5、v6それぞれからbへ辺を張る。
【００２９】
以上のようにして、区間条件を満たす区間同士に張った辺、入口頂点から張った辺、出口条件へ張った辺の集合が、辺集合である。
【００３０】
各頂点を設定し、頂点間に辺を張ったグラフネットワークの各辺に重みを設定する。辺重みの設定について説明する前に、このグラフネットワークの意味を簡単に説明する。グラフネットワークには入口頂点から出口頂点までの経路が0個以上あり得る。各経路は、Workを割り当てる空き時間を創出するための装置間の作業の交換（空き時間の交換）手順に相当する。1つの経路の入口頂点の次の頂点に対応する区間より後の作業を、それより後の頂点を辿るごとに、辿った頂点の区間より後のすべての作業と交換することを出口頂点に至るまで繰り返すと、Workを当該入口頂点の次の頂点に対応する区間を有する装置にWorkを割り当て可能な時間の区間が創出されるため、Workを当該区間に割り当て、作業計画を更新する。経路が0個の場合は、Workの割り当ては不可能であることを意味する。
【００３１】
辺重みは、辺重み関数に従って計算する。辺重み関数は事前に与えておく。辺重みは、切替えコストを利用して算出する。
【００３２】
区間頂点v1からv2への辺を例にとって辺重みを説明する。v1からv2への辺の辺重みの値を、辺重み関数により、2c(w3, w2)−c(w1, w2)−c(w3, w4)と定義する。図2の切替えコスト表の値を利用して、2×2−1−1＝2と求める。つまり、辺の始点側の区間頂点の区間の前後の作業間(w1, w2)と、辺の終点側の区間の前後の作業間(w3, w4)と、終点側の区間の前の作業と始点側の区間の後の作業間(w3, w2)との切替えコストに基づく辺重みを辺に設定する。
【００３３】
v1からv2への辺は、v1よりも後ろのWorkすべて（つまりw2から後ろのWorkすべて）と、v2よりも後ろのWorkすべて（つまり、w4から後ろのWorkすべて）とを交換することを意味する。このような交換を行った場合を想定した交換前後の切替えコストの変動に基づく値が辺重みである。交換前の切替えコストc(w1,w2)、c(w3,w4)が存在し、切替え後は、c(w3,w2)と、c(w1,w4)が存在し得るが、v1からv2の辺を辿る場合は、後述のように、その前に、入口頂点aからv1に辿ることとなり、これはv1の区間内の時間からwを割り当てる場合を意味することから、c(w1,w4)は交換後では発生しない。このため、交換後の評価では、c(w1,w4)を対象としていない。よって交換前後の切替えコスト変動を、辺重みとして、2c(w3, w2)−c(w1, w2)−c(w3, w4)と与える。
【００３４】
パラメータα（≠0）、k を変数として、v1からv2への辺の辺重みの値はα[2c(w3, w2)−(2−k) c(w1, w2)−k c(w3, w4)]とする自由度がある。本例は、パラメータαを1、kを1にした場合に相当する。あるいは、パラメータαを1／2、k＝1として、c(w3, w2)−c(w1, w2)/2−c(w3, w4)/2として評価することもできる。
【００３５】
他の区間頂点間の辺についても同様にして、辺重みを計算する。たとえばv2からv3への辺の辺重みは、2c(w5,w4)-c(w3,w4)-(w5,w6)となる（α＝1、k＝1）。あるいはパラメータαを1／2、k＝1として、c(w5,w4)- c(w3,w4)/2-(w5,w6)/2としてもよい。
【００３６】
また、入口頂点aから張った辺の重みを求める。ここでは入口頂点aと区間頂点v1を例に取る。aからv1への辺の辺重みの値を、辺重み関数により、2c(w1, w)−c(w1, w2)とする。図2の切替えコスト表を利用して、2×0−1＝−1と求める。つまり、入口頂点aから区間頂点v1に張った辺に対し、区間頂点v1に対応する区間の前後の作業間(w1, w2)と、当該区間の前の作業と追加作業との間（w1,w）の切替コストに基づく辺重みを設定する。
【００３７】
入口頂点aからv1に辿ることは、上述したようにwをv1の区間内の時間から割り当てることになり、変更前はc(w1,w2)、変更後はc(w1,w)、c(w,w2)の存在が考えられるが、c(w,w2)は、w2の後の交換により、存在しないかもしれない。このため、c(w,w2)は対象としない。よって交換前後の切替えコスト変動を評価するため辺重みを、2c(w1, w)−c(w1, w2)とする。
【００３８】
入口頂点から張る辺についても、区間頂点間に張る辺と同様に、パラメータα（≠0）、k を変数として、aからv1への辺の辺重みの値をα[2c(w1, w)−k c(w1, w2)]とする自由度がある。本例は、パラメータαを1、kを1にした場合に相当する。あるいは、パラメータαを1／2、k＝1として、c(w1, w)−c(w1, w2)/2として評価することもできる。
【００３９】
ここで、α＝1／2、k＝1の場合で考えたとき、v1からv2の辺重み計算でも、−c(w1, w2)/2が辺重みに含まれるから、−c(w1, w2)/2が重複して現れることになり、これらを足すと、−c(w1, w2)となる。仮にwを装置m1に割り当てると、c(w1,w2)は発生しないことから、この辺を通る経路で交換作業を行った場合、更新前後での作業計画の切替えコスト変動を評価する場合、−c(w1, w2)の項が出てくる。本重み関数では、この−c(w1, w2)を2つの辺（a→v1と、v1→v2）で分担していることになる。
【００４０】
また、出口頂点bへ張った辺の重みも求める。ここでは区間頂点v3と出口頂点bを例に取る。v3からbへの辺の辺重みの値を、2c(w, w6)−c(w5, w6)とする。図2の切替えコスト表を利用して、2×10−5＝15と求める。区間頂点v3から出口頂点bに張った辺に対して、区間頂点v3の区間の前後の作業間(w5, w6)と、追加作業と当該区間の後の作業間（w, w6）との切替えコストに基づく辺重みを設定する。
【００４１】
出口頂点へ張る辺についても、区間頂点間に張る辺と同様に、パラメータα（≠0）、k を変数として、v3からbへの辺の辺重みの値をα[2c(w, w6)−(2−k) c(w5, w6)]とする自由度がある。本例は、パラメータαを1、kを1にした場合に相当する。あるいは、パラメータαを1／2、k＝1として、c(w, w6)−c(w5, w6)/2として評価することもできる。
【００４２】
なお、パラメータαを1／2、k＝1で考えたとき、−c(w5, w6)/2は、v2からv3の辺の辺重みでも出てくるから、−c(w5, w6)/2が重複して現れることになり、これらを足すと−c(w5, w6)となる。つまり、−c(w5, w6)を2つの辺で分担していることになる（w5からw6の切替えコストは、この経路での交換後の作業計画では発生しない。）。
【００４３】
経路選択部4が、入口頂点から出口頂点に至る、辺重みの総和が最小の最短路を一つ求める。最短路を求める方法は、グラフ・アルゴリズム分野で幅広く研究されており、それらを用いればよい（伊理ほか：演習グラフ理論、コロナ社、1983年 p.88〜96）。最も単純には、入口頂点から出口頂点に至るまでの全ての経路パターンを列挙し、各経路パターンでそれぞれ辺重みの総和を計算し、辺重みの総和が最小の経路パターンを最短路として求めればよい。図5の例では、（a, v1, v2, v3, b）という頂点列が求まる。辺重みの総和が最小の経路が複数あるときは、任意の方法で一つ選択すればよい。変形例として、辺重みの総和が最小のものではなく、閾値以下の経路を選択してもよい。経路数が多い場合などは、閾値以下の経路が見つかった時点で処理を打ち切ることで、処理時間を短縮できる利点がある。
【００４４】
作業計画作成部6が、求まった最短路を元に、すでに割り当たっているWorkを装置間で移動して、wを装置に割り当てる。その方法を例を用いて説明する。
【００４５】
（a, v1, v2, v3, b）という頂点列の最短路が求まった場合、wを割り当てる先の装置は、v1の属する装置m1である。これは、入口頂点の次の区間頂点がv1であるためである。この後、w1の後ろにwが入るだけの空き区間（空き時間）を創出する必要がある。空き区間の創出の仕方は以下のとおりである。
【００４６】
まず、v1の次の区間頂点はv2であるため、v1よりも後ろのWorkすべて（つまりw2から後ろのWorkすべて）と、v2よりも後ろのWorkすべて（つまり、w4から後ろのWorkすべて）とを交換する。このときの状態を図6（a）に示す。これにより、区間v2のうち区間v1の終了時刻よりも後の区間が装置m1に追加の空き区間として創出される。
【００４７】
次に、v2の次の区間頂点はv3である。次も、v2よりも後ろの Workすべてとv3よりも後ろのWorkすべてとを交換した。v2を示す区間が既になくなっていることから、ここで行う操作は、装置m2から装置m1へ移動されたw4から後ろのWorkすべて（つまり、元の状態におけるv2よりも後ろの Workすべて）と、v3よりも後ろの Workすべて（つまり、w6から後ろの Workすべて）とを交換する。このときの状態を図6（b）に示す。つまり、装置m1で先ほど創出された追加の空き区間の終了時刻からv3の終了時刻までの区間が新たに装置m1に対して連続的に追加される。
【００４８】
このように最短路のうち、区間頂点の間の辺に対応する交換作業が終わると、装置m1にwが割り当てられる空き区間が創出される。よって、図6（c）に示すように、この空き区間にwを挿入する。
【００４９】
作業計画記憶部6は、作業計画作成部6によって作成されたこの新しい作業計画の状態を保存する。作業抽出部2で抽出するべきWorkがまだ存在する場合は、作業抽出部2が次のWorkを選択して、上述した処理を行うことで、当該次のWorkを、上記の新しい作業計画に追加する。
【００５０】
作業抽出部2で抽出するべきWorkが存在しなくなった場合は、出力部8は、作業計画記憶部7に記憶されている作業計画を出力する。たとえば、作業計画を表示装置に表示してもよいし、ユーザが所持する端末に有線または無線で送信してもよいし、プリンタで出力してもよい。
【００５１】
図7は、第1の実施形態に係る動作のフローチャートである。
【００５２】
作業抽出部2が、抽出すべき作業（追加作業）が、データ格納部1内の作業リストに残っているかを判断し（S11）、残っていなければ、作業計画記憶部7内の作業計画を出力部8が出力して、本動作を終了する。
【００５３】
作業が残っていれば、作業抽出部2が作業wを1つ抽出し（S12）、グラフネットワーク作成部3が、抽出した作業wの情報と、切替えコスト表と、作業計画記憶部7内に格納されている現状の作業計画に基づき、グラフネットワークを作成する（S13）。経路選択部4は、グラフネットワークから経路を1つ選択する。たとえば辺重みの総和が最も小さい経路、または、当該総和が閾値以下の経路を選択する（S13）。
【００５４】
作業計画作成部6は、経路選択部4で選択された経路に従って、装置間（作業主体間）で作業の割り当てを変更して、作業wを追加するための空き時間（区間）を創出し、当該区間に作業wを割り当てる（S15）。これにより作業計画を更新し、更新後の作業計画（新しい作業計画）を作業計画記憶部7に保存する（S16）。
【００５５】
以上、本発明の実施形態は、空き時間と切換えコストに着目して、グラフネットワーク上の辺の重みを、切換えコストの変化量を元にした値で定めたグラフネットワークを作成し、そのグラフネットワーク上で最短路を見つけて、その最短路に従って、一度決めたスケジュールを（部分的に）変更する。上記で求まった最短路は、切換えコストの変化量が最小になっている（グラフネットワークの作成方法として、辺重み関数の値の設定が技巧的である）。これにより、一度決めたスケジュールを（部分的に）変更して、よりよいスケジュールを立てることが可能になる。つまり、一度割り付けた作業を他の装置に割り付けることでより大きな空き時間を確保して、いま割り付けたい作業を割り付けられることができ、そのとき、他の装置に割り付けることで生じる新たな作業切換えコストの総和が最小にできる。
【００５６】
（第2の実施形態）
図8は、本発明の実施形態に係る作業計画スケジューリング装置のブロック図である。
【００５７】
図8の作業計画スケジューリング装置は、データ格納部1と、作業抽出部2と、グラフネットワーク作成部3と、経路選択部4と、作業計画作成部6と、作業計画記憶部7と、出力部8を備える。経路選択部4は、グラフネットワーク別経路選択部4aと経路決定部5を有する。図1と同等部分の要素には同一の符合を付して、拡張または変更された処理を除き、重複する説明を省略する。以下、第1の実施形態との差分を中心に説明する。
【００５８】
図9にデータ格納部1に格納された情報の例を示す。第1の実施形態と異なり、Work  wに関して、最早可能時刻と処理時間と期日を保持している。本実施形態では、最早可能時刻以降から開始して、処理時間だけの時間がかかる処理を行い、期日までに処理が終了するような装置を見つけて、Work wを割り当てる。なお、期日は守れる限り守るものとする。
【００５９】
図10は、作業計画の例を示す。本実施形態では、図10の作業計画に、新しくWork wを割り当てる場合を例にとって説明する。図10の作業計画では、装置m1, m2, m3があり、Work w1, w2, w3, w4, w5, w6がすでに割り当たっている。
【００６０】
グラフネットワーク作成部3が、Work wの情報と、データ格納部1に格納された切替えコスト表と、作業計画記憶部7に格納されている既存の作業計画から、グラフネットワークを作成する。本実施形態では、第1の実施形態と異なり、期日までに処理が終了するために開始しなければ間に合わなくなる時刻tを求める。最早可能時刻からtまでに処理開始できれば、期日に間に合う。つまり、本実施形態では開始時刻の候補が複数ある。
【００６１】
図10の例では、v1もしくはv2の区間から処理を開始できれば期日に間に合う。なお、処理はできるだけ早く始めたほうが、トラブルなどに対応できるため、区間v1に入れるときには最早可能時刻から、区間v2に入れるときには、v2の開始時刻から処理を開始させる。
【００６２】
すると、v1に入れたときには、v3, v4, v5, v6のいずれかの区間で終了させることができるが、v2の開始時刻から処理を開始したときには、v3の区間では処理を終えられないので、v4, v5, v6のいずれかの区間で終了させなければならない。
【００６３】
これを実現するため、本実施形態では、処理開始させる区間の頂点ごとに、グラフネットワークを作成する。区間v1から処理を開始させるグラフネットワークをG1と名付け、入口頂点をa1、出口頂点をb1と名付ける。同様に、区間v2から処理を開始させるグラフネットワークをG2と名付け、入口頂点をa2、出口頂点をb2と名付ける。図11には、グラフネットワーク作成部3によって作成されたグラフネットワークG1,G2が示される。グラフネットワークG1,G2はそれぞれ完全に別個に作成してもよいし、グラフネットワークG1をコピーし、変更部分のみ修正して、グラフネットワークG2を作成してもい。
【００６４】
グラフネットワークG2を例に取って、入口頂点と区間頂点との間の辺の張り方、区間頂点間の辺の張り方、区間頂点と出口頂点との間の辺の張り方、および辺重みについて説明する。基本的な考え方は第１の実施形態と同様である。
【００６５】
入口頂点a2からは、作業wをv2の区間から開始することから、v2の頂点に対して辺を張る。この辺の辺重みの値は、図11の例では、2c(w3, w)−c(w3, w4)となる。図10の切替えコスト表を利用して、2×5−5＝5と求める。
【００６６】
v2で最も早く開始できる時刻から、wが処理を終了する時刻を求め、その時刻を含むか、あるいはそれ以降の区間に対応する区間頂点から、出口頂点へ辺を張る。図11の例では、v4、v5、v6それぞれからb2へ辺を張る。辺重みの値も定めるが、ここでは区間頂点v4と出口頂点b2を例に取る。v4からb2への辺の辺重みの値を2c(w, φ)−c(w2, φ)とする。ここで、φ（空集合）とは、Workがないことを示す。図9の切替えコスト表を利用して、2×30−30＝30と求める。
【００６７】
なお、区間頂点間の辺の張り方および辺重みの計算は、第１の実施形態と同様である。たとえばv1からv2への辺の辺重みの値を、2c(w3, w2)−c(w1, w2)−c(w3, w4)と定義する。図10の値を利用して、10×2−5−5＝10と求める。
【００６８】
なお、第1の実施形態と同様に、グラフネットワーク作成部3で設定する辺重みは次のような自由度がある。α（≠0）、k を変数として、たとえば、v1からv2への辺の辺重みの値はα[2c(w3, w2)−(2−k) c(w1, w2)−k c(w3, w4)]、a1からv1への辺の辺重みの値をα[2c(w1, w)−k c(w1, w2)]、v3からb1への辺の辺重みの値をα[2c(w, w6)−(2−k) c(w5, w6)]とできる。
【００６９】
グラフネットワーク別経路選択部4aが、それぞれのグラフネットワークに対して、入口頂点から出口頂点に至る、辺重みの総和が最小の最短路を求める。最短路を求める方法は、グラフ・アルゴリズム分野で幅広く研究されており、それらを用いればよい（たとえば、伊理ほか：演習グラフ理論、コロナ社、1983年 p.88〜96）。図11のグラフG2の例では、（a2, v2, v3, v4, b2）という頂点列が求まる。なお入口頂点から出口頂点に至る経路が1つもないときは、wを追加できないことになる。経路決定部5は、各グラフネットワークから求まった最短路から、何らかの基準によって、一つの最短路を決定する。例えば、図11の例では、グラフネットワークG1からは最短路の辺重みの総和が50、グラフネットワークG2からは最短路の辺重みの総和が40、の最短路が求まり、グラフネットワークG2の最短路のほうが切換えコストの総和を抑えたいという目的のためには有利である。一方、処理開始時刻を鑑みると、グラフネットワークG1の最短路のほうが早くから開始できるという点で有利である。ここでどの最短路に決定するかは、ユーザの意思によって、本装置に予め指定しておけばよい。
【００７０】
作業計画作成部6が、経路決定部5が決定した最短路を元に、すでに割り当たっているWorkを装置間で移動して、wを装置に割り当てる。これにより、既存の作業計画を更新する。その方法は、第1の実施形態と同様である。
【００７１】
作業計画記憶部7は、作業計画作成部6により更新された作業計画を保存する。
【００７２】
作業抽出部2で抽出するべきWorkがなくなったら、出力部8は、作業計画記憶部7に記憶されている作業計画を、予め定められた方法で出力する。出力の例は、第1の実施形態と同様である。
【００７３】
図8は、第2の実施形態に係る動作のフローチャートである。
【００７４】
第1の実施形態と同様に、作業抽出部2が、抽出すべき作業（追加作業）が、データ格納部1内の作業リストに残っているかを判断し、残っていなければ、作業計画記憶部7内の作業計画を出力部8が出力して、本動作を終了する。作業が残っていれば、作業抽出部2が作業wを1つ抽出し、グラフネットワーク作成部3が、抽出した作業wの情報と、切替えコスト表と、作業計画記憶部7内に格納されている現状の作業計画に基づき、グラフネットワークを作成する（S21）。
【００７５】
このステップS21では、まず、wを期日までに処理が終了するために開始しなければ間に合わなくなる時刻tを求める。最早可能時刻からtまでに処理開始できれば、期日に間に合う。処理開始可能な区間をすべて特定する。処理開始させる区間の頂点ごとに、グラフネットワークを作成する。処理を開始可能な区間がN個あれば、N個のグラフネットワークG1，G2，・・・，Gnを作成する（S21）。
【００７６】
グラフネットワーク別経路選択部4aは、各グラフネットワークからそれぞれ1つの経路、たとえば最短路を選択する。選択した最短路の集合を集合Hとする（S22）。経路決定部5は、集合Hの中から1つの最短路hを決定する（S23）。作業計画作成部6は、最短路Hに従って装置間で作業の割り当てを変更して空き時間を創出し、創出した空き時間に作業wを割り当てる。これにより作業計画を更新し、更新後の作業計画（新しい作業計画）を作業計画記憶部7に保存する。
【００７７】
以上、本実施形態によれば、作業開始時刻の可能性に応じて複数の最短路を求めて、その中から切換えコストの最小変化量以外の指標に応じて適切な最短路を選択して、スケジュールすることができる。
【００７８】
（第3の実施形態）
本実施形態では、第1の実施形態の具体的な適用例として、配送計画への適用例を示す。つまり、倉庫にあるパッケージ（荷物の集まり）を、倉庫から複数のトラックを用いて配送先へ送る問題に対して、第1の実施形態を適用する。図13に本実施形態を説明するための図を示す。
【００７９】
倉庫には、配送しなければならない荷物が集まっている。近い配送時間帯・近い配送先荷物・同じ温度指定の荷物を集めたパッケージを作成しておく。パッケージ（荷物の集まり）は、配送時に守らなければならない温度設定が「冷蔵」「冷凍」「常温」の3種類あり、トラックは一度には「冷蔵」「冷凍」「常温」のいずれかしか設定することができない。
【００８０】
トラックの設定温度を変更するには、人手などの手間がかかり、「冷蔵→冷凍」「冷蔵→常温」「冷凍→冷蔵」「常温→冷蔵」「冷凍→常温」「常温→冷凍」のそれぞれに対して手間の値が定められている。これを切換えコストと呼ぶ。
【００８１】
また、トラック1台にはパッケージ1個しか詰込めない。パッケージには配送先の情報が紐付いており、配送して倉庫に戻ってくるまでの時間は定められている。
【００８２】
パッケージを配送開始する時刻と、配送終了する時刻が定まっているときに、どのパッケージをどのトラックで配送させるかの課題を解決したい。
【００８３】
このとき、配送を「作業」と、パッケージを「Work」と、装置を「トラック」と読み替え、第1の実施形態における作業抽出部2、グラフネットワーク作成部3、経路選択部4、作業計画作成部6、作業計画記憶部7、出力部8を、上記第1の実施形態の通りに動作させれば、パッケージを配送開始する時刻と、配送終了する時刻が定まっているときに、どのパッケージをどのトラックで配送させるかの課題が解決できる。
【００８４】
なお、各実施形態のスケジューリング装置は、例えば汎用のコンピュータ装置を基本ハードウェアとして用いることでも実現することが可能である。スケジューリング装置内の各処理ブロックは、上記のコンピュータ装置に搭載されたプロセッサにプログラムを実行させることにより実現することができる。このとき、スケジューリング装置は、上記のプログラムをコンピュータ装置にあらかじめインストールすることで実現してもよいし、ＣＤ−ＲＯＭなどの記憶媒体に記憶して、あるいはネットワークを介して上記のプログラムを配布して、このプログラムをコンピュータ装置に適宜インストールすることで実現してもよい。また、スケジューリング装置内の各記憶部または格納部は、上記のコンピュータ装置に内蔵あるいは外付けされたメモリ、ハードディスクもしくはＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＡＭ、ＤＶＤ−Ｒなどの記憶媒体などを適宜利用して実現することができる。
【００８５】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【図１】
2015060566.tif 000003
【図２】
2015060566.tif 000004
【図３】
2015060566.tif 000005
【図４】
2015060566.tif 000006
【図５】
2015060566.tif 000007
【図６】
2015060566.tif 000008
【図７】
2015060566.tif 000009
【図８】
2015060566.tif 000010
【図９】
2015060566.tif 000011
【図１０】
2015060566.tif 000012
【図１１】
2015060566.tif 000013
【図１２】
2015060566.tif 000014
【図１３】
2015060566.tif 000015