JPH04177457A - 多資源システムスケジューリング方式 - Google Patents
多資源システムスケジューリング方式Info
- Publication number
- JPH04177457A JPH04177457A JP2302930A JP30293090A JPH04177457A JP H04177457 A JPH04177457 A JP H04177457A JP 2302930 A JP2302930 A JP 2302930A JP 30293090 A JP30293090 A JP 30293090A JP H04177457 A JPH04177457 A JP H04177457A
- Authority
- JP
- Japan
- Prior art keywords
- processing
- exchange
- resources
- resource
- evaluation
- Prior art date
- Legal status (The legal status 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 status listed.)
- Pending
Links
- 238000011156 evaluation Methods 0.000 claims abstract description 56
- 238000000034 method Methods 0.000 claims description 27
- 239000000284 extract Substances 0.000 abstract description 3
- 238000004519 manufacturing process Methods 0.000 description 3
- 238000010586 diagram Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 230000010365 information processing Effects 0.000 description 2
- 238000005457 optimization Methods 0.000 description 1
Classifications
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02P—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS
- Y02P90/00—Enabling technologies with a potential contribution to greenhouse gas [GHG] emissions mitigation
- Y02P90/30—Computing systems specially adapted for manufacturing
Landscapes
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は情報処理システムにおける多資源システムスケ
ジューリング方式に関し、特に３つ以上の複数の資源を
持ち一定の処理を行う処理システムの処理タスク（その
処理システムにおける全体の処理を構成する個々の処理
単位。電子計算機の分野におけるプロセスを意味するタ
スクではない）を資源に割り当てるスケジューリングを
自動的に行う多資源システムスケジューリング方式に間
する。
ジューリング方式に関し、特に３つ以上の複数の資源を
持ち一定の処理を行う処理システムの処理タスク（その
処理システムにおける全体の処理を構成する個々の処理
単位。電子計算機の分野におけるプロセスを意味するタ
スクではない）を資源に割り当てるスケジューリングを
自動的に行う多資源システムスケジューリング方式に間
する。
例えば、「複数の製品の製造」という処理を行う「工場
」という処理システムにおいて、「製造ライン」という
資源に「製造に要する時間」という負荷を持つ「個々の
製品の製造」という処理タスクを全製品の製造時間をで
きるだけ短くするように割り当てる場合のスケジューリ
ングを自動的に行う方式が該当する。
」という処理システムにおいて、「製造ライン」という
資源に「製造に要する時間」という負荷を持つ「個々の
製品の製造」という処理タスクを全製品の製造時間をで
きるだけ短くするように割り当てる場合のスケジューリ
ングを自動的に行う方式が該当する。
元来、多資源システムにおけるスケジューリングは、人
間の勘に軒って人手で行われるのが一般的であった。し
かし、人手によると、人件費に多くを要し、スケジュー
リングのためのノウハウがスケジューリングの担当者の
閉した情報となり担当者が交替した場合にはスケジュー
リング結果の効率（スケジューリングがなされた処理シ
ステムの処理の効率）が大幅に低下するという問題点が
あった。そこで、電子計算機を用いた情報処理システム
によって自動的に多資源システムにおけるスケジューリ
ングを行う多資源システムスケジューリング方式が採用
されるようになった。
間の勘に軒って人手で行われるのが一般的であった。し
かし、人手によると、人件費に多くを要し、スケジュー
リングのためのノウハウがスケジューリングの担当者の
閉した情報となり担当者が交替した場合にはスケジュー
リング結果の効率（スケジューリングがなされた処理シ
ステムの処理の効率）が大幅に低下するという問題点が
あった。そこで、電子計算機を用いた情報処理システム
によって自動的に多資源システムにおけるスケジューリ
ングを行う多資源システムスケジューリング方式が採用
されるようになった。
従来、この種の多資源システムスケジューリング方式で
は、全てのスケジューリングの可能性が試験され考察さ
れた上で、最終的なスケジューリングが決定される方式
が行われていた。
は、全てのスケジューリングの可能性が試験され考察さ
れた上で、最終的なスケジューリングが決定される方式
が行われていた。
上述した従来の多資源システムスケジューリング方式で
は、全てのスケジューリングの可能性が試験され考察さ
れた上で最終的なスケジューリングが決定されるので、
資源数をｎ（正整数）とし処理タスク数をｍ（正整数）
とするとｎｍのオーダでスケジューリングのための試験
回数が増加することとなり、処理タスクを実用的なレベ
ルで多く持つ処理システムのスケジューリングでは実質
的には実行不可能な程度にスケジューリング処理時間を
要することになるという欠点がある。
は、全てのスケジューリングの可能性が試験され考察さ
れた上で最終的なスケジューリングが決定されるので、
資源数をｎ（正整数）とし処理タスク数をｍ（正整数）
とするとｎｍのオーダでスケジューリングのための試験
回数が増加することとなり、処理タスクを実用的なレベ
ルで多く持つ処理システムのスケジューリングでは実質
的には実行不可能な程度にスケジューリング処理時間を
要することになるという欠点がある。
本発明の目的は、上述の点に鑑み、スケジューリングに
要する処理時間を短縮することができる多資源システム
スケジューリング方式を提供することにある。
要する処理時間を短縮することができる多資源システム
スケジューリング方式を提供することにある。
本発明の多資源システムスケジューリング方式は、複数
の資源を持ち処理を行う処理システムにおける処理タス
クを資源に割り当てるスケジューリングを自動的に行う
多資源システムスケジューリング方式おいて、スケジュ
ーリングの初めに処理タスクを複数の資源に平均的に割
り当てる平均割り当て手段と、処理タスクの交換を行う
２つの資源を選択する処理タスク交換資源選択手段と、
この処理タスク交換資源選択手段により選択された両資
源に割り当てられている処理タスクの１つずつを交換し
た後の両資源の評価値を求める処理タスク交換評価手段
と、この処理タスク交換評価手段により求められた評価
値に基づき前記処理タスク交換資源選択手段により選択
された両資源の評価値の差が最小になる処理タスクの交
換を選択して実際にその交換を行う処理タスク交換手段
と、前記処理タスク交換手段による処理の後に行われる
前記処理タスク交換資源選択手段による資源の選択が有
効か否かを評価する資源選択評価手段とを有する。
の資源を持ち処理を行う処理システムにおける処理タス
クを資源に割り当てるスケジューリングを自動的に行う
多資源システムスケジューリング方式おいて、スケジュ
ーリングの初めに処理タスクを複数の資源に平均的に割
り当てる平均割り当て手段と、処理タスクの交換を行う
２つの資源を選択する処理タスク交換資源選択手段と、
この処理タスク交換資源選択手段により選択された両資
源に割り当てられている処理タスクの１つずつを交換し
た後の両資源の評価値を求める処理タスク交換評価手段
と、この処理タスク交換評価手段により求められた評価
値に基づき前記処理タスク交換資源選択手段により選択
された両資源の評価値の差が最小になる処理タスクの交
換を選択して実際にその交換を行う処理タスク交換手段
と、前記処理タスク交換手段による処理の後に行われる
前記処理タスク交換資源選択手段による資源の選択が有
効か否かを評価する資源選択評価手段とを有する。
本発明の多資源システムスケジューリング方式では、平
均割り当て手段がスケジューリングの初めに処理タスク
を複数の資源に平均的に割り当て、処理タスク交換資源
選択手段が処理タスクの交換を行う２つの資源を選択し
、処理タスク交換評価手段が処理タスク交換資源選択手
段により選択された両資源に割り当てられている処理タ
スクの１つずつを交換した後の両資源の評価値を求め、
処理タスク交換手段が処理タスク交換評価手段により求
められた評価値に基づき処理タスク交換資源選択手段に
より選択された両資源の評価値の差が最小になる処理タ
スクの交換を選択して実際にその交換を行い、資源選択
評価手段が処理タスク交換手段による処理の後に行われ
る処理タスク交換資源選択手段による資源の選択が有効
か否かを評価する。
均割り当て手段がスケジューリングの初めに処理タスク
を複数の資源に平均的に割り当て、処理タスク交換資源
選択手段が処理タスクの交換を行う２つの資源を選択し
、処理タスク交換評価手段が処理タスク交換資源選択手
段により選択された両資源に割り当てられている処理タ
スクの１つずつを交換した後の両資源の評価値を求め、
処理タスク交換手段が処理タスク交換評価手段により求
められた評価値に基づき処理タスク交換資源選択手段に
より選択された両資源の評価値の差が最小になる処理タ
スクの交換を選択して実際にその交換を行い、資源選択
評価手段が処理タスク交換手段による処理の後に行われ
る処理タスク交換資源選択手段による資源の選択が有効
か否かを評価する。
〔実施例〕
次に、本発明について図面を参照して詳細に説明する。
第１図は、本発明の多資源システムスケジューリング方
式の一実施例の構成を示すブロック図である。本実施例
の多資源システムスケジューリング方式は、平均割り当
て手段１と、処理タスク交換資源選択手段２と、処理タ
スク交換評価手段３と、処理タスク交換手段４と、資源
選択評価手段５とを含んで構成されている。
式の一実施例の構成を示すブロック図である。本実施例
の多資源システムスケジューリング方式は、平均割り当
て手段１と、処理タスク交換資源選択手段２と、処理タ
スク交換評価手段３と、処理タスク交換手段４と、資源
選択評価手段５とを含んで構成されている。
第２図は、本実施例の多資源システムスケジューリング
方式の処理を示す流れ図である。この処理は、初期化処
理ステップ２１と、平均的割り当てステップ２２と、資
源選択ステップ２３と、交換評価値夏山ステップ２４と
、全交換評価終了判定ステップ２５と、交換ステップ２
６と、評価値改良判定ステップ２７と、再交換ステップ
２８と、資源選択ステップ２９と、選択評価ステップ３
０と、終了処理ステップ３１とからなる。
方式の処理を示す流れ図である。この処理は、初期化処
理ステップ２１と、平均的割り当てステップ２２と、資
源選択ステップ２３と、交換評価値夏山ステップ２４と
、全交換評価終了判定ステップ２５と、交換ステップ２
６と、評価値改良判定ステップ２７と、再交換ステップ
２８と、資源選択ステップ２９と、選択評価ステップ３
０と、終了処理ステップ３１とからなる。
次に、このように構成された本実施例の多資源システム
スケジューリング方式の動作について説明する。
スケジューリング方式の動作について説明する。
平均割り当て手段１は、スケジューリング対象の資源お
よび処理タスクに関する情報を入力してスケジューリン
グの準備を行う初期化処理を行う（ステップ２１）。
よび処理タスクに関する情報を入力してスケジューリン
グの準備を行う初期化処理を行う（ステップ２１）。
さらに、平均割り当て手段１は、後述する一連のスケジ
ューリング処理の前作業として、とりあえず全ての処理
タスクを各資源に平均的に（各資源に割り当てられる処
理タスク数が可能な限り同一になるように）割り当てる
（ステップ２２）。
ューリング処理の前作業として、とりあえず全ての処理
タスクを各資源に平均的に（各資源に割り当てられる処
理タスク数が可能な限り同一になるように）割り当てる
（ステップ２２）。
処理タスク交換資源選択手段２は、平均割り当て手段１
により処理タスクが割り当てられた各資源を評価し、評
価値が最大の資源と最小の資源とを「処理タスクの交換
を行う２つの資源」として選択する（ステップ２３）。
により処理タスクが割り当てられた各資源を評価し、評
価値が最大の資源と最小の資源とを「処理タスクの交換
を行う２つの資源」として選択する（ステップ２３）。
ここで、「資源の評価値」とは、その資源に割り当てら
れた処理タスクの負荷（処理タスクを行うに要する処理
量。例えば、「個々の製品の製造」が処理タスクである
場合のその製造に要する時間）の和をいう。
れた処理タスクの負荷（処理タスクを行うに要する処理
量。例えば、「個々の製品の製造」が処理タスクである
場合のその製造に要する時間）の和をいう。
処理タスク交換評価手段３は、処理タスク交換資源選択
手段２によって選択された交換対象の２つの資源に割り
当てられている処理タスクを両資源について１つずつ抽
出し、抽出した２つの処理タスクを交換した後の両資源
の評価値を求める（ステップ２４）。
手段２によって選択された交換対象の２つの資源に割り
当てられている処理タスクを両資源について１つずつ抽
出し、抽出した２つの処理タスクを交換した後の両資源
の評価値を求める（ステップ２４）。
さらに、処理タスク交換評価手段３は、ステップ２４の
評価を全ての交換について行ったか否かを判定しくステ
ップ２５）、まだ全ての交換の評価が終了していない場
合には両資源から抽出される処理タスクの組み合わせを
変更してステップ２４の評価を繰り返し、全ての交換の
評価が終了している場合には処理タスク交換手段４に制
御を渡す、このようにして、ステップ２３またはステッ
プ２９（後述参照）で選択された２つの資源にステップ
２２またはステップ２６（後述参照）で割り当てられて
いる全ての処理タスクに関する交換に基づく評価が繰り
返して実行される。
評価を全ての交換について行ったか否かを判定しくステ
ップ２５）、まだ全ての交換の評価が終了していない場
合には両資源から抽出される処理タスクの組み合わせを
変更してステップ２４の評価を繰り返し、全ての交換の
評価が終了している場合には処理タスク交換手段４に制
御を渡す、このようにして、ステップ２３またはステッ
プ２９（後述参照）で選択された２つの資源にステップ
２２またはステップ２６（後述参照）で割り当てられて
いる全ての処理タスクに関する交換に基づく評価が繰り
返して実行される。
処理タスク交換手段４は、処理タスク交換評価手段３に
より試行され評価された交換の中で処理タスク交換後の
両資源の評価値の差が最小となる交換を選択して実際に
その交換を行う（ステップ２６）。
より試行され評価された交換の中で処理タスク交換後の
両資源の評価値の差が最小となる交換を選択して実際に
その交換を行う（ステップ２６）。
さらに、処理タスク交換手段４は、ステップ２６で実行
した交換によって両資源の評価値の差が交換前よりも小
さくなったか否かを判定する（ステップ２７）。
した交換によって両資源の評価値の差が交換前よりも小
さくなったか否かを判定する（ステップ２７）。
この判定で小さくなった場合には、同じ２つの資源に関
してさらに最適な処理タスクの交換を探すために、処理
タスク交換手段４は処理タスク交換評価手段３によるス
テップ２４の処理に制御を戻す。
してさらに最適な処理タスクの交換を探すために、処理
タスク交換手段４は処理タスク交換評価手段３によるス
テップ２４の処理に制御を戻す。
ステップ２７の判定で小さくならなかった場合には、処
理タスク交換手段４はステップ２６で実行した交換を無
効にするために交換前の状態に戻しくステップ２８）、
処理タスク交換資源選択手段２に制御を渡す。
理タスク交換手段４はステップ２６で実行した交換を無
効にするために交換前の状態に戻しくステップ２８）、
処理タスク交換資源選択手段２に制御を渡す。
処理タスク交換資源選択手段２は、その時点における各
資源を評価し、評価値が最大の資源と最小の資源とを「
処理タスクの交換を行う２つの責 ・源」として選択
しくステップ２９）、資源選択評価手段５に制御を渡す
。
資源を評価し、評価値が最大の資源と最小の資源とを「
処理タスクの交換を行う２つの責 ・源」として選択
しくステップ２９）、資源選択評価手段５に制御を渡す
。
資源選択評価手段５は、ステップ２９で選択された２つ
の資源が前回にステップ２３またはステップ２９で選択
された２つの資源と同じか否かを判定してステップ２９
における選択の有効性を評価する（ステップ３０）。
の資源が前回にステップ２３またはステップ２９で選択
された２つの資源と同じか否かを判定してステップ２９
における選択の有効性を評価する（ステップ３０）。
ステップ３０の判定で両者が違う場合（ステップ２９に
おける選択が有効である場合）には、ステ、ブ２９で選
択された新たな２つの資源に関して最適な処理タスクの
交換を探すために、資源選択評価手段５は処理タスク交
換評価手段３によるステップ２４の処理に制御を戻す。
おける選択が有効である場合）には、ステ、ブ２９で選
択された新たな２つの資源に関して最適な処理タスクの
交換を探すために、資源選択評価手段５は処理タスク交
換評価手段３によるステップ２４の処理に制御を戻す。
ステップ３０の判定で両者が同じ場合（ステップ２９に
おける選択が有効でない場合）には、資源選択評価手段
５はその時点における各資源への各処理タスクの割り当
ての状態を最適なスケジューリング結果として出力する
終了処理を行う（ステップ３１）。
おける選択が有効でない場合）には、資源選択評価手段
５はその時点における各資源への各処理タスクの割り当
ての状態を最適なスケジューリング結果として出力する
終了処理を行う（ステップ３１）。
以上説明したように本発明は、複数の資源を持ち一定の
処理を行う処理システムにおいて、−旦平均的に各資源
に処理タスクを割り当てた状態からスケジューリングを
始めることと、評価値に基づいて処理タスクを交換する
対象の２つの資源を選択してそれらの資源だけで最適化
を試みることとにより、一定の効率を持つスケジューリ
ング結果を得るためのスケジューリングに要する処理時
間を短縮することができるという効果がある。
処理を行う処理システムにおいて、−旦平均的に各資源
に処理タスクを割り当てた状態からスケジューリングを
始めることと、評価値に基づいて処理タスクを交換する
対象の２つの資源を選択してそれらの資源だけで最適化
を試みることとにより、一定の効率を持つスケジューリ
ング結果を得るためのスケジューリングに要する処理時
間を短縮することができるという効果がある。
第１図は本発明の一実施例の構成を示すブロック図、
第２図は第１図に示す多資源システムスケジューリング
方式の処理を示す流れ図である。 図において、 ■・・・平均割り当て手段、 ２・・・処理タスク交換資源選択手段、３・・・処理タ
スク交換評価手段、 ４・・・処理タスク交換手段、 ５・・・資源選択評価手段である。
方式の処理を示す流れ図である。 図において、 ■・・・平均割り当て手段、 ２・・・処理タスク交換資源選択手段、３・・・処理タ
スク交換評価手段、 ４・・・処理タスク交換手段、 ５・・・資源選択評価手段である。
Claims (1)
- 【特許請求の範囲】 複数の資源を持ち処理を行う処理システムにおける処理
タスクを資源に割り当てるスケジューリングを自動的に
行う多資源システムスケジューリング方式おいて、 スケジューリングの初めに処理タスクを複数の資源に平
均的に割り当てる平均割り当て手段と、処理タスクの交
換を行う２つの資源を選択する処理タスク交換資源選択
手段と、 この処理タスク交換資源選択手段により選択された両資
源に割り当てられている処理タスクの１つずつを交換し
た後の両資源の評価値を求める処理タスク交換評価手段
と、 この処理タスク交換評価手段により求められた評価値に
基づき前記処理タスク交換資源選択手段により選択され
た両資源の評価値の差が最小になる処理タスクの交換を
選択して実際にその交換を行う処理タスク交換手段と、 前記処理タスク交換手段による処理の後に行われる前記
処理タスク交換資源選択手段による資源の選択が有効か
否かを評価する資源選択評価手段と を有することを特徴とする多資源システムスケジューリ
ング方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2302930A JPH04177457A (ja) | 1990-11-08 | 1990-11-08 | 多資源システムスケジューリング方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2302930A JPH04177457A (ja) | 1990-11-08 | 1990-11-08 | 多資源システムスケジューリング方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH04177457A true JPH04177457A (ja) | 1992-06-24 |
Family
ID=17914846
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2302930A Pending JPH04177457A (ja) | 1990-11-08 | 1990-11-08 | 多資源システムスケジューリング方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH04177457A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110688204A (zh) * | 2019-08-08 | 2020-01-14 | 平安科技（深圳）有限公司 | 分布式计算系统任务分配方法及相关设备 |
-
1990
- 1990-11-08 JP JP2302930A patent/JPH04177457A/ja active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110688204A (zh) * | 2019-08-08 | 2020-01-14 | 平安科技（深圳）有限公司 | 分布式计算系统任务分配方法及相关设备 |
| CN110688204B (zh) * | 2019-08-08 | 2022-08-26 | 平安科技（深圳）有限公司 | 分布式计算系统任务分配方法及相关设备 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7079266B1 (en) | Printshop resource optimization via the use of autonomous cells | |
| Gong et al. | Performance modeling and prediction of nondedicated network computing | |
| US6487455B1 (en) | Distributed real time operating system | |
| KR101733117B1 (ko) | 멀티코어 시스템의 태스크 분배 방법 및 장치 | |
| WO2015117565A1 (en) | Methods and systems for dynamically allocating resources and tasks among database work agents in smp environment | |
| CN113886034A (zh) | 任务调度方法、系统、电子设备及存储介质 | |
| KR102029378B1 (ko) | 생산 스케줄링 시스템 | |
| JP3541212B2 (ja) | プロセッサ割当て装置 | |
| Yadav et al. | A fuzzy clustering method to minimize the inter task communication effect for optimal utilization of processor’s capacity in distributed real time systems | |
| Ramamritham et al. | Issues in the static allocation and scheduling of complex periodic tasks | |
| US20040093477A1 (en) | Scalable parallel processing on shared memory computers | |
| JP2023171264A (ja) | 分散型異機種混在システムに基づくタスクインテリジェント処理方法 | |
| JPH04177457A (ja) | 多資源システムスケジューリング方式 | |
| KR20050057834A (ko) | 멀티프로세서 시스템에서 스케줄러를 이용한 대규모데이터 처리 방법 | |
| CN115904724B (zh) | 线程分配方法、装置、存储介质及计算机设备 | |
| Mohamed | A flexible approach to (re) configure flexible manufacturing cells | |
| CN114584567B (zh) | 基于区块链的批量作业处理方法及装置 | |
| Sim et al. | Simulation of a multi-agent protocol for task allocation in cooperative design | |
| EP1076275B1 (en) | Distributed real-time operating system | |
| JPH0496141A (ja) | ２資源システムスケジューリング方式 | |
| JPH11195007A (ja) | 分散処理システム及び分散処理方法 | |
| CN115361287B (zh) | 一种边缘节点流量调度方法及装置 | |
| Alelyani et al. | DAScheduler: Dependency-Aware Scheduling Algorithm for Containerized Dependent Jobs: A. Alelyani et al. | |
| CN112395088B (zh) | 任务调度方法、装置、设备及存储介质 | |
| Jayakumar et al. | An Heuristic approach for solving OSSP with the objective of minimizing the Total Completion Time |