JP7486161B2 - 情報処理システム、情報処理方法及びプログラム - Google Patents

Description

本発明は、情報処理システム、情報処理方法及びプログラムに関する。

量子アニーリングは、組合せ最適化処理を高速かつ高精度に実行すると期待されている計算技術として知られている（例えば、特許文献１参照）。

特開２０２０－０４６８０６号公報

しかし、量子アニーリングマシンは、二次関数までの問題までしか扱えないという制限がある。制約条件を適切に利用することにより、非線形変換を含む一般の関数などの複雑なコスト関数を利用することができる可能性があったが、上記の制限で、その可能性の実現性には疑問符が残されていた。

本発明は、上記問題に鑑みてなされたものであり、量子アニーリングマシンを用いた解探索において複雑なコスト関数を利用可能にする情報処理システム、情報処理方法及びプログラムを提供することを目的とする。

本発明の第１の態様に係る情報処理システムは、複数の対象物について、ある対象物の一部もしくは全部を別の順番に挿入する処理、ある対象物の一部もしくは全部を別の対象物の一部もしくは全部と入れ替える処理、対象物を別の対象物と入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する対象物の候補それぞれと、アニーリングマシン用のコスト関数を、アニーリングマシンに入力する手段と、アニーリングマシンがアニーリングマシン用のコスト関数に基づいて決定した、前記対象物の候補それぞれについて処理を実行するか否かの情報を、当該アニーリングマシンから取得する手段と、前記対象物の候補それぞれについて処理を実行するか否かを示す情報に基づいて、目的のコスト関数を決定し、当該目的のコスト関数の値に応じて、対象物の候補それぞれについて処理を実行するか否かを決定する手段と、を備え、前記入力する手段と、前記取得する手段と、前記決定する手段の処理を繰り返す。

この構成によれば、目的のコスト関数とアニーリングマシン用のコスト関数を分けることにより、アニーリングマシン用のコスト関数は二次関数までの利用としつつ、目的のコスト関数を、三次以上の関数など複雑なコスト関数を利用することができる。また、情報処理システムが、制約条件を満たすタイムスロットについて処理を行うようにすることで、アニーリングマシンは制約条件を気にすることがなく処理を実行できる。
できる。

本発明の第２の態様に係る情報処理システムは、第１の態様に係る情報処理システムであって、前記アニーリングマシンに入力する手段は、複数種類の製品について複数の生産ラインで生産する場合に、一つの生産ラインのタイムスロットをカットして別の生産ラインに挿入する処理、一つの生産ラインのある製品のタイムスロットの一部もしくは全部を別の生産ラインのタイムスロットに挿入する処理、一つの生産ラインの製品のタイムスロットの一部もしくは全部を別の生産ラインの製品のタイムスロットの一部もしくは全部と入れ替える処理、一つの生産ラインの各製品のタイムスロットと別の生産ラインの各製品のタイムスロットと入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する対象物の候補それぞれと、アニーリングマシン用のコストを、アニーリングマシンに入力する。

この構成によれば、複数種類の製品について複数の生産ラインで生産する場合の時間スケジュールを、より短時間で決定することができる。

本発明の第３の態様に係る情報処理システムは、第２の態様に係る情報処理システムであって、前記選択された処理の実行の際には、前の工程での処理が終了しているという制約を満たすタイムスロットに対して実行される。

この構成によれば、一つの製品について前の工程が終わってから、次の工程が実施されるという前後関係の制約が保証される。

本発明の第４の態様に係る情報処理システムは、第２または３の態様に係る情報処理システムであって、前記目的のコスト関数には、生産ライン毎の終了時刻の差が小さいほど評価が高くなる項が含まれる。

この構成によれば、生産ライン毎の終了時刻の差を縮めることができる。

本発明の第５の態様に係る情報処理システムは、第１の態様に係る情報処理システムであって、前記アニーリングマシンに入力する手段は、複数の都市について、都市を別の順番に挿入する処理、都市を別の都市と入れ替える処理、都市を別の都市と入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する都市の候補それぞれと、アニーリングマシン用のコスト関数を、アニーリングマシンに入力する。

この構成によれば、巡回セールスマン問題を、より短時間で解くことができる。

本発明の第６の態様に係る情報処理システムは、第１の態様に係る情報処理システムであって、前記アニーリングマシンに入力する手段は、性質の異なる複数の宿泊施設群について、宿泊施設群の一部もしくは全部を別の順番に挿入する処理、ある性質の宿泊施設群の一部もしくは全部を別の性質の宿泊施設群の一部もしくは全部と入れ替える処理、ある性質の宿泊施設群を別の性質の宿泊施設群と入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する宿泊施設の候補それぞれと、アニーリングマシン用のコスト関数を、前記アニーリングマシンに入力する。

この構成によれば、複数の宿泊施設群を混在した状態になるように複数の宿泊施設群の表示順を決定する際に、より短時間で決定することができる。

本発明の第７の態様に係る情報処理システムは、第１から４のいずれかの態様に係る情報処理システムであって、前記決定する手段は、目的のコスト関数が小さくなることを目的としている場合当該コスト関数が低減すれば前記アニーリングマシンの出力を採用し、該コスト関数が低減しなければ前記アニーリングマシンの出力を採用せず、一方、目的のコスト関数が大きくなることを目的としている場合当該コスト関数が増大すれば前記アニーリングマシンの出力を採用し、該コスト関数が増大しなければ前記アニーリングマシンの出力を採用しない。

この構成によれば、アニーリングマシンの出力を採用、不採用を決定することができる。

本発明の第８の態様に係る情報処理方法は、複数の対象物について、ある対象物の一部もしくは全部を別の順番に挿入する処理、ある対象物の一部もしくは全部を別の対象物の一部もしくは全部と入れ替える処理、対象物を別の対象物と入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する対象物の候補それぞれと、アニーリングマシン用のコスト関数を、アニーリングマシンに入力する工程と、アニーリングマシンがアニーリングマシン用のコスト関数に基づいて決定した、前記対象物の候補それぞれについて処理を実行するか否かの情報を、当該アニーリングマシンから取得する工程と、前記対象物の候補それぞれについて処理を実行するか否かを示す情報に基づいて、目的のコスト関数を決定し、当該目的のコスト関数の値に応じて、対象物の候補それぞれについて処理を実行するか否かを決定する工程と、を有し、前記入力する工程と、前記取得する工程と、前記決定する工程の処理を繰り返す情報処理方法である。

この構成によれば、目的のコスト関数とアニーリングマシン用のコスト関数を分けることにより、アニーリングマシン用のコスト関数は二次関数までの利用としつつ、目的のコスト関数を、三次以上の関数など複雑なコストを利用することができる。また、制約条件を満たすタイムスロットについて処理を行うようにすることで、アニーリングマシンは制約条件を気にすることがなく処理を実行できる。

本発明の第９の態様に係るプログラムは、コンピュータを、複数の対象物について、ある対象物の一部もしくは全部を別の順番に挿入する処理、ある対象物の一部もしくは全部を別の対象物の一部もしくは全部と入れ替える処理、対象物を別の対象物と入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する対象物の候補それぞれと、アニーリングマシン用のコスト関数を、アニーリングマシンに入力する手段と、アニーリングマシンがアニーリングマシン用のコスト関数に基づいて決定した、前記対象物の候補それぞれについて処理を実行するか否かの情報を、当該アニーリングマシンから取得する手段と、前記対象物の候補それぞれについて処理を実行するか否かを示す情報に基づいて、目的のコスト関数を決定し、当該目的のコスト関数の値に応じて、対象物の候補それぞれについて処理を実行するか否かを決定する手段と、として機能させるためのプログラムであって、前記入力する手段と、前記取得する手段と、前記決定する手段の処理を繰り返すプログラムである。

この構成によれば、目的のコスト関数とアニーリングマシン用のコスト関数を分けることにより、アニーリングマシン用のコスト関数は二次関数までの利用としつつ、目的のコスト関数を、三次以上の関数など複雑なコスト関数を利用することができる。また、制約条件を満たすタイムスロットについて処理を行うようにすることで、アニーリングマシンは制約条件を気にすることがなく処理を実行できる。

本発明の一態様によれば、目的のコスト関数とアニーリングマシン用のコスト関数を分けることにより、アニーリングマシン用のコスト関数は二次関数までの利用としつつ、目的のコスト関数を、三次以上の関数など複雑なコスト関数を利用することができる。また、制約条件を満たすタイムスロットについて処理を行うようにすることで、アニーリングマシンは制約条件を気にすることがなく処理を実行できる。

第１の実施形態に係る情報処理システムの概略構成図である。 第１の実施形態に係る端末の概略構成図である。 第１の実施形態に係る一つの工程を説明するための模式図である。 一つの生産ラインの最後のタイムスロットをカットして別の生産ラインに挿入する処理を説明するための図である。 一つの生産ラインのある製品のタイムスロットの一部もしくは全部を別の生産ラインのタイムスロットに挿入する処理を説明するための図である。 一つの生産ラインの製品のタイムスロットの一部もしくは全部を別の生産ラインの製品のタイムスロットの一部もしくは全部と入れ替える処理を説明するための図である。 一つの生産ラインの各製品のタイムスロットと別の生産ラインの各製品のタイムスロットと入れ替え及び／または順番の並び替えを説明するための図である。 第１の実施形態に係る処理に流れの一例を示すフローチャートである。 第１の実施形態において、２つの工程を実行した場合の処理結果の一例である。 ２つの工程を実行した場合の目的のコスト関数の時間経過を示すグラフである。 第１の実施形態において、４つの工程を実行した場合の処理結果の一例である。 ４つの工程を実行した場合の目的のコスト関数の時間経過を示すグラフである。 第１の実施形態において、６つの工程を実行した場合の処理結果の一例である。 ６つの工程を実行した場合の目的のコスト関数の時間経過を示すグラフである。 第１の実施形態においてプロセス数と計算時間の関係を示すグラフである。 第２の実施形態において初期状態の巡回路を表す模式図である。 第２の実施形態において計算処理後の巡回路を表す模式図である。 第２の実施形態に係る処理に流れの一例を示すフローチャートである。

以下、各実施形態について、図面を参照しながら説明する。但し、必要以上に詳細な説明は省略する場合がある。例えば、既によく知られた事項の詳細説明や実質的に同一の構成に対する重複説明を省略する場合がある。これは、以下の説明が不必要に冗長になるのを避け、当業者の理解を容易にするためである。

＜第１の実施形態＞
上記、課題に加えて、第１の実施形態では、量子アニーリングマシンは制約条件を持つような組合せ最適化問題を必ずしも適切に解くことができなかったという課題を解決する。

第１の実施形態では、複数種類の製品について複数の生産ラインで生産する場合に、生産スケジュールの最適化を目的とする。第１の実施形態では、工場の複数の製造ラインにおいて、複数の種類の製品それぞれを一つ以上生産することを想定する。また一例として本実施形態の生産には複数の工程があり、前の工程が終わらなければ次の工程に進めないとい制約がある。

図１は、第１の実施形態に係る情報処理システムの概略構成図である。図１に示すように、情報処理システムＳは一例として、デジタルコンピュータの一例である端末１を備える。端末１は、通信回路網ＣＮを介してアニーリングマシン２に接続されており、アニーリングマシン２と通信可能である。ここでは一例として情報処理システムＳは一台の端末１で構成される例を示すが、これに限定されるものではなく、複数の情報処理装置で構成されてもよい。

端末１は、ユーザが使用する端末装置であり、例えば、多機能携帯電話（いわゆるスマートフォン）などの携帯電話、タブレット、ノートパソコン、またはデスクトップパソコンなどである。端末１には例えば、本実施形態に係るプログラムを含むアプリケーションがインストールされており、このアプリケーションを立ち上げ、端末１はユーザの操作に応じて処理を実行する。以下、本実施形態では、端末１は、一例としてデスクトップパソコンであるものとして説明する。

アニーリングマシン２は、量子アニーリングを実行するハードウェアである。アニーリングマシン２は例えば、Ｄ－Ｗａｖｅであるが、これに限ったものではない。

図２は、第１の実施形態に係る端末の概略構成図である。図２に示すように、端末１は例えば、入力インタフェース１１と、通信回路１２と、ストレージ１３と、メモリ１４と、ディスプレイ１５と、プロセッサ１６とを備える。
入力インタフェース１１は、ユーザからの入力を受け付け、受け付けた入力に応じた入力信号をプロセッサ１６へ出力する。
通信回路１２は、通信回路網ＣＮに接続されて、通信回路網ＣＮに接続されているアニーリングマシン２と通信する。この通信は有線であっても無線であってもよい。

ストレージ１３には、プロセッサ１６が読み出して実行するためのアプリケーションのプログラム及び各種のデータが格納されている。このアプリケーションは、サーバもしくはクラウド経由でダウンロードされてインストールされたものであってもよい。
メモリ１４は、データ及びプログラムを一時的に保持する。メモリ１４は、揮発性メモリであり、例えばＲＡＭ（Random Access Memory）である。

プロセッサ１６は、ストレージ１３から本実施形態に係るアプリケーションのプログラムをメモリ１４にロードし、当該プログラムに含まれる一連の命令を実行する。

ディスプレイ１７は、プロセッサ１６の指令に従って情報をディスプレイ１７に表示する。なお、ディスプレイ１７は端末１に外付けではなく、内蔵であってもよい。

図３は、第１の実施形態に係る一つの工程を説明するための模式図である。図３に示すように、一つの工程において、製造ラインが３つあり、図３において製造ライン毎の工程スケジュールが示されている。工程ｐの製造ラインのインデックスｉの作業終了時間ｔ_p,iは、（各製品の処理数×処理時間の総和）＋（各製品間の切り替え時間の総和）である。例えば図３の工程ｐ（＝１）の製造ラインのインデックスｉ＝１の工程時間ｔ_p=1,i=1は、例えば、（製品Ａの処理数１６×処理時間１００＋製品Ｅの処理数３２×処理時間１０００＋製品Ｃの処理数２４×処理時間６００）＋（製品Ａから製品Ｅへの切り替え時間１８０＋製品Ｅから製品Ｃへの切り替え時間２２０）＝４８４００（ｓｅｃ）である。

本実施形態において、目的とするコスト関数Ｈは一例として以下の通りである。

ここで、ｔ_max＝ｍａｘ（ｔ_p,i）、すなわちｔ_maxは工程ｐの製造ラインのインデックスｉの作業終了時間ｔ_p,iの最大値である。ｊは製造ラインのインデックスであり、α、βは、必要に応じて調整する係数である。ここで、コスト関数Ｈが小さくなることを目的としており、第２項は、生産ライン毎の終了時刻の差が小さいほど、コスト関数Ｈが小さくなる。ここでは一例として、生産ライン毎の終了時刻がそろっているほど、全体の工程の終了時間が短くなる経験則があったので、生産ライン毎の終了時刻の差が小さいほど、コスト関数Ｈが小さくなるように第２項が設定されている。すなわち、目的のコスト関数Ｈには一例として、生産ライン毎の終了時刻の差が小さいほど評価が高くなる項が第２項として含まれる。

続いて、本実施形態において繰り返し行われる処理について図４～図７を用いて説明する。図４は、一つの生産ラインの最後のタイムスロットをカットして別の生産ラインに挿入する処理を説明するための図である。図４に示すように、インデックスｉの生産ラインの最後のタイムスロットのうち、インデックスｊの生産ラインの最後のタイムスロットより延長している部分（２Ｃ_p,i,jの時間）を半分にカットして、別のインデックスｊの生産ラインの最後のタイムスロットに付け足す。これにより、インデックスｉの生産ラインの作業終了時間ｔ’_p,i＝ｔ’_p,i－ｃ_p,i,jｑ_p,i,jに短縮され、別のインデックスｊの生産ラインの作業終了時間ｔ’_p,j＝ｔ’_p,j＋ｃ_p,j,iｑ_p,i,jに延長される。このことにより、全体の作業終了時間が短縮される効果がある。

図５は、一つの生産ラインのある製品のタイムスロットの一部もしくは全部を別の生産ラインのタイムスロットに挿入する処理を説明するための図である。図５に示すように、インデックスｉの生産ラインの先頭のタイムスロットを、別のインデックスｊの生産ラインの生産工程の切れ目に挿入する。これにより、インデックスｉの生産ラインの作業終了時間ｔ’_p,i＝ｔ’_p,i－ｃ_p,i,jｑ_p,i,jに短縮され、別のインデックスｊの生産ラインの作業終了時間ｔ’_p,j＝ｔ’_p,j＋ｃ_p,j,iｑ_p,i,jに延長される。

図６は、一つの生産ラインの製品のタイムスロットの一部もしくは全部を別の生産ラインの製品のタイムスロットの一部もしくは全部と入れ替える処理を説明するための図である。図６に示すように、インデックスｉの生産ラインの先頭のタイムスロットと、別のインデックスｊの生産ラインの最後のタイムスロットを入れ替える。これにより例えば、インデックスｉの生産ラインの作業終了時間ｔ’_p,i＝ｔ’_p,i－ｃ_p,i,jｑ_p,i,jに変更され、別のインデックスｊの生産ラインの作業終了時間ｔ’_p,j＝ｔ’_p,j＋ｃ_p,j,iｑ_p,i,jに変更される。ここで、入れ替え前のインデックスｉの生産ラインの先頭のタイムスロットの時間をａ_p,i,j、入れ替え後のインデックスｉの生産ラインの先頭のタイムスロットの時間をｂ_p,i,jとすると、ｃ_p,i,j＝ａ_p,i,j－ｂ_p,i,jである。同様に、入れ替え前のインデックスｊの生産ラインの最後のタイムスロットの時間をａ_p,i,j、入れ替え後のインデックスｊの生産ラインの最後のタイムスロットの時間をｂ_p,i,jとすると、ｃ_p,j,j＝ａ_p,i,j－ｂ_p,i,jである。

図７は、一つの生産ラインの各製品のタイムスロットと別の生産ラインの各製品のタイムスロットと入れ替え及び／または順番の並び替えを説明するための図である。図７に示すように、インデックスｉの生産ラインの最後のタイムスロットと、別のインデックスｊの生産ラインの最後のタイムスロットを入れ替え、その後にインデックスｉの生産ラインの先頭と最後のタイムスロットを入れ替え、別のインデックスｊの生産ラインの先頭と最後のタイムスロットを入れ替える。これにより例えば、インデックスｉの生産ラインの作業終了時間ｔ’_p,i＝ｔ’_p,i－ｃ_p,i,jｑ_p,i,jに変更され、別のインデックスｊの生産ラインの作業終了時間ｔ’_p,j＝ｔ’_p,j＋ｃ_p,j,iｑ_p,i,jに変更される。ここで、入れ替え前のインデックスｉの生産ラインの作業終了時間をａ_p,i,j、入れ替え後のインデックスｉの生産ラインの作業終了時間をｂ_p,i,jとすると、ｃ_p,i,j＝ａ_p,i,j－ｂ_p,i,jである。同様に、入れ替え前のインデックスｊの生産ラインの作業終了時間をａ_p,i,j、入れ替え後のインデックスｊの生産ラインの作業終了時間をｂ_p,i,jとすると、ｃ_p,j,j＝ａ_p,i,j－ｂ_p,i,jである。

続いて、第１の実施形態に係る処理に流れの一例について説明する。図８は、第１の実施形態に係る処理に流れの一例を示すフローチャートである。

（ステップＳ１０）端末１のプロセッサ１６は、アニーリングマシンに入力する手段として機能する。当該アニーリングマシンに入力する手段は、複数種類の製品について複数の生産ラインで生産する場合に、一つの生産ラインの最後のタイムスロットをカットして別の生産ラインに挿入する処理、一つの生産ラインのある製品のタイムスロットの一部もしくは全部を別の生産ラインのタイムスロットに挿入する処理、一つの生産ラインの製品のタイムスロットの一部もしくは全部を別の生産ラインの製品のタイムスロットの一部もしくは全部と入れ替える処理、一つの生産ラインの各製品のタイムスロットと別の生産ラインの各製品のタイムスロットと入れ替え及び／または順番の並び替えのうちの少なくとも一つから選択された処理を実行する対象の候補を一つ以上決定する。

この処理の選択は、予め各処理の順番が決められていてその順番に沿って自動で選択されてもよいし、ランダムであってもよい。

（ステップＳ２０）端末１のプロセッサ１６は、アニーリングマシン用のコスト関数、
選択された処理を実行する対象の候補を、アニーリングマシン２へ送信する。

このように、端末１のプロセッサ１６は、アニーリングマシンに入力する手段として機能する。当該アニーリングマシンに入力する手段は、複数種類の製品について複数の生産ラインで生産する場合に、一つの生産ラインの最後のタイムスロットをカットして別の生産ラインに挿入する処理、一つの生産ラインのある製品のタイムスロットの一部もしくは全部を別の生産ラインのタイムスロットに挿入する処理、一つの生産ラインの製品のタイムスロットの一部もしくは全部を別の生産ラインの製品のタイムスロットの一部もしくは全部と入れ替える処理、一つの生産ラインの各製品のタイムスロットと別の生産ラインの各製品のタイムスロットと入れ替え及び／または順番の並び替えの少なくとも一つから選択された処理を実行する対象物の候補それぞれと、アニーリングマシン用のコスト関数を、アニーリングマシン２に入力する。

本実施形態では、一つの製品について前の工程が終わっていなければ、次の工程が実施できないという制約条件がある。そのため、前記選択された処理の実行の際には、前の工程での処理が終了しているという制約を満たすタイムスロットに対して実行される。これにより、一つの製品について前の工程が終わってから、次の工程が実施されるという前後関係の制約が保証される。この制約条件については、端末１のプロセッサ１６側で考慮することで、アニーリングマシン２では考慮する必要がない。

目的のコスト関数とは、別にアニーリング用のコスト関数が、アニーリングマシンに設定されている。このアニーリング用のコスト関数は、目的のコスト関数が２次関数以下で表される場合には、同じであってもよい。一方、アニーリング用のコスト関数は、目的のコスト関数が３次以上などの非線形関数で表される場合、別のコスト関数が設定されていてもよい。本実施形態では、アニーリング用のコスト関数も、目的のコスト関数の第２項と第３項の和であるものとして説明する。

（ステップＳ３０）アニーリングマシン２は、アニーリングマシン用のコスト関数を用いて、選択された処理を実行する対象の候補それぞれについて、処理を実行するか否かを出力する。

（ステップＳ３０）アニーリングマシン２は、対象の候補それぞれについて処理を実行するか否かを示す情報を端末１へ送信する。

そして端末１のプロセッサ１６は、アニーリングマシン２がアニーリングマシン用のコスト関数に基づいて決定した、前記対象の候補それぞれについて処理を実行するか否かを示す情報を、当該アニーリングマシン２から取得する手段として機能する。

（ステップＳ５０）端末１のプロセッサ１６は、前記対象の候補それぞれについて処理を実行するか否かを示す情報を受信した場合、前記対象の候補それぞれについて処理を実行するか否かを示す情報に基づいて、目的のコスト関数を決定し、当該目的のコスト関数の値に応じて、対象の候補それぞれについて処理を実行するか否かを決定する手段として機能する。

ここで、当該決定する手段は、本実施形態のように、目的のコスト関数が小さくなることを目的としている場合当該コスト関数が低減すれば前記アニーリングマシンの出力を採用し、該コスト関数が低減しなければ前記アニーリングマシンの出力を採用しない。

なお、目的のコスト関数が大きくなることを目的としている場合、当該決定する手段は、当該コスト関数が増大すれば前記アニーリングマシンの出力を採用し、該コスト関数が増大しなければ前記アニーリングマシンの出力を採用しないようにしてもよい。

（ステップＳ６０）端末１のプロセッサ１６は、所定の回数、繰り返したか否か判定し、所定の回数繰り返していない場合、ステップＳ１０に戻って、処理を繰り返す。一方、所定の回数、繰り返した場合、端末１のプロセッサ１６は、本フローチャートの処理を終了する。

図９は、第１の実施形態において、２つの工程を実行した場合の処理結果の一例である。図９に示すように、製造工程において各タイムスロットがほぼ隙間なく埋まり、終了時刻が４１８６０［ｓｅｃ］である。図１０は、２つの工程を実行した場合の目的のコスト関数の時間経過を示すグラフである。１００００ＭＣＳに対して実行時間は４５．９秒であり、５０００ＭＣＳでほぼ極小解に到達している。

図１１は、第１の実施形態において、４つの工程を実行した場合の処理結果の一例である。図１１に示すように、製造工程において各タイムスロットが割り当てられ、終了時刻が５１８８０［ｓｅｃ］である。図１２は、４つの工程を実行した場合の目的のコスト関数の時間経過を示すグラフである。１００００ＭＣＳに対して実行時間は１０１．８６秒である。

図１３は、第１の実施形態において、６つの工程を実行した場合の処理結果の一例である。図１３に示すように、製造工程において各タイムスロットが割り当てられ、終了時刻が６５３８０［ｓｅｃ］である。図１４は、６つの工程を実行した場合の目的のコスト関数の時間経過を示すグラフである。１００００ＭＣＳに対して実行時間は１４８．９２秒である。

図１５は、第１の実施形態においてプロセス数と計算時間の関係を示すグラフである。図１５に示すように、プロセス数の増加に応じて、計算時間が線形に増加する。

以上、第１の実施形態に係る情報処理システムＳは、複数種類の製品について複数の生産ラインで生産する場合に、一つの生産ラインのタイムスロット（例えばある製品の後半のタイムスロット）をカットして別の生産ラインに挿入する処理、一つの生産ラインのある製品のタイムスロットの一部もしくは全部を別の生産ラインのタイムスロットに挿入する処理、一つの生産ラインの製品のタイムスロットの一部もしくは全部を別の生産ラインの製品のタイムスロットの一部もしくは全部と入れ替える処理、一つの生産ラインの各製品のタイムスロットと別の生産ラインの各製品のタイムスロットと入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する対象の候補それぞれと、アニーリングマシン用のコスト関数を、アニーリングマシンに入力する手段を備える。更に情報処理システムＳは、アニーリングマシンがアニーリングマシン用のコスト関数に基づいて決定した、前記対象の候補それぞれについて処理を実行するか否かを示す情報を、当該アニーリングマシンから取得する手段を備える。更に情報処理システムＳは、前記対象の候補それぞれについて処理を実行するか否かを示す情報に基づいて、目的のコスト関数を決定し、当該目的のコスト関数の値に応じて、前記対象の候補それぞれについて処理を実行するか否かを決定する手段を備える。情報処理システムＳは、前記入力する手段と、前記取得する手段と、前記決定する手段の処理を繰り返す。

この構成により、複数種類の製品について複数の生産ラインで生産する場合の時間スケジュールを、より短時間で決定することができる。また、目的のコスト関数とアニーリングマシン用のコスト関数を分けることにより、アニーリングマシン用のコスト関数は二次関数までの利用としつつ、目的のコスト関数を、三次以上の関数など非線形変換を含む一般の関数を利用することができる。また、情報処理システムＳが、制約条件を満たすタイムスロットについて処理を行うようにすることで、アニーリングマシンは制約条件を気にすることがなく処理を実行できる。

なお、第１の実施形態では製造が複数の工程である場合について説明したが、製造が１つの工程であっても同様に適用可能である。

＜第２の実施形態＞
続いて第２の実施形態について説明する。第１の実施形態では、複数種類の製品について複数の生産ラインで生産する場合に、生産スケジュールの最適化を目的とした。第２の実施形態では、巡回セールスマン問題を解くことを目的とする。巡回セールスマン問題は、都市の集合と各２都市間の移動コスト（ここでは例えば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を１回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。

本実施形態では、一例として、０番から２３番までの都市があるものとする。この場合、目的のコスト関数とアニーリング用のコスト関数は同じであり、総移動距離である。第２の実施形態では、第１の実施形態とは制約条件が異なっており、第２の実施形態では
また、特定の都市に特定のタイミングで訪問しなくてはならないという制約条件を付してもよい。この制約条件については、端末１のプロセッサ１６側で考慮することで、アニーリングマシン２では考慮する必要がない。

処理工程としては、端末１のプロセッサ１６は例えば、初期状態の訪問順番に対して、Ｘ番目に訪問する都市とＹ番目に訪問する都市を入れ替えるか否かを０、１で用意しておいて、Ｘ番目に訪問する都市とＹ番目に訪問する都市の入れ替えを採択するかどうかをアニーリングマシンで決定し、端末１のプロセッサ１６は、採択した結果、総移動距離が短くなっていれば採用し、総移動距離が長くなっていれば採用しない。

また、第２の実施形態において、アニーリングマシンに入力する手段は、複数の対象物（ここでは都市）について、ある対象物（ここでは都市）を別の順番に挿入する処理、ある対象物（ここでは都市）を別の対象物（ここでは都市）と入れ替える処理、対象物（ここでは都市）を別の対象物（ここでは都市）と入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する対象物の候補それぞれと、アニーリングマシン用のコスト関数を、アニーリングマシンに入力する。

図１６は、第２の実施形態において初期状態の巡回路を表す模式図である。図１６に示すように、各都市が番号とともに示されており、経路が実線で示されている。初期状態の巡回路はランダムで決定されている。

図１７は、第２の実施形態において計算処理後の巡回路を表す模式図である。図１７に示すように、総移動距離が最短になるように、各都市が実線で結ばれている。

＜カット＆フリップを含めたデジタルコンピュータの処理内容＞
カット＆フリップを含めたデジタルコンピュータの処理内容について、以下、三つの利用例について説明する。

（１）素朴な利用例
巡回セールスマン問題では、訪問都市の番号を１，２，３，４，５と振った時にその番号の順列組み合わせで答えが出る。例えば、「５，２，３，１，４」などが答えとなる。この場合、５，２，３，１，４の順に都市を回ると、総移動距離が最短になることを意味する。ここで「１」、「２」などの１都市をカットしてカットした都市同士を入れ替え（フリップ）てもよいし、「５，２」、「１，４」などの連続する複数の都市をカットして、カットした複数都市同士を入れ替え（フリップ）してもよい。このカットは、偶数個用意する。すなわち入れ替える都市候補は複数個用意する。フリップは、これらのカットした都市同士を入れ替えることである。

「５，２，３，１，４」の場合、カット候補（すなわち入れ替える都市候補）として、「２」，「１」とした場合（但し、入れ替える都市候補同士は隣接せず離れていることが条件）、アニーリングマシンの出力値０の場合、「２」，「１」のまま（結果は「５，２，３，１，４」のなる）であることを表し、アニーリングマシンの出力値１の場合、「１」，「２」に変える（結果は「５，１，３，２，４」のなる）ことを表す。
デジタルコンピュータの一例である端末１では、このカットする候補（すなわち入れ替える都市候補）を提案する処理を実行する。そして、端末１は、このカットする候補（すなわち入れ替える都市の候補）を入れ替えた場合の、目的のコスト関数の増減の比較を行う。

上記の手続きで提案した入れ替える都市の候補、増減を基に、アニーリングマシンに対してコスト関数を準備する。具体的には、ｉ番目の入れ替える都市候補のペアを、入れ替える（フリップする）とコストが上がるか下がるかを示す数値ΔＥｉに対してΔＥｉ×Σｉというコスト関数を用意する。このΣｉが０と１をとる二値の変数である。ペアの数分この項を足し上げて、その総和を最小化する問題をアニーリングマシンで解く。巡回セールスマン問題の場合は、各ペアｉごとに独立に決定される項であるので、各ペアｉについてΔＥｉが負であればΣｉは１とするのがコスト関数を最小化する解となる。

（２）少し高度な利用例
上記の利用例では独立にカットする候補（すなわち入れ替える都市候補）を考慮して、採用するかどうかを判定することでも処理を行うことができる。
しかしながら、本手法では、より柔軟に、入れ替える都市候補に対してコスト関数をデザインする任意性があり、連続するカットを避けた上記の例から踏み込み、入れ替える都市候補間の相互作用、例えばカットが隣り合うために入替において、独立にコスト関数が決定されず、ΔＥｉとして書くことができず、ΔＥｉｊΣｉΣｊという二次の項を持つ場合（片方を採用する（Σｉ＝＋１）がもう片方は採用しない（Σｊ＝０）場合、両者を採用した場合（Σｉ＝Σｊ＝＋１）など）を考慮したコスト関数を用意することも可能である。

（３）高度な利用例
同様に「８，２，５，３，６，４，７，１」などの経路があった時に、入れ替える都市候補として、「５，３，６，４」などの４箇所の連続する都市を抜き取ってもよい。このカット内部の都市の入れ替えは４！通りであるが、この４！通りのうち最適なものへ都市の並びを入れ替える（フリップする）というやり方でもよい。その場合、４！通りの中から最適なものを出すためのコスト関数（これは従前の巡回セールスマン問題で、巡回するという条件を外したコスト関数）でよい。
その際、従前の巡回セールスマン問題から巡回する条件を外して、次のようなコスト関数Ｅ（ｘ）を利用する。

ここでσ_iは２値変数０または１であり、地点間（ｉ，ｊ）の間の距離ｄ_ij、第二項、および第三項は必ず異なるタイミングで一度訪問する制約条件を課すための項である。Ｎは訪問可能な都市の総数である。ｔは時刻を表すインデックスで、Ｔは考慮するべき地点の数Ｎと等しい。またσ_i,tはｉ地点に時刻ｔに訪れるかどうかを示す０と１の情報、λは制約条件を満たす強制力の強さである。このように、アニーリング用のコスト関数及び／または目的のコスト関数は、都市間の距離を表すパラメータを含む。

以下、図１８を用いて、第２の実施形態に係る処理に流れの一例を説明する。図１８は第２の実施形態に係る処理に流れの一例を示すフローチャートである。ここでは、一例として、上記の素朴な利用例を前提として説明する。

（ステップＳ１１０）端末１のプロセッサ１６は、巡回セールスマン問題に関する情報を受け付ける。ここで巡回セールスマン問題に関する情報は、訪問する場所（例えば都市）、場所の座標、場所の間の距離情報などである。

（ステップＳ１２０）端末１のプロセッサ１６は、回答の初期値を設定する。ここで回答の初期値は、「１，２，３，４，５，６，７，８」などの順番データで表される。回答の初期値は、予め決められていてもよいし、乱数で設定されてもよい。

（ステップＳ１３０）端末１のプロセッサ１６は、入れ替える都市ペアの候補を決定する。

（ステップＳ１４０）端末１のプロセッサ１６は、アニーリングマシン用のコスト関数、入れ替える都市ペアの候補を送信する。ここで、アニーリングマシン用のコスト関数は、上記の素朴な利用例、少し高度な利用例、高度な利用例に応じて端末１で設定される。このアニーリングマシン用のコスト関数は例えば、量子アニーリングの利用において必要な２次形式（ＱＵＢＯ（Quadratic Unconstrained Binary Optimization）形式）の行列にかかる係数値である。

（ステップＳ１５０）アニーリングマシン２は、アニーリングマシン用のコスト関数の最適化を実行する。

（ステップＳ１６０）アニーリングマシン２は、ステップＳ１５０の実行によって得られた、候補となった都市ペアを入れ替えるか否かの情報を端末１へ送信する。ここで、都市ペアを入れ替えるか否かの情報は、０か１の情報である。これは、少し高度な利用例でも同様である。

なお、高度な利用例の場合、このステップ１６０でアニーリングマシン２から端末１へ送信される情報は例えば、０と１のみのデータであるが、それが「５，３，６，４」に対して、例えば、どのような順番で入れ替えをするかを示す０か１の情報である。例えば、［［０，０，０，１］，［０，０，１，０］，［１，０，０，０］，［０，１，０，０］］という場合、４番目、３番目、１番目、２番目の数字をこの順番に並び替えるという意味であり、例えば元の数字の順番が「５，３，６，４」（１番目は５、２番目は３、３番目は６、４番目は４）の場合、「５，３，６，４」から「４，６，５，３」に並び替えよという意味を持つ０，１からなる行列データである。

（ステップＳ１７０）端末１のプロセッサ１６は、都市候補を入れ替えるかの情報に基づき、都市を入れ替えた場合に、目的のコスト関数（もしくはエネルギー）を下げる場合、採用する。端末１のプロセッサ１６は、目的のコスト関数（もしくはエネルギー）を上げるものであっても、確率的な基準（例えば、マルコフ連鎖モンテカルロ法）により、採用・不採用を決定する。

（ステップＳ１８０）端末１のプロセッサ１６は、終了条件を満たすか否かを判定する。終了条件を満たさなければステップＳ１３０へ戻って処理を繰り返す。終了条件を満たす場合、）端末１のプロセッサ１６は、本フローチャートの処理を終了する。

＜第３の実施形態＞
続いて第３の実施形態について説明する。第２の実施形態では、巡回セールスマン問題を解くことを目的としたが、第３の実施形態では、ＷＥＢページにおいて、ビジネスホテル群の掲載と、リゾートホテル群の掲載とが、ミックスされることを目的とする。

目的とするコスト関数及びアニーリングマシン用のコスト関数は、ｉ番目とｊ番目のホテルの類似度ｄ_ijを用いて、以下のようなコスト関数Ｅ（ｘ）にする。第３項と第４項は、各ホテルが各順番において１度だけ表示されるために必要な項である。

ここでＮはホテルの総数である。ｈ_iはｉ番目のホテルの好感度、σ_i,tはＷＥＢページにおけるリスト順番（掲載順番）ｔに対してホテルｉが選ばれるかどうかを示す０か１の値、第三項と第四項はホテルが必ず一つ選ばれどの順番にするべきかを一つ答えるための制約項であり、λは制約条件を満たす強制力の強さである。Ｔはリストで並べるホテルの総数である。なお、ｈ_iはｉ番目のホテルのランキングを示してもよい。このコスト関数Ｅ（ｘ）が小さくなると、アニーリングマシン及び情報処理システムは、選択された処理の実行を採用する。このように、アニーリング用のコスト関数及び／または目的のコスト関数は、ホテルの類似度を表すパラメータ、及びホテルの好感度及び／またはランキングを表すパラメータのうち少なくとも一つを含む。

この場合、第３の実施形態において、アニーリングマシンに入力する手段は、複数の対象物（ここではビジネスホテル群とリゾートホテル群）について、ある対象物（例えばビジネスホテル群）の一部もしくは全部を別の順番に挿入する処理、ある対象物（例えばビジネスホテル群）の一部もしくは全部を別の対象物（例えばリゾートホテル群）の一部もしくは全部と入れ替える処理、対象物（例えばビジネスホテル群）を別の対象物（例えばリゾートホテル群）と入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する対象物の候補それぞれと、アニーリングマシン用のコスト関数を、アニーリングマシン２に入力する。なお、ここでは、性質（もしくは種類）の異なる複数の宿泊施設群の一例として、ビジネスホテル群とリゾートホテル群について説明したが、これに限ったものではなく、例えば、旅館群とホテル群に適用してもよく、あらゆる性質（もしくは種類）の異なる複数の宿泊施設群に対して適用可能である。

なお、上述した実施形態で説明した情報処理システムＳは、一つの端末の例について説明したが、これに限らず、複数の情報処理装置によって、情報処理システムＳを機能させてもよい。この場合、情報処理システムＳの少なくとも一部は、ハードウェアで構成してもよいし、ソフトウェアで構成してもよい。ソフトウェアで構成する場合には、情報処理システムＳの少なくとも一部の機能を実現するプログラムをフレキシブルディスクやＣＤ－ＲＯＭ等の記録媒体に収納し、コンピュータに読み込ませて実行させてもよい。記録媒体は、磁気ディスクや光ディスク等の着脱可能なものに限定されず、ハードディスク装置やメモリなどの固定型の記録媒体でもよい。

また、情報処理システムＳの少なくとも一部の機能を実現するプログラムを、インターネット等の通信回線（無線通信も含む）を介して頒布してもよい。さらに、同プログラムを暗号化したり、変調をかけたり、圧縮した状態で、インターネット等の有線回線や無線回線を介して、あるいは記録媒体に収納して頒布してもよい。

以上、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。

１ 端末
１１ 入力インタフェース
１２ 通信回路
１３ ストレージ
１４ メモリ
１５ ディスプレイ
１６ プロセッサ
１７ カメラ
２ アニーリングマシン
Ｓ 情報処理システム

Claims (9)

1. 複数の対象物について、ある対象物の一部もしくは全部を別の順番に挿入する処理、ある対象物の一部もしくは全部を別の対象物の一部もしくは全部と入れ替える処理、対象物を別の対象物と入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する対象物の候補それぞれと、アニーリングマシン用のコスト関数を、アニーリングマシンに入力する手段と、
   アニーリングマシンがアニーリングマシン用のコスト関数に基づいて決定した、前記対象物の候補それぞれについて処理を実行するか否かの情報を、当該アニーリングマシンから取得する手段と、
   前記対象物の候補それぞれについて処理を実行するか否かを示す情報に基づいて、目的のコスト関数を決定し、当該目的のコスト関数の値に応じて、対象物の候補それぞれについて処理を実行するか否かを決定する手段と、
   を備え、
   前記入力する手段と、前記取得する手段と、前記決定する手段の処理を繰り返す
   情報処理システム。
2. 前記アニーリングマシンに入力する手段は、複数種類の製品について複数の生産ラインで生産する場合に、一つの生産ラインのタイムスロットをカットして別の生産ラインに挿入する処理、一つの生産ラインのある製品のタイムスロットの一部もしくは全部を別の生産ラインのタイムスロットに挿入する処理、一つの生産ラインの製品のタイムスロットの一部もしくは全部を別の生産ラインの製品のタイムスロットの一部もしくは全部と入れ替える処理、一つの生産ラインの各製品のタイムスロットと別の生産ラインの各製品のタイムスロットと入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する対象物の候補それぞれと、アニーリングマシン用のコスト関数を、アニーリングマシンに入力する
   請求項１に記載の情報処理システム。
3. 前記選択された処理の実行の際には、前の工程での処理が終了しているという制約を満たすタイムスロットに対して実行される
   請求項２に記載の情報処理システム。
4. 前記目的のコスト関数には、生産ライン毎の終了時刻の差が小さいほど評価が高くなる項が含まれる
   請求項２または３に記載の情報処理システム。
5. 前記アニーリングマシンに入力する手段は、複数の都市について、都市を別の順番に挿入する処理、都市を別の都市と入れ替える処理、都市を別の都市と入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する都市の候補それぞれと、アニーリングマシン用のコスト関数を、アニーリングマシンに入力する
   請求項１に記載の情報処理システム。
6. 前記アニーリングマシンに入力する手段は、性質の異なる複数の宿泊施設群について、宿泊施設群の一部もしくは全部を別の順番に挿入する処理、ある性質の宿泊施設群の一部もしくは全部を別の性質の宿泊施設群の一部もしくは全部と入れ替える処理、ある性質の宿泊施設群を別の性質の宿泊施設群と入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する宿泊施設の候補それぞれと、アニーリングマシン用のコスト関数を、前記アニーリングマシンに入力する
   請求項１に記載の情報処理システム。
7. 前記決定する手段は、目的のコスト関数が小さくなることを目的としている場合当該コスト関数が低減すれば前記アニーリングマシンの出力を採用し、該コスト関数が低減しなければ前記アニーリングマシンの出力を採用せず、一方、目的のコスト関数が大きくなることを目的としている場合当該コスト関数が増大すれば前記アニーリングマシンの出力を採用し、該コスト関数が増大しなければ前記アニーリングマシンの出力を採用しない
   請求項１から４のいずれか一項に記載の情報処理システム。
8. 入力する手段が、複数の対象物について、ある対象物の一部もしくは全部を別の順番に挿入する処理、ある対象物の一部もしくは全部を別の対象物の一部もしくは全部と入れ替える処理、対象物を別の対象物と入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する対象物の候補それぞれと、アニーリングマシン用のコスト関数を、アニーリングマシンに入力する工程と、
   取得する手段が、アニーリングマシンがアニーリングマシン用のコスト関数に基づいて決定した、前記対象物の候補それぞれについて処理を実行するか否かの情報を、当該アニーリングマシンから取得する工程と、
   決定する手段が、前記対象物の候補それぞれについて処理を実行するか否かを示す情報に基づいて、目的のコスト関数を決定し、当該目的のコスト関数の値に応じて、対象物の候補それぞれについて処理を実行するか否かを決定する工程と、
   を有し、
   前記入力する工程と、前記取得する工程と、前記決定する工程の処理を繰り返す
   情報処理方法。
9. コンピュータを、
   複数の対象物について、ある対象物の一部もしくは全部を別の順番に挿入する処理、ある対象物の一部もしくは全部を別の対象物の一部もしくは全部と入れ替える処理、対象物を別の対象物と入れ替え及び／または順番の並び替えのうちの少なくとも一つの処理から選択された処理を実行する対象物の候補それぞれと、アニーリングマシン用のコスト関数を、アニーリングマシンに入力する手段と、
   アニーリングマシンがアニーリングマシン用のコスト関数に基づいて決定した、前記対象物の候補それぞれについて処理を実行するか否かの情報を、当該アニーリングマシンから取得する手段と、
   前記対象物の候補それぞれについて処理を実行するか否かを示す情報に基づいて、目的のコスト関数を決定し、当該目的のコスト関数の値に応じて、対象物の候補それぞれについて処理を実行するか否かを決定する手段と、
   として機能させるためのプログラムであって、
   前記入力する手段と、前記取得する手段と、前記決定する手段の処理を繰り返すプログラム。