(57)【要約】【課題】長方形及び長方形以外の多角形が混在する製品を、一種類あるいは２種類以上の原材料に割付けるとき、原材料の合計価格の最小化を図る。【解決手段】  長方形も長方形以外の多角形も含めて、原材料に割付けるための引当順を予め設定する。さらに、原材料上への製品の割付け方法に多角形でも適応できる一定のルールを決める。引当順に取り出した原材料への割付結果を比較しながら、遺伝子工学的手法により上記の引当順を最適化するように演算処理をする。【選択図】図１
2020112965.tif 000002
【特許請求の範囲】
【請求項１】
建築物に使用する長方形および長方形以外の多角形が混在するｍ枚の製品を、ｋ種類の長方形の原材料から切り出すときに、種類毎に必要な原材料枚数と、各原材料への製品の割付方を求めて、原材料費用を最小化するものであって、
ｋ＝１の場合は、原材料を１枚取り出し、引当順を定めた未割付製品を引当順に取り出すものとし、
「新たに１枚の原材料を取り出し、上記原材料に予め定めた割付方法で上記取り出した未割付製品が割付可能ならば割付をして、上記未割付製品を割付済み製品とし、
割付可能でなければ、上記取り出した未割付製品を、上記引当順を保ったまま元に戻す操作を最初の引当順から最後の引当順の未割付製品に対して行う」という、取り出した原材料への割付処理をすべての製品が割付済み製品になるまで行い、
必要な原材料枚数と各原材料への製品の割付方と、原材料費用と、を求めるように計算を制御する第一の製品引当順割付手段と、
ｋ＞１の場合は、各原材料の価格を設定し、ｊ＝１からｋまでのうちのｊ種類目の原材料ｊを１枚取り出し、引当順を定めた未割付製品を引当順に取り出すものとし、
上記取り出した原材料への割付処理をｊ種類目の原材料ｊに対して行い、引き続き、
「原材料ｊに割り付いた製品を求め、上記の原材料ｊの価格と、割り付けられた製品の面積の合計から製品面積当り価格ｐｊを求める」という、製品面積当り価格計算処理を、ｋ種類の原材料全て（ｊ＝１からｋまで）について実行して、引き続き、
「最も安い製品面積当り価格ｐL（1≦L≦ｋ）を選び、L種類目の原材料Lと製品の組合せに決定して、該当する製品を割付済み製品とし、L種類目以外の原材料に割り付けられた、上記該当する製品を割付済みとした製品以外を未割付に戻す」という、製品面積当り価格比較判定処理を行うことを、すべての製品が割付済み製品になるまで行い、
種類毎に必要な原材料枚数と各原材料への製品の割付方と、原材料費用と、を求めるように計算を制御する第二の製品引当順割付手段と、
上記長方形および長方形以外の多角形が混在するｍ枚の製品をそれぞれ指定する遺伝子と、その遺伝子を上記選択された引当順に配列させる遺伝子座を有する複数の染色体を個体として生成する個体生成手段と、
上記生成した個体を親個体とし、交叉処理、または突然変異処理、または選択処理をして、複数の子個体を生成し、その複数の子個体を次世代の親個体とし、世代交代を繰返して、上記製品の引当順を表す個体を生成する世代交代手段とを備え、
ｋ＝１のときは、上記の第一の製品引当順割付手段と前記個体生成手段と前記世代交代手段とによる演算処理を実行し、必要な原材料枚数と、各原材料への製品の割付方を求め、ｋ＞１のときは、上記の第二の製品引当順割付手段と前記個体生成手段と前記世代交代手段とによる演算処理を実行し、種類毎に必要な原材料枚数と、各原材料への製品の割付方を求めて、原材料費用を最小化することを特徴とする部材割付システム。
【請求項２】
上記取り出した製品の向きが、ある状態と、このある状態を９０度回転させた状態と、１８０度回転させた状態と、２７０度回転させた状態と、これら４種類の状態を鏡のように反転させた状態のいずれかを含む、複数種類の状態を、それぞれ別々の遺伝子として扱うことを特徴とする請求項１に記載の部材割付システム。
【請求項３】
上記予め定めた割付方法は、長方形の原材料のいずれかの頂点を選択してこれを特定の頂点と呼ぶとき、この原材料上に新たな製品を割り付けるときに、上記特定の頂点に一端を有する原材料の一対の辺と平行な２方向に沿って製品を移動させて、その製品の位置を原材料に割付け可能な範囲で上記特定の頂点に近づけて配置し、既に割付け済みの製品が配置されているときは、割付け済みの製品と新たな製品とが、互いに重なり合い部分を生じさせない範囲で、新たな製品を上記特定の頂点に近づけて配置するという処理を、その原材料に新たな製品が割付け出来なくなるまで順に繰り返すことを特徴とする請求項１乃至２のいずれかに記載の部材割付システム。
【請求項４】
上記予め定めた割付方法は、長方形の原材料の上に割付済みの製品と次に割付をする製品とを、互いに重なり合い部分を生じさせることなく、両方の製品がいずれかの頂点を共有するように配置することが可能ならば配置するという処理を、その原材料に新たな製品が割付け出来なくなるまで順に繰り返すことを特徴とする請求項３に記載の部材割付システム。
【請求項５】
上記世代交代手段は、以下の手順で製品引当順を選択することを特徴とする請求項１乃至４のいずれかに記載の部材割付システム。
（１）初期の個体集団（第一世代）をランダムにＭ個生成する。
（２）そのＭ個の個体集団から２個の親個体をランダムに選択する。
（３）２個の親個体から交叉処理で子個体をＭ個つくる。
（４）得られたＭ個の子個体のうち設定した数の子個体に突然変異処理を行う。
（５）親個体がＭ個、子個体がＭ個で合せて２Ｍ個の個体について、必要な原材料枚数
か、または原材料費を算出する。
（６）必要な原材料枚数か、または原材料費の少ないほうからＭ個の個体を取り出して、
次世代（第二世代）の個体集団とする。
（７）上記（１）から（６）の世代交代を繰返し、必要な原材料枚数か、または原材料費の差が収束判定基準に達したとき、設定した世代交代回数に達したとき、計算を終了する。
（８）最小もしくは最小に近い固体の中から、それらの染色体を参照して製品引当順を選択する。
【請求項６】
上記交叉処理においては、
上記親個体の任意の２つを「親１」と「親２」とし、その両方から遺伝子配列の一部を承継した子個体の遺伝子を上記親個体と同数生成して、
上記突然変異処理においては、
上記いずれかの子個体に対して遺伝子座の任意に２つの遺伝子を交換して、新たな子個体を生成し、
上記個体の選択処理においては、
上記親個体と上記子個体の表す製品引当順のうち、上記必要な原材料枚数が少ないものからか、または上記必要な原材料の費用が少ないものから上記親個体と同数選択して次世代とすることを特徴とする請求項１乃至５のいずれかに記載の部材割付システム。
【請求項７】
コンピュータを請求項１乃至請求項６のいずれかに記載の部材割付システムとして機能させるコンピュータプログラム。
【請求項８】
請求項７に記載のコンピュータプログラムを記録したコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、建築用に使用する多様な寸法の多角形の製品を、供給される何種類かの原材料に割り付けて、原材料費用を最小化するように原材料への製品の割付方を計算する部材割付システムに関する。
【背景技術】
【０００２】
例えば、壁材のような多様な寸法の長方形の製品を、与えられた原材料から切り出すときに、原材料費用を最小にするための様々な計算手法が開発されている（特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第５８３８０４７号公報
【非特許文献】
【０００４】
【非特許文献１】切出し・詰込み問題に対する実用的解法（梅谷俊治著）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
既知の従来の技術には、次のような解決すべき課題があった。
特許文献１に示される技術では、例えば、台形、三角形のような長方形以外の多角形の製品の割付ができない。仮にそれぞれの多角形に外接する長方形を製品とみなして割り付けるようにすると歩留が下がるという問題があった。
非特許文献１によると、多様な寸法の多角形の製品の割付が、ストリップパッキング問題として取扱われている。ストリップパッキング問題は、例えばロール状に巻いた鉄板のように、幅が定寸で、長さが十分長い原材料に、切り出したい多様な寸法の多角形の製品を割り付けて、使用する原材料の長さを最小化する問題である。すなわち、原材料の枚数は１枚である。それに対して、建築用の製品を切り出す原材料は、幅や長さ寸法が限定されており、多様な形状および寸法の多角形の製品を切り出すには、複数枚の原材料を使用することになり、そのままストリップパッキング問題として解けない。また、寸法が異なる複数種類の原材料を選んで使用することも少なくない。
本発明は、産業廃棄物の最小化という環境上の要請に応えるために、ストリップパッキング問題を解くための配置（割付）場所決定ルールを改良したルールを使用し、上記の課題を解決することを目的とする。
【課題を解決するための手段】
【０００６】
以下の構成はそれぞれ上記の課題を解決するための手段である。
＜構成１＞
建築物に使用する長方形および長方形以外の多角形が混在するｍ枚の製品を、ｋ種類の長方形の原材料から切り出すときに、種類毎に必要な原材料枚数と、各原材料への製品の割付方を求めて、原材料費用を最小化するものであって、
ｋ＝１の場合は、原材料を１枚取り出し、引当順を定めた未割付製品を引当順に取り出すものとし、
「新たに１枚の原材料を取り出し、上記原材料に予め定めた割付方法で上記取り出した未割付製品が割付可能ならば割付をして、上記未割付製品を割付済み製品とし、
割付可能でなければ、上記取り出した未割付製品を、上記引当順を保ったまま元に戻す操作を最初の引当順から最後の引当順の未割付製品に対して行う」という、取り出した原材料への割付処理をすべての製品が割付済み製品になるまで行い、
必要な原材料枚数と各原材料への製品の割付方と、原材料費用と、を求めるように計算を制御する第一の製品引当順割付手段と、
ｋ＞１の場合は、各原材料の価格を設定し、ｊ＝１からｋまでのうちのｊ種類目の原材料ｊを１枚取り出し、引当順を定めた未割付製品を引当順に取り出すものとし、
上記取り出した原材料への割付処理をｊ種類目の原材料ｊに対して行い、引き続き、
「原材料ｊに割り付いた製品を求め、上記の原材料ｊの価格と、割り付けられた製品の面積の合計から製品面積当り価格ｐｊを求める」という、製品面積当り価格計算処理を、ｋ種類の原材料全て（ｊ＝１からｋまで）について実行して、引き続き、
「最も安い製品面積当り価格ｐL（1≦L≦ｋ）を選び、L種類目の原材料Lと製品の組合せに決定して、該当する製品を割付済み製品とし、L種類目以外の原材料に割り付けられた、上記該当する製品を割付済みとした製品以外を未割付に戻す」という、製品面積当り価格比較判定処理を行うことを、すべての製品が割付済み製品になるまで行い、
種類毎に必要な原材料枚数と各原材料への製品の割付方と、原材料費用と、を求めるように計算を制御する第二の製品引当順割付手段と、
上記長方形および長方形以外の多角形が混在するｍ枚の製品をそれぞれ指定する遺伝子と、その遺伝子を上記選択された引当順に配列させる遺伝子座を有する複数の染色体を個体として生成する個体生成手段と、
上記生成した個体を親個体とし、交叉処理、または突然変異処理、または選択処理をして、複数の子個体を生成し、その複数の子個体を次世代の親個体とし、世代交代を繰返して、上記製品の引当順を表す個体を生成する世代交代手段とを備え、
ｋ＝１のときは、上記の第一の製品引当順割付手段と前記個体生成手段と前記世代交代手段とによる演算処理を実行し、必要な原材料枚数と、各原材料への製品の割付方を求め、ｋ＞１のときは、上記の第二の製品引当順割付手段と前記個体生成手段と前記世代交代手段とによる演算処理を実行し、種類毎に必要な原材料枚数と、各原材料への製品の割付方を求めて、原材料費用を最小化することを特徴とする部材割付システム。
【０００７】
＜構成２＞
上記取り出した製品の向きが、ある状態と、このある状態を９０度回転させた状態と、１８０度回転させた状態と、２７０度回転させた状態と、これら４種類の状態を鏡のように反転させた状態のいずれかを含む、複数種類の状態を、それぞれ別々の遺伝子として扱うことを特徴とする構成１に記載の部材割付システム。
【０００８】
＜構成３＞
上記予め定めた割付方法は、長方形の原材料のいずれかの頂点を選択してこれを特定の頂点と呼ぶとき、この原材料上に新たな製品を割り付けるときに、上記特定の頂点に一端を有する原材料の一対の辺と平行な２方向に沿って製品を移動させて、その製品の位置を原材料に割付け可能な範囲で上記特定の頂点に近づけて配置し、既に割付け済みの製品が配置されているときは、割付け済みの製品と新たな製品とが、互いに重なり合い部分を生じさせない範囲で、新たな製品を上記特定の頂点に近づけて配置するという処理を、その原材料に新たな製品が割付け出来なくなるまで順に繰り返すことを特徴とする構成１乃至２のいずれかに記載の部材割付システム。
【０００９】
＜構成４＞
上記予め定めた割付方法は、長方形の原材料の上に割付済みの製品と次に割付をする製品とを、互いに重なり合い部分を生じさせることなく、両方の製品がいずれかの頂点を共有するように配置することが可能ならば配置するという処理を、その原材料に新たな製品が割付け出来なくなるまで順に繰り返すことを特徴とする構成３に記載の部材割付システム。
【００１０】
＜構成５＞
上記世代交代手段は、以下の手順で製品引当順を選択することを特徴とする構成１乃至４のいずれかに記載の部材割付システム。
（１）初期の個体集団（第一世代）をランダムにＭ個生成する。
（２）そのＭ個の個体集団から２個の親個体をランダムに選択する。
（３）２個の親個体から交叉処理で子個体をＭ個つくる。
（４）得られたＭ個の子個体のうち設定した数の子個体に突然変異処理を行う。
（５）親個体がＭ個、子個体がＭ個で合せて２Ｍ個の個体について、必要な原材料枚数
か、または原材料費を算出する。
（６）必要な原材料枚数か、または原材料費の少ないほうからＭ個の個体を取り出して、
次世代（第二世代）の個体集団とする。
（７）上記（１）から（６）の世代交代を繰返し、必要な原材料枚数か、または原材料費の差が収束判定基準に達したとき、設定した世代交代回数に達したとき、計算を終了する。
（８）最小もしくは最小に近い固体の中から、それらの染色体を参照して製品引当順を選択する。
【００１１】
＜構成６＞
上記交叉処理においては、
上記親個体の任意の２つを「親１」と「親２」とし、その両方から遺伝子配列の一部を承継した子個体の遺伝子を上記親個体と同数生成して、
上記突然変異処理においては、
上記いずれかの子個体に対して遺伝子座の任意に２つの遺伝子を交換して、新たな子個体を生成し、
上記個体の選択処理においては、
上記親個体と上記子個体の表す製品引当順のうち、上記必要な原材料枚数が少ないものからか、または上記必要な原材料の費用が少ないものから上記親個体と同数選択して次世代とすることを特徴とする構成１乃至５のいずれかに記載の部材割付システム。
【００１２】
＜構成７＞
コンピュータを構成１乃至構成６のいずれかに記載の部材割付システムとして機能させるコンピュータプログラム。
＜構成８＞
構成７に記載のコンピュータプログラムを記録したコンピュータで読み取り可能な記録媒体。
【発明の効果】
【００１３】
長方形及び長方形以外の多角形が混在する製品を、原材料に割付ける場合に、特定の引当順を設定して、取り出した原材料への割付処理と、遺伝子工学的手法により上記の引当順を最適化して、従来よりも高歩留な割付方を求めることができる。
【図面の簡単な説明】
【００１４】
【図１】本発明のシステムの機能ブロック図である。
【図２】実施例１に使用する原材料データを例示した説明図である。
【図３】実施例１に使用する製品データを例示した説明図である。
【図４】本発明のシステムの演算処理動作フローチャートである。
【図５】第一の製品引当順割付手段の演算処理例フローチャートである。
【図６】第二の製品引当順割付手段の演算処理例フローチャートである。
【図７】ＢＬ法による引当順設定法の演算処理例フローチャートである。
【図８】多角形の頂点に着目した引当順設定法の演算処理例フローチャートである。
【図９】製品のＡ状態とこれを回転したり反転したりした状態および遺伝子構造の説明図である。
【図１０】図７の引当順設定法を図解した説明図である。
【図１１】図８の引当順設定法を図解した説明図である。
【発明を実施するための形態】
【００１５】
本発明による原材料費用の最小化は、遺伝アルゴリズムによる製品の引当順の更新（世代交代）と、予め定めた方法で原材料への製品の割付で得られる原材料費の算出とを、交互に繰り返して行うものである。すなわち、初めに長方形と長方形以外の多角形を混在させた製品の引当順（第一世代個体）を求め、次にその引当順を採用した場合の原材料費（評価値）を求め、その次に優秀な引当順が残るように進化した引当順を求める、ということを繰り返すのである。以下、本発明の実施の形態を順に説明する。
【実施例１】
【００１６】
（システム構成）
図１は、本発明のシステムを実現するためにコンピュータ上に構築した機能ブロックの説明図である。
この、コンピュータの記憶装置には、原材料の寸法等の情報を示す原材料データ１２と、製品の寸法等の情報を示す製品データ１４と、演算処理の結果得られる（種類毎に）必要な原材料枚数１８、各原材料への製品の割付方２０、原材料費用２２等が記憶される。
【００１７】
また、その演算処理のために、第一の製品引当順割付手段２４、第二の製品引当順割付手段２８、個体生成手段３６、世代交代手段３８等が設けられている。この演算処理の途中で、引当順を示す個体データ４０が繰り返し生成される。個体データ４０は遺伝子座に引当順を整列したデータで、世代交代により進化するデータである。
【００１８】
個体生成手段３６は、個体生成処理により第一世代の個体を一定個数生成する。世代交代手段３８は、交叉処理、突然変異処理、選択処理により次世代個体を一定個数生成する機能を持つ。
【００１９】
第一の製品引当順割付手段２４は、原材料種類数が１のときに機能するもので、取り出した原材料への割付け処理と、原材料費用算出処理とを実行して、与えられた引当順から（種類毎に）必要な原材料枚数１８と各原材料への製品の割付方２０と原材料費用２２を算出するものである。
【００２０】
第二の製品引当順割付手段２８は、原材料種類数が１を超えるときに機能するもので、取り出した原材料への割付け処理と、製品面積当り価格計算処理と、製品面積当り価格比較判定処理と、原材料費用算出処理とを実行して、与えられた引当順から（種類毎に）必要な原材料枚数１８と、各原材料への製品の割付方２０と原材料費用２２とを求めるものである。各原材料への製品の割付方２０は、実際に加工機で製品を切り出すときに使用する。
【００２１】
つまり、このシステムのコンピュータは、原材料データ１２と製品データ１４とを受付けて、個体生成手段３６と世代交代手段３８と第一の製品引当順割付手段２４または第二の製品引当順割付手段２８を繰返し動作させて、演算処理をして、原材料費用２２の最小化探求処理を実行する。
【００２２】
（使用データ）
図２（ａ）は、実施例１で使用する原材料データの一例を示し、幅が９１０mm、高さが１８２０mmの長方形で、原材料の種類は１種類だけであることを示す。したがって、上記の第一の製品引当順割付手段２４が動作する。演算処理の出力は（種類毎に）必要な原材料枚数１８と各原材料への製品の割付方２０と原材料費用２２になる。なお、図２（ｂ）に示すように、例えば、幅が９１０mm、高さが１８２０mmの長方形ｆ１と、幅も高さも９１０mmの正方形ｆ２の２種類の原材料を使用するような場合には、第二の製品引当順割付手段２８を動作させて計算することができる。
【００２３】
図３の（ａ）は、実施例１で使用する製品データ１４の一例を示す。製品番号１〜５は製品の形状の種別を示し、種類毎の数量が示してある。例えば、製品番号２は４枚、製品番号５は３０枚ある。全部の製品枚数（ｍ枚）は３８枚である。
【００２４】
各製品の形状は、頂点の数と頂点のｘ−ｙ座標とで示している。この図の例では頂点数は最大４である。例えば、製品番号１の製品は、辺の長さが２００mmと３００mmの四角形（長方形）であって、その数量は２枚である。また、製品番号２の製品は三角形である。頂点がないことは＊で示す。なお、図３（ｂ）に示すように、製品は、正方形ｇ１、長方形ｇ２、台形ｇ３、三角形ｇ４のほかに、頂点数が６のＬ字形ｇ５のものや、頂点数が８のコ字形ｇ６のものがあり、これらも同様にして計算の対象にすることができる。
【００２５】
（フローチャートと割付方）
図４から図８までは、本発明のシステムの演算処理フローチャートである。図４はメインルーチンで、そのステップＳ４の処理を、図５と図６に示した。また、原材料への各製品の予め定めた割付方法の例を図７と図８に示した。
【００２６】
図５は第一の製品引当順割付手段２４の動作例である。また、図６は、第二の製品引当順割付手段２８の動作例である。図７は、非特許文献１に示される「最も単純な」ＢＬ法であり、図８は、工夫されたＢＬ法の例を示す。この割付け方法は一例であり、これ以外の方法も選択できる。
【００２７】
実施例１では、図２に示したように、原材料の種類が１種類であるので、図４のステップＳ４には図５に示す第一の製品引当順割付手段２４を使用し、図５のステップS１０７で図７に示す最も単純なＢＬ法を選択して、図４に示すフローチャートにしたがって演算処理を実行した。
【００２８】
（世代交代と遺伝子）
演算処理の結果得られる（種類毎に）必要な原材料枚数１８、あるいはその原材料費用２２は、製品を原材料に割り付ける引当順に大きく依存する。この引当順を最適化するために遺伝アルゴリズムを適用する。遺伝アルゴリズムの演算処理に使用するパラメータは、経験則から考慮した実用的な演算処理時間から、個体数Ｍ＝５００、突然変異数＝１０、世代交代回数＝１００とした。
【００２９】
遺伝アルゴリズムにより製品の引当順を最適に近づけていくと、ある時点で評価値の収束が始まる。評価値は、演算処理の結果としてそのつど得られる原材料費用２２のことである。経験的には、製品数が約２０個以上では、世代交代を繰り返していると、一時的に収束したような状態が見られるが、さらに世代交代を続けると、再度評価値が小さくなる場合も多い。そこで、この実施例１では、製品数が３８枚なので、収束判定を終了条件に使用せず、終了条件を世代交代回数の上限値とした。
【００３０】
即ち、１００回世代交代をした後に、評価値を比較して、最小評価値となる個体が備える染色体を引当順とする割付方を結果として出力する。この計算方法によれば、処理待ち時間はほぼ一定になる。製品数が約２０個未満の場合は、収束判定と世代交代回数の両方の上限値を終了条件に使用するとよい。
【００３１】
（具体的な処理手順）
図４のステップＳ１で、個体生成手段３６は、図３の製品データ１４から第一世代個体を５００個ランダムに生成した。５００種類の引当順を設定したことになる。この後で、例えば、図９（ａ）に示すような、図中Ａと表示した三角形の製品を、原材料の上で製品を図１０や図１１で説明するように移動させながら割付場所を選択する。
【００３２】
この製品の割付け時の状態は、図９（ａ）と（ｂ）に示すように、Ａ状態のほかに、９０度回転したＢ状態、１８０度回転したＣ状態、２７０度回転したＤ状態と、これらの各状態をｘ軸かｙ軸に対して反転したＥ状態、Ｆ状態、Ｇ状態、Ｈ状態の、合計８種類の状態が存在する。
【００３３】
同じ製品でも状態が異なると割付方が異なってくる。当然に個体の進化に影響を及ぼす。任意の製品の品番をPとしたとき、８種類の状態をPA,PB,PC,PD,PE,PF,PG,PHのように表す。図３の例に示した製品番号が１〜５の製品については、図９（ｃ）に示すように、それぞれ８種類ずつの状態が存在する。これらの状態を別々の製品のように扱って、３８枚の製品の引当順を生成する。
【００３４】
なお、特に多角形の製品に直角に等しい内角が１つ以上ある場合、直角を挟む辺をｘ軸、ｙ軸に平行になるように配置して、その向きを製品の基本の向きとしておくとよい。また、演算処理時間が長くなるような場合は、回転と反転を含めた８種類ではなく、反転したものを除く４種類にしてもよい。
【００３５】
当然のことながら、反転できない（表裏区別のある）ものは反転を考慮できないし、反転しても製品の状態が不変であるものや、回転しても製品の状態が不変であるものは、種類を減少させてよい。他の角度を考慮することも可能であるが、種類が過多となり、演算処理時間が現実離れしたものになる可能性が高く、例外を除いて考慮する必要はない。
【００３６】
以上の要領で、図９（ｄ）に示すような染色体を備える個体をランダムに５００個生成した。遺伝子配列は、製品の引当順に用いられると同時に製品の向きも決定している。この際に、第一世代個体５００個の中に含まれる1A,1B,1C,1D,1E,1F,1G,1Hのような同一品番、異符号の遺伝子の数は、それぞれ等しくしておくと好都合である。即ち、1Aの個数の和＝1Bの個数の和＝…＝1Hの個数の和というようにである。
【００３７】
次に、図４のステップＳ２で、世代交代手段３８は、上記５００個の個体を親個体とし、ランダムに２個の親個体を選択し、交叉処理で子個体２個を生成する。この処理を子個体が５００個生成されるまで行った。その後、５００個の子個体からランダムに１０個を選択し、突然変異処理を行った。
【００３８】
上記交叉処理においては、親個体のうちの任意の２個を「親１」と「親２」とし、その両方から遺伝子配列の一部を承継した染色体を備えた子個体を２個生成する。上記突然変異処理においては、上記子個体の中からランダムに選択した１０個に対して遺伝子座の任意の２つの遺伝子を交換しておく。
【００３９】
次に図４のステップＳ３、Ｓ４、Ｓ５で、実施例１では原材料の種類数＝１なので第一の製品引当順割付手段２４が全個体に適用されるまで実行される。原材料の種類数＞１ならば第二の製品引当順手段２８が動作する。親個体５００個と子個体５００個すべてについて、第一の製品引当順割付手段２４の動作を繰返し、１０００個の評価値と各原材料への割付方２０を求める。
【００４０】
未適用個体がなくなったら、ステップＳ６で世代交代回数を判断する。設定した世代交代回数＝１００に達したときは、ステップＳ８で、５００個の親個体と５００個の子個体による１０００個の評価値、即ち、原材料費用２２を比較する。最小値を持つ個体を選択して、（種類毎に）必要な原材料枚数１８と、各原材料への割付方２０と原材料費用２２を生成して処理を終了する。
【００４１】
ステップＳ６で、設定した世代交代回数に未達と判断したときは、ステップＳ７で、世代交代手段３８が個体の選択処理を実行する。ステップＳ７では上記１０００個の個体の評価値の小さいほうから５００個を選択して、次世代の親個体５００個として、ステップＳ２に戻る。この実施例１では、ステップＳ２からステップＳ７までのフローを、第１００世代まで繰り返した。
【００４２】
上記ステップＳ４で実行した第一の製品引当順割付手段２４の演算処理を、図５を用いて説明する。図４で説明したように、第一の製品引当順割付手段２４には、子個体５００個が１個ずつ与えられる。親個体は第一世代のみ５００個が１個ずつ与えられる。
【００４３】
したがって、まずステップS１０１で、与えられた個体に応じて製品の引当順を定める。次に、ステップＳ１０２で、すべての製品を未割付にし、（種類毎に）必要な原材料枚数１８を（a＝０）というように初期化する。
【００４４】
次にステップＳ１０３で、すべての製品が割付済みかどうかを判断する。割付済みときは、（種類毎に）必要な原材料枚数１８と各原材料への割付方２０と原材料費用２２を出力して、図４のステップＳ４を完了する。割付済みでないときは、ステップＳ１０４に進む。ステップＳ１０４では、（種類毎に）必要な原材料枚数１８を１枚加算し（ａ＝ａ＋１）、ステップＳ１０５へ進む。ステップＳ１０５では、遺伝子座を示すｉを１に初期化してステップＳ１０６へ進む。
【００４５】
ステップＳ１０６では、ｉ番目の製品が未割付であるか、割付済みであるかを判定する。割付済みのときは、ステップＳ１１０へ進む。未割付のときは、ステップＳ１０７に進み、予め定めた割付方法、即ち、実施例１では図７で示す方法を実行し、ステップＳ１０８で、ｉ番目の製品が割付途中の原材料４２に割付可能どうかを判定する。
【００４６】
ステップＳ１０８で割付不可能と判断したときは、ステップＳ１１０へ進む。割付可能のときは、ステップＳ１０９で、ｉ番目の製品を、割付途中の原材料４２に割り付けて、ｉ番目の製品を割付済みにし、ステップＳ１１０へ進む。ステップＳ１１０では、ｉ番目の次の製品について処理するために、ｉを１増加し、ステップＳ１１１へ進む。
【００４７】
ステップＳ１１１では、製品をすべて割付対象にしたかを判定する。即ち、ｉ＞ｍ（ｍは製品数）でないならば、次の引当順の製品についての判定のためにステップＳ１０６に戻り、ステップＳ１０６からステップＳ１１１の手順を繰り返す。ｉ＞ｍならば、すべて製品を割付対象にしたので、ステップＳ１１２へ進む。ステップＳ１１２では、いま取り出した原材料４２と割り付けた製品の割付方を確定し、記憶装置に記憶する。その後、ステップＳ１０３に戻る。
【００４８】
ステップＳ１０３で、すべて製品の割付方が確定したかどうかを判断する。未処割付の製品がある場合には、ステップＳ１０４で新たな原材料を取りだして、ステップＳ１０５からステップＳ１１２までの処理を繰り返す。一方、ステップＳ１０３で、すべて製品の割付方が確定したと判断したら、このフローチャートの処理を終了する。即ち、図４のステップＳ４の処理を完了する。
【００４９】
なお、図５のステップＳ１０７で使用する割付方法を、図７と図１０を用いて説明する。図７と図１０で示す方法は、最も単純なＢＬ法を利用したもので、非特許文献１に記載されたものである。図７のステップＳ３０１では、図５のステップＳ１０７で与えられた未割付製品を、原材料上に割付できるかを判定する。
【００５０】
図１０の（ａ）には、原材料４２の平面図を示す。この割付方法では、原材料４２の上で製品を右上から左方に移動し動けなくなったら、次に下方に動けるところまで移動して、割付場所を確定する。
【００５１】
図１０（ｂ）に示す原材料４２には、既に２枚の製品４３と４４とが割付けられているものとする。ここで、新たに製品４５を原材料４２の右上隅に配置する。このとき、その原材料４２にすでに割付済みの製品４３，４４と重ならないように割付できるかを判定する。
【００５２】
割付できないときは、図７のステップＳ３０１からステップＳ３０３に進み、割付不可能として、図５のステップＳ１０８に制御を戻して図５のステップＳ１１０に移行する。割付できるときは、図７のステップＳ３０２に進む。ステップＳ３０２では、その未割付製品４５を原材料の中からはみ出るか、あるいは、既に割付済みの製品４３と４４に阻まれて動けなくなるような位置まで左方に動かし、その後下方に動かす。図１０（ｂ）に示すように割付けができたら、その割付方を記憶装置に記憶して、制御を図５のステップＳ１０８に戻し、ステップＳ１０９に移行する。
【００５３】
以上のように、図１０の（ｂ）の例では、原材料４２に既に四角形の製品４３と三角形の製品４４とが割り付けられていた。次の引当順の四角形の製品４５は、原材料４２の右上隅に割付済みの製品４３や４４に重ならないように割付できる。そして、その製品４５を左方に移動し、さらに下方に移動して、動けなくなる位置で割付を確定する。
【００５４】
図１０（ｃ）の例では、原材料４２に既に四角形の製品４６が割り付けられていた。次の引当順の三角形の製品４７も、上記の要領で始めに左方に移動し、さらに下方に移動して、動けなくなる位置で割付を確定する。
【００５５】
そして、新たな製品を配置して、割付済みの製品に重ならないように同じ要領で移動させて、動けなくなる位置で割付を確定する。先に下方に移動し、その後左方に移動するという方法を採用してもよい。なお、原材料４２の寸法が限定されているから、最初から製品をどこにも割り付けできない場合もある。このときは、その製品を新たな原材料に割付する処理から処理が再開されることになる。
【００５６】
図８は、新たに割り付ける製品の最左頂点を、割付済み製品の頂点に重ねるように割付けるという方法を試行するＢＬ法のフローチャートである。図１１は、その割付例の説明図である。図１１に示すように、原材料４２には、四角形（台形）４８がすでに割り付けられている。
【００５７】
三角形の未割付製品４９の最左でかつ最下の頂点を重ねることができる四角形の製品４８の頂点は３つある。従って、新たに三角形の未割付製品４９を割り付ける方法は、（ａ）〜（ｃ）に示した３種類ある。これらのうち、未割付製品４９の原材料４２の下辺からの高さが最小の（ｂ）を選択することになる。
【実施例２】
【００５８】
図６は、原材料が２種類以上の場合の動作フローチャートである。このステップＳ２０１では、図５のステップＳ１０１と同様にして、製品の引当順を定める。次に、ステップＳ２０２では、やはり、図５のステップＳ１０２と同様にして、すべての製品を未割付にするとともに、原材料の数について初期化を実行する。
【００５９】
即ち、ｋ種類の原材料ｊの数を（ａｊ＝０）とし、ｋ種類の原材料ｊ（ｊ=1〜ｋ）の価格をＣｊ（ｊ=1〜ｋ）に設定する。その後、ステップＳ２０３で、すべての製品が割付済みかどうかを判断する。未処割付製品が存在する場合には、ステップＳ２０４に進み、ステップＳ２０４からステップＳ２０６までの処理をｊ=1〜ｋでかつ、ｉ=1〜ｍの間の繰り返し処理を設定する。
【００６０】
ステップＳ２０５では、ｍ枚の製品の割付試行を実行する。この図のステップＳ２０５は、図５のステップＳ１０６からステップＳ１１２の処理と同様である。この実施例２では、複数種類の製品があるので、各原材料について、製品面積当り価格ｐｊ＝価格Cj／原材料ｊに割り付けた製品面積合計を算出する。
【００６１】
与えられた引当順の全ての製品の割付が終了すると、ステップＳ２０６の処理をする。ステップＳ２０６では、製品面積当り価格を比較して、最も安い製品の面積当り価格ｐＬ（1≦Ｌ≦ｋ）を選択し、Ｌ種類目の原材料Ｌとその原材料Ｌに割り付けた製品の組合せと割付方を記憶する。図４のステップＳ４でこの処理を実行する。その他の処理は実施例１と同様である。
【００６２】
以上の処理により、製品に長方形と長方形以外の多角形が混在していても、遺伝アルゴリズム（個体生成手段、世代交代手段）と第一または第二製品引当順割付手段によって最適な引当順を求め、最適な割付結果をえることにより、製造コストの低減を図ることができる。また、実用的な演算処理時間でその最適化が可能になる。
【００６３】
なお、刃物の厚さによる割付への影響についての説明は、省略した。
【符号の説明】
【００６４】
１２  原材料データ
１４  製品データ
１８  （種類毎に）必要な原材料枚数
２０  各原材料への製品の割付方
２２  原材料費用
２４  第一の製品引当順割付手段
２８  第二の製品引当順割付手段
３６  個体生成手段
３８  世代交代手段
４０  個体データ
４２  原材料
４３  製品
４４  製品
４５  製品
４６  製品
４７  製品
【図１】
2020112965.tif 000003
【図２】
2020112965.tif 000004
【図３】
2020112965.tif 000005
【図４】
2020112965.tif 000006
【図５】
2020112965.tif 000007
【図６】
2020112965.tif 000008
【図７】
2020112965.tif 000009
【図８】
2020112965.tif 000010
【図９】
2020112965.tif 000011
【図１０】
2020112965.tif 000012
【図１１】
2020112965.tif 000013