特許ウォッチ

公開番号2025159919
公報種別公開特許公報(A)
公開日2025-10-22
出願番号2024062781
出願日2024-04-09
発明の名称演算方法、プログラム及び演算装置
出願人三菱重工業株式会社
代理人弁理士法人酒井国際特許事務所
主分類G06N 99/00 20190101AFI20251015BHJP(計算;計数)
要約【課題】イジングモデルを用いた演算負荷を低減する。
【解決手段】演算方法は、演算対象となる複数のジョブを示すジョブ情報を取得するステップと、複数のタイムスロットを含む分割時間帯を、時系列毎に複数設定するステップと、イジングマシンによる、分割時間帯に含まれるタイムスロットにジョブ情報が示す前記ジョブを割り当てた演算結果を、分割時間帯毎に取得するステップと、を含む。演算結果を取得するステップにおいては、分割時間帯の直後のタイムスロットである後続タイムスロットに対して、その分割時間帯に含まれるタイムスロットに割り当てられないジョブが割り当てられることを条件として、その分割時間帯に含まれるタイムスロットと後続タイムスロットとにジョブを割り当てた、演算結果を取得する。
【選択図】図8
特許請求の範囲【請求項１】
単位時間毎のタイムスロットにジョブを割り当てるスケジューリング問題についての演算を実行する演算方法であって、
演算対象となる複数のジョブを示すジョブ情報を取得するステップと、
複数のタイムスロットを含む分割時間帯を、時系列毎に複数設定するステップと、
イジングマシンによる、前記分割時間帯に含まれる前記タイムスロットに前記ジョブ情報が示す前記ジョブを割り当てた演算結果を、前記分割時間帯毎に取得するステップと、
を含み、
前記演算結果を取得するステップにおいては、前記分割時間帯の直後の前記タイムスロットである後続タイムスロットに対して、その分割時間帯に含まれる前記タイムスロットに割り当てられない前記ジョブが割り当てられることを条件として、その分割時間帯に含まれる前記タイムスロットと前記後続タイムスロットとに前記ジョブを割り当てた、前記演算結果を取得する、
演算方法。
続きを表示（約 1,600 文字）【請求項２】
前記演算結果を取得するステップにおいては、前記分割時間帯の直前の前記タイムスロットである先行タイムスロットに対して、その分割時間帯より前の分割時間帯に割り当て済みの前記ジョブが割り当てられ、かつ、前記後続タイムスロットに対して、その分割時間帯に含まれる前記タイムスロットと前記先行タイムスロットとに割り当てられない全ての前記ジョブが割り当てられることを条件として、その分割時間帯に含まれる前記タイムスロットと前記先行タイムスロットと前記後続タイムスロットとに前記ジョブを割り当てた、前記演算結果を取得する、請求項１に記載の演算方法。
【請求項３】
前記分割時間帯を設定するステップにおいては、前記ジョブの数と、前記分割時間帯に含まれるタイムスロットの数とを乗じた値が、前記イジングマシンが扱える上限ビット数以下となるように、前記分割時間帯に含めるタイムスロットの数を設定する、請求項１又は請求項２に記載の演算方法。
【請求項４】
前記ジョブ情報を取得するステップにおいては、前記ジョブの実行に要する実行時間の情報と、前記ジョブの他のジョブに対する実行順序を示す情報とを、前記ジョブ情報として取得し、
前記実行時間と前記実行順序とに基づいて、演算対象となるジョブに対して、そのジョブが実行されないタイムスロットである不実施タイムスロットを設定するステップをさらに含み、
前記イジングマシンは、前記演算対象となるジョブに対して、そのジョブに設定された前記不実施タイムスロットを割り当てないことを条件として、ジョブを割り当てる演算を実行する、請求項１又は請求項２に記載の演算方法。
【請求項５】
単位時間毎のタイムスロットにジョブを割り当てるスケジューリング問題についての演算をコンピュータに実行させるプログラムであって、
演算対象となる複数のジョブを示すジョブ情報を取得するステップと、
複数のタイムスロットを含む分割時間帯を、時系列毎に複数設定するステップと、
イジングマシンによる、前記分割時間帯に含まれる前記タイムスロットに前記ジョブ情報が示す前記ジョブを割り当てた演算結果を、前記分割時間帯毎に取得するステップと、
を前記コンピュータに実行させ、
前記演算結果を取得するステップにおいては、前記分割時間帯の直後の前記タイムスロットである後続タイムスロットに対して、その分割時間帯に含まれる前記タイムスロットに割り当てられない前記ジョブが割り当てられることを条件として、その分割時間帯に含まれる前記タイムスロットと前記後続タイムスロットとに前記ジョブを割り当てた、前記演算結果を取得する、
プログラム。
【請求項６】
単位時間毎のタイムスロットにジョブを割り当てるスケジューリング問題についての演算を実行する演算装置であって、
演算対象となる複数のジョブを示すジョブ情報を取得するジョブ情報取得部と、
複数のタイムスロットを含む分割時間帯を、時系列毎に複数設定する分割時間帯設定部と、
イジングマシンによる、前記分割時間帯に含まれる前記タイムスロットに前記ジョブ情報が示す前記ジョブを割り当てた演算結果を、前記分割時間帯毎に取得する演算結果取得部と、
を含み、
前記演算結果取得部は、前記分割時間帯の直後の前記タイムスロットである後続タイムスロットに対して、その分割時間帯に含まれる前記タイムスロットに割り当てられない前記ジョブが割り当てられることを条件として、その分割時間帯に含まれる前記タイムスロットと前記後続タイムスロットとに前記ジョブを割り当てた、前記演算結果を取得する、
演算装置。

発明の詳細な説明【技術分野】
【０００１】
本開示は、演算方法、プログラム及び演算装置に関する。
続きを表示（約 2,200 文字）【背景技術】
【０００２】
２つの状態のいずれかをとり得る複数のビットからなるイジングモデルについて、解を求める演算手法が知られている。例えば特許文献１には、アニーリングを物理的に模擬したイジングマシンにより、予め与えられた終了時間Ｔｕで複数のオペレーションを終了できる実行可能解を見つける解算出ステップと、実行可能解が見つかった場合に、終了時間ＴｕをＴｕ－１に更新して解算出ステップを繰り返すことで、イジングモデルに対応するスケジューリング問題についての近似解を算出する旨が記載されている。
【先行技術文献】
【特許文献】
【０００３】
特許第６７７８９４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ここで、イジングモデルを用いてスケジューリング問題の解を求める際に、イジングモデルを用いた演算負荷を低減することが求められている。
【０００５】
本開示は、上述した課題を解決するものであり、イジングモデルを用いた演算負荷を低減可能な演算方法、プログラム及び演算装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本開示に係る演算方法は、単位時間毎のタイムスロットにジョブを割り当てるスケジューリング問題についての演算を実行する演算方法であって、演算対象となる複数のジョブを示すジョブ情報を取得するステップと、複数のタイムスロットを含む分割時間帯を、時系列毎に複数設定するステップと、イジングマシンによる、前記分割時間帯に含まれる前記タイムスロットに前記ジョブ情報が示す前記ジョブを割り当てた演算結果を、前記分割時間帯毎に取得するステップと、を含み、前記演算結果を取得するステップにおいては、前記分割時間帯の直後の前記タイムスロットである後続タイムスロットに対して、その分割時間帯に含まれる前記タイムスロットに割り当てられない前記ジョブが割り当てられることを条件として、その分割時間帯に含まれる前記タイムスロットと前記後続タイムスロットとに前記ジョブを割り当てた、前記演算結果を取得する。
【０００７】
本開示に係るプログラムは、単位時間毎のタイムスロットにジョブを割り当てるスケジューリング問題についての演算をコンピュータに実行させるプログラムであって、演算対象となる複数のジョブを示すジョブ情報を取得するステップと、複数のタイムスロットを含む分割時間帯を、時系列毎に複数設定するステップと、イジングマシンによる、前記分割時間帯に含まれる前記タイムスロットに前記ジョブ情報が示す前記ジョブを割り当てた演算結果を、前記分割時間帯毎に取得するステップと、を前記コンピュータに実行させ、前記演算結果を取得するステップにおいては、前記分割時間帯の直後の前記タイムスロットである後続タイムスロットに対して、その分割時間帯に含まれる前記タイムスロットに割り当てられない前記ジョブが割り当てられることを条件として、その分割時間帯に含まれる前記タイムスロットと前記後続タイムスロットとに前記ジョブを割り当てた、前記演算結果を取得する。
【０００８】
本開示に係る演算装置は、単位時間毎のタイムスロットにジョブを割り当てるスケジューリング問題についての演算を実行する演算装置であって、演算対象となる複数のジョブを示すジョブ情報を取得するジョブ情報取得部と、複数のタイムスロットを含む分割時間帯を、時系列毎に複数設定する分割時間帯設定部と、イジングマシンによる、前記分割時間帯に含まれる前記タイムスロットに前記ジョブ情報が示す前記ジョブを割り当てた演算結果を、前記分割時間帯毎に取得する演算結果取得部と、を含み、前記演算結果取得部は、前記分割時間帯の直後の前記タイムスロットである後続タイムスロットに対して、その分割時間帯に含まれる前記タイムスロットに割り当てられない前記ジョブが割り当てられることを条件として、その分割時間帯に含まれる前記タイムスロットと前記後続タイムスロットとに前記ジョブを割り当てた、前記演算結果を取得する。
【発明の効果】
【０００９】
本開示によれば、イジングモデルを用いた演算負荷を低減できる。
【図面の簡単な説明】
【００１０】
図１は、本実施形態に係る演算システムの模式的なブロック図である。
図２は、演算装置の模式的なブロック図である。
図３は、分割時間帯の一例を説明するための模式図である。
図４は、演算結果の一例を示す表である。
図５は、分割時間帯における演算結果の一例を示す表である。
図６は、分割時間帯における演算結果の一例を示す表である。
図７は、スケジューリング問題の演算の処理フローを説明するフローチャートである。
図８は、ジョブ情報の一例を示す模式図である。
図９は、不実施タイムスロットの設定の例を示す模式図である。
図１０は、不実施タイムスロットの設定の例を示す模式図である。
【発明を実施するための形態】
（【００１１】以降は省略されています）

関連特許