JPH01240973A - ワーク割付方式 - Google Patents
ワーク割付方式Info
- Publication number
- JPH01240973A JPH01240973A JP63067443A JP6744388A JPH01240973A JP H01240973 A JPH01240973 A JP H01240973A JP 63067443 A JP63067443 A JP 63067443A JP 6744388 A JP6744388 A JP 6744388A JP H01240973 A JPH01240973 A JP H01240973A
- Authority
- JP
- Japan
- Prior art keywords
- schedule
- work
- violation
- period
- constraint
- 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
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/02—Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
-
- 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
- Multi-Process Working Machines And Systems (AREA)
- General Factory Administration (AREA)
- Feedback Control In General (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は、各種スケジューリング問題を解く計算機シス
テムに係り、特に、必ず守らなければならない制約条件
、できれば守りたい制約条件等が存在する制約条件があ
いまいな場合のスケジュール作成に好適なワーク割付方
式に関する。
テムに係り、特に、必ず守らなければならない制約条件
、できれば守りたい制約条件等が存在する制約条件があ
いまいな場合のスケジュール作成に好適なワーク割付方
式に関する。
スケジューリング問題は、一般に順列組合せの問題であ
り、定式化して数学的手法で解くことは困難である。そ
こで、従来から、対象とする問題毎に、その問題個有の
スケジュール立案のノウハウ、条件を全てのプログラム
化し、スケジュールを作成する方式がとられていること
が多い。しかし、上記方式では、スケジュール作成のノ
ウハウ。
り、定式化して数学的手法で解くことは困難である。そ
こで、従来から、対象とする問題毎に、その問題個有の
スケジュール立案のノウハウ、条件を全てのプログラム
化し、スケジュールを作成する方式がとられていること
が多い。しかし、上記方式では、スケジュール作成のノ
ウハウ。
条件の変更に迅速に対応できないという問題がある。こ
の問題を解決する方式として、最近、知識工学技術を応
用し、スケジュール作成のノウハウ、条件の変更に迅速
に対応できる様、スケジュール作成のノウハウ、条件を
知識ベース化し、シミュレーション的に解く方式が考え
られている。上記方式の例としては、情報処理学会第３
３回（昭和６１年後期）全国大会講演論文集Ｈの１１６
５頁から１１６６頁に述べられている。この方法では。
の問題を解決する方式として、最近、知識工学技術を応
用し、スケジュール作成のノウハウ、条件の変更に迅速
に対応できる様、スケジュール作成のノウハウ、条件を
知識ベース化し、シミュレーション的に解く方式が考え
られている。上記方式の例としては、情報処理学会第３
３回（昭和６１年後期）全国大会講演論文集Ｈの１１６
５頁から１１６６頁に述べられている。この方法では。
ワークを１つずつ割付け、制約条件違反が発生した場合
は、バックトラックしなから制約条件違反を回避しスケ
ジュールを作成している。制約条件違反を回避できない
場合は、違反が許される範囲であればこれを割付けてい
る。
は、バックトラックしなから制約条件違反を回避しスケ
ジュールを作成している。制約条件違反を回避できない
場合は、違反が許される範囲であればこれを割付けてい
る。
上記従来技術の様に、ワークを一つずつ着目し順次割付
けている方式では、制約条件違反が発生した場合、バッ
クトラックにより違反を回避できるか、違反して割付け
ないと解がないのか否か、の判断が困難である。そのた
め、不要なバックトラックを繰返すことにより、スケジ
ュール作成に多大な時間を要すという問題があった。ま
た、違反して割付けるにしても、どの制約条件をゆるめ
るのが良いかの判断が困難であり、全体としては、軽度
の違反で済むスケジュールであっても、重大な違反をし
たスケジュール結果を作ってしまうという問題があった
。更に、バックトラックの発生に伴って計算時間もスケ
ジュール条件によって不安定であるという問題があった
。
けている方式では、制約条件違反が発生した場合、バッ
クトラックにより違反を回避できるか、違反して割付け
ないと解がないのか否か、の判断が困難である。そのた
め、不要なバックトラックを繰返すことにより、スケジ
ュール作成に多大な時間を要すという問題があった。ま
た、違反して割付けるにしても、どの制約条件をゆるめ
るのが良いかの判断が困難であり、全体としては、軽度
の違反で済むスケジュールであっても、重大な違反をし
たスケジュール結果を作ってしまうという問題があった
。更に、バックトラックの発生に伴って計算時間もスケ
ジュール条件によって不安定であるという問題があった
。
本発明の目的は、上記問題点を解決して、質の良いスケ
ジュールを高速かつ安定した時間で作成できるワーク割
付方式を提供することにある。
ジュールを高速かつ安定した時間で作成できるワーク割
付方式を提供することにある。
上記目的は、ワークのスケジュール作成時に、制約条件
違反の重要度を評価し、ワークを一括して割付ける機能
を設けることにより達成される。
違反の重要度を評価し、ワークを一括して割付ける機能
を設けることにより達成される。
具体的には、（１）スケジュール期間を部分期間に分割
する手段、（２）該部分期間において、ワークと装置の
組合せの好ましさを評価する手段、（３）部分期間のワ
ークについて、総合的に判断し、上記評価が最大となる
組合せを計算する手段を設ける。
する手段、（２）該部分期間において、ワークと装置の
組合せの好ましさを評価する手段、（３）部分期間のワ
ークについて、総合的に判断し、上記評価が最大となる
組合せを計算する手段を設ける。
前記手段は、以下の様に動作する。
ワークと装置が１対１に対応する部分期間に分割するこ
とにより、数理計画の割当アルゴリズムを適用し、制約
条件違反なしで解があるものについては解を算出できる
。制約条件違反をしないとスケジュールができない場合
、制約条件違反の重要度の評価ができるので、できるだ
け軽度の違反、できるだけ違反の少ない範囲でスケジュ
ールを作成することができる。これにより、質の良いス
ケジュールを高速かつ安定した時間で作成できる。
とにより、数理計画の割当アルゴリズムを適用し、制約
条件違反なしで解があるものについては解を算出できる
。制約条件違反をしないとスケジュールができない場合
、制約条件違反の重要度の評価ができるので、できるだ
け軽度の違反、できるだけ違反の少ない範囲でスケジュ
ールを作成することができる。これにより、質の良いス
ケジュールを高速かつ安定した時間で作成できる。
以下、本発明の一実施例を製造装置へのワークへ割当て
を例として、第１図〜第６図により説明する。第１図は
、本発明の全体構成を示す。１１は本システムを制御す
るための計算機であり、部分期間決定部１０１．ワーク
制約違反の重要度決定部１０２、割付討算部１０３、ス
ケジュール結果の表示部１０４で構成される６１２は、
スケジュール結果を表示するためのデイスプレィ装置で
あり、キーボード、マウス、トラックボール等の入力装
置を有する、１３は、スケジュール対象データを格納す
る装置、１４は、スケジュール立案のノウハウを格納す
る装置、１５はスケジュール作成の制約条件を格納する
装置、１６は、スケジュール結果を格納する装置である
。
を例として、第１図〜第６図により説明する。第１図は
、本発明の全体構成を示す。１１は本システムを制御す
るための計算機であり、部分期間決定部１０１．ワーク
制約違反の重要度決定部１０２、割付討算部１０３、ス
ケジュール結果の表示部１０４で構成される６１２は、
スケジュール結果を表示するためのデイスプレィ装置で
あり、キーボード、マウス、トラックボール等の入力装
置を有する、１３は、スケジュール対象データを格納す
る装置、１４は、スケジュール立案のノウハウを格納す
る装置、１５はスケジュール作成の制約条件を格納する
装置、１６は、スケジュール結果を格納する装置である
。
以下、装置の稼動時間の制約条件を例に本発明の一実施
例を、第２図に示すフローチャートの動作ステップに従
って詳細に説明する。
例を、第２図に示すフローチャートの動作ステップに従
って詳細に説明する。
ステップ２０１ニジステムは、スケジュール結果の記憶
装置１６上のスケジュール結果をデイスプレィ装置に表
示し、ステップ２０２八進む。
装置１６上のスケジュール結果をデイスプレィ装置に表
示し、ステップ２０２八進む。
ステップ２０２ニジステムは、スケジュール作成が完了
したか否かを判定する。完了の場合は、システムを終了
し、完了していない場合は、ステップ２０３八進む。
したか否かを判定する。完了の場合は、システムを終了
し、完了していない場合は、ステップ２０３八進む。
ステップ２ｏ３ニジステムは、記憶装置１４に格納され
ているスケジュール作成のノウハウを基に、スケジュー
ルを作成する期間（以下５部分期間と呼ぶ）、例えば、
第３図に示す様に、製造装置１台に高々１つのワークし
か割付けられない期間を決定する。第３図では、］−６
日〜１８日が部分期間となる。次にステップ２０４へ進
む。
ているスケジュール作成のノウハウを基に、スケジュー
ルを作成する期間（以下５部分期間と呼ぶ）、例えば、
第３図に示す様に、製造装置１台に高々１つのワークし
か割付けられない期間を決定する。第３図では、］−６
日〜１８日が部分期間となる。次にステップ２０４へ進
む。
ステップ２０４ニジステムは、記憶装置１４に格納され
ているスケジュール対象データから、部分期間に割付可
能な装置１割付けるべきワークを検索し、第４図に示す
、ワーク格納テーブルに格納する。
ているスケジュール対象データから、部分期間に割付可
能な装置１割付けるべきワークを検索し、第４図に示す
、ワーク格納テーブルに格納する。
次にステップ２０５へ進む。
ステップ２０５ニジステムは、記憶装置１５に格納され
ているスケジュール作成上の制約条件を検索する。第５
図は、装置の稼動時間に関する制約条件のテーブルの一
例である。５０１は装置名、５０２は装置の使用実績、
５０３は稼動時間の制限値、５０４は制限値を超えて稼
動させる場合の限界値である。次に、ステップ２０６へ
進む。
ているスケジュール作成上の制約条件を検索する。第５
図は、装置の稼動時間に関する制約条件のテーブルの一
例である。５０１は装置名、５０２は装置の使用実績、
５０３は稼動時間の制限値、５０４は制限値を超えて稼
動させる場合の限界値である。次に、ステップ２０６へ
進む。
ステップ２０６：システムは、ステップ２０５で検索し
た制約条件を基に、ワークの制約条件違反の重要度を決
定する。重要度は、例えば、制限時間内でワークを割付
できる、限界値は超えないが割付できる、限界値を超え
るといった順に評価する。次に、ステップ２０７へ進む
。
た制約条件を基に、ワークの制約条件違反の重要度を決
定する。重要度は、例えば、制限時間内でワークを割付
できる、限界値は超えないが割付できる、限界値を超え
るといった順に評価する。次に、ステップ２０７へ進む
。
ステップ２０７：システムは、ステップ２０６で決定し
た重要度を数値化し第６図に示す様なマトリックスを作
成する。本実施例では、装置ａに対して、 （１）制限時間内に割付けられるワークＡ→１０点 （２）制限時間を超えるが限界は超えずに割付けられる
ワークＢ→７点 （３）上記（２）と同様であるが、制限時間をワークＢ
より大きく超えるワークＣ−５点 （４）限界値を超えてしまうワークＤ→○点としている
。次に、ステップ２０８に進む。
た重要度を数値化し第６図に示す様なマトリックスを作
成する。本実施例では、装置ａに対して、 （１）制限時間内に割付けられるワークＡ→１０点 （２）制限時間を超えるが限界は超えずに割付けられる
ワークＢ→７点 （３）上記（２）と同様であるが、制限時間をワークＢ
より大きく超えるワークＣ−５点 （４）限界値を超えてしまうワークＤ→○点としている
。次に、ステップ２０８に進む。
ステップ２０８ニジステムは、ステップ２０７で求めた
マトリックスを、数理計画の割当問題として、マトリク
スの各要素の値の合計が最大になる組合せを求める。次
にステップ２０１に戻る。
マトリックスを、数理計画の割当問題として、マトリク
スの各要素の値の合計が最大になる組合せを求める。次
にステップ２０１に戻る。
本実施例の場合、線形計画法における割当て問題として
解く際に、制限時間の制約条件に対する違反の程度に応
じて評点を分けている。これにより、違反が発生せざる
を得なくなった時に、全体として、評点の高い軽度の違
反のワークを割付ける。これにより、質の良いかつ効率
の良いスケジュールが作成できる。
解く際に、制限時間の制約条件に対する違反の程度に応
じて評点を分けている。これにより、違反が発生せざる
を得なくなった時に、全体として、評点の高い軽度の違
反のワークを割付ける。これにより、質の良いかつ効率
の良いスケジュールが作成できる。
また、評点の決定は、例えば、次の様にすれば良い。今
、制約条件Ａ、Ｂがあるとする。スケジュール全体から
みて、Ａの違反が２つある場合とＢの違反１つある場合
が同等であるならば、Ａの違反・・・５点滅点、Ｂの違
反・・・１０点減点とする。
、制約条件Ａ、Ｂがあるとする。スケジュール全体から
みて、Ａの違反が２つある場合とＢの違反１つある場合
が同等であるならば、Ａの違反・・・５点滅点、Ｂの違
反・・・１０点減点とする。
本発明によれば、スケジュール作成の際に、全体のスケ
ジュールのバランスを総合評価し、−括割付ができ、バ
ツクトラツ゛り、既に最適割付をされている部分の再割
付といったワークの割付やり直しが少ないので、質の良
いスケジュールを作成することができる。すなわち、ス
ケジュール作成時の違反の発生を少なくし、しかも発生
する違反を軽度にすることができる。
ジュールのバランスを総合評価し、−括割付ができ、バ
ツクトラツ゛り、既に最適割付をされている部分の再割
付といったワークの割付やり直しが少ないので、質の良
いスケジュールを作成することができる。すなわち、ス
ケジュール作成時の違反の発生を少なくし、しかも発生
する違反を軽度にすることができる。
また、バックトラックを抑制できるので、高速かつ安定
した時間で、質の良いスケジュールを作成できる効果が
ある。
した時間で、質の良いスケジュールを作成できる効果が
ある。
第１図は本発明の一実施例の全体植成を示すブロック図
、第２図は本発明を実現するシステムのフローチャート
、第３図は部分期間の例を示す説明図、第４図は割付ワ
ークテーブルの例を示す説明図、第５図は制約条件テー
ブルの例を示す説明図、第６図は割付計算をする為のマ
トリクス図の羊 １ 図 第２図 □ ■−−■ 第 ３ 図 ′４４ 口 手 Ｓ 図 第 乙 図
、第２図は本発明を実現するシステムのフローチャート
、第３図は部分期間の例を示す説明図、第４図は割付ワ
ークテーブルの例を示す説明図、第５図は制約条件テー
ブルの例を示す説明図、第６図は割付計算をする為のマ
トリクス図の羊 １ 図 第２図 □ ■−−■ 第 ３ 図 ′４４ 口 手 Ｓ 図 第 乙 図
Claims (1)
- １、生産工程のワークスケジユーリング等の各種スケジ
ュールを作成するシステムにおいて、作成したスケジュ
ール結果を表示する手段、スケジュール結果を記憶する
手段に加え、複数のワークを一括して割付ける際に、制
約条件違反をすることがどの程度悪いことかを評価する
手段を設けたことを特徴とするワーク割付方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63067443A JPH01240973A (ja) | 1988-03-23 | 1988-03-23 | ワーク割付方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63067443A JPH01240973A (ja) | 1988-03-23 | 1988-03-23 | ワーク割付方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH01240973A true JPH01240973A (ja) | 1989-09-26 |
Family
ID=13345075
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63067443A Pending JPH01240973A (ja) | 1988-03-23 | 1988-03-23 | ワーク割付方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH01240973A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06314271A (ja) * | 1993-05-06 | 1994-11-08 | Nec Corp | 組合せ最適化初期割付け作成方式 |
| JP2019532435A (ja) * | 2016-10-13 | 2019-11-07 | ロヴィ ガイズ， インコーポレイテッド | 広告掲載の競合を解決するためのシステムおよび方法 |
-
1988
- 1988-03-23 JP JP63067443A patent/JPH01240973A/ja active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06314271A (ja) * | 1993-05-06 | 1994-11-08 | Nec Corp | 組合せ最適化初期割付け作成方式 |
| JP2019532435A (ja) * | 2016-10-13 | 2019-11-07 | ロヴィ ガイズ， インコーポレイテッド | 広告掲載の競合を解決するためのシステムおよび方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5053970A (en) | Work scheduling method | |
| Colville | A comparative study of nonlinear programming codes | |
| US4847761A (en) | Automated bill of material | |
| Champati et al. | Automated operation sequencing in intelligent process planning: a case-based reasoning approach | |
| JP2002279132A (ja) | 要員配置システムおよび要員配置プログラム | |
| Chang | A study of factors affecting due-date predictability in a simulated dynamic job shop | |
| JPH01240973A (ja) | ワーク割付方式 | |
| CN114139925A (zh) | 一种基于三维矩阵运算的快速收敛排课算法 | |
| JPH02130678A (ja) | 製造計画作成装置 | |
| JP3225739B2 (ja) | 作業編成装置 | |
| JPH0295549A (ja) | 生産計画作成装置 | |
| Montazeri et al. | A modular simulator for design, planning, and control of flexible manufacturing systems | |
| JP3034580B2 (ja) | スケジュール作成方法 | |
| JP2709010B2 (ja) | スケジューリングのための推論方法 | |
| JPH0415865A (ja) | スケジュール作成支援装置 | |
| JP2581428B2 (ja) | 生産シミュレーション装置 | |
| Garg et al. | On the simulation run length: a step towards real time control in an FMS | |
| JPH07120335B2 (ja) | 計算機システムの階層性評価装置 | |
| Mamalis et al. | On-line scheduling in metal removal processing using variable routings and control strategies | |
| Gan et al. | Managing event traces for a web front-end to a parallel simulation | |
| JP2003015717A (ja) | 生産計画作成システムおよび方法 | |
| JPH08137949A (ja) | ガントチャートの計画変更方法 | |
| JPH04348452A (ja) | 制約条件満足化探索の多重プロセッサの実行のためのプロセッサ割当ての方法 | |
| Yang et al. | An appellate court case assignment algorithm | |
| JPH06162035A (ja) | 生産計画作成方法およびその装置 |