[go: up one dir, main page]

WO2018180740A1 - 計算システム、計算方法および計算プログラムが記録された記録媒体 - Google Patents

計算システム、計算方法および計算プログラムが記録された記録媒体 Download PDF

Info

Publication number
WO2018180740A1
WO2018180740A1 PCT/JP2018/010934 JP2018010934W WO2018180740A1 WO 2018180740 A1 WO2018180740 A1 WO 2018180740A1 JP 2018010934 W JP2018010934 W JP 2018010934W WO 2018180740 A1 WO2018180740 A1 WO 2018180740A1
Authority
WO
WIPO (PCT)
Prior art keywords
time
management
node table
time zone
resource
Prior art date
Application number
PCT/JP2018/010934
Other languages
English (en)
French (fr)
Inventor
広宣 森
Original Assignee
日本電気株式会社
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 日本電気株式会社 filed Critical 日本電気株式会社
Priority to US16/498,482 priority Critical patent/US20210192425A1/en
Priority to JP2019509367A priority patent/JP6866921B2/ja
Publication of WO2018180740A1 publication Critical patent/WO2018180740A1/ja

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G06Q10/063—Operations research, analysis or management
    • G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
    • G06Q10/06311—Scheduling, planning or task assignment for a person or group
    • G06Q10/063114—Status monitoring or status determination for a person or group
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G06Q10/063—Operations research, analysis or management
    • G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
    • G06Q10/06314—Calendaring for a resource

Definitions

  • FIG. 14 is a flowchart showing the longest path search process of the calculation system according to the embodiment of the present invention.
  • FIG. 15 is a flowchart showing a process of outputting a solution of the calculation system according to the embodiment of the present invention.
  • FIG. 16 is a block diagram illustrating an example of a hardware configuration of the computer apparatus according to the embodiment of the present invention.
  • FIG. 3 is an explanatory diagram of the generalized assignment problem according to the embodiment of the present invention.
  • the embodiment of the present invention solves the generalized assignment problem as follows. That is, the allocation problem of using a plurality of resources for as long as possible without time overlap between the start time Ts and the end time Te is solved (upper part of FIG. 3).
  • the node table construction unit 102 creates a node table by a two-stage process of going straight from start to end (step S203) and creating a branch (step S204).
  • step S203 the first definition process, ie, the process of going straight from the start to the end of the l-th stage (step S203) will be described in more detail.
  • the node table construction unit 102 ends the process of creating the l-th branch (step S204).
  • the longest path search unit 103 substitutes toNode_i of the variable edge into the variable ti and substitutes toNode_j of the variable edge into the variable tj (step S309).

Landscapes

  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Engineering & Computer Science (AREA)
  • Strategic Management (AREA)
  • Economics (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Educational Administration (AREA)
  • Game Theory and Decision Science (AREA)
  • Development Economics (AREA)
  • Marketing (AREA)
  • Operations Research (AREA)
  • Quality & Reliability (AREA)
  • Tourism & Hospitality (AREA)
  • Physics & Mathematics (AREA)
  • General Business, Economics & Management (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

割当問題において、要素の数が増えても、最適な組み合わせを求めることを可能とする。本発明の計算システムは、開始時刻から終了時刻までの間に、複数回使える複数個の経営資源を、時間重複なく、できるだけ長い時間使用する場合に、すべての経営資源について、当該経営資源の使用後に使える次の時間帯を定義する第１の定義処理と、当該経営資源の使用後に使える別の経営資源とその時間帯を定義する第２の定義処理とを行うノードテーブル構築部と、ノードテーブル構築部により定義された経営資源とその時間帯を1つずつ辿ることによって使用時間の合計が最も長い工程を特定する最長経路探索部と、特定した最も長い工程を出力する解出力部とを備え、ノードテーブル構築部は、第２の定義処理において、すでに定義された経営資源の時間帯の中で最も遅い時間帯以降の経営資源の時間帯のみを処理対象とする。

Description

計算システム、計算方法および計算プログラムが記録された記録媒体
　本発明は、計算システムに関し、特に、割り当て問題を解決する計算システム等に関する。
　割当問題とは，集合Aの要素（a1,a2,a3…）を集合Bの要素（b1,b2,b3…）のどれに割り当てるかを決定する問題である(図１)。一般に、割当問題においては、要素の数が増えると、組み合わせの数は階乗のオーダーで増大する。その膨大な組み合わせの中から、最適な組み合わせを探索しようとすると、膨大な処理時間がかかる。このため、一般に、割当問題においては、要素の数が増えるほど、最適な組み合わせを求めることは困難になる（組み合わせ爆発）。
　たとえば、作業者Cと作業者Dに空き時間にいずれか一人でしかできない作業をしてもらうことにしたときに、作業時間の合計をできるだけ大きくするためには、どの時間に誰に作業を頼むと良いか、という問題を考える。作業者CおよびDの1日の空き時間は、図２上の通りとする。これはつまり、作業者CおよびDの1日の空き時間という集合の要素を、作業時間という集合の要素に割り当てる問題である。
　この問題を解決するにあたり、次の条件を満たすものとする。（１）作業を行うための設備が1台しかなく、複数人同時の作業ができない。（２）必ず、空き時間の開始から終了まで作業をし、空き時間の途中から作業を始めたり、空き時間の途中で作業をやめたりはしない。以上の条件のもとで作業時間の合計を最大化する。
　結果として、図２下のようにすると、最大の「１３時間」作業してもらうことができる。
特開２００８－０６４０８１号公報 特開２００８－０４６８０８号公報
　上記の例では考慮すべき要素の数が少なくなるように設定したため、わずかな試行錯誤を繰り返すことで最適な組み合わせを求めることができる。ところが、作業者の数を増やしたり、作業を行うための設備を増やしたり、空き時間の途中で作業を交代できるようにしたりなどすると、考慮すべき要素の数が増えて、最適な組み合わせを求めることは困難になっていく。本発明は上述した課題を解決することを目的とする。
　本発明の計算システムは、開始時刻から終了時刻までの間に、複数回使える複数個の経営資源を、時間重複なく、できるだけ長い時間使用する場合に、すべての経営資源について、当該経営資源の使用後に使える次の時間帯を定義する第１の定義処理と、当該経営資源の使用後に使える別の経営資源とその時間帯を定義する第２の定義処理とを行うノードテーブル構築部と、ノードテーブル構築部により定義された経営資源とその時間帯を1つずつ辿ることによって使用時間の合計が最も長い工程を特定する最長経路探索部と、特定した最も長い工程を出力する解出力部とを備え、ノードテーブル構築部は、第２の定義処理において、すでに定義された経営資源の時間帯の中で最も遅い時間帯以降の経営資源の時間帯のみを処理対象とする。
　本発明の計算方法は、開始時刻から終了時刻までの間に、複数回使える複数個の経営資源を、時間重複なく、できるだけ長い時間使用する場合に、すべての経営資源について、当該経営資源の使用後に使える次の時間帯を定義し、当該経営資源の使用後に使える別の経営資源とその時間帯を定義し、定義された経営資源とその時間帯を1つずつ辿ることによって使用時間の合計が最も長い工程を特定し、特定した前記最も長い工程を出力し、すでに定義された経営資源の時間帯の中で最も遅い時間帯以降の経営資源の時間帯のみを処理対象とする。
　本発明の計算プログラムは、開始時刻から終了時刻までの間に、複数回使える複数個の経営資源を、時間重複なく、できるだけ長い時間使用する場合に、コンピュータを、すべての経営資源について、当該経営資源の使用後に使える次の時間帯を定義する手段と、当該経営資源の使用後に使える別の経営資源とその時間帯を定義する手段と、定義された経営資源とその時間帯を1つずつ辿ることによって使用時間の合計が最も長い工程を特定する手段と、特定した前記最も長い工程を出力する手段として機能させ、すでに定義された経営資源の時間帯の中で最も遅い時間帯以降の経営資源の時間帯のみを処理対象とする。
　本発明の目的は、上記計算プログラムが記録された記録媒体によっても達成可能である。
　本発明によれば、割当問題において最適な組み合わせを効率よく求めることができる。
図１は、割当問題の概念図である。 図２は、割当問題の例題の説明図である。 図３は、本発明の実施形態にかかる一般化された割当問題の説明図である。 図４は、本発明の実施形態にかかる計算システムの構成を示すブロック図である。 図５は、本発明の実施形態にかかる計算システムの全体の動作を示すフローチャートである。 図６は、本発明の実施形態にかかる計算システムのノードテーブルの初期化の処理を示すフローチャートである。 図７は、本発明の実施形態にかかるノードテーブルのデータ構造を示す図である。 図８は、本発明の実施形態にかかる計算システムのノードテーブルの構築の処理を示すフローチャートである。 図９は、本発明の実施形態にかかる計算システムの開始から終了まで直進の処理を示すフローチャートである。 図１０は、本発明の実施形態にかかるエッジのデータ構造を示す図である。 図１１は、本発明の実施形態にかかる２段目の開始から終了まで直進の処理を行った後のノードテーブルの一例を示す図である。 図１２は、本発明の実施形態にかかる計算システムの分岐を作成の処理を示すフローチャートである。 図１３は、本発明の実施形態にかかるインデックステーブルのデータ構造を示す図である。 図１４は、本発明の実施形態にかかる計算システムの最長経路の探索の処理を示すフローチャートである。 図１５は、本発明の実施形態にかかる計算システムの解の出力の処理を示すフローチャートである。 図１６は、本発明の実施形態に係るコンピュータ装置のハードウェア構成の一例を示すブロック図である。
　以下に、図面を参照しながら、本発明の実施形態について詳細に説明する。なお、以下の説明では、同じ機能を有するものには同じ符号をつけ、その説明を省略する場合がある。
　図３は本発明の実施形態にかかる一般化された割当問題の説明図である。本発明の実施形態では、次のように一般化された割当問題を解決する。すなわち、開始時刻Tsから終了時刻Teまでの間に、複数のリソースを、時間重複なく、できるだけ長い時間使用する割当問題を解決する（図３上）。
　ここで、リソースとは、経営資源のことであり、たとえば、上述した「作業者の空き時間」のような人材や「作業を行うための設備」のような設備のことである。または、リソースとは、コンピュータで、動作の実行に必要な処理システムの要素や機器およびそれらの空き時間のことである。
　また、リソースを段として数えN段あるものとし、さらに、1つの段（すなわちリソース）は、時間重複なくP個に区分されるものとする。つまり、Ｐ回使えるN個の経営資源である。以降、i段目・j番目のリソースを、リソースi,jと呼ぶ（iは1からNまでの自然数、jは1からPまでの自然数）。各リソースi,jは、開始時刻Rsi,jから終了時刻Rei,jの間使用することができるものとする（図３下）。
　（構成）
　図４は本発明の実施形態にかかる計算システムの構成を示すブロック図である。本発明の実施形態にかかる計算システム１００は、ノードテーブル初期化部１０１、ノードテーブル構築部１０２、最長経路探索部１０３、解出力部１０４をもつ。
　（作用）
　図５は本発明の実施形態にかかる計算システムの全体の動作を示すフローチャートである。全体の動作は、大きく分けてノードテーブルの初期化S1、ノードテーブルの構築S2、最長経路の探索S3、解の出力S4の4つの処理に分けられる。以下に各処理の詳細について説明する。
　図６は本発明の実施形態にかかる計算システムのノードテーブルの初期化の処理を示すフローチャートである。以下にノードテーブルの初期化S1の処理について説明する。
　ノードテーブル初期化部１０１は、ノードテーブルの、EDGESの列のすべての要素へ「空」を代入し、COSTの列のすべての要素へ「０」を代入し、FROMの列のすべての要素へ「空」を代入する（ステップS101）。ステップS101が終了したら、ノードテーブル初期化部１０１は、ノードテーブルの初期化S1の処理を終了する。
　図７は、本発明の実施形態にかかるノードテーブルのデータ構造を示す図である。ノードテーブルとは、i、ｊ、EDGES、COST、FROMの列項目をもつ２次元配列の構造を持つデータである。ノードテーブルは、i、ｊのすべての組み合わせにそれぞれ対応する行と、（i=START,j=0）および（i=GOAL,j=0）に対応する行をもつ。
　以上が、ノードテーブルの初期化S1の処理である。
　図８は本発明の実施形態にかかる計算システムのノードテーブルの構築の処理を示すフローチャートである。以下にノードテーブルの構築S2の処理について説明する。
　ノードテーブル構築部１０２は、開始から終了まで直進（ステップS203）と、分岐を作成（ステップS204）の２段階の処理でノードテーブルを作成する。
　ノードテーブル構築部１０２は、ステップS203およびステップS204をループ変数ｌが１からNまでの間繰り返す（ステップS201、ステップS202においてYes、ステップS205、ｌ=1,2,…N）。ステップS203およびステップS204のループ処理が終了したら（ステップS202においてNo）、ノードテーブル構築部１０２は、ノードテーブルの構築S2の処理を終了する。
　以上が、ノードテーブルの構築S2の処理である。
　ここから、第1の定義処理である、ｌ段目の開始から終了まで直進（ステップS203）の処理についてより詳細に説明する。
　図９は本発明の実施形態にかかる計算システムの開始から終了まで直進の処理を示すフローチャートである。開始から終了まで直進（ステップS203）の処理は、1つの段の中でのリソースの関係性を定義する処理である。すなわち、ある経営資源の使用後に使える時間帯を定義する処理である。
　ノードテーブル構築部１０２は、エッジの、toNode_i列の要素へｌの値を代入し、toNode_j列の要素へ１を代入し、edgeCost列の要素へ（ｄ=開始時刻Rsｌ,1-終了時刻Reｌ,１）の値を代入する（ステップS2011）。
　図１０は本発明の実施形態にかかるエッジのデータ構造を示す図である。エッジとは、toNode_i、toNode_ｊ、edgeCostの列項目をもつ１次元配列の構造を持つデータである。
　次に、ノードテーブル構築部１０２は、ノードテーブル（i=START,j=0）に対応する行のEDGESにステップS2011で作成したエッジを追加する（ステップS2012）。
　ノードテーブル構築部１０２は、次のステップS2015およびステップS2016をループ変数mが２からPまでの間繰り返す（ステップS2013、ステップS2014においてYes、ステップS2017、ｍ=2,3,…P）。
　ノードテーブル構築部１０２は、エッジの、toNode_i列の要素へｌの値を代入し、toNode_j列の要素へｍの値を代入し、edgeCost列の要素へ（ｄ=開始時刻Rsｌ,ｍ-終了時刻Reｌ,ｍ）の値を代入する（ステップS2015）。
　次に、ノードテーブル構築部１０２は、ノードテーブル(i＝ｌ,j＝ｍ)のEDGESにステップS2015で作成したエッジを追加する（ステップS2016）。ステップS2016の後はステップS2017へ進む。
　ステップS2015およびステップS2016のループ処理が終了したら（ステップS2014においてNo）、次に、ノードテーブル構築部１０２は、エッジの、toNode_i列の要素へGOALを代入し、toNode_j列の要素へ0を代入し、edgeCost列の要素へ0を代入する（ステップS2018）。
　次に、ノードテーブル構築部１０２は、ノードテーブル(i=l,j=P)のEDGESにステップS2018で作成したエッジを追加する（ステップS2019）。ステップS2019が終了したら、ノードテーブル構築部１０２は、開始から終了まで直進（ステップS203）の処理を終了する。
　以上が、ｌ段目の開始から終了まで直進（ステップS203）の処理の詳細である。
　図１１は、本発明の実施形態にかかる２段目の開始から終了まで直進の処理を行った後のノードテーブルの一例を示す図である。開始から終了まで直進（ステップS203）の処理によって、段の先頭を「START」、末尾に「GOAL」として、「START」から「GOAL」までを1つずつ繋ぐようにエッジが作成され（図１１上）、ノードテーブルに登録される。ノードテーブルのi,jがエッジの始点となるリソースを示している。また、EDGESのtoNode_i、toNode_ｊが、エッジの終点となるリソースを示している。EDGESのedgeCostはエッジの終点となるリソースの使用時間を示している。（図１１下）
　ここから、第２の定義処理である、ｌ段目の分岐を作成（ステップS204）の処理の詳細についてより詳細に説明する。
　図１２は本発明の実施形態にかかる計算システムの分岐を作成の処理を示すフローチャートである。分岐を作成（ステップS204）の処理は、ある段から別の段へのリソースの関係性を定義する処理である。すなわち、ある経営資源の使用後に使える別の経営資源とその時間帯を定義する処理である。
　ノードテーブル構築部１０２は、インデックステーブルの、indexの列のすべての要素へ「０」を代入する（ステップS2021）。
　図１３は本発明の実施形態にかかるインデックステーブルのデータ構造を示す図である。
インデックステーブルとは、k、indexの列項目をもつ２次元配列の構造を持つデータである。
　ノードテーブル構築部１０２は、ステップS2024からステップS20214までのステップをループ変数ｍが１からPまでの間繰り返す（ステップS2022、ステップS2023においてYes、ステップS20215、ｍ=1,2,…P）。ステップS2024からステップS20214までのループ処理が終了したら（ステップS2023においてNo）、ノードテーブル構築部１０２は、ｌ段目の分岐を作成（ステップS204）の処理を終了する。
　さらに、ノードテーブル構築部１０２は、ステップS2027からステップS20213までのステップをループ変数ｎが１からNまでの間繰り返す（ステップS2024、ステップS2025においてYes、ステップS20214、ｎ=1,2,…N）。ただし、n=ｌのときは処理を行わない（ステップS2026）。処理を行わない理由は、同一段の処理は「開始から終了まで直進（S201）」の処理で行うからである。ステップS2027からステップS20213までのループ処理が終了したら（ステップS2025においてNo）、ステップS20215へ進む。
　ノードテーブル構築部１０２は、インデックステーブル（k=n）のindexの値を変数ikに代入する（ステップS2027）。
　次に、ノードテーブル構築部１０２は、Rsｎ,ik>Reｌ,ｍであるか否か判定する（ステップS2028）これにより、ｎ段目ik番目のリソースが、ｌ段目ｍ番目のリソースの次に使えるか否かを判定している。
　ステップS2028においてRsｎ,ik>Reｌ,ｍである場合（ステップS2028においてYes）、次に、ノードテーブル構築部１０２は、エッジの、toNode_i列の要素へｎの値を代入し、toNode_j列の要素へikの値を代入し、edgeCost列の要素へｄ= Reｎ,ik-Rsｎ,ikの値を代入する（ステップS2029）。次に、ノードテーブル構築部１０２は、ノードテーブル(i＝ｌ,j＝ｍ)のEDGESにステップS2029で作成したエッジを追加する（ステップS20210）。ステップS20210の後はステップS20214へ進む。
　ステップS2028においてRsｎ,ik>Reｌ,ｍではない場合（ステップS2028においてNo）、次に、ノードテーブル構築部１０２は、ik＝Pであるか否か判断する（ステップS20211）。
　ステップS20211においてik＝Pである場合（ステップS20211においてYes）、ステップS20214へ進む。
　ステップS20211においてik＝Pではない場合（ステップS20211においてNo）、ノードテーブル構築部１０２は、変数ikにik+1を代入する（ステップS20212）。次に、ノードテーブル構築部１０２は、変数ikの値をインデックステーブル（k=n）のindexに代入する（ステップS20213）。ステップS20213の後はステップS2028へ進む。
　以上が、ｌ段目の分岐を作成（ステップS204）の処理の詳細である。この処理において、すでに定義された経営資源の時間帯よりも前の当該経営資源の別の時間帯を処理対象としないことにより処理工程が効率化されている。
　図１４は本発明の実施形態にかかる計算システムの最長経路の探索の処理を示すフローチャートである。以下に最長経路の探索S3の処理について説明する。
　最長経路探索部１０３は、空のFIFOキューを作成する（ステップS301）。次に、最長経路探索部１０３は、ステップS301で作成したキューに(i=START,j=0)を追加する（ステップS302）。
　最長経路探索部１０３は、次のステップS305からステップS314までのステップをステップS301で作成したキューが空になるまでの間繰り返す（ステップS303、ステップS304においてYes）。ステップS301で作成したキューが空の場合（ステップS304においてNo）、最長経路探索部１０３は、最長経路の探索S3の処理を終了する。
　最長経路探索部１０３は、変数node_iへステップS303で取り出した先頭データのiを代入し、また、変数node_jへステップS303で取り出した先頭データのjを代入する（ステップS305）
　次に、最長経路探索部１０３は、変数oへ1を代入し、変数ksizeへノードテーブル（i=node_i,j=node_j）のEDGESに格納されているデータの個数を代入する（ステップS306）。
　最長経路探索部１０３は、次のステップS308からステップS313までのステップをo≦kSizeである間繰り返す（ステップS307においてYes、ステップS314）。o≦kSizeではなくなった場合（ステップS307においてNo）、ステップS303へ進む。
　最長経路探索部１０３は、変数edgeへノードテーブル（i=node_i,j=node_j）のEDGESに格納されているo番目のデータを代入する（ステップS308）。
　次に、最長経路探索部１０３は、変数tiへ変数edgeのtoNode_iを代入し、変数tjへ変数edgeのtoNode_jを代入する（ステップS309）。
　次に、最長経路探索部１０３は、変数newCostへノードテーブル（i=node_i,j=node_j）のCOSTと変数edgeのedgeCostとの合計値を代入する（ステップS310）。
　次に、最長経路探索部１０３は、ノードテーブル(i=ti,j=tj)のCOST<newCostであるか否か判定する（ステップS311）。
　ステップS311においてノードテーブル(i=ti,j=tj)のCOST<newCostである場合（ステップS311においてYes）、次に、ノードテーブル構築部１０２は、ノードテーブル(i=ti,j=tj)のCOSTへ変数newCostを代入し、ノードテーブル(i=ti,j=tj)のFROMへステップS303で取り出した先頭データを代入する（ステップS312）。
　次に、最長経路探索部１０３は、キューに(i=ti,j=tj)を追加する（ステップS313）。
ステップS313の後はステップS314へ進む。
　ステップS311においてノードテーブル(i=ti,j=tj)のCOST<newCostではない場合（ステップS311においてNo）、ステップS314へ進む。
　以上が、最長経路の探索S3の処理である。
　図１５は本発明の実施形態にかかる計算システムの解の出力の処理を示すフローチャートである。以下に解の出力S4の処理について説明する。
　解出力部１０４は、変数tiへGOALを代入し、変数tjへ0を代入する（ステップS401）。
次に、解出力部１０４は、空の配列rootを作成し（ステップS402）、配列rootに(i=ti,j=tj)を追加する（ステップS403）。
　次に、解出力部１０４は、ノードテーブル(i=ti,j=tj)のFROMが空か否か判断する（ステップS404）。
　ステップS404においてノードテーブル(i=ti,j=tj)のFROMが空である場合（ステップS４０４においてYes）、次に、解出力部１０４は、rootに格納されているデータを末尾から先頭に向かって出力する（ステップS405）。ステップS405が終了したら、解出力部１０４は、解の出力S4の処理を終了する。
　ステップS404においてノードテーブル(i=ti,j=tj)のFROMが空ではない場合（ステップS４０４においてNo）、次に、解出力部１０４は、変数tiへノードテーブル(i=ti,j=tj)のFROMのiを代入し、変数tjへノードテーブル(i=ti,j=tj)のFROMのjを代入する（ステップS406）。ステップS406の後はステップS403へ進む。
　以上が、解の出力S4の処理である。
　（効果）
　本実施形態によれば、すでに定義された経営資源の時間帯の中で最も遅い時間帯以降の経営資源の時間帯のみを処理対象とし、すでに定義された経営資源の時間帯よりも前の当該経営資源の別の時間帯を処理対象としないことにより処理工程が効率化されている。また、本実施形態によれば、「リソース割り当て問題」を「最長経路問題」に変換したことで、処理速度の劇的な改善が見られる。
（ハードウェア構成）
　図１６は、本発明の実施形態に係るコンピュータ装置のハードウェア構成の一例を示すブロック図である。コンピュータ装置４００は、上述した計算システム１００を実現する装置の一例である。コンピュータ装置４００は、ＣＰＵ（Central Processing Unit）４０１と、ＲＯＭ（Read Only Memory）４０２と、ＲＡＭ（Random Access Memory）４０３と、記憶装置４０４と、ドライブ装置４０５と、通信インタフェース４０６と、入出力インタフェース４０７とを備える。計算システム１００は、図１６に示される構成（又はその一部）によって実現され得る。
　ＣＰＵ４０１は、ＲＡＭ４０３を用いてプログラム４０８を実行する。プログラム４０８は、ＲＯＭ４０２に記憶されていてもよい。また、プログラム４０８は、フラッシュメモリなどの記録媒体４０９に記録され、ドライブ装置４０５によって読み出されてもよいし、外部装置からネットワーク４１０を介して送信されてもよい。通信インタフェース４０６は、ネットワーク４１０を介して外部装置とデータをやり取りする。入出力インタフェース４０７は、周辺機器（入力装置、表示装置など）とデータをやり取りする。通信インタフェース４０６及び入出力インタフェース４０７は、データを取得又は出力する手段として機能することができる。
　なお、ノードテーブル初期化部１０１、ノードテーブル構築部１０２、最長経路探索部１０３、解出力部１０４等のそれぞれは、単一の回路（プロセッサ等）によって構成されてもよいし、複数の回路の組み合わせによって構成されてもよい。ここでいう回路（circuitry）は、専用又は汎用のいずれであってもよい。また、ノードテーブル初期化部１０１、ノードテーブル構築部１０２、最長経路探索部１０３、解出力部１０４等は、これらが単一の回路によって構成されてもよい。
　本発明は上記実施形態に限定されることなく、請求の範囲に記載の発明の範囲内で、種々の変形が可能であり、それらも本発明の範囲内に含まれるものであることはいうまでもない。即ち、本発明は、本発明のスコープ内において、当業者が理解し得る様々な態様を適用することができる。
　この出願は、２０１７年３月３１日に出願された日本出願特願２０１７－０６９４５５を基礎とする優先権を主張し、その開示の全てをここに取り込む。
　１００　　計算システム
　１０１　　ノードテーブル初期化部
　１０２　　ノードテーブル構築部
　１０３　　最長経路探索部
　１０４　　解出力部
　４００　　コンピュータ装置
　４０１　　ＣＰＵ（Central Processing Unit）
　４０２　　ＲＯＭ（Read Only Memory）
　４０３　　ＲＡＭ（Random Access Memory）
　４０４　　記憶装置
　４０５　　ドライブ装置
　４０６　　通信インタフェース
　４０７　　入出力インタフェース
　４０８　　プログラム
　４０９　　記録媒体
　４１０　　ネットワーク

Claims (3)

  1. 　開始時刻から終了時刻までの間に、複数回使える複数個の経営資源を、時間重複なく、できるだけ長い時間使用する場合に、
    　すべての経営資源について、当該経営資源の使用後に使える次の時間帯を定義する第１の定義処理と、当該経営資源の使用後に使える別の経営資源とその時間帯を定義する第２の定義処理とを行うノードテーブル構築手段と、
    　前記ノードテーブル構築手段により定義された経営資源とその時間帯を1つずつ辿ることによって使用時間の合計が最も長い工程を特定する最長経路探索手段と、
    　特定した前記最も長い工程を出力する解出力手段
    　とを備え、
    　前記ノードテーブル構築手段は、前記第２の定義処理において、すでに定義された経営資源の時間帯の中で最も遅い時間帯以降の経営資源の時間帯のみを処理対象とする、
    　計算システム。
  2. 　開始時刻から終了時刻までの間に、複数回使える複数個の経営資源を、時間重複なく、できるだけ長い時間使用する場合に、
    　すべての経営資源について、当該経営資源の使用後に使える次の時間帯を定義する第１の定義処理と、当該経営資源の使用後に使える別の経営資源とその時間帯を定義する第２の定義処理とを実行し、
    　定義された経営資源とその時間帯を1つずつ辿ることによって使用時間の合計が最も長い工程を特定し、
    　特定した前記最も長い工程を出力し、
    　前記第２の定義処理において、すでに定義された経営資源の時間帯の中で最も遅い時間帯以降の経営資源の時間帯のみを処理対象とする計算方法。
  3. 　開始時刻から終了時刻までの間に、複数回使える複数個の経営資源を、時間重複なく、できるだけ長い時間使用する場合に、コンピュータに、
    　すべての経営資源について、当該経営資源の使用後に使える次の時間帯を定義する第１の定義処理と、当該経営資源の使用後に使える別の経営資源とその時間帯を定義する第２の定義処理と、
    　定義された経営資源とその時間帯を1つずつ辿ることによって使用時間の合計が最も長い工程を特定する処理と、
    　特定した前記最も長い工程を出力する処理と、を実行させ、
    　前記第２の定義処理において、すでに定義された経営資源の時間帯の中で最も遅い時間帯以降の経営資源の時間帯のみを処理対象とする計算プログラムが記録された記録媒体。
PCT/JP2018/010934 2017-03-31 2018-03-20 計算システム、計算方法および計算プログラムが記録された記録媒体 WO2018180740A1 (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
US16/498,482 US20210192425A1 (en) 2017-03-31 2018-03-20 Calculation system, calculation method and recording medium on which calculation program is recorded
JP2019509367A JP6866921B2 (ja) 2017-03-31 2018-03-20 計算システム、計算方法および計算プログラム

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2017069455 2017-03-31
JP2017-069455 2017-03-31

Publications (1)

Publication Number Publication Date
WO2018180740A1 true WO2018180740A1 (ja) 2018-10-04

Family

ID=63677116

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2018/010934 WO2018180740A1 (ja) 2017-03-31 2018-03-20 計算システム、計算方法および計算プログラムが記録された記録媒体

Country Status (3)

Country Link
US (1) US20210192425A1 (ja)
JP (1) JP6866921B2 (ja)
WO (1) WO2018180740A1 (ja)

Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH07262273A (ja) * 1994-02-25 1995-10-13 Minnesota Mining & Mfg Co <3M> リソースの割当とスケジューリングのための方法
JP2002373013A (ja) * 2001-06-14 2002-12-26 Asprova Corp 生産スケジューリング方法、その生産スケジューリング方法をコンピュータに実行させるためのプログラム、並びにその生産スケジューリング方法をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体
JP2003029988A (ja) * 2001-07-13 2003-01-31 Nec Corp タスクスケジューリングシステムおよび方法、プログラム
JP2003233740A (ja) * 2002-02-08 2003-08-22 Nec Corp 予約システム
JP2004265333A (ja) * 2003-03-04 2004-09-24 Sony Corp 情報処理装置および方法、並びにプログラム
JP2006285784A (ja) * 2005-04-01 2006-10-19 Canon Inc スケジューリングシステム及び方法
JP2009015597A (ja) * 2007-07-04 2009-01-22 Nagaoka Univ Of Technology スケジュール作成方法，スケジュール作成装置，およびコンピュータプログラム
US20150356483A1 (en) * 2014-06-05 2015-12-10 Abb Technology Ag Method and system for improving route assignment performance

Patent Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH07262273A (ja) * 1994-02-25 1995-10-13 Minnesota Mining & Mfg Co <3M> リソースの割当とスケジューリングのための方法
JP2002373013A (ja) * 2001-06-14 2002-12-26 Asprova Corp 生産スケジューリング方法、その生産スケジューリング方法をコンピュータに実行させるためのプログラム、並びにその生産スケジューリング方法をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体
JP2003029988A (ja) * 2001-07-13 2003-01-31 Nec Corp タスクスケジューリングシステムおよび方法、プログラム
JP2003233740A (ja) * 2002-02-08 2003-08-22 Nec Corp 予約システム
JP2004265333A (ja) * 2003-03-04 2004-09-24 Sony Corp 情報処理装置および方法、並びにプログラム
JP2006285784A (ja) * 2005-04-01 2006-10-19 Canon Inc スケジューリングシステム及び方法
JP2009015597A (ja) * 2007-07-04 2009-01-22 Nagaoka Univ Of Technology スケジュール作成方法，スケジュール作成装置，およびコンピュータプログラム
US20150356483A1 (en) * 2014-06-05 2015-12-10 Abb Technology Ag Method and system for improving route assignment performance

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
TAKASUGA MASAHIDE ET AL.: "Proposal of the solution to the personnel resource allocation problems in the development that takes into account the ability difference", IPSJ SIG TECHNICAL REPORTS : MATHEMATICAL MODELING AND PROBLEM SOLVING (MPS), vol. 2017 -MP, no. 26, 20 February 2017 (2017-02-20), pages 1 - 4 *

Also Published As

Publication number Publication date
JPWO2018180740A1 (ja) 2020-01-09
JP6866921B2 (ja) 2021-04-28
US20210192425A1 (en) 2021-06-24

Similar Documents

Publication Publication Date Title
Fisher Optimal solution of scheduling problems using Lagrange multipliers: Part I
We¸ Glarz On certain models of resource allocation problems
Rosvall et al. A constraint-based design space exploration framework for real-time applications on MPSoCs
CN106874094A (zh) 定时任务处理方法、装置及计算设备
CN105988872A (zh) 一种cpu资源分配的方法、装置及电子设备
CN109359732A (zh) 一种芯片及基于其的数据处理方法
Zhang et al. Pareto‐optimization of three‐agent scheduling to minimize the total weighted completion time, weighted number of tardy jobs, and total weighted late work
Redwine et al. A mixed integer programming model for scheduling orders in a steel mill
Burdett et al. Techniques to effectively buffer schedules in the face of uncertainties
Grzechca et al. The assembly line balancing problem with task splitting: A case study
Lackner et al. Exact methods for the oven scheduling problem
Bozoki et al. A branch-and-bound algorithm for the continuous-process job-shop scheduling problem
WO2018180740A1 (ja) 計算システム、計算方法および計算プログラムが記録された記録媒体
Cheng et al. Preemptive parallel‐machine scheduling with a common server to minimize makespan
Krishnaraj et al. Simulated annealing algorithms to minimise the completion time variance of jobs in permutation flowshops
Chetty et al. A Study on the Enhanced Best Performance Algorithm for the Just‐in‐Time Scheduling Problem
Luo On scheduling a deteriorating rate-modifying activity to minimize the number of tardy jobs
Shi et al. An Introduction to Selecting Optimal Linear Systems and Their Contingency Plans
JP6885459B2 (ja) 計算システム、計算方法および計算プログラム
JP7235239B2 (ja) スケジューリング装置、スケジューリング方法、及びスケジューリングプログラム
Escribe et al. Competitive algorithms for the online minimum peak appointment scheduling
Garg et al. A k-factor CPU scheduling algorithm
Ward et al. In search of scientific Agile
JP2802393B2 (ja) 生産ラインの予測シミュレーション方法
Ponnambalam et al. Giffler and Thompson procedure based genetic algorithms for scheduling job shops

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 18776504

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2019509367

Country of ref document: JP

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 18776504

Country of ref document: EP

Kind code of ref document: A1