(57)【要約】【課題】遺伝的アルゴリズムにおける致死遺伝子に相当する実行不可能な製造計画の作成を回避でき、製造計画の作成時間を短縮させる。【解決手段】実施形態の交配部１４は、装置名に装置／品種対応条件データ内で対応する品種名を含む注文情報の作業ＩＤを表現した遺伝子の遺伝子配列からなる第一世代の製造計画データを作成する。交配部１４は、遺伝子配列毎の切断点をランダムに選択し、切断点以降の各遺伝子を、各遺伝子として表現された作業ＩＤを含む注文情報の品種名に装置／品種対応条件データ内で対応する装置名のうち、他の装置名の遺伝子配列の切断点以降の処理順に移動させて次世代の複数の製造計画データを書き込む処理を繰り返し実行する。交配部１４は、最終世代の各製造計画データについて、評価関数値を算出する。製造計画出力部１５は、評価関数値が最小である製造計画データを出力する。【選択図】図１
2011253451.tif 000002
【特許請求の範囲】
【請求項１】
読出／書込可能な記憶手段を備え、遺伝的アルゴリズムを用いて各作業の作業ＩＤを遺伝子として表現し、製造装置の装置名毎に遺伝子を処理順に並べた可変長の複数の遺伝子配列からなる製造計画データを作成する製造計画作成装置であって、
前記装置名毎に当該装置名の製造装置によって製造可能な製品の品種名を対応付けた装置／品種対応条件データを記憶する条件データ記憶手段と、
作業ＩＤ、納期、製造量及び品種名を含む注文情報と、装置名、品種名及び製造速度を含む製造装置情報と、評価関数のパラメータとを入力して前記記憶手段に書き込む入力手段と、
前記装置名毎に、当該装置名に前記装置／品種対応条件データ内で対応する品種名と同じ品種名を含む前記注文情報の作業ＩＤを表現した遺伝子、を処理順に並べた可変長の複数の遺伝子配列からなる第一世代の製造計画データを複数生成し、当該第一世代の各製造計画データを前記記憶手段に書き込む第一世代データ作成手段と、
前記記憶手段に新たに記憶された遺伝子配列毎の遺伝子間の切断点をランダムに選択し、当該切断点以降の各遺伝子を、当該各遺伝子として表現された作業ＩＤと同じ作業ＩＤを含む前記注文情報の品種名に前記装置／品種対応条件データ内で対応する装置名のうち、他の装置名の遺伝子配列における切断点以降の処理順にそれぞれ移動させることにより、次世代の複数の製造計画データを作成し、当該次世代の複数の製造計画データを前記記憶手段に書き込む交配処理を実行する交配処理実行手段と、
前記交配処理を所定回数だけ繰り返し実行するように前記交配処理実行手段を制御する制御手段と、
前記制御手段による制御の完了後、前記記憶手段に書き込まれた最終世代の各製造計画データについて、前記製造量を前記製造速度で除算した製造時間を日数に換算した製造日数と前記納期との差分を示す納期遅れと、前記パラメータとに基づいて、前記納期遅れの大きさを評価する評価関数値を算出する評価関数値算出手段と、
前記最終世代の各製造計画データのうち、前記評価関数値が最小である製造計画データを出力する製造計画出力手段と
を備えたことを特徴とする製造計画作成装置。
【請求項２】
請求項１に記載の製造計画作成装置において、
前記交配処理実行手段により書き込まれた遺伝子配列のうち、ランダムに選択した遺伝子配列から１つの遺伝子をランダムに選択し、当該選択した遺伝子を、この遺伝子が表現する作業ＩＤと同じ作業ＩＤを含む前記注文情報の品種名に前記装置／品種対応条件データ内で対応する装置名のうち、他のいずれかの装置名の遺伝子配列に移動させる突然変異処理を実行する突然変異実行手段、
を更に備え、
前記制御手段は、前記交配処理及び前記突然変異処理を所定回数だけ繰り返し実行するように前記交配処理実行手段及び前記突然変異実行手段をそれぞれ制御することを特徴とする製造計画作成装置。
【請求項３】
読出／書込可能な記憶手段及び条件データ記憶手段を備え、遺伝的アルゴリズムを用いて各作業の作業ＩＤを遺伝子として表現し、製造装置の装置名毎に遺伝子を処理順に並べた可変長の複数の遺伝子配列からなる製造計画データを作成する製造計画作成装置に用いられるプログラムであって、
前記製造計画作成装置を、
前記装置名毎に当該装置名の製造装置によって製造可能な製品の品種名を対応付けた装置／品種対応条件データを前記条件データ記憶手段に書き込む手段、
作業ＩＤ、納期、製造量及び品種名を含む注文情報と、装置名、品種名及び製造速度を含む製造装置情報と、評価関数のパラメータとを入力して前記記憶手段に書き込む入力手段、
前記装置名毎に、当該装置名に前記装置／品種対応条件データ内で対応する品種名と同じ品種名を含む前記注文情報の作業ＩＤを表現した遺伝子、を処理順に並べた可変長の複数の遺伝子配列からなる第一世代の製造計画データを複数生成し、当該第一世代の各製造計画データを前記記憶手段に書き込む第一世代データ作成手段、
前記記憶手段に新たに記憶された遺伝子配列毎の遺伝子間の切断点をランダムに選択し、当該切断点以降の各遺伝子を、当該各遺伝子として表現された作業ＩＤと同じ作業ＩＤを含む前記注文情報の品種名に前記装置／品種対応条件データ内で対応する装置名のうち、他の装置名の遺伝子配列における切断点以降の処理順にそれぞれ移動させることにより、次世代の複数の製造計画データを作成し、当該次世代の複数の製造計画データを前記記憶手段に書き込む交配処理を実行する交配処理実行手段、
前記交配処理を所定回数だけ繰り返し実行するように前記交配処理実行手段を制御する制御手段、
前記制御手段による制御の完了後、前記記憶手段に書き込まれた最終世代の各製造計画データについて、前記製造量を前記製造速度で除算した製造時間を日数に換算した製造日数と前記納期との差分を示す納期遅れと、前記パラメータとに基づいて、前記納期遅れの大きさを評価する評価関数値を算出する評価関数値算出手段、
前記最終世代の各製造計画データのうち、前記評価関数値が最小である製造計画データを出力する製造計画出力手段、
として機能させるためのプログラム。
【請求項４】
請求項３に記載のプログラムにおいて、
前記製造計画作成装置を、
前記交配処理実行手段により書き込まれた遺伝子配列のうち、ランダムに選択した遺伝子配列から１つの遺伝子をランダムに選択し、当該選択した遺伝子を、この遺伝子が表現する作業ＩＤと同じ作業ＩＤを含む前記注文情報の品種名に前記装置／品種対応条件データ内で対応する装置名のうち、他のいずれかの装置名の遺伝子配列に移動させる突然変異処理を実行する突然変異実行手段、
として更に機能させ、
前記制御手段は、前記交配処理及び前記突然変異処理を所定回数だけ繰り返し実行するように前記交配処理実行手段及び前記突然変異実行手段をそれぞれ制御することを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、製造計画作成装置及びプログラムに関する。
【背景技術】
【０００２】
工場の製造計画を作成する際に、遺伝的アルゴリズム（ＧＡ： Genetic Algorithm）が広く用いられている。遺伝的アルゴリズムを用いると、計画の目標とする事項が複数（たとえば、納期、消費電力、作業員の稼動時間など）ある複雑な条件であっても、それらを係数で指定した割合で勘案して、製造計画の作成を達成することができる。
【０００３】
遺伝的アルゴリズムで製造計画問題を扱う場合、一般的には、製造計画を遺伝子として表現し、二つの遺伝子に交配と呼ばれる操作をして次世代の計画（準最適解の候補）を作り、目的関数をよりよく満たす個体（準最適解）を見つけている。遺伝的アルゴリズムにおける交叉では、次世代の計画（子）が現世代の計画（親）の形質を一部継承するので、早く準最適解に到達する可能性が高い。
【０００４】
なお、一つの作業名の作業を処理する製造装置が一台である場合、あるいは、同じ能力の製造装置が複数台設置されている場合には、この作業の計画を、個々の作業名を一次元に並べた遺伝子で表現でき、遺伝的アルゴリズムの交配を、一般的な「一点交叉法」、「二点交叉法」又は「一様交叉法」などで実現可能となっている。
【０００５】
また、遺伝的アルゴリズムでは、交叉法による操作に限らず、突然変異と呼ばれる操作を実行可能となっている。突然変異の方法として「摂動」、「逆位」、「スクランブル」、「転座」、「重複」、「位置移動」、「挿入」及び「欠失」などが知られている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第４３６９１８９号公報
【特許文献２】特許第４３１３４９１号公報
【非特許文献】
【０００７】
【非特許文献１】“遺伝的アルゴリズム（GA: Genetic Algorithm）”、[online]、［平成２２年５月６日検索］、インターネット＜URL：http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/GA/GA.htm＞
【非特許文献２】“遺伝的アルゴリズム Introduction to Genetic Algorithms”、[online]、［平成２２年５月６日検索］、インターネット＜URL：http://www.obitko.com/tutorials/genetic-algorithms/japanese/index.php＞
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、以上のような遺伝的アルゴリズムにおいては、複数の作業名の各作業を処理する製造装置が複数台設置されており、作業名の品種に応じて、作業名の作業を処理できる製造装置と処理できない製造装置がそれぞれあることになる。そして、処理できる製造装置の中でも処理能力に差がある場合には、一般的な交叉法で交配を実現できる遺伝子表現と交叉法が知られていない。
【０００９】
このような場合に公知の交叉法を用いると、交配によってできた子孫の製造計画が実行不可能な「致死遺伝子」となる確率が高い。このため、遺伝的アルゴリズムの実行時間が長くなってしまう。
【００１０】
突然変異についても「逆位」、「スクランブル」又は「転座」などを単純に実行する場合、作業の移動先がその作業を処理できない製造装置となる可能性が高いため、前述同様に、子孫の製造計画が致死遺伝子となる確率が高い。
【００１１】
本明細書に開示する実施形態は、遺伝的アルゴリズムにおける致死遺伝子に相当する実行不可能な製造計画の作成を回避でき、製造計画の作成時間を短縮し得る製造計画作成装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
以下で説明する本発明の実施形態の製造計画作成装置は、読出／書込可能な作業用製造計画記憶部を備え、遺伝的アルゴリズムを用いて各作業の作業ＩＤを遺伝子として表現し、製造装置の装置名毎に遺伝子を処理順に並べた可変長の複数の遺伝子配列からなる製造計画データを作成するものである。
【００１３】
例えば、実施形態の製造計画作成装置は、条件データ記憶部、作業用製造計画記憶部、入力部、交配部及び製造計画出力部を備えている。
【００１４】
実施形態の条件データ記憶部は、装置名毎に当該装置名の製造装置によって製造可能な製品の品種名を対応付けた装置／品種対応条件データを記憶する。
【００１５】
実施形態の入力部は、作業ＩＤ、納期、製造量及び品種名を含む注文情報と、装置名、品種名及び製造速度を含む製造装置情報と、評価関数のパラメータとを入力して作業用製造計画記憶部に書き込む。
【００１６】
実施形態の交配部は、装置名毎に、当該装置名に装置／品種対応条件データ内で対応する品種名と同じ品種名を含む注文情報の作業ＩＤを表現した遺伝子、を処理順に並べた可変長の複数の遺伝子配列からなる第一世代の製造計画データを複数生成し、当該第一世代の各製造計画データを作業用製造計画記憶部に書き込む。
【００１７】
また、実施形態の交配部は、作業用製造計画記憶部に新たに記憶された遺伝子配列毎の遺伝子間の切断点をランダムに選択し、当該切断点以降の各遺伝子を、当該各遺伝子として表現された作業ＩＤと同じ作業ＩＤを含む注文情報の品種名に装置／品種対応条件データ内で対応する装置名のうち、他の装置名の遺伝子配列における切断点以降の処理順にそれぞれ移動させることにより、次世代の複数の製造計画データを作成し、当該次世代の複数の製造計画データを作業用製造計画記憶部に書き込む交配処理を実行する交配処理実行機能を有している。
【００１８】
実施形態の交配部は、交配処理を所定回数だけ繰り返し実行するように交配処理実行機能を制御する制御機能を有している。
【００１９】
実施形態の交配部は、制御機能による制御の完了後、作業用製造計画記憶部に書き込まれた最終世代の各製造計画データについて、製造量を製造速度で除算した製造時間を日数に換算した製造日数と納期との差分を示す納期遅れと、パラメータとに基づいて、納期遅れの大きさを評価する評価関数値を算出する。
【００２０】
実施形態の製造計画出力部は、最終世代の各製造計画データのうち、評価関数値が最小である製造計画データを出力する。
【図面の簡単な説明】
【００２１】
【図１】第１の実施形態に係る製造計画作成装置の構成を示す模式図である。
【図２】同実施形態における装置／品種対応条件データの一例を示す模式図である。
【図３】同実施形態における注文情報の一例を示す模式図である。
【図４】同実施形態における製造装置情報の一例を示す模式図である。
【図５】同実施形態における段取り時間情報の一例を示す模式図である。
【図６】同実施形態における全体動作を説明するためのフローチャートである。
【図７】同実施形態におけるステップＳＴ３０の処理の動作を説明するためのフローチャートである。
【図８】同実施形態における作業ＩＤと遺伝子を説明するための模式図である。
【図９】第２の実施形態に係る製造計画作成装置の構成を示す模式図である。
【図１０】同実施形態における全体動作を説明するためのフローチャートである。
【図１１】同実施形態におけるステップＳＴ４０の処理の動作を説明するためのフローチャートである。
【発明を実施するための形態】
【００２２】
以下、各実施形態について説明するが、その前に、致死遺伝子について遺伝子表現の例を用いて説明する。
【００２３】
［従来の交叉法がうまく機能する例］
均質な４台の装置１〜４がある場合、各装置１〜４の処理する作業列を直列に並べて、以下のように表現する。以下の表現中、「親１」及び「親２」は、それぞれ「親世代の第１計画」及び「親世代の第２計画」を意味する。
【数１】
2011253451.tif 000003
【００２４】
なお、「子１」及び「子２」も同様に、それぞれ「子世代の第１計画」及び「子世代の第２計画」を意味している。
【００２５】
ここで、装置１〜４の能力が同じ場合には、各装置１〜４の処理する作業列を、［装置１の処理する作業列］［装置２の処理する作業列］…［装置４の処理する作業列］と直列に並べて一本の遺伝子とすれば、交配した結果も実行可能な製造計画になる。
【００２６】
一方、製造装置の能力・対象品種に差がある場合には、交配した結果、作業がその品種を処理できない製造装置に割付けられる可能性があり、実行可能な製造計画が得られる確率が低くなる。このため、製造装置の能力・対象品種に差がある場合には、遺伝的アルゴリズムによって扱うことが困難となってしまう。このような例を次に述べる。
【００２７】
［従来の交叉法が致死遺伝子を生む例］
製造計画によって、同じ装置の処理する作業の数が異なる可能性があり、一つの計画の中で各装置が処理する作業の数も一般に異なる。
【数２】
2011253451.tif 000004
【００２８】
このとき、例えば、作業Ｉ，Ｊは装置３から装置２に移ったことになる。しかしながら、装置２が作業Ｉ，Ｊを処理できるとは限らない。装置２が作業Ｉ，Ｊを処理できない場合、子の遺伝子は実行不能な計画（致死遺伝子）となってしまう。
【００２９】
各実施形態はこのような致死遺伝子を発生させずに製造計画を作成するものである。以下、基本的な遺伝的アルゴリズムの枠組の中で、遺伝子表現として「製造装置ごとの作業順序によって表した」ものを用いて説明する。
【００３０】
＜第１の実施形態＞
図１は第１の実施形態に係る製造計画作成装置の構成を示す模式図であり、図２乃至図５は同装置に用いられる情報の一例を示す模式図である。この製造計画作成装置は、遺伝的アルゴリズムを用いて各作業の作業ＩＤを遺伝子として表現し、製造装置の装置名毎に遺伝子を処理順に並べた可変長の複数の遺伝子配列からなる製造計画データを作成するものである。具体的には、製造計画作成装置は、条件データ記憶部１１、入力部１２、作業用製造計画記憶部１３、交配部１４及び製造計画出力部１５を備えている。なお、製造計画作成装置は、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から製造計画作成装置のコンピュータにインストールされ、製造計画作成装置の機能を実現させるためのプログラムが用いられる。
【００３１】
ここで、条件データ記憶部１１は、各部１３〜１５から読出／書込可能な記憶装置であり、製造装置の処理できる品種と条件データを記憶する。例えば、条件データ記憶部１１は、図２に示すように、装置名毎に当該装置名の製造装置によって製造可能な製品の品種名を対応付けた装置／品種対応条件データ１１ａを記憶する。この装置／品種対応条件データ１１ａは、操作者の操作により、予め入力部１３から条件データ記憶部１１に書き込まれる。なお、装置／品種対応条件データ１１ａは、各作業で製造される製品は品種が決まっていることから、用いられている。
【００３２】
作業用製造計画記憶部１２は、各部１３〜１５から読出／書込可能な記憶装置であり、例えば、製造装置ごとの作業順序によって表した、一世代の複数の製造計画を記憶する。なお、作業用製造計画記憶部１２及び条件データ記憶部１１は、１台の記憶装置内の異なる記憶領域を各部１１，１２に用いて実現してもよく、２台の記憶装置を各部１１，１２に用いて実現してもよい。また例えば、作業用製造計画記憶部１２は、入力部１３から書き込まれた遺伝的アルゴリズムのパラメータと、注文情報１２ａ、製造装置情報１２ｂ、段取り時間情報１２ｃ及び評価関数のパラメータと、交配部１４から書き込まれた各世代の各製造計画データとを記憶する。但し、遺伝的アルゴリズムのパラメータは、予めプログラムに記述されたデフォルト値を用いる場合などには入力しなくてもよい。ここで、遺伝的アルゴリズムのパラメータとしては、例えば、世代数ｔ、世代内の個体数ｕ、交配により生成する個体数ｖ、突然変異させる個体数ｗ等がある。なお、突然変異される個体数ｗは、本実施形態では用いず、第２の実施形態で用いる。
【００３３】
注文情報１２ａは、図３に示すように、作業ＩＤ、納期［日］、製造量［ｔ］及び品種名を含んでいる。作業ＩＤは作業を識別する番号である。作業は、各装置α，β，γで製品を作る単位である。
【００３４】
製造装置情報１２ｂは、図４に示すように、装置名、品種名、製造速度［ｔ／ｈ］及び消費電力量［ｋＷｈ］を含んでいる。評価関数のパラメータは、例えば、評価関数値Ｅｖ＝ａ１・ΣＤｉ＋ａ２・Ｐａに用いられる係数ａ１，ａ２である。この評価関数の詳細は後述するが、Ｄｉが納期遅延を示し（但し、ｉは作業ＩＤ番号で、ΣＤｉは、全ての作業ｉについての納期遅延Ｄｉの総和）、Ｐａは全装置の消費電力量を示している。
【００３５】
また、消費電力量は、必須ではなく、例えば、各装置間で消費電力量の差が小さい等のように無視できる場合には省略してもよい。また、消費電力量は、消費した電力の量に限らず、消費した水や油などの量などの消費資源量として拡張または一般化してもよい。
【００３６】
段取り時間情報１２ｃは、図５に示すように、装置名毎に当該装置名の製造装置によって製造可能な製品の品種を先行品種から後続品種に切り替える段取り替え作業に必要な時間を示す情報である。なお、段取り時間情報１２ｃは、必須ではなく、例えば、段取り時間が数分程度のように無視できる場合には省略してもよい。
【００３７】
入力部１３は、操作者の操作により、データを入力する入力インターフェースであり、例えば、第一世代の製造計画の元となる情報を入力する。例えば、入力部１３は、遺伝的アルゴリズムのパラメータと、作業ＩＤ、納期、製造量及び品種名を含む注文情報１２ａと、装置名、品種名、製造速度及び消費電力量を含む製造装置情報１２ｂと、先行品種と後続品種の組合せごとの段取り時間情報１２ｃと、評価関数のパラメータとを入力して作業用製造計画記憶部１２に書き込む機能をもっている。
【００３８】
交配部１４は、二つの親世代の製造計画から、一方の製造計画の装置ごとの作業列から他方の計画に移動可能な作業を選んで移し、実行可能な子世代の製造計画を作成する。具体的には例えば、交配部１４は、以下の各機能(f14-1)〜(f14-4)をもっている。
【００３９】
(f14-1)  装置名毎に、当該装置名に装置／品種対応条件データ１１ａ内で対応する品種名と同じ品種名を含む注文情報１２ａの作業ＩＤを表現した遺伝子、を処理順に並べた可変長の複数の遺伝子配列からなる第一世代の製造計画データを複数生成し、当該第一世代の各製造計画データを作業用製造計画記憶部１２に書き込む第一世代データ作成機能。
【００４０】
(f14-2)  作業用製造計画記憶部１２に新たに記憶された遺伝子配列毎の遺伝子間の切断点をランダムに選択し、当該切断点以降の各遺伝子を、当該各遺伝子として表現された作業ＩＤと同じ作業ＩＤを含む注文情報１２ａの品種名に装置／品種対応条件データ１１ａ内で対応する装置名のうち、他の装置名の遺伝子配列における切断点以降の処理順にそれぞれ移動させることにより、次世代の複数の製造計画データを作成し、当該次世代の複数の製造計画データを作業用製造計画記憶部１２に書き込む交配処理を実行する交配処理実行機能。
【００４１】
(f14-3)  交配処理を所定回数だけ繰り返し実行するように交配処理実行機能を制御する制御機能。
【００４２】
(f14-4)  制御機能による制御の完了後、作業用製造計画記憶部１２に書き込まれた最終世代の各製造計画データについて、製造装置情報１２ｂ内の製造量を製造速度で除算した製造時間を日数に換算した製造日数と注文情報１２ａ内の納期との差分を示す納期遅れと、製造装置情報１２ｂ内の消費電力量の合計値と、評価関数のパラメータとに基づいて、当該納期遅れ及び当該合計値の大きさを評価する評価関数値Ｅｖを算出する評価関数値算出機能。
【００４３】
ここで、製造量は生産量に読み替えてもよい。
【００４４】
また、日数に換算する計算は、製造時間を２４［ｈ］で除算する換算式、あるいは残業無しの８［ｈ］で除算する換算式といった任意の時間数で除算する換算式により実行可能となっている。
【００４５】
また、製造装置情報１２ｂから消費電力量を省略する場合、評価関数算出機能(f14-4)は、前述した納期遅れと、評価関数のパラメータとに基づいて、当該納期遅れの大きさを評価する評価関数値Ｅｖを算出する機能となる。
【００４６】
評価関数値Ｅｖは、後述するＥｖ＝ａ１・ΣＤｉ＋ａ２・Ｐａの式に限らず、任意の数式を用いて算出可能となっている。
【００４７】
製造計画出力部１５は、データを出力する出力インターフェースであり、例えば、最終世代の製造計画を出力する。例えば、製造計画出力部１５は、最終世代の各製造計画データのうち、評価関数値が最小である製造計画データを出力する製造計画出力機能をもっている。
【００４８】
次に、以上のように構成された製造計画作成装置の動作を図６及び図７のフローチャートを用いて説明する。なお、以下では、説明の便宜上、図８に示すように、同一の作業ＩＤをアルファベットの大文字Ａ，Ｂ，…，Ｓと、小文字ａ，ｂ，…，ｓで表す。本実施形態では、同一の作業ＩＤについて、二つの個体すなわち製造計画に配列されたものを識別する必要があることから、親世代の第１製造計画「親１」では大文字Ａ，…，Ｓを用い、親世代の第２製造計画「親２」では小文字ａ，…，ｓを用いている。
【００４９】
始めに、製造計画作成装置においては、操作者の操作により、遺伝的アルゴリズムのパラメータ（世代数ｔ、世代内の個体数ｕ、交配により生成する個体数ｖ）が入力部１３から作業用製造計画記憶部１２に書き込まれる。しかる後、製造計画作成装置は、以下のような手順で製造計画を作成する。
【００５０】
入力部１１は、操作者の操作により、注文情報１２ａ、製造装置情報１２ｂ、段取り時間情報１２ｃ及び評価関数のパラメータを入力して作業用製造計画記憶部１２に書き込む（ＳＴ１０）。
【００５１】
交配部１４は、第一世代のｕ個体（＝ｕ個の製造計画データ）を生成する（ＳＴ２０）。具体的には、交配部１４は、装置名α，β，γ毎に、当該装置名α，β，γに装置／品種対応条件データ１１ａ内で対応する品種名ア，イ，ウ，…と同じ品種名を含む注文情報１２ａの作業ＩＤを表現した遺伝子Ａ，Ｂ，…，Ｓ、ａ，ｂ，…，ｓを処理順に並べた可変長の３つの遺伝子配列からなる第一世代の製造計画データを２個生成し（例、ｕ＝２）、当該第一世代の各製造計画データを作業用製造計画記憶部１２に書き込む
続いて、交配部１４は、現在の世代に対し、ｖ回の交配を行って、親遺伝子から生成した子遺伝子を追加する（ＳＴ３０）。具体的には交配部１４は、作業用製造計画記憶部１２に新たに記憶された遺伝子配列毎の遺伝子間の切断点をランダムに選択し、当該切断点以降の各遺伝子を、当該各遺伝子として表現された作業ＩＤと同じ作業ＩＤを含む注文情報１２ａの品種名に装置／品種対応条件データ１１ａ内で対応する装置名のうち、他の装置名の遺伝子配列における切断点以降の処理順にそれぞれ移動させることにより、次世代のｖ個の製造計画データを作成し、当該次世代のｖ個の製造計画データを作業用製造計画記憶部１２に書き込む交配処理を実行する。
【００５２】
交配部１４は、ステップＳＴ３０の結果のｕ＋ｖ個の個体のうち、ｖ個の個体を選択して除き、残ったｕ個の個体を次世代とする（ＳＴ５０）。なお、ｖ個の個体の選択方法は、遺伝的アルゴリズムにおける一般的な選択アルゴリズム（例、ルーレット選択、ランキング選択、トーナメント選択、エリート選択など）が適宜使用可能となっている。また、ステップＳＴ５０は、必須ではなく、省略してもよい。例えば、図７に示すように、現世代の製造計画データの個数と、次世代の製造計画データの個数とが同数（例、ｕ＝ｖ＝２）の場合で、現世代の製造計画データを残さず、次世代の製造計画データに変更する場合には省略可能となっている。
【００５３】
交配部１４は、ステップＳＴ３０〜ＳＴ５０を、ｔ回繰り返し実行する（ＳＴ６０）。
【００５４】
交配部１４は、ｔ回の繰り返し実行の完了後、作業用製造計画記憶部１２内の最終世代の各製造計画データについて、評価関数値Ｅｖをそれぞれ計算する。
【００５５】
評価関数としては、例えば次のようなものを用いる。
【００５６】
（ａ）全装置の消費電力量をＰａとする。
【００５７】
（ｂ）作業ｉの完工時点をＦｉ、納期をＬｉとし、納期遅延Ｄｉを次式で求める（但し、ｉは作業ＩＤ番号）。
【００５８】
Ｄｉ＝０          （但し、Ｆｉ≦Ｌｉ）
Ｄｉ＝Ｆｉ−Ｌｉ  （但し、Ｆｉ＞Ｌｉ）
（ｃ）係数ａ１，ａ２を用いて、評価関数値Ｅｖを次式に示すように算出する。
【００５９】
Ｅｖ＝ａ１・ΣＤｉ＋ａ２・Ｐａ
但し、ΣＤｉは、全ての作業ｉについての納期遅延Ｄｉの総和である。
【００６０】
（ｄ）評価関数値Ｅｖが小さいものほど、よい製造計画である。
【００６１】
製造計画出力部１５は、最終世代の各製造計画データのうち、評価関数値が最良の製造計画データを出力する（ＳＴ７０）。この例では「評価関数値Ｅｖが最良」は「評価関数値Ｅｖが最小」を意味する。
【００６２】
次に、ステップＳＴ３０の処理を図７のフローチャートを用いて詳細に説明する。ステップＳＴ３０の処理は、以下のステップＳＴ３１〜ＳＴ３５の処理から構成されている。
【００６３】
交配部１４は、装置名α，β，γ毎に、遺伝子Ａ，Ｂ，…，Ｓ、ａ，ｂ，…，ｓを処理順に並べた遺伝子配列を、それぞれ乱数で決めた位置で切断する（ＳＴ３１）。言い換えると、交配部１４は、遺伝子配列毎の遺伝子間の切断点（位置）をランダムに選択する。ここで、遺伝子配列は作業配列と呼んでもよい。
【００６４】
交配部１４は、切断点以前の遺伝子配列をその製造計画データのその位置にそのまま保存する（ＳＴ３２）。
【００６５】
交配部１４は、切断点以降の遺伝子を他の製造計画に移動する（ＳＴ３３）。言い換えると、交配部１４は、切断点以降の各遺伝子を、当該各遺伝子として表現された作業ＩＤと同じ作業ＩＤを含む注文情報１２ａの品種名に装置／品種対応条件データ１１ａ内で対応する装置名のうち、他の装置名の遺伝子配列における切断点以降の処理順にそれぞれ移動させる。
【００６６】
このとき、各作業はその製造計画データ内で一意でなければならないので、一意性に反する場合は他方の製造計画データへ移動せず元の製造計画データの中で移動させる。例えば、作業ＩＤ“１”を表現した２つの遺伝子“Ａ”，“ａ”は、３つの遺伝子配列からなる１つの製造計画データ内でいずれか１つだけ（“Ａ”又は“ａ”だけ）でなければならない。そうでないと、作業ＩＤ“１”の作業を２回行う製造計画になるからである。このように、個々の作業ＩＤが同じ製造計画内で１つでなければならないことを「一意性」と表現している。そして、一意性に反する場合（同じ作業ＩＤを表す２つの遺伝子が同じ製造計画データに集まる場合）が生じないように、遺伝子を移動させる必要がある。また、製造計画データ間で移動する場合も留まる場合も、装置／品種対応データ１１ａに基づき、移動先の装置の装置名はその作業を処理できる装置の中から乱数によって選択される。
【００６７】
遺伝子の移動を受け入れの製造計画データ側から見ると、切断点以降の遺伝子は、一般に両方の製造計画データの複数の遺伝子配列から移動してくることになる。交配部１４は、切断点以降の遺伝子を移動元の遺伝子配列における処理順を保存したままマージして一次元の遺伝子配列とする（ＳＴ３４）。
【００６８】
交配部１４は、ステップＳＴ３２〜ＳＴ３４の結果を、切断点の前後で入れ替えた移動も、同じ確率で発生させる（ＳＴ３５）。
【００６９】
製造計画作成装置は、ステップＳＴ３５の終了後、前述したステップＳＴ５０に移行して処理を実行する。
【００７０】
上述したように第１の実施形態によれば、実行可能な製造計画を表す親世代から、交配によって実行可能な次世代の製造計画だけを作成することができる。このため、高い確率で致死遺伝子を生成する従来の交配法に比べ、短い時間で次世代の製造計画を得ることができる。
【００７１】
＜第２の実施形態＞
図９は第２の実施形態に係る製造計画作成装置の構成を示す模式図であり、図１と略同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。
【００７２】
第２の実施形態は、第１の実施形態に突然変異の機能を追加したものであり、具体的には、図１に示した構成に比べ、図９に示すように、突然変異部１６が追加された構成となっている。
【００７３】
ここで、突然変異部１６は、一つの製造計画中の製造装置ごとの作業列の中で、他の装置に移動できるものの中から移動候補を選び、突然変異個体である製造計画を作成するものである。具体的には、突然変異部１６は、交配部１４により作業用製造計画記憶部１２に書き込まれた遺伝子配列のうち、ランダムに選択した遺伝子配列から１つの遺伝子をランダムに選択し、当該選択した遺伝子を、この遺伝子が表現する作業ＩＤと同じ作業ＩＤを含む注文情報１２ａの品種名に装置／品種対応条件データ１１ａ内で対応する装置名のうち、他のいずれかの装置名の遺伝子配列に移動させる突然変異処理を実行する突然変異実行機能をもっている。
【００７４】
また、突然変異部１６の追加に伴い、交配部１４は、ステップＳＴ６０において、交配処理及び突然変異処理を所定回数だけ繰り返し実行するように交配処理実行機能及び突然変異実行機能をそれぞれ制御するものとなっている。
【００７５】
次に、以上のように構成された製造計画作成装置の動作を図１０及び図１１のフローチャートを用いて説明する。
【００７６】
始めに、製造計画作成装置においては、操作者の操作により、遺伝的アルゴリズムのパラメータ（世代数ｔ、世代内の個体数ｕ、交配により生成する個体数ｖ、突然変異させる個体数ｗ）が入力部１３から作業用製造計画記憶部１２に書き込まれる。
【００７７】
また、製造計画作成装置は、前述した通り、ステップＳＴ１０〜ＳＴ３０の処理を実行する。
【００７８】
続いて、製造計画作成装置においては、突然変異部１６が、ステップＳＴ３０の結果のｕ＋ｖ個の個体（製造計画データ）のうち、ｗ個（例、ｗ＝１）の個体に突然変異を起こす（ＳＴ４０）。具体的には、突然変異部１６は、交配部１４により作業用製造計画記憶部１２に書き込まれた遺伝子配列のうち、ランダムに選択した遺伝子配列から１つの遺伝子をランダムに選択し、当該選択した遺伝子を、この遺伝子が表現する作業ＩＤと同じ作業ＩＤを含む注文情報１２ａの品種名に装置／品種対応条件データ１１ａ内で対応する装置名のうち、他のいずれかの装置名の遺伝子配列に移動させる。
【００７９】
しかる後、交配部１４は、前述同様に、ステップＳＴ４０の結果のｕ＋ｖ個の個体のうち、ｖ個の個体を選択して除き、残ったｕ個の個体を次世代とする（ＳＴ５０）。
【００８０】
また同様に、交配部１４は、ステップＳＴ３０〜ＳＴ５０を、ｔ回繰り返し実行する（ＳＴ６０）。
【００８１】
以下、前述した通り、ステップＳＴ７０の処理が実行される。
【００８２】
次に、ステップＳＴ４０の処理を図１１のフローチャートを用いて詳細に説明する。ステップＳＴ４０の処理は、以下のステップＳＴ４１〜ＳＴ４７の処理から構成されている。
【００８３】
突然変異部１６は、移動する遺伝子の数ｎを決める（ＳＴ４１）。
【００８４】
突然変異部１６は、作業用製造計画記憶部１２内の各遺伝子配列の装置名のうち、いずれかの装置名をランダムに選択する（ＳＴ４２）。
【００８５】
突然変異部１６は、当該選択した装置名の遺伝子配列から一つの遺伝子をランダムに選択する（ＳＴ４３）。
【００８６】
突然変異部１６は、当該選択した遺伝子が表す作業を処理できる装置の内、ステップＳＴ４２で選択した装置名の装置以外の装置の装置名を一つ選択する（ＳＴ４４）。言い換えると、突然変異部１６は、ステップＳＴ４３で選択した遺伝子を、この遺伝子が表現する作業ＩＤと同じ作業ＩＤを含む注文情報１２ａの品種名に装置／品種対応条件データ１１ａ内で対応する装置名のうち、他のいずれかの装置名を選択する。なお、ステップＳＴ４２で選択した装置名の装置しか処理できない場合、突然変異部１６は、ステップＳＴ４２に戻って選択し直す。
【００８７】
突然変異部１６は、ステップＳＴ４３で選択した遺伝子をステップＳＴ４４で選択した装置名の遺伝子配列に追加する（ＳＴ４５）。
【００８８】
突然変異部１６は、ステップＳＴ４１で決めた数ｎの回数だけステップＳＴ４２〜ＳＴ４５を繰り返し実行する（ＳＴ４６）。
【００８９】
突然変異部１６は、ｎ回の繰り返し実行の完了後、各装置名の遺伝子配列の中で、遺伝子の順序をランダムに入れ替える（ＳＴ４７）。
【００９０】
製造計画作成装置は、ステップＳＴ４７の終了後、前述したステップＳＴ５０に移行して処理を実行する。
【００９１】
上述したように本実施形態によれば、第１の実施形態の効果に加え、実行可能な製造計画を表す親世代から、突然変異によって実行可能な次世代の製造計画だけを作成することができる。このため、高い確率で致死遺伝子を生成する従来の交配法に比べ、短い時間で次世代の製造計画を得ることができる。
【００９２】
また、以上の各実施形態によれば、複数の能力（例、製造速度）の異なる製造装置からなる工程の製造計画を、各工程の作業ＩＤである遺伝子を処理順に並べた可変長の配列で表すと共に、交配と突然変異を、処理後の製造計画が実行可能となるよう制約条件（例、装置／品種対応条件データ１１ａ）を満たしながら生成する。これにより、遺伝的アルゴリズムにおける致死遺伝子に相当する実行不可能な製造計画の作成を回避することができる。
【００９３】
また、各実施形態によれば、致死遺伝子を作らずに遺伝的アルゴリズムによって製造計画を作成することから、短い時間で従来の交配法と同程度の準最適解に到達することができる。すなわち、製造計画の作成時間を短縮することができる。
【００９４】
さらに、各実施形態によれば、製造計画の作成時間を短縮できるので、工場内の製造計画だけでなく、複数の工場を一括して作業を融通する工場群の製造計画にも応用することが容易になる。
【００９５】
なお、上記の各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【００９６】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【００９７】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【００９８】
さらに、本発明の各実施形態における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【００９９】
また、記憶媒体は１つに限らず、複数の媒体から上記の各実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１００】
なお、本発明の各実施形態におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記の各実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１０１】
また、本発明の各実施形態におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１０２】
なお、本発明は、上記の各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記の各実施形態に開示されている複数の構成要素の適宜な組合せにより種々の変形例を形成できる。例えば、各実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜に組合せてもよい。
【符号の説明】
【０１０３】
１１…条件データ記憶部、１１ａ…装置／品種対応条件データ、１２…作業用製造計画記憶部、１２ａ…注文情報、１２ｂ…製造装置情報、１２ｃ…段取り時間情報、１３…入力部、１４…交配部、１５…製造計画出力部、１６…突然変異部。
【図１】
2011253451.tif 000005
【図２】
2011253451.tif 000006
【図３】
2011253451.tif 000007
【図４】
2011253451.tif 000008
【図５】
2011253451.tif 000009
【図６】
2011253451.tif 000010
【図７】
2011253451.tif 000011
【図８】
2011253451.tif 000012
【図９】
2011253451.tif 000013
【図１０】
2011253451.tif 000014
【図１１】
2011253451.tif 000015