多品目多段工程動的ロットサイズスケジューリング方法
【課題】本発明は生産納期遅れを許して実行可能解を求めるための多品目多段工程動的ロットサイズスケジューリング方法を提案する。
【解決手段】計画対象期間末における累積負荷が累積工程能力を超える場合には、負荷を減らさないで必要な工程能力を確保するために、計算上の計画対象期間末を問題自体の計画対象期間末よりも長めに設定する。納期遅れの解を許すように解の空間を拡張する。納期遅れの発生しない場合の基本解法におけるモデルの目的関数に納期遅れペナルティの項を追加する。数値計算については、ラグランジュ分解調整法にヒューリスティクスを併用する方法を適用する。
【解決手段】計画対象期間末における累積負荷が累積工程能力を超える場合には、負荷を減らさないで必要な工程能力を確保するために、計算上の計画対象期間末を問題自体の計画対象期間末よりも長めに設定する。納期遅れの解を許すように解の空間を拡張する。納期遅れの発生しない場合の基本解法におけるモデルの目的関数に納期遅れペナルティの項を追加する。数値計算については、ラグランジュ分解調整法にヒューリスティクスを併用する方法を適用する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は多品目多段工程動的ロットサイズスケジューリング問題：Multi-Item Multi-Process Dynamic Lot Size Scheduling Problem（以後MIMPDLSSPと略記する）と称する最適化問題において、注文の納期遅れを許さない限り実行可能なスケジュールを生成できない場合に、その実行可能な合理的スケジュールを生成するための多品目多段工程動的ロットサイズスケジューリング方法に関する。
【背景技術】
【０００２】
MIMPDLSSPとは、複数の機械により複数の工程で当該各工程に対応した品目をそれぞれ処理し、かつ少なくとも１つの機械または工程では段取を伴う品目の切り換えが可能な多品目多段工程生産システムに適用される生産スケジュールを生成するのに好適なスケジューリング問題であって、次の要件を満たすものである。
【０００３】
（1）処理されるものを総称して品目と呼び、システム内の機械で処理されるすべての品目（部品、半製品、製品などを含む）を対象とする。品目の集合は最終品目（製品）の集合と仕掛かり品目の集合とに分割される。最終品目（製品）とは、システム内にそれを使って作られる品目をもたない品目を指す。出荷品目は最終品目のすべての他に、仕掛かり品目の一部（問題に所与）を含む。後者は補修部品などとして出荷される品目を指す。仕掛かり品目とは、それを使って作られる品目をもつ品目を指す。
【０００４】
（2）システムに対して注文（及び計画品目の生産依頼）があり、その各々には仕様の他に数量、納期（あるいは出荷時点）が指定されている。ここに、計画品目とは、上位の生産計画によって生産されることの決められている品目、いわゆる見込み品を指す。さらに、注文の中には繰り返し品も含まれている。繰り返し品とは、計画対象期間内に複数回にわたって注文のある品目を指す。出荷要求量はその都度異なってよい。
【０００５】
（3）システムは複数の工程から成り、各工程には一つあるいは性能の異なる複数の機械がある。
【０００６】
（4）計画対象期間の各時点に納期（出荷時点）を指定された各注文及び計画品目は部品展開によって、品目毎に所要量が展開される。
【０００７】
（5）どの品目も、ロットの残りの処理を待つことなく、処理されたものから次工程へ引き渡されて次の処理のために利用できる。
【０００８】
（6）各品目の初期在庫（仕掛かり）水準データは所与である。さらに、必要であれば、計画対象期間以降の処理に対する配慮として、計画対象期間末における品目別目標在庫水準を所与のデータに追加することも許される。
【０００９】
（7）機械干渉禁止制約（どの機械も、同時に複数の異なる品目を処理することはできない）がある。
【００１０】
（8）仕掛かり品目の品切れ禁止制約（どの仕掛かり品目も品切れは許されない）がある。
【００１１】
このとき、所与の注文及び出荷要求などのデータセットに対して、総段取り費と総仕掛かり保管費との総和を最小にするなどの評価基準のもとで、実行可能で合理的なスケジュールを生成することがMIMPDLSSPである。ここに、動的ロットサイズスケジューリング（DLSS）とは、各品目の処理のロットサイズが、問題のデータセットに応じて可変time-variant（動的）であることが許されるスケジューリングを指す。
【００１２】
受注量が工程能力を超えない場合のMIMPDLSSPについては、すでに解法（以後、基本解法と略記する）が提案されている（特許文献１、非特許文献１、２）
基本解法は問題を品目別に分解してラグランジュ分解調整法Lagrangean Decomposition Coordination Method（ＬＤＣ法と略記する）を適用して解く方法である。
【００１３】
実際の製造企業のスケジューリング環境に目を向けると、納期遅れの避けられないことが決して少なくない上に、その場合には解の合理性がそうでない場合にも増して問われる。
【００１４】
計画対象期間のある時点において、ある工程の累積負荷（段取りを含む累積処理時間）が累積工程能力（累積操業時間）を超えれば、どのようなスケジューリング法によってもいずれかの注文において納期遅れが起きることは避けられない。
【００１５】
このような事態が頻発する理由として、第一に多くの企業において、工程能力余裕（バッファ）が抑えられていること、第二に仕掛かりバッファを削減する傾向にあること、第三に短納期要求、すなわちタイムバッファが極端に少ないこと、第四に製品の多様化と受注変動の激化などが考えられる。
【００１６】
第一の工程能力余裕に関しては、先の需要が読めないこと、急激な技術革新による既存技術の陳腐化などによって設備投資をした場合の資金回収のリスクを恐れて、設備投資を控える傾向が見られることが余裕の抑えられている一因である。第四の受注変動については、看過される嫌いがあるが、実態としては本来負荷変動を吸収する働きを担うはずの上記三種類のバッファが削減される一方で、外部からはそれをはるかに超える負荷変動が加わり、受注変動の激化となる。
【００１７】
納期遅れの危険が生ずると営業担当者あるいは利害関係者の思惑が絡んで出荷要求量あるいは要求納期にバイアスが入る嫌いがあり、その結果、製造販売部門間の調整あるいは営業担当者間の調整が難航する傾向が見られる。そこで、納期遅れの避けられない場合には、その影響をできる限り食い止めるために納期遅れを許すスケジューリング法が必要となる。
【００１８】
納期遅れに関する文献はあるが、多品目多段工程の生産システムを対象としたスケジューリングにおいて納期遅れを許して解を求める研究は少ない。
【００１９】
Ｗ．Ｈ．Ｉｐ等（非特許文献３）は通常の多品目多段工程から成る生産システムを対象として注文処理の納期前処理と遅れの罰金総額を最小化する問題をＧＡ（遺伝的アルゴリズム）によって解いている。しかし、各期各品目の注文ロットサイズは所与で、決定の局面が品目別期別の生産量に限られており、処理のロットの順序付けや差立ての局面には触れられていないので、処理の実行可能性については保証されない。したがって、この問題はスケジューリングの問題というよりはむしろ生産計画の問題である。
【００２０】
Ｗ．Ｋ．Ｗｏｎｇ等（非特許文献４）は服飾メーカのフローショップに対する生産計画とスケジューリングにおける納期前処理と遅れの罰金総額を最小化する問題をやはりＧＡ（遺伝的アルゴリズム）によって解いている。問題を工場への注文の負荷の割付けと各工程への処理の割付けとの二段階に分けて取り扱っており、前者においては注文に対して、後者においては各工程の処理に対して、それぞれ順序付けをする問題であり、ロットサイズは所与である。
【００２１】
Ｒｕｅｙ−Ｍａｗ Ｃｈｅｎ等（非特許文献５）は多品目多機械問題においてやはりすべてのジョブの納期前処理と遅れの罰金総額を最小化する問題であるが、そのためにロットサイズとロット順序とを決定局面としている。解法としてはニューラルネットワークが使われている。しかし、このモデルには通常の生産システムの属性として欠かせない製品構成と多段工程あるいは先行関係が陽にモデル化されていないので、このモデルは実際のスケジューリングのモデルというよりはむしろ割当問題のモデルに近い。
【００２２】
これら三つの論文に共通していえることは、（1）一般型の製品構成が取り扱えないこと、（2）段取り時間が考慮されていないこと、（3）ロットサイズ決定、ロット順序決定、差立て（使用機械決定）という三つの決定局面を同時には取り扱うことができないことである。
【特許文献１】特開２００２−３２８９７７号公報
【非特許文献１】アディティア・ワルマン，村松健児：“段取り時間のある多品目多段工程動的ロットサイズスケジューリング：ラグランジュ分解調整法”，日本経営工学会論文誌，Vol.53, No.5, pp.385-396 (2002)
【非特許文献２】Muramatsu, K.et al.: “A Near-Optimal Solution Method of A Multi-Item Multi-Process Dynamic Lot Size Scheduling Problem”，JSME Int. J. Ser. C, Vol.46, No.1, pp.46-53, March (2003)
【非特許文献３】W.H.Ip.et al.: “Multi-product planning and scheduling using genetic algorithm approach”, Computers & Industrial Engineering, Volume 38, Issue 2, pp.283-296 (2000)
【非特許文献４】W.K.Wong.et al.: “A hybrid flowshop scheduling model for apparel manufacture”, International Journal of Clothing Science and Technology, Vol.13, No.2, pp. 115-131(2001)
【非特許文献５】Ruey-Maw Chen. et al.: “Combining competitive scheme with slack neurons to solve real-time job scheduling problem”, Expert Systems with Applications, Volume 33, Issue 1, pp.75-85(2007)
【発明の開示】
【発明が解決しようとする課題】
【００２３】
このように従来の多品目多段工程動的ロットサイズスケジューリング方法には、注文の納期遅れを許されない限り実行可能な合理的スケジュール（実行可能解）を生成できない場合があった。
【００２４】
本発明の目的は多品目多段工程動的ロットサイズスケジューリング方法において、受注量が工程能力を超えるため納期遅れを許すことを余儀なくされた場合に、納期遅れを許す実行可能スケジュールを生成する方法を提供することである。
【課題を解決するための手段】
【００２５】
計画対象期間末における累積負荷が累積工程能力を超える場合には、負荷を減らさないで必要な工程能力を確保するために、計算上の計画対象期間末を問題自体の計画対象期間末よりも長めに設定する。納期遅れの解を許すように解の空間を拡張する。納期遅れの発生しない場合の基本解法におけるモデルの目的関数に納期遅れペナルティの項を追加する。数値計算については、ラグランジュ分解調整法にヒューリスティクスを併用する方法を適用する。
【発明の効果】
【００２６】
本発明によれば、生産納期遅れを許して実行可能解を求めるための多品目多段工程動的ロットサイズスケジューリング方法を提案することができる。
【発明を実施するための最良の形態】
【００２７】
以下、図面を参照して本発明による多品目多段工程動的ロットサイズスケジューリング方法の実施の形態を説明する。
【００２８】
第１の実施の形態
生産スケジューリングにおいては、短期需要の変動などによって受注量が工程能力を超える場合が少なくない。そこで、本実施の形態では、納期遅れを許して実行可能解を求めるための多品目多段工程動的ロットサイズスケジューリング問題を取り扱う。この問題を納期遅れのない場合の解法に帰着させて解く方法（提案法）を提案する。これは次の操作から成る。
【００２９】
（1）計画対象期間末における累積負荷が累積工程能力を超える場合には、負荷を減らさないで必要な工程能力を確保するために、計算上の計画対象期間末を問題自体の計画対象期間末よりも長めに設定する。
【００３０】
（2）納期遅れの解を許すように解の空間を拡張する。
【００３１】
（3）基本解法におけるモデルの目的関数に納期遅れペナルティの項を追加する。数値計算については、基本解法におけると同様にラグランジュ分解調整法にヒューリスティクスを併用する方法を適用する。さらに、その解法によって実行可能解を求めることができるか否かの検証をする。
【００３２】
[１] 提案法の前提となる基本的な考え方
既に述べたように、提案法は納期遅れのない場合のMIMPDLSSPのモデルとその解法（基本解法）を基礎にしている。そこで、その理解を助けるために基本解法と提案法に共通する解法の基本的考え方と特徴について説明する。
【００３３】
[１．１] 解法の基本的考え方と特徴
先ず、納期遅れのない場合の解法を説明する。
【００３４】
対象とする一般型製品構成（複数の品目から作られて、後工程において複数の品目の処理に使われる品目を含む）の多品目多段工程生産在庫システムの挙動は各工程における各品目の処理とそれに伴う仕掛かりの状態推移によって記述することができる。そこで、これらの挙動をできる限り実態に近い形でモデル化し目的に照らして全体最適志向で制御するために、次のような考え方をする。
【００３５】
（1）品目の処理に伴う仕掛かりの推移をモデルの中で陽に取り扱って、スケジューリング問題を動的（時間的）最適化問題、すなわち最適制御問題であると見做す。その結果、一つの品目の仕掛かり推移を記述するために一つの数学的次元が使われるから、この問題は品目数と同じ数学的次元を持つ高次元の時間最適化問題になる。
【００３６】
（2）計画対象期間を小さなタイムスロットに刻んで時間及び問題を離散化する。したがって本解法は離散化に伴う丸め誤差を容認する。
【００３７】
（3）機械ｋと品目ｉとがタイムスロットｔにおいて処理中であるか否かの関係を、モデルにおける情報の最小単位として把握して、これを原始オブジェクトと称して、その状態を、０−１決定変数δitkを用いて表示する。
【００３８】
（4）各品目の処理とそれに伴う仕掛かりの推移を、決定変数δitk及び段取りの残り時間ｓを用いて、仕掛かり推移方程式（後述の（２）式）に記述する。同様に、段取りの残り時間の推移に対しても、推移方程式（後述の（３）式）に記述する。したがって、解法においては、各品目の仕掛かりを媒介として解（スケジュール）を制御する方法を採る。
【００３９】
（5）機械干渉禁止制約（後述の（４）式）を置く。この制約が各機械とその機械を使って処理される品目の集合とをひとつの部分システムに統合する働きをすることに注目する。
【００４０】
（6）仕掛かり品目の品切れ禁止制約（後述の（５）式）を置く。この制約が各品目とそれに続く品目（作られる品目とそれを使って新たに生み出される品目）との間を繋いでひとつの多品目多段工程の生産システムを構成する働きをすることに注目する。
【００４１】
（7）全品目の計画対象期間にわたる在庫（仕掛かり）保管費と段取り費との総和の最小化などを目的関数（後述の（１）式）にとる。
【００４２】
（8）問題を品目別に分解する。この時間最適化問題の数学的次元は品目数と同じで、高次元になるから、問題を分解して次元を落とさない限り、合理的な計算時間とメモリの範囲内で解を求めることができない。ところが、どの品目の仕掛かりも処理されればその分だけ増え、次の工程において使われれば（別の品目に組み込まれれば）その分だけ減るから、一つの品目の仕掛かり推移が、その品目の処理のみでなく、それを使って処理される品目の処理にも依存することになる。言い換えると、一つの仕掛かり品目の処理が、その品目の仕掛かりを増やすと同時に、それに使われる品目の仕掛かりを減らすことになる。したがって、このままでは問題を分解することが難しい。
【００４３】
そこで、問題を品目別に分解するための工夫として、人為的に、各品目の仕掛かり推移を他の品目の処理とは独立にするために、仕掛かり（在庫）を定式化するに当って、梯状在庫（echelon inventory）（後述の（２）式）の概念を用いる。この概念は単一品目多段階在庫点を持つ在庫システムにおける最適購買政策を導くためのものである。
【００４４】
梯状在庫とは、対象在庫点にある在庫だけでなく、その在庫点から消費者に最も近い在庫点までの間に滞留している在庫を指す。
【００４５】
基本解法においては、梯状在庫の概念を次のように拡張して定義して、一般型製品構成の多品目多段工程生産在庫（仕掛かり）システムに適用する。このシステムにおける各品目の梯状在庫とは、その品目の仕掛かりの他にも、既に半製品、製品などに組み込まれるか使われて、見かけの形を変えて系内に滞留しているものを含むものとする。この定義によれば、各品目の梯状在庫の推移はその品目が処理されればその分だけ増え、その品目を組み込まれたかそれによって作り出された品目が出荷されたときに初めて、その分だけ減ることになって、他の品目の処理には影響を受けないことになる。そこで、この性質に注目して、問題を品目別に分解して、加算分離可能性を導く。ここに、加算分離可能性とは、問題を部分問題に分解したときに、同じ決定変数が複数の部分問題に表れないように分解することができることを指す。
【００４６】
この取り扱いに応じて、品目の在庫保管費についても、その品目に対する付加価値のみを基礎にして算定する方法に変更するものとする。このようにしても、算定されるシステム内の総在庫保管費は通常の算定法によるものと異ならない。
【００４７】
（9）この問題を品目別に分解した後、ラグランジュ分解調整法を基礎にして解く。すなわち、この最適化問題の機械干渉禁止制約（（４）式）と、仕掛かり品目の品切れ禁止制約（（５）式）とをラグランジュ緩和した後に品目別に分解して、それぞれ部分最適化をすることと、各制約の摂動に応じたラグランジュ乗数の調整とを繰り返して、最適化と制約違反解消とを共に追求する。
【００４８】
[１．２] 基本解法の特徴
基本解法の諸特徴の中で、後述する提案法と関連する特徴を掲げる。
【００４９】
（1）モデル化に当たって、１．１節の（3）の原始オブジェクトを制御（あるいは情報）の最小単位として、実システムの挙動をありのままに記述する方法（後述の（２）式、（３）式）が採られ、離散化における丸めの誤差が入ることの他には、処理の自由度が人為的に制約される心配がなく、その結果、実行可能解の領域が大きく広がること。
【００５０】
（2）各品目の仕掛かり推移方程式（後述の（２）式）を陽に取り扱うこと。
【００５１】
（3）問題に含まれる、ロットサイズの決定、順序の決定、負荷の平準化、差立て（使用機械の決定）などの多様な異質の決定局面を意識しないで決定する（解から読み取る）ことができること。
【００５２】
（4）各品目の処理のロットサイズは可変になる、すなわち、同じ品目であっても、状況に応じて計画対象期間の時点によってサイズが異なること。
【００５３】
（5）各品目の処理とその品目を使って生み出される品目の処理との時間的な関係（位相）は重複あるいはその逆に間を置くことも含めて、品切れが生じない限り（仕掛かり品目の品切れ禁止制約）どのようであっても許されること。
【００５４】
（6）上記（3）に述べた多様な異質の決定局面をすべて同時に全体最適志向で決定することができること。
【００５５】
（7）分解調整法であるから、問題の規模が増えても計算に要する時間とメモリについては組合せ爆発を避けることができること。
【００５６】
要するに、これらの基本解法の特徴は採りうるアクションの自由度を実際の問題におけると同じにして、全体最適志向で状況に応じて解を求めることができるための条件を満たしていることを示している。
【００５７】
上述の基本概念、モデル、解法を総称して、Object Oriented Optimization Technologyオブジェクト指向最適化技術（Ｏ２Ｏ−テクノロジ）と呼ぶ。
【００５８】
結局、基本解法においては、各品目に対して部分最適化問題が解かれることと、制約条件の充足のためのラグランジュ乗数の更新とが、予め決められた停止条件が満たされるまで反復される。ここに、部分最適化問題においては、その都度制約条件の充足のためのペナルティコスト（ラグランジュ乗数）の変化を配慮して、その品目の可変ロットサイズでの処理の計画が下される。
【００５９】
[２] 納期遅れを許す問題の数理モデル
[２．１] 本問題のモデル化の考え方
本問題を基本解法に帰着させて解くためのモデル化の考え方を述べる。
【００６０】
（1）計算上の計画対象期間の延長
ある工程の計画対象期間末における累積操業率が1を超えると予想される場合には、消化しきれない負荷が生じる危険が高い。ここに、累積操業率とは、その時点までの稼動時間と段取り時間の累積を累積工程能力で除した値である。そこで、その場合には、問題自体の計画対象期間についてはそのままにして、計算上の計画対象期間を、累積操業時間に余裕ができる程度にまで、延長する。そうでない場合（計画対象期間の途中では予想累積操業率の推移が１を超えるが、期間末においては１を超えない場合）には、それを変更しない。
【００６１】
（2）実在庫の梯状在庫による記述
納期遅れのある実行可能解の梯状在庫を用いたモデル化における必要十分条件を明らかにして、それをモデル化する。基本解法においては、問題の加算分離可能性を保つために梯状在庫による問題の定式化がなされているから、この解についてもそれに沿ってモデル化がなされない限り基本解法が適用できない。
【００６２】
そこで、まず、この解の実在庫を用いたモデルにおける必要条件に注目すれば、これは、最終品目（製品）に対しては負の在庫をもつが、仕掛かり品目に対しては仕掛かり不足の生じていない解である。なぜならば、製品が納期遅れを起こせば、それは、広く知られているように、未処理の受注残（backlog）として取り扱うことができるから、負の在庫と見做すことができる。一方、出荷品目を除く仕掛かり品目に対しては、それが品切れを起こせば、それを使って処理される品目が作れないから解は実行可能にならない。したがって、出荷品目を除く仕掛品目については品切れが許されない。さらに、出荷品目でもある仕掛品目については、出荷される数量に限って納期遅れを認めて受注残として取り扱うことが理論的には可能である。しかし、出荷される部分に対しては補修品のように出荷の優先順位が高いことが多いので、出荷品目でない仕掛り品目の場合と同様に品切れは許されないものとして取り扱う。
【００６３】
次に、この条件を梯状在庫の概念を用いて再定式化する。最終品目（製品）に対しては、梯状在庫と実在庫とは同じであるから、在庫が負になることを認めることで片付く。しかし、仕掛かり品目（最終品目でない品目）に対しては、次のように考えることができる。最終品目のみでなく、それに使われている仕掛かり品目についても、最終品目の出荷時点までに処理が片付かなければ、仕掛かり品目の梯状在庫が不足して負になることは避けられない。そこで、仕掛かり品目の梯状在庫が負になることを認める。しかし、その品目の実在庫が負になることは、先に述べた理由によって、許されない。そこで、実在庫を梯状在庫によって定式化した後に、仕掛かりの実在庫の品切れ禁止制約（後述の（５）式）を置く。これらの取り扱いによって、納期遅れのある実行可能解の梯状在庫によるモデル化は解決する。
【００６４】
（3）目的関数において納期遅れコストを付加する
これでモデルの拡張はできる。このモデルに対して、非実行可能解から始めてラグランジュ分解調整法の反復を逐次実行して解を実行可能解へ導いていくプロセス（後述の（１）式）は、納期遅れのないMIMPDLSSPに対する基本解法と何ら異ならない。
【００６５】
[２．２] 数理モデル
本問題の数理モデルは基本的には、納期遅れの無い場合の問題を定式化した既存モデルと異ならない。本問題のモデルをまとめると、以下のように記述できる。
【数１】
【００６６】
梯状在庫量の推移方程式
【数２】
【００６７】
段取時間の推移方程式
【数３】
【００６８】
機械干渉禁止制約
【数４】
【００６９】
仕掛かり品目の実在庫の品切れ禁止制約
【数５】
【００７０】
梯状在庫量の範囲
【数６】
【００７１】
各種所要量の関係
【数７】
【００７２】
すなわち、納期遅れのある多品目多段工程動的ロットサイズスケジューリング法は（２）式〜（６）式の制約条件の下で，（１）式の目的関数を最小化する問題である。
【００７３】
記号の説明の前に、このモデルにおいて新しく追加された部分を説明する。先ず、（１）式の括弧（ ）内の第一項ｂikは基本モデルにおいては見られなかった項で不要な機械の使用を避けるための機械使用料に相当する。第二に、基本モデルにおける仕掛かり保管費の項が梯状在庫の符号に応じて、（ ）内の第三項と第四項のように別れたことである。第三に、（６）式の梯状在庫量の下限ｘiminを負の値にまで拡張したことである。
【００７４】
続いて、記号の説明をする。
【００７５】
（１）添字
ｉ：品目または処理番号を表し，その集合をＩ＝｛1,2,…,nI-1,nI｝とする。ただし，ｉ＝０は市場（システムの外）を表す。
【００７６】
ｋ：機械を表し，その集合をＫ＝｛1,2,…,nK-1,nK｝とする。
【００７７】
ｔ：タイムスロット（以降tsと略記することもある）を表し，その集合をＴ＝｛1,2,…,nT-1,nT｝とする。
【００７８】
（２）集合
Ａ：仕掛かり品目の集合
Ｋ(i)：品目ｉを処理することのできる機械の集合
Ｍ(k)：機械ｋが処理できる品目の集合
Ｐ(i)：品目ｉの先行直結品目（品目iに使われる品目）の集合
Ｓ(i)：品目ｉの後続直結品目（品目iが使われる品目）の集合（空集合を含む）
（３）入力データ
ｂik：機械ｋにおける品目ｉの１タイムスロット当たりの機械使用料（所与）
ｃik：機械ｋにおける品目ｉの1回当たりの段取費用（所与）
ｄi：品目ｉの１単位当たり１タイムスロット当たりの納期遅れペナルティ（所与）
ｈi：品目ｉの処理によって新たに付加される価値に対する１単位当たり１タイムスロット当たりの仕掛かり保管費、すなわち梯状在庫（仕掛かり）保管費（所与）
ｐik：機械ｋにおける１タイムスロット当たりの品目ｉの処理量（所与）
ｒi0t：品目ｉのタイムスロットｔにおける外部需要あるいは出荷要求量（所与）
ｒijt：タイムスロットｔにおいて品目ｊを生産するために使用される品目ｉの所要量
ｒi・t：品目ｉのタイムスロットｔにおける部品展開後の所要量
ｓimaxk：機械ｋにおける品目ｉに対する段取り時間（所与）
ｘi0：品目ｉのタイムスロットｔ＝０における梯状在庫量，すなわち初期梯状在庫量
ｘimax：品目ｉの梯状在庫量の上限値（所与）
ｘimin：品目ｉの梯状在庫量の下限値（所与）
ｙi0：品目ｉのタイムスロットｔ＝０における実在庫量，すなわち初期実在庫量（所与）
δi0k：機械ｋにおける品目ｉのｔ＝０における処理の状態，すなわち初期値（所与）
ρij：品目ｊ１単位当たりの品目ｉの所要量（所与）
（４）ラグランジュ乗数
μ・tk：機械ｋのタイムスロットｔにおける機械干渉禁止制約（４）式に対応するラグランジュ乗数
μit：仕掛かり品目ｉのタイムスロットｔにおける品切れ禁止制約（５）式に対応するラグランジュ乗数
（５）決定変数
δitk：タイムスロットｔにおいて、機械ｋにより、品目ｉを処理するときに１をとり、その他の場合には０をとる０−１決定変数。
【数８】
【００７９】
（６）状態変数
【数９】
【００８０】
しかし、品目ｉが最終品目（製品）の場合には梯状在庫は実在庫と一致する。
【００８１】
（７）その他
ν：計算の反復を表す番号
[２．３] ラグランジュ関数とその分解
ラグランジュ関数を次式に示す。
【数１０】
【００８２】
ラグランジュ関数の分解
【数１１】
【００８３】
部分最適化問題
したがって、ラグランジュ関数の最小化問題（（１）式）は次のような部分最適化問題に分解することができる。
【数１２】
【００８４】
[３] 提案法及びその例解
[３．１] 提案法の構成
本提案法はラグランジュ分解調整（LDC：Lagrange Decomposition Coordination）法による基本解法の計算を途中で打ち切って、その中間結果（非実行可能解）を受け取り、この解から実行可能解を導出するためのヒューリスティクス解法へ切り替えるものである。
【００８５】
定義：基本解法の計算打ち切りルール
この基本解法の計算打ち切りの評価式として、
機械干渉違反総タイムスロット数／（計算上の計画対象期間タイムスロット数×機械台数）と、
仕掛かり品目の総品切れタイムスロット数／（計算上の計画対象期間タイムスロット数×仕掛かり品目数）と、
を用い、これらの比が初めて共に予め定めたある値α(％)を下回ったときの反復νにおいて計算打ち切りを実施するものとする。
【００８６】
定義：提案法Ｈ(α)法
基本解法を打ち切り、上記のルールを適用する解法を、以後、Ｈ(α)法と称することにする。
【００８７】
したがって、提案法は（1）負荷の把握と計画対象期間の調整、（2）基本解法による最適化と制約充足の数値計算、（3）Ｈ(α)法による実行可能解の導出から成る。その構成と手順との関係を図１に示す。図１のステップＳ１の「負荷の把握と計画対象期間の調整」の手順を図２に示す。図１のステップＳ２の「基本手法による最適化と制約充足の数値計算」の手順を図３に示す。図１のステップＳ３の「Ｈ(α)法による実行可能解の導出」の手順を図４に示す。
【００８８】
[３．２] 解法の手順と例解
以下に解法の手順（流れ）を示す。Ｈ(α)法の手順、したがって、基本解法の解（非実行可能解）を初期解とするヒューリスティクスについては、様々な解法が考えられる。
【００８９】
説明の便宜を考慮して、例解を括弧（ ）内に併記する。例解の工程フローを図５に、さらに、計算の結果については、図６から図１１に示す。
【００９０】
ステップＳ１１：問題の入力データ一式を登録して、前処理によりスケジュール生成の計算に必要なデータ一式を用意する。
【００９１】
（1）品目j1単位当たりの品目iの所要量ρij（表１）
（2）生産技術データ（1タイムスロット当たりの処理量ｐik、段取時間ｓimaxk、段取費用ｃik、機械使用料ｂik）（表２の各欄の４つの数値が左から順に処理量、段取時間、段取費用、機械使用料を示す）
（3）初期実在庫量ｙi0、仕掛かり保管費ｈi、納期遅れペナルティｄi、外部需要ｒi0t（表３）
（4）初期梯状在庫量ｘi0、梯状在庫量の下限値ｘimin、上限値ｘimax、部品展開後の所要量ｒi t（表４）
【表１】
【００９２】
【表２】
【００９３】
【表３】
【００９４】
【表４】
【００９５】
表１の品目j1単位当たりの品目iの所要量ρijと表２の生産技術データについては、データを読み込む。表４の部品展開後の所要量ｒi・tは表３の外部需要ｒi0tに対して、（７）式、（８）式を用いて算出する。
【００９６】
ステップＳ１２：システムパラメータ一式を設定する。
【００９７】
（1）タイムスロット（ts）：（１ts＝30分）
（2）計画対象期間：スケジューリング立案期間（２４０tsとする。ここに、２４０tsは１tsを30分、１日の実働時間を２４時間、５日間を計画対象期間として算出した値である。）
（3）基本解法におけるＬＤＣ法の計算打ち切りの基準値α：（例えば３％とする。制約違反件数の減少状況に応じて、再設定する場合もある。）
ステップＳ１３：最適化問題の基本解法における反復計算を一回だけ行う。
【００９８】
これは、入力データから、機械干渉、仕掛かり不足などの実行可能性を無視して、品目別の部分最適化のみを考慮した解に基づいて、機械別、タイムスロット別負荷の状況を把握するための基礎データを得ることが目的である。（ｘimin＝０、ｎＴ＝２４０とし、さらに、すべてのラグランジュ乗数を０とおいて、すべてのｉについて（１３）式を１回だけ（反復回数ν＝１）解いてすべてのｉ、ｔ、ｋの解を得る。）
ステップＳ１４：累積操業率グラフを作成して表示する。オペレータはこのグラフを見て、必要ならば計算上の計画対象期間を延長し、計画対象期間の再設定をする（２．１節（1）を参照）。ここまでの手順で前処理が終わる。（例えば、図６に示すように、２４０tsの(1)計画対象期間を、２４ts（半日）延長して、２６４ts（(2)計算上の計画対象期間）とする。）
ステップＳ２１：延長された期間に対して各制約に対する違反件数比が共にαを下回るまで基本解法（ＬＤＣ法：(１３)式を計算する）を反復実施する。図７の(a)から(f)に示すように、各制約に対する違反件数比が共にαを下回った計算の反復回数νにおいて、ＬＤＣ法の計算を打ち切り、Ｈ（α）法へ切換える。
【００９９】
ステップＳ３：ヒューリスティクスによって実行可能解を生成する。ここでは、最初に機械干渉を解消して、続いて機械干渉を避けながら、仕掛かり不足を解消させる。
【０１００】
ステップＳ３１：ステップＳ２１の結果から、すべての品目ｉ、すべての機械ｋ、すべてのタイムスロットｔに対して、解（決定変数）δitkの値（実行可能解の場合は１か０）を読み取る。
【数１３】
【０１０１】
（2）解δitkを用いて、機械別にすべての遊休時間の開始時点と終了時点を把握する。これも（１）式と同様に数式による記述ができる。
【数１４】
【０１０２】
ステップＳ３２：機械干渉箇所を特定する。
【０１０３】
（1）機械干渉禁止制約（（４）式）は左辺の値が１以下であることを示し、左辺の値が２以上となるロット（δitk集合）が制約違反箇所である。これにより、システムが解δitkに基づいて（４）式より機械別、品目別に機械干渉を起こしているロット、および干渉を起こしている期間を特定することができる。
【０１０４】
ステップＳ３３：機械干渉を解消する。
【０１０５】
（1）機械干渉を起こしているロットを、状況に応じて、バックワード法、フォワード法等により移動して、機械干渉を解消する。ステップＳ３２で機械干渉を起こしているロットとその期間が特定されているので、ステップＳ３３ではシステムが機械干渉を起こしているロットを選び出し、そのロットをバックワード法（時間軸上で見た場合、後ろへシフトさせる）、あるいはフォワード法（時間軸上で見た場合、前へシフトさせる）によって移動させることによって機械干渉を解消することができる。
【０１０６】
（2）機械干渉解消後はそのロット順序を基本的に保ちながら、以後の各手順を行う。
【０１０７】
ステップＳ３４：仕掛かり品目の品切れ箇所を特定する。
【０１０８】
（1）仕掛かり品目の実在庫の品切れ禁止制約（（５）式）は左辺の値が負であることを示し、左辺の値が正になるロットが制約違反箇所である。これにより、システムが品目ｉのタイムスロットｔにおける梯状在庫量ｘitに基づいて、（５）式より品目別に品切れを起こしているロット、および品切れを起こしている期間を特定することができる。
【０１０９】
ステップＳ３５：仕掛かり品目の品切れ箇所を解消させる。
【０１１０】
（1）仕掛かり不足を起こしている品目のロットを早める、あるいは遅らせる。
【０１１１】
（2）あるいは、そのロットと一つ前のロットの順序を入れ替える。
【０１１２】
（3）さらに、後続直結品目のロット処理を遅らせるなどにより状況に応じて処置を取る。ステップＳ３４で仕掛かり品目の品切れ箇所とその期間が特定されているので、ステップＳ３５ではシステムが品切れを起こしているロットを選び出し、梯状在庫量ｘitに基づいてｘitのマイナスの箇所が無くなるように、(1)から(3)を実施することにより仕掛かり品目の品切れ箇所を解消することができる。ｘitのマイナスの箇所とは、その品目ｉ、タイムスロットtにおいて品切れを起こしている箇所である。ｘitは０以上でなければ実行可能解ではなく、ｘitにマイナスの箇所があると実行可能解ではない。
【０１１３】
ステップＳ３６：納期遅れスケジュール結果の保存と出力をする。
【０１１４】
すべての制約違反が解消されたら、計画対象期間にわたる品目別在庫推移グラフ及び機械別品目別ガントチャートデータを作成し、メモリに保存する（図８、図９）。
【０１１５】
ステップＳ３７：納期遅れ箇所を確認する。
【０１１６】
品目別在庫推移グラフ及び機械別品目別ガントチャートデータを表示し、オペレータが納期遅れ品目とその期間を確認する。納期遅れが許容されない期間となっている場合は、ステップＳ１１の入力データの一部、具体的には、表２の段取費用、表３の仕掛かり在庫保管費、外部需要を変更して解きなおす。あるいは、ステップＳ１２のシステムパラメータの一部、具体的には，計画対象期間、制約違反件数比αを変更して解きなおす。なお、ステップＳ１１、Ｓ１２の変更はかならずしも両方ともこの順番に変更する必要は無く、得られた解の状況に応じて何れか一方のみでも良いし、先ずステップＳ１１（またはＳ１２）のデータ（またはシステムパラメータ）を変更して解きなおし、オペレータの納得いく解が得られなかった場合は、さらにステップＳ１２（またはＳ１１）のシステムパラメータ（またはデータ）を変更して解きなおせばよい。
【０１１７】
[４] 例解の結果と考察
[４．１] 例解の結果
順を追って例解に対する計算の過程とその結果を説明する。
【０１１８】
（1）入力データ
図５は例解に用いられた数値例に対する生産システムの工程フローである。８台の機械（機械１〜機械８）によって２０品目（図５の丸数字）を処理しているが、工程間のフロー及び品目構成はそれなりに複雑である。例えば、品目１４、６、２のように逆流（通常は左から出荷側の右へ流れるが、出荷側から左へ逆流する）がある、あるいは品目１７、１８のように同一の機械７が繰り返し使われる、さらに、２つの品目９、１０から１つの品目１６が作られる、あるいは、品目５は２つの品目８、１０へ使われる、さらにまた、品目３、４、５等々に代替ラインが存在するなどの様に製品構成、工程編成等々に関しても、現実にも起きうる構造をほぼすべて反映している。例えば、品目３は機械１と機械２で処理され、品目４は機械２と機械３で処理され、品目５は機械２と機械３で処理されているが、一つの品目を複数の機械で処理が可能な場合、それらを代替ラインと呼ぶ。
【０１１９】
表１から表４はステップＳ１１で使われる。表３のタイムスロット２４０の外部需要には、計画対象期間末における持ち越し在庫量が含まれている。これは次期計画対象期間の初期実在庫量に相当する。表２の段取り費用ｃikと表３の仕掛かり保管費ｈiについては、標準原価あるいは政策的費用の意味合いがある。したがって、段取り回数を減らすために段取り費用を増やす、あるいは仕掛かりを減らす意図で保管費を増やすなどのように、数値計算の過程でこれらの値を試行錯誤により修正することができる。
【０１２０】
（2）各機械の累積操業率グラフと計画対象期間の修正
図６はステップＳ１３により基本解法を一回だけ回して差立てられたときの負荷状況に対する累積操業率グラフ（ステップＳ１４で作成）である。機械７の期間末の累積操業率が１００％を超えているので、計算上の計画対象期間を２６４tsまで延長した。必要に応じて、ステップＳ１３、Ｓ１４を繰り返し、計画対象期間の再設定を行うことができる。
【０１２１】
（3）ＬＤＣ法の計算過程
図７はステップＳ２１でＬＤＣ法により（１３）式を解が収束するまで反復させたときの制約（機械干渉禁止制約（４）式と、仕掛り品目在庫の品切れ禁止制約（５）式）違反数の推移である。図の黒い線が機械干渉禁止制約（（４）式）の推移を示し、灰色の線が仕掛り品目在庫の品切れ禁止制約（（５）式）の推移を示す。(a)から(e)は計算の打ち切り時点を、(f)はＬＤＣ法のみで実行可能解を算出した時点を示す。図１０（ａ）、（ｂ）はそれぞれ、ＬＤＣ法のみで実行可能解を算出したとき、すなわちＨ(０)法、ν＝８８８２（図７の(f)）の機械別、品目別のタイムスロット別のラグランジュ乗数（禁止制約(４)式、(５)式に対応するラグランジュ乗数μ・tkとμit）値である。
【０１２２】
ラグランジュ乗数は制約に対する双対コスト、すなわち、影の価格（shadow price）を表すことが知られている。したがって、これらのグラフから、何時、どの機械とどの品目に対して資源が不足し、調整が難航しているかの様子が概観できる。すなわち、図１０（ａ）から、計画対象期間全般にわたって機械７に高い負荷が掛っており、その機械の干渉を解消させることが困難であったことがわかる。一方、図１０（ｂ）からは、各品目に対するラグランジュ乗数の推移に周期性があることが読み取れる。
【０１２３】
これには二つ理由がある。第一は、入力データにおける毎日の出荷要求時点（表３の外部需要がある時点）が日によって変わらないで、それが丁度ラグランジュ乗数のグラフの山に対応していることによる。第二は、本発明においては前処理の段階でオフセット（手番）を考慮しないで所要量を出荷要求時点に対して展開し、それらを提案法のＨ(α)法自体が自動調整して品目間の処理の位相を決定する仕組みを内包しているために、どの品目についても出荷要求時点にラグランジュ乗数値のグラフの山が来ることによる。
【０１２４】
（4）ＬＤＣ法の反復に伴う累積操業率グラフの変化から見た提案法の納期遅れスケジューリング効果
図１１（ａ）は計算打ち切り基準α＝３(％)、つまりＨ(３)法、ν＝２９５９で計算を打ち切ったときの累積操業率グラフ（非実行可能解）であり、図１１（ｂ）はＨ(３)法、ν=２９５９からヒューリスティクスを用いて実行可能解を算出したときの累積操業率グラフである。図１１（ａ）では機械５は１５ts付近で、機械７は７tsから３２ts間、１７９tsから２６４ts間で累積操業率が１００％を越えている。ヒューリスティクスを用いて実行可能解を算出したときの図１１（ｂ）では、すべての機械について累積操業率は１００％以下に抑えられている。また、図１１（ｃ）はＨ(０)法、ν＝８８２２で実行可能解が算出されたときの累積操業率グラフであって、こちらも同様に１００％以下となっている。これは、本発明が、納期遅れスケジューリングに効いていることを示唆している。すなわち、その原理が有効に働いて、納期遅れを認めて工程能力を超える負荷の処理が先送りされている。また、一部に他の機械への処理の移動によって負荷調整が行われている。
【０１２５】
（5）納期遅れスケジュール結果の例
図８（ａ）はＨ(３)法、ν＝２９５９からヒューリスティクスを用いて実行可能解を算出したときの品目別在庫推移グラフ、図８（ｂ）はそのときの機械別品目別ガントチャートを示す。図９（ａ）はＨ(０)法、ν＝８８２２で実行可能解を算出したときの品目別在庫推移グラフ、図９（ｂ）はそのときの機械別品目別ガントチャートを示す。
【０１２６】
図８（ａ）、図９（ａ）は計画対象期間における品目別の在庫推移を図示したものである。図８（ａ）の在庫推移グラフから、４つの最終品目で合計１４箇所（納期遅れ総タイムスロット数は１８９）の納期遅れが発生していることがわかる。すなわち、品目１６については４箇所（ts＝４８〜５６、ts＝１４４〜１６６、ts＝１９２〜１９５、ts＝２４０〜２４８）、品目１８については２箇所（ts＝１９２〜２２５、ts＝２４０〜２６１）であり、品目１９、２０についても納期遅れが見られる。
【０１２７】
図８（ｂ）、図９（ｂ）のガントチャートから、機械ｋ、品目ｉ、タイムスロットｔの状態は、すべて読み取ることができる。例えば、図８（ｂ）の品目１９に注目すれば、機械７と機械８で処理され、ロットサイズは可変である。また、両機械にはほとんど遊休がないことが分かる。
【０１２８】
その他のＨ(α)法の結果については、いずれも同じような傾向を示すので、説明の便宜上最終結果のみの統計データを表５に掲げる。
【表５】
【０１２９】
（6）ＬＤＣ法及びＨ(α)法の比較
表５は（１）式の目的関数値とその内訳に関する比較である。ＬＤＣ法による結果と異なるαに対するＨ(α)法の結果との間に大きな差異は見られない。
【０１３０】
最後に、納期遅れの解の合理性を評価するために、次式（１４）によって納期遅れ対応後の機械別操業率と称する指標を定義する。
【数１５】
【０１３１】
図１１の例においては、機械７と機械８がボトルネック工程である。そこで、表６には機械７と機械８についてのみ、結果を掲げている。これらの結果から、次の特徴が見られる。第一に、ＬＤＣ法の打ち切り基準値αの変化に対しては大差がない。第二に、機械の遊休がほぼ極限まで下げられており、したがって、納期遅れは避けられないものの、納期遅れの少ない合理的な解が得られていると判断できる。第三に、納期遅れ総タイムスロット数については多少変動が見られるが、これは解法に伴う誤差変動によるものと考えられる。
【表６】
【０１３２】
図１２は本発明の一実施形態に係る多品目多工程ロットサイズスケジューリング装置の構成を示す。このスケジューリング装置は多工程から成る生産システムにおいて多様な注文を複数の品目に分類して切り換え生産をするためのスケジューリング（多品目多工程ロットサイズスケジューリング）の有する問題、つまり高次元時間最適化問題を解いて最適スケジュール（最適生産スケジュール）を決定するものである。この装置は全体を制御するＣＰＵ１０２、当該ＣＰＵ１０２が実行する最適化スケジューリングプログラム１１８を含む各種プログラム及びデータ等が記憶される主メモリ１０４とを備えている。本装置はまた、外部記憶装置としての例えば磁気ディスク装置（以下、ＨＤＤと称する）１１２と、記録媒体としての例えばＣＤ−ＲＯＭ１１６に予め格納されている情報を計算機内に読み込むことが可能なＣＤ−ＲＯＭ装置１０６とを有している。この例では、ＣＤ−ＲＯＭ１１６には、上述した複数の工程（多工程）、多機械（多設備）で複数の品目を生産する生産システムにおける多品目多工程ロットサイズスケジューリングを行うための最適化スケジューリングプログラム１１８が予め格納されている。この最適化スケジューリングプログラム１１８はＣＤ−ＲＯＭ装置１０６によりＣＤ−ＲＯＭ１１６から計算機内に読み込まれて、ＨＤＤ１１２に格納（インストール）されていものとする。ＣＰＵ１０２がＨＤＤ１１２から最適化スケジューリングプログラム１１８を主メモリ１０４上に読み込んで当該プログラム１１８を実行することにより、図１に示したフローチャートに従ったスケジューリング方法が実現される。
【０１３３】
本装置は更に、入力装置としてのキーボード１０８と、表示用の出力装置としてのディスプレイ１１０とを有している。ＣＰＵ１０２、主メモリ１０４、ＨＤＤ１１２、ＣＤ−ＲＯＭ装置１０６、キーボード１０８及びディスプレイ１１０はシステムバス１１４により相互接続されている。
【０１３４】
[４．２] 考察と検証
上述した例解の結果を考察して本発明の有効性を検証する。
【０１３５】
（1）なぜＨ(α)法によって納期遅れのある実行可能解を導くことができるか
ＬＤＣ法はラグランジュ緩和法の一つである。ラグランジュ緩和法が制約を満たすための効果的な方法であることは広く知られている。しかし、乗数の更新は他の乗数の更新とは独立になされる。制約付きの最適化問題が連続で凸である場合には、そのような取り扱いによっても最適解へ収束することが保証されている。
【０１３６】
ところが、スケジューリング問題においては、この種の数学的に収束を保証するための性質は成り立たない。したがって、他の乗数と独立に乗数の更新を行うラグランジュ緩和法によって解の収束を期待することには無理がある。
本問題においては、各機械ｋ、タイムスロットｔに対して機械干渉禁止制約（４）式に対応するラグランジュ乗数μ・tkが、あるいは各品目i、タイムスロットtに対して品切れ禁止制約（５）式に対応するラグランジュ乗数μitが、それぞれ、その他のラグランジュ乗数とは独立に更新される。このことは、それぞれある機械ｋとタイムスロットｔに対する機械干渉違反を解消する際に、近隣の機械干渉の状況を利用しないで処置をとる、あるいはある品目iとタイムスロットｔに対する仕掛かり品の品切れを解消する際に、近隣の仕掛かり品の品切れの情報を利用しないことを指す。
【０１３７】
そこで、この欠陥を解消するための容易な方法として、近傍の情報を利用して納期遅れのある実行可能解を生成するために状況に応じてバックワード法、フォワード法を併用するヒューリスティクス（Ｈ(α)法）を提案した。しかし、ヒューリスティクスの適用は既に反復打ち切り時における各制約の違反件数百分比αが十分に下がった段階での解の微調整であるから、目的関数値に与える影響は少なくて済み、納期遅れのある実行可能解を求めることができる。
【０１３８】
（2）なぜ合理的な（無駄な納期遅れの無い）解が得られるか
４．１節（6）で述べたとおり、納期遅れを来している工程の機械に対しては、納期遅れ対応後の機械別操業率がＬＤＣ法のみでなく反復打ち切り時における各制約の違反件数百分比αが５％以下の幅広い範囲に対しても、Ｈ(α)法が高い評価値を示した。
【０１３９】
それには次の三つの理由が考えられる。第一に、目的関数において遅れの発生に対して遅れコストが設定されていることである。したがって、できる限り遅れを発生させない力が働く。第二に、どの品目に対しても部品展開の段階でオフセット（手番）を０として取り扱っており、提案法には工程リードタイムの概念が無いので、仕掛かり品目が品切れを来さない限りその品目を作るための処理とそれを使ってなされる処理の位相を、同期化も含めて、近づけることができる。すなわち、計画対象期間内の処理を密にすることができる。第三に、ロットサイズ固定、リードタイム固定などの人為的な制約が置かれていないので、状況に応じてロットサイズを可変にすることができる。すなわち、解法自体に大きな処理の間の隙間を埋める力が働くと考えられる。
【０１４０】
以上説明したように本発明では納期遅れを許して実行可能解を求めるための多品目多段工程動的ロットサイズスケジューリング問題を納期遅れのない場合の解法に帰着させて解いた。これは大別して次の三つの付加的段階から構成される。先ず、計画対象期間末における累積負荷が累積工程能力を超える場合には、必要な工程能力を確保するために、計算上の計画対象期間を延長する。さらに、納期遅れの解を許すように、解の空間を拡張する。最後に、基本モデルの目的関数に納期遅れペナルティの項を追加する。
【０１４１】
数値計算については、ラグランジュ分解調整法にヒューリスティクスを併用する方法を用いた。
【０１４２】
なお、この発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【０１４３】
また、本発明はコンピュータに所定の手段を実行させるため、コンピュータを所定の手段として機能させるため、コンピュータに所定の機能を実現させるため、あるいはプログラムを記録したコンピュータ読取り可能な記録媒体としても実施することもできる。
【図面の簡単な説明】
【０１４４】
【図１】本発明の一実施形態による多品目多段工程動的ロットサイズスケジューリング方法の構成を示す図。
【図２】図１のステップＳ１の「負荷の把握と計画対象期間の調整」の手順を示す図。
【図３】図１のステップＳ２の「基本手法による最適化と制約充足の数値計算」の手順を示す図。
【図４】図１のステップＳ３の「Ｈ(α)法による実行可能解の導出」の手順を示す図。
【図５】例解の工程フローを示す図。
【図６】反復回数ν＝１のときの累積操業率グラフを示す図。
【図７】制約違反件数の推移を示す図。
【図８】計画対象期間にわたる品目別在庫推移グラフ及び機械別品目別ガントチャートデータを示す図。
【図９】計画対象期間にわたる品目別在庫推移グラフ及び機械別品目別ガントチャートデータを示す図。
【図１０】機械別タイムスロット別、品目別タイムスロット別のラグランジュ乗数値を示す図。
【図１１】計算を打ち切ったときの累積操業率グラフ（非実行可能解）、打ち切り後ヒューリスティクスを用いて実行可能解を算出したときの累積操業率グラフ、Ｈ(０)法で実行可能解が算出されたときの累積操業率グラフを示す図。
【図１２】本発明の一実施形態による多品目多段工程動的ロットサイズスケジューリング装置の構成を示す図。
【符号の説明】
【０１４５】
１０２…ＣＰＵ、１０４…主メモリ、１０６…ＣＤ−ＲＯＭ装置、１０８…キーボード、１１０…ディスプレイ、１１２…ＨＤＤ、１１４…システムバス、１１６…ＣＤ−ＲＯＭ、１１８…最適化スケジューリングプログラム。
【技術分野】
【０００１】
本発明は多品目多段工程動的ロットサイズスケジューリング問題：Multi-Item Multi-Process Dynamic Lot Size Scheduling Problem（以後MIMPDLSSPと略記する）と称する最適化問題において、注文の納期遅れを許さない限り実行可能なスケジュールを生成できない場合に、その実行可能な合理的スケジュールを生成するための多品目多段工程動的ロットサイズスケジューリング方法に関する。
【背景技術】
【０００２】
MIMPDLSSPとは、複数の機械により複数の工程で当該各工程に対応した品目をそれぞれ処理し、かつ少なくとも１つの機械または工程では段取を伴う品目の切り換えが可能な多品目多段工程生産システムに適用される生産スケジュールを生成するのに好適なスケジューリング問題であって、次の要件を満たすものである。
【０００３】
（1）処理されるものを総称して品目と呼び、システム内の機械で処理されるすべての品目（部品、半製品、製品などを含む）を対象とする。品目の集合は最終品目（製品）の集合と仕掛かり品目の集合とに分割される。最終品目（製品）とは、システム内にそれを使って作られる品目をもたない品目を指す。出荷品目は最終品目のすべての他に、仕掛かり品目の一部（問題に所与）を含む。後者は補修部品などとして出荷される品目を指す。仕掛かり品目とは、それを使って作られる品目をもつ品目を指す。
【０００４】
（2）システムに対して注文（及び計画品目の生産依頼）があり、その各々には仕様の他に数量、納期（あるいは出荷時点）が指定されている。ここに、計画品目とは、上位の生産計画によって生産されることの決められている品目、いわゆる見込み品を指す。さらに、注文の中には繰り返し品も含まれている。繰り返し品とは、計画対象期間内に複数回にわたって注文のある品目を指す。出荷要求量はその都度異なってよい。
【０００５】
（3）システムは複数の工程から成り、各工程には一つあるいは性能の異なる複数の機械がある。
【０００６】
（4）計画対象期間の各時点に納期（出荷時点）を指定された各注文及び計画品目は部品展開によって、品目毎に所要量が展開される。
【０００７】
（5）どの品目も、ロットの残りの処理を待つことなく、処理されたものから次工程へ引き渡されて次の処理のために利用できる。
【０００８】
（6）各品目の初期在庫（仕掛かり）水準データは所与である。さらに、必要であれば、計画対象期間以降の処理に対する配慮として、計画対象期間末における品目別目標在庫水準を所与のデータに追加することも許される。
【０００９】
（7）機械干渉禁止制約（どの機械も、同時に複数の異なる品目を処理することはできない）がある。
【００１０】
（8）仕掛かり品目の品切れ禁止制約（どの仕掛かり品目も品切れは許されない）がある。
【００１１】
このとき、所与の注文及び出荷要求などのデータセットに対して、総段取り費と総仕掛かり保管費との総和を最小にするなどの評価基準のもとで、実行可能で合理的なスケジュールを生成することがMIMPDLSSPである。ここに、動的ロットサイズスケジューリング（DLSS）とは、各品目の処理のロットサイズが、問題のデータセットに応じて可変time-variant（動的）であることが許されるスケジューリングを指す。
【００１２】
受注量が工程能力を超えない場合のMIMPDLSSPについては、すでに解法（以後、基本解法と略記する）が提案されている（特許文献１、非特許文献１、２）
基本解法は問題を品目別に分解してラグランジュ分解調整法Lagrangean Decomposition Coordination Method（ＬＤＣ法と略記する）を適用して解く方法である。
【００１３】
実際の製造企業のスケジューリング環境に目を向けると、納期遅れの避けられないことが決して少なくない上に、その場合には解の合理性がそうでない場合にも増して問われる。
【００１４】
計画対象期間のある時点において、ある工程の累積負荷（段取りを含む累積処理時間）が累積工程能力（累積操業時間）を超えれば、どのようなスケジューリング法によってもいずれかの注文において納期遅れが起きることは避けられない。
【００１５】
このような事態が頻発する理由として、第一に多くの企業において、工程能力余裕（バッファ）が抑えられていること、第二に仕掛かりバッファを削減する傾向にあること、第三に短納期要求、すなわちタイムバッファが極端に少ないこと、第四に製品の多様化と受注変動の激化などが考えられる。
【００１６】
第一の工程能力余裕に関しては、先の需要が読めないこと、急激な技術革新による既存技術の陳腐化などによって設備投資をした場合の資金回収のリスクを恐れて、設備投資を控える傾向が見られることが余裕の抑えられている一因である。第四の受注変動については、看過される嫌いがあるが、実態としては本来負荷変動を吸収する働きを担うはずの上記三種類のバッファが削減される一方で、外部からはそれをはるかに超える負荷変動が加わり、受注変動の激化となる。
【００１７】
納期遅れの危険が生ずると営業担当者あるいは利害関係者の思惑が絡んで出荷要求量あるいは要求納期にバイアスが入る嫌いがあり、その結果、製造販売部門間の調整あるいは営業担当者間の調整が難航する傾向が見られる。そこで、納期遅れの避けられない場合には、その影響をできる限り食い止めるために納期遅れを許すスケジューリング法が必要となる。
【００１８】
納期遅れに関する文献はあるが、多品目多段工程の生産システムを対象としたスケジューリングにおいて納期遅れを許して解を求める研究は少ない。
【００１９】
Ｗ．Ｈ．Ｉｐ等（非特許文献３）は通常の多品目多段工程から成る生産システムを対象として注文処理の納期前処理と遅れの罰金総額を最小化する問題をＧＡ（遺伝的アルゴリズム）によって解いている。しかし、各期各品目の注文ロットサイズは所与で、決定の局面が品目別期別の生産量に限られており、処理のロットの順序付けや差立ての局面には触れられていないので、処理の実行可能性については保証されない。したがって、この問題はスケジューリングの問題というよりはむしろ生産計画の問題である。
【００２０】
Ｗ．Ｋ．Ｗｏｎｇ等（非特許文献４）は服飾メーカのフローショップに対する生産計画とスケジューリングにおける納期前処理と遅れの罰金総額を最小化する問題をやはりＧＡ（遺伝的アルゴリズム）によって解いている。問題を工場への注文の負荷の割付けと各工程への処理の割付けとの二段階に分けて取り扱っており、前者においては注文に対して、後者においては各工程の処理に対して、それぞれ順序付けをする問題であり、ロットサイズは所与である。
【００２１】
Ｒｕｅｙ−Ｍａｗ Ｃｈｅｎ等（非特許文献５）は多品目多機械問題においてやはりすべてのジョブの納期前処理と遅れの罰金総額を最小化する問題であるが、そのためにロットサイズとロット順序とを決定局面としている。解法としてはニューラルネットワークが使われている。しかし、このモデルには通常の生産システムの属性として欠かせない製品構成と多段工程あるいは先行関係が陽にモデル化されていないので、このモデルは実際のスケジューリングのモデルというよりはむしろ割当問題のモデルに近い。
【００２２】
これら三つの論文に共通していえることは、（1）一般型の製品構成が取り扱えないこと、（2）段取り時間が考慮されていないこと、（3）ロットサイズ決定、ロット順序決定、差立て（使用機械決定）という三つの決定局面を同時には取り扱うことができないことである。
【特許文献１】特開２００２−３２８９７７号公報
【非特許文献１】アディティア・ワルマン，村松健児：“段取り時間のある多品目多段工程動的ロットサイズスケジューリング：ラグランジュ分解調整法”，日本経営工学会論文誌，Vol.53, No.5, pp.385-396 (2002)
【非特許文献２】Muramatsu, K.et al.: “A Near-Optimal Solution Method of A Multi-Item Multi-Process Dynamic Lot Size Scheduling Problem”，JSME Int. J. Ser. C, Vol.46, No.1, pp.46-53, March (2003)
【非特許文献３】W.H.Ip.et al.: “Multi-product planning and scheduling using genetic algorithm approach”, Computers & Industrial Engineering, Volume 38, Issue 2, pp.283-296 (2000)
【非特許文献４】W.K.Wong.et al.: “A hybrid flowshop scheduling model for apparel manufacture”, International Journal of Clothing Science and Technology, Vol.13, No.2, pp. 115-131(2001)
【非特許文献５】Ruey-Maw Chen. et al.: “Combining competitive scheme with slack neurons to solve real-time job scheduling problem”, Expert Systems with Applications, Volume 33, Issue 1, pp.75-85(2007)
【発明の開示】
【発明が解決しようとする課題】
【００２３】
このように従来の多品目多段工程動的ロットサイズスケジューリング方法には、注文の納期遅れを許されない限り実行可能な合理的スケジュール（実行可能解）を生成できない場合があった。
【００２４】
本発明の目的は多品目多段工程動的ロットサイズスケジューリング方法において、受注量が工程能力を超えるため納期遅れを許すことを余儀なくされた場合に、納期遅れを許す実行可能スケジュールを生成する方法を提供することである。
【課題を解決するための手段】
【００２５】
計画対象期間末における累積負荷が累積工程能力を超える場合には、負荷を減らさないで必要な工程能力を確保するために、計算上の計画対象期間末を問題自体の計画対象期間末よりも長めに設定する。納期遅れの解を許すように解の空間を拡張する。納期遅れの発生しない場合の基本解法におけるモデルの目的関数に納期遅れペナルティの項を追加する。数値計算については、ラグランジュ分解調整法にヒューリスティクスを併用する方法を適用する。
【発明の効果】
【００２６】
本発明によれば、生産納期遅れを許して実行可能解を求めるための多品目多段工程動的ロットサイズスケジューリング方法を提案することができる。
【発明を実施するための最良の形態】
【００２７】
以下、図面を参照して本発明による多品目多段工程動的ロットサイズスケジューリング方法の実施の形態を説明する。
【００２８】
第１の実施の形態
生産スケジューリングにおいては、短期需要の変動などによって受注量が工程能力を超える場合が少なくない。そこで、本実施の形態では、納期遅れを許して実行可能解を求めるための多品目多段工程動的ロットサイズスケジューリング問題を取り扱う。この問題を納期遅れのない場合の解法に帰着させて解く方法（提案法）を提案する。これは次の操作から成る。
【００２９】
（1）計画対象期間末における累積負荷が累積工程能力を超える場合には、負荷を減らさないで必要な工程能力を確保するために、計算上の計画対象期間末を問題自体の計画対象期間末よりも長めに設定する。
【００３０】
（2）納期遅れの解を許すように解の空間を拡張する。
【００３１】
（3）基本解法におけるモデルの目的関数に納期遅れペナルティの項を追加する。数値計算については、基本解法におけると同様にラグランジュ分解調整法にヒューリスティクスを併用する方法を適用する。さらに、その解法によって実行可能解を求めることができるか否かの検証をする。
【００３２】
[１] 提案法の前提となる基本的な考え方
既に述べたように、提案法は納期遅れのない場合のMIMPDLSSPのモデルとその解法（基本解法）を基礎にしている。そこで、その理解を助けるために基本解法と提案法に共通する解法の基本的考え方と特徴について説明する。
【００３３】
[１．１] 解法の基本的考え方と特徴
先ず、納期遅れのない場合の解法を説明する。
【００３４】
対象とする一般型製品構成（複数の品目から作られて、後工程において複数の品目の処理に使われる品目を含む）の多品目多段工程生産在庫システムの挙動は各工程における各品目の処理とそれに伴う仕掛かりの状態推移によって記述することができる。そこで、これらの挙動をできる限り実態に近い形でモデル化し目的に照らして全体最適志向で制御するために、次のような考え方をする。
【００３５】
（1）品目の処理に伴う仕掛かりの推移をモデルの中で陽に取り扱って、スケジューリング問題を動的（時間的）最適化問題、すなわち最適制御問題であると見做す。その結果、一つの品目の仕掛かり推移を記述するために一つの数学的次元が使われるから、この問題は品目数と同じ数学的次元を持つ高次元の時間最適化問題になる。
【００３６】
（2）計画対象期間を小さなタイムスロットに刻んで時間及び問題を離散化する。したがって本解法は離散化に伴う丸め誤差を容認する。
【００３７】
（3）機械ｋと品目ｉとがタイムスロットｔにおいて処理中であるか否かの関係を、モデルにおける情報の最小単位として把握して、これを原始オブジェクトと称して、その状態を、０−１決定変数δitkを用いて表示する。
【００３８】
（4）各品目の処理とそれに伴う仕掛かりの推移を、決定変数δitk及び段取りの残り時間ｓを用いて、仕掛かり推移方程式（後述の（２）式）に記述する。同様に、段取りの残り時間の推移に対しても、推移方程式（後述の（３）式）に記述する。したがって、解法においては、各品目の仕掛かりを媒介として解（スケジュール）を制御する方法を採る。
【００３９】
（5）機械干渉禁止制約（後述の（４）式）を置く。この制約が各機械とその機械を使って処理される品目の集合とをひとつの部分システムに統合する働きをすることに注目する。
【００４０】
（6）仕掛かり品目の品切れ禁止制約（後述の（５）式）を置く。この制約が各品目とそれに続く品目（作られる品目とそれを使って新たに生み出される品目）との間を繋いでひとつの多品目多段工程の生産システムを構成する働きをすることに注目する。
【００４１】
（7）全品目の計画対象期間にわたる在庫（仕掛かり）保管費と段取り費との総和の最小化などを目的関数（後述の（１）式）にとる。
【００４２】
（8）問題を品目別に分解する。この時間最適化問題の数学的次元は品目数と同じで、高次元になるから、問題を分解して次元を落とさない限り、合理的な計算時間とメモリの範囲内で解を求めることができない。ところが、どの品目の仕掛かりも処理されればその分だけ増え、次の工程において使われれば（別の品目に組み込まれれば）その分だけ減るから、一つの品目の仕掛かり推移が、その品目の処理のみでなく、それを使って処理される品目の処理にも依存することになる。言い換えると、一つの仕掛かり品目の処理が、その品目の仕掛かりを増やすと同時に、それに使われる品目の仕掛かりを減らすことになる。したがって、このままでは問題を分解することが難しい。
【００４３】
そこで、問題を品目別に分解するための工夫として、人為的に、各品目の仕掛かり推移を他の品目の処理とは独立にするために、仕掛かり（在庫）を定式化するに当って、梯状在庫（echelon inventory）（後述の（２）式）の概念を用いる。この概念は単一品目多段階在庫点を持つ在庫システムにおける最適購買政策を導くためのものである。
【００４４】
梯状在庫とは、対象在庫点にある在庫だけでなく、その在庫点から消費者に最も近い在庫点までの間に滞留している在庫を指す。
【００４５】
基本解法においては、梯状在庫の概念を次のように拡張して定義して、一般型製品構成の多品目多段工程生産在庫（仕掛かり）システムに適用する。このシステムにおける各品目の梯状在庫とは、その品目の仕掛かりの他にも、既に半製品、製品などに組み込まれるか使われて、見かけの形を変えて系内に滞留しているものを含むものとする。この定義によれば、各品目の梯状在庫の推移はその品目が処理されればその分だけ増え、その品目を組み込まれたかそれによって作り出された品目が出荷されたときに初めて、その分だけ減ることになって、他の品目の処理には影響を受けないことになる。そこで、この性質に注目して、問題を品目別に分解して、加算分離可能性を導く。ここに、加算分離可能性とは、問題を部分問題に分解したときに、同じ決定変数が複数の部分問題に表れないように分解することができることを指す。
【００４６】
この取り扱いに応じて、品目の在庫保管費についても、その品目に対する付加価値のみを基礎にして算定する方法に変更するものとする。このようにしても、算定されるシステム内の総在庫保管費は通常の算定法によるものと異ならない。
【００４７】
（9）この問題を品目別に分解した後、ラグランジュ分解調整法を基礎にして解く。すなわち、この最適化問題の機械干渉禁止制約（（４）式）と、仕掛かり品目の品切れ禁止制約（（５）式）とをラグランジュ緩和した後に品目別に分解して、それぞれ部分最適化をすることと、各制約の摂動に応じたラグランジュ乗数の調整とを繰り返して、最適化と制約違反解消とを共に追求する。
【００４８】
[１．２] 基本解法の特徴
基本解法の諸特徴の中で、後述する提案法と関連する特徴を掲げる。
【００４９】
（1）モデル化に当たって、１．１節の（3）の原始オブジェクトを制御（あるいは情報）の最小単位として、実システムの挙動をありのままに記述する方法（後述の（２）式、（３）式）が採られ、離散化における丸めの誤差が入ることの他には、処理の自由度が人為的に制約される心配がなく、その結果、実行可能解の領域が大きく広がること。
【００５０】
（2）各品目の仕掛かり推移方程式（後述の（２）式）を陽に取り扱うこと。
【００５１】
（3）問題に含まれる、ロットサイズの決定、順序の決定、負荷の平準化、差立て（使用機械の決定）などの多様な異質の決定局面を意識しないで決定する（解から読み取る）ことができること。
【００５２】
（4）各品目の処理のロットサイズは可変になる、すなわち、同じ品目であっても、状況に応じて計画対象期間の時点によってサイズが異なること。
【００５３】
（5）各品目の処理とその品目を使って生み出される品目の処理との時間的な関係（位相）は重複あるいはその逆に間を置くことも含めて、品切れが生じない限り（仕掛かり品目の品切れ禁止制約）どのようであっても許されること。
【００５４】
（6）上記（3）に述べた多様な異質の決定局面をすべて同時に全体最適志向で決定することができること。
【００５５】
（7）分解調整法であるから、問題の規模が増えても計算に要する時間とメモリについては組合せ爆発を避けることができること。
【００５６】
要するに、これらの基本解法の特徴は採りうるアクションの自由度を実際の問題におけると同じにして、全体最適志向で状況に応じて解を求めることができるための条件を満たしていることを示している。
【００５７】
上述の基本概念、モデル、解法を総称して、Object Oriented Optimization Technologyオブジェクト指向最適化技術（Ｏ２Ｏ−テクノロジ）と呼ぶ。
【００５８】
結局、基本解法においては、各品目に対して部分最適化問題が解かれることと、制約条件の充足のためのラグランジュ乗数の更新とが、予め決められた停止条件が満たされるまで反復される。ここに、部分最適化問題においては、その都度制約条件の充足のためのペナルティコスト（ラグランジュ乗数）の変化を配慮して、その品目の可変ロットサイズでの処理の計画が下される。
【００５９】
[２] 納期遅れを許す問題の数理モデル
[２．１] 本問題のモデル化の考え方
本問題を基本解法に帰着させて解くためのモデル化の考え方を述べる。
【００６０】
（1）計算上の計画対象期間の延長
ある工程の計画対象期間末における累積操業率が1を超えると予想される場合には、消化しきれない負荷が生じる危険が高い。ここに、累積操業率とは、その時点までの稼動時間と段取り時間の累積を累積工程能力で除した値である。そこで、その場合には、問題自体の計画対象期間についてはそのままにして、計算上の計画対象期間を、累積操業時間に余裕ができる程度にまで、延長する。そうでない場合（計画対象期間の途中では予想累積操業率の推移が１を超えるが、期間末においては１を超えない場合）には、それを変更しない。
【００６１】
（2）実在庫の梯状在庫による記述
納期遅れのある実行可能解の梯状在庫を用いたモデル化における必要十分条件を明らかにして、それをモデル化する。基本解法においては、問題の加算分離可能性を保つために梯状在庫による問題の定式化がなされているから、この解についてもそれに沿ってモデル化がなされない限り基本解法が適用できない。
【００６２】
そこで、まず、この解の実在庫を用いたモデルにおける必要条件に注目すれば、これは、最終品目（製品）に対しては負の在庫をもつが、仕掛かり品目に対しては仕掛かり不足の生じていない解である。なぜならば、製品が納期遅れを起こせば、それは、広く知られているように、未処理の受注残（backlog）として取り扱うことができるから、負の在庫と見做すことができる。一方、出荷品目を除く仕掛かり品目に対しては、それが品切れを起こせば、それを使って処理される品目が作れないから解は実行可能にならない。したがって、出荷品目を除く仕掛品目については品切れが許されない。さらに、出荷品目でもある仕掛品目については、出荷される数量に限って納期遅れを認めて受注残として取り扱うことが理論的には可能である。しかし、出荷される部分に対しては補修品のように出荷の優先順位が高いことが多いので、出荷品目でない仕掛り品目の場合と同様に品切れは許されないものとして取り扱う。
【００６３】
次に、この条件を梯状在庫の概念を用いて再定式化する。最終品目（製品）に対しては、梯状在庫と実在庫とは同じであるから、在庫が負になることを認めることで片付く。しかし、仕掛かり品目（最終品目でない品目）に対しては、次のように考えることができる。最終品目のみでなく、それに使われている仕掛かり品目についても、最終品目の出荷時点までに処理が片付かなければ、仕掛かり品目の梯状在庫が不足して負になることは避けられない。そこで、仕掛かり品目の梯状在庫が負になることを認める。しかし、その品目の実在庫が負になることは、先に述べた理由によって、許されない。そこで、実在庫を梯状在庫によって定式化した後に、仕掛かりの実在庫の品切れ禁止制約（後述の（５）式）を置く。これらの取り扱いによって、納期遅れのある実行可能解の梯状在庫によるモデル化は解決する。
【００６４】
（3）目的関数において納期遅れコストを付加する
これでモデルの拡張はできる。このモデルに対して、非実行可能解から始めてラグランジュ分解調整法の反復を逐次実行して解を実行可能解へ導いていくプロセス（後述の（１）式）は、納期遅れのないMIMPDLSSPに対する基本解法と何ら異ならない。
【００６５】
[２．２] 数理モデル
本問題の数理モデルは基本的には、納期遅れの無い場合の問題を定式化した既存モデルと異ならない。本問題のモデルをまとめると、以下のように記述できる。
【数１】
【００６６】
梯状在庫量の推移方程式
【数２】
【００６７】
段取時間の推移方程式
【数３】
【００６８】
機械干渉禁止制約
【数４】
【００６９】
仕掛かり品目の実在庫の品切れ禁止制約
【数５】
【００７０】
梯状在庫量の範囲
【数６】
【００７１】
各種所要量の関係
【数７】
【００７２】
すなわち、納期遅れのある多品目多段工程動的ロットサイズスケジューリング法は（２）式〜（６）式の制約条件の下で，（１）式の目的関数を最小化する問題である。
【００７３】
記号の説明の前に、このモデルにおいて新しく追加された部分を説明する。先ず、（１）式の括弧（ ）内の第一項ｂikは基本モデルにおいては見られなかった項で不要な機械の使用を避けるための機械使用料に相当する。第二に、基本モデルにおける仕掛かり保管費の項が梯状在庫の符号に応じて、（ ）内の第三項と第四項のように別れたことである。第三に、（６）式の梯状在庫量の下限ｘiminを負の値にまで拡張したことである。
【００７４】
続いて、記号の説明をする。
【００７５】
（１）添字
ｉ：品目または処理番号を表し，その集合をＩ＝｛1,2,…,nI-1,nI｝とする。ただし，ｉ＝０は市場（システムの外）を表す。
【００７６】
ｋ：機械を表し，その集合をＫ＝｛1,2,…,nK-1,nK｝とする。
【００７７】
ｔ：タイムスロット（以降tsと略記することもある）を表し，その集合をＴ＝｛1,2,…,nT-1,nT｝とする。
【００７８】
（２）集合
Ａ：仕掛かり品目の集合
Ｋ(i)：品目ｉを処理することのできる機械の集合
Ｍ(k)：機械ｋが処理できる品目の集合
Ｐ(i)：品目ｉの先行直結品目（品目iに使われる品目）の集合
Ｓ(i)：品目ｉの後続直結品目（品目iが使われる品目）の集合（空集合を含む）
（３）入力データ
ｂik：機械ｋにおける品目ｉの１タイムスロット当たりの機械使用料（所与）
ｃik：機械ｋにおける品目ｉの1回当たりの段取費用（所与）
ｄi：品目ｉの１単位当たり１タイムスロット当たりの納期遅れペナルティ（所与）
ｈi：品目ｉの処理によって新たに付加される価値に対する１単位当たり１タイムスロット当たりの仕掛かり保管費、すなわち梯状在庫（仕掛かり）保管費（所与）
ｐik：機械ｋにおける１タイムスロット当たりの品目ｉの処理量（所与）
ｒi0t：品目ｉのタイムスロットｔにおける外部需要あるいは出荷要求量（所与）
ｒijt：タイムスロットｔにおいて品目ｊを生産するために使用される品目ｉの所要量
ｒi・t：品目ｉのタイムスロットｔにおける部品展開後の所要量
ｓimaxk：機械ｋにおける品目ｉに対する段取り時間（所与）
ｘi0：品目ｉのタイムスロットｔ＝０における梯状在庫量，すなわち初期梯状在庫量
ｘimax：品目ｉの梯状在庫量の上限値（所与）
ｘimin：品目ｉの梯状在庫量の下限値（所与）
ｙi0：品目ｉのタイムスロットｔ＝０における実在庫量，すなわち初期実在庫量（所与）
δi0k：機械ｋにおける品目ｉのｔ＝０における処理の状態，すなわち初期値（所与）
ρij：品目ｊ１単位当たりの品目ｉの所要量（所与）
（４）ラグランジュ乗数
μ・tk：機械ｋのタイムスロットｔにおける機械干渉禁止制約（４）式に対応するラグランジュ乗数
μit：仕掛かり品目ｉのタイムスロットｔにおける品切れ禁止制約（５）式に対応するラグランジュ乗数
（５）決定変数
δitk：タイムスロットｔにおいて、機械ｋにより、品目ｉを処理するときに１をとり、その他の場合には０をとる０−１決定変数。
【数８】
【００７９】
（６）状態変数
【数９】
【００８０】
しかし、品目ｉが最終品目（製品）の場合には梯状在庫は実在庫と一致する。
【００８１】
（７）その他
ν：計算の反復を表す番号
[２．３] ラグランジュ関数とその分解
ラグランジュ関数を次式に示す。
【数１０】
【００８２】
ラグランジュ関数の分解
【数１１】
【００８３】
部分最適化問題
したがって、ラグランジュ関数の最小化問題（（１）式）は次のような部分最適化問題に分解することができる。
【数１２】
【００８４】
[３] 提案法及びその例解
[３．１] 提案法の構成
本提案法はラグランジュ分解調整（LDC：Lagrange Decomposition Coordination）法による基本解法の計算を途中で打ち切って、その中間結果（非実行可能解）を受け取り、この解から実行可能解を導出するためのヒューリスティクス解法へ切り替えるものである。
【００８５】
定義：基本解法の計算打ち切りルール
この基本解法の計算打ち切りの評価式として、
機械干渉違反総タイムスロット数／（計算上の計画対象期間タイムスロット数×機械台数）と、
仕掛かり品目の総品切れタイムスロット数／（計算上の計画対象期間タイムスロット数×仕掛かり品目数）と、
を用い、これらの比が初めて共に予め定めたある値α(％)を下回ったときの反復νにおいて計算打ち切りを実施するものとする。
【００８６】
定義：提案法Ｈ(α)法
基本解法を打ち切り、上記のルールを適用する解法を、以後、Ｈ(α)法と称することにする。
【００８７】
したがって、提案法は（1）負荷の把握と計画対象期間の調整、（2）基本解法による最適化と制約充足の数値計算、（3）Ｈ(α)法による実行可能解の導出から成る。その構成と手順との関係を図１に示す。図１のステップＳ１の「負荷の把握と計画対象期間の調整」の手順を図２に示す。図１のステップＳ２の「基本手法による最適化と制約充足の数値計算」の手順を図３に示す。図１のステップＳ３の「Ｈ(α)法による実行可能解の導出」の手順を図４に示す。
【００８８】
[３．２] 解法の手順と例解
以下に解法の手順（流れ）を示す。Ｈ(α)法の手順、したがって、基本解法の解（非実行可能解）を初期解とするヒューリスティクスについては、様々な解法が考えられる。
【００８９】
説明の便宜を考慮して、例解を括弧（ ）内に併記する。例解の工程フローを図５に、さらに、計算の結果については、図６から図１１に示す。
【００９０】
ステップＳ１１：問題の入力データ一式を登録して、前処理によりスケジュール生成の計算に必要なデータ一式を用意する。
【００９１】
（1）品目j1単位当たりの品目iの所要量ρij（表１）
（2）生産技術データ（1タイムスロット当たりの処理量ｐik、段取時間ｓimaxk、段取費用ｃik、機械使用料ｂik）（表２の各欄の４つの数値が左から順に処理量、段取時間、段取費用、機械使用料を示す）
（3）初期実在庫量ｙi0、仕掛かり保管費ｈi、納期遅れペナルティｄi、外部需要ｒi0t（表３）
（4）初期梯状在庫量ｘi0、梯状在庫量の下限値ｘimin、上限値ｘimax、部品展開後の所要量ｒi t（表４）
【表１】
【００９２】
【表２】
【００９３】
【表３】
【００９４】
【表４】
【００９５】
表１の品目j1単位当たりの品目iの所要量ρijと表２の生産技術データについては、データを読み込む。表４の部品展開後の所要量ｒi・tは表３の外部需要ｒi0tに対して、（７）式、（８）式を用いて算出する。
【００９６】
ステップＳ１２：システムパラメータ一式を設定する。
【００９７】
（1）タイムスロット（ts）：（１ts＝30分）
（2）計画対象期間：スケジューリング立案期間（２４０tsとする。ここに、２４０tsは１tsを30分、１日の実働時間を２４時間、５日間を計画対象期間として算出した値である。）
（3）基本解法におけるＬＤＣ法の計算打ち切りの基準値α：（例えば３％とする。制約違反件数の減少状況に応じて、再設定する場合もある。）
ステップＳ１３：最適化問題の基本解法における反復計算を一回だけ行う。
【００９８】
これは、入力データから、機械干渉、仕掛かり不足などの実行可能性を無視して、品目別の部分最適化のみを考慮した解に基づいて、機械別、タイムスロット別負荷の状況を把握するための基礎データを得ることが目的である。（ｘimin＝０、ｎＴ＝２４０とし、さらに、すべてのラグランジュ乗数を０とおいて、すべてのｉについて（１３）式を１回だけ（反復回数ν＝１）解いてすべてのｉ、ｔ、ｋの解を得る。）
ステップＳ１４：累積操業率グラフを作成して表示する。オペレータはこのグラフを見て、必要ならば計算上の計画対象期間を延長し、計画対象期間の再設定をする（２．１節（1）を参照）。ここまでの手順で前処理が終わる。（例えば、図６に示すように、２４０tsの(1)計画対象期間を、２４ts（半日）延長して、２６４ts（(2)計算上の計画対象期間）とする。）
ステップＳ２１：延長された期間に対して各制約に対する違反件数比が共にαを下回るまで基本解法（ＬＤＣ法：(１３)式を計算する）を反復実施する。図７の(a)から(f)に示すように、各制約に対する違反件数比が共にαを下回った計算の反復回数νにおいて、ＬＤＣ法の計算を打ち切り、Ｈ（α）法へ切換える。
【００９９】
ステップＳ３：ヒューリスティクスによって実行可能解を生成する。ここでは、最初に機械干渉を解消して、続いて機械干渉を避けながら、仕掛かり不足を解消させる。
【０１００】
ステップＳ３１：ステップＳ２１の結果から、すべての品目ｉ、すべての機械ｋ、すべてのタイムスロットｔに対して、解（決定変数）δitkの値（実行可能解の場合は１か０）を読み取る。
【数１３】
【０１０１】
（2）解δitkを用いて、機械別にすべての遊休時間の開始時点と終了時点を把握する。これも（１）式と同様に数式による記述ができる。
【数１４】
【０１０２】
ステップＳ３２：機械干渉箇所を特定する。
【０１０３】
（1）機械干渉禁止制約（（４）式）は左辺の値が１以下であることを示し、左辺の値が２以上となるロット（δitk集合）が制約違反箇所である。これにより、システムが解δitkに基づいて（４）式より機械別、品目別に機械干渉を起こしているロット、および干渉を起こしている期間を特定することができる。
【０１０４】
ステップＳ３３：機械干渉を解消する。
【０１０５】
（1）機械干渉を起こしているロットを、状況に応じて、バックワード法、フォワード法等により移動して、機械干渉を解消する。ステップＳ３２で機械干渉を起こしているロットとその期間が特定されているので、ステップＳ３３ではシステムが機械干渉を起こしているロットを選び出し、そのロットをバックワード法（時間軸上で見た場合、後ろへシフトさせる）、あるいはフォワード法（時間軸上で見た場合、前へシフトさせる）によって移動させることによって機械干渉を解消することができる。
【０１０６】
（2）機械干渉解消後はそのロット順序を基本的に保ちながら、以後の各手順を行う。
【０１０７】
ステップＳ３４：仕掛かり品目の品切れ箇所を特定する。
【０１０８】
（1）仕掛かり品目の実在庫の品切れ禁止制約（（５）式）は左辺の値が負であることを示し、左辺の値が正になるロットが制約違反箇所である。これにより、システムが品目ｉのタイムスロットｔにおける梯状在庫量ｘitに基づいて、（５）式より品目別に品切れを起こしているロット、および品切れを起こしている期間を特定することができる。
【０１０９】
ステップＳ３５：仕掛かり品目の品切れ箇所を解消させる。
【０１１０】
（1）仕掛かり不足を起こしている品目のロットを早める、あるいは遅らせる。
【０１１１】
（2）あるいは、そのロットと一つ前のロットの順序を入れ替える。
【０１１２】
（3）さらに、後続直結品目のロット処理を遅らせるなどにより状況に応じて処置を取る。ステップＳ３４で仕掛かり品目の品切れ箇所とその期間が特定されているので、ステップＳ３５ではシステムが品切れを起こしているロットを選び出し、梯状在庫量ｘitに基づいてｘitのマイナスの箇所が無くなるように、(1)から(3)を実施することにより仕掛かり品目の品切れ箇所を解消することができる。ｘitのマイナスの箇所とは、その品目ｉ、タイムスロットtにおいて品切れを起こしている箇所である。ｘitは０以上でなければ実行可能解ではなく、ｘitにマイナスの箇所があると実行可能解ではない。
【０１１３】
ステップＳ３６：納期遅れスケジュール結果の保存と出力をする。
【０１１４】
すべての制約違反が解消されたら、計画対象期間にわたる品目別在庫推移グラフ及び機械別品目別ガントチャートデータを作成し、メモリに保存する（図８、図９）。
【０１１５】
ステップＳ３７：納期遅れ箇所を確認する。
【０１１６】
品目別在庫推移グラフ及び機械別品目別ガントチャートデータを表示し、オペレータが納期遅れ品目とその期間を確認する。納期遅れが許容されない期間となっている場合は、ステップＳ１１の入力データの一部、具体的には、表２の段取費用、表３の仕掛かり在庫保管費、外部需要を変更して解きなおす。あるいは、ステップＳ１２のシステムパラメータの一部、具体的には，計画対象期間、制約違反件数比αを変更して解きなおす。なお、ステップＳ１１、Ｓ１２の変更はかならずしも両方ともこの順番に変更する必要は無く、得られた解の状況に応じて何れか一方のみでも良いし、先ずステップＳ１１（またはＳ１２）のデータ（またはシステムパラメータ）を変更して解きなおし、オペレータの納得いく解が得られなかった場合は、さらにステップＳ１２（またはＳ１１）のシステムパラメータ（またはデータ）を変更して解きなおせばよい。
【０１１７】
[４] 例解の結果と考察
[４．１] 例解の結果
順を追って例解に対する計算の過程とその結果を説明する。
【０１１８】
（1）入力データ
図５は例解に用いられた数値例に対する生産システムの工程フローである。８台の機械（機械１〜機械８）によって２０品目（図５の丸数字）を処理しているが、工程間のフロー及び品目構成はそれなりに複雑である。例えば、品目１４、６、２のように逆流（通常は左から出荷側の右へ流れるが、出荷側から左へ逆流する）がある、あるいは品目１７、１８のように同一の機械７が繰り返し使われる、さらに、２つの品目９、１０から１つの品目１６が作られる、あるいは、品目５は２つの品目８、１０へ使われる、さらにまた、品目３、４、５等々に代替ラインが存在するなどの様に製品構成、工程編成等々に関しても、現実にも起きうる構造をほぼすべて反映している。例えば、品目３は機械１と機械２で処理され、品目４は機械２と機械３で処理され、品目５は機械２と機械３で処理されているが、一つの品目を複数の機械で処理が可能な場合、それらを代替ラインと呼ぶ。
【０１１９】
表１から表４はステップＳ１１で使われる。表３のタイムスロット２４０の外部需要には、計画対象期間末における持ち越し在庫量が含まれている。これは次期計画対象期間の初期実在庫量に相当する。表２の段取り費用ｃikと表３の仕掛かり保管費ｈiについては、標準原価あるいは政策的費用の意味合いがある。したがって、段取り回数を減らすために段取り費用を増やす、あるいは仕掛かりを減らす意図で保管費を増やすなどのように、数値計算の過程でこれらの値を試行錯誤により修正することができる。
【０１２０】
（2）各機械の累積操業率グラフと計画対象期間の修正
図６はステップＳ１３により基本解法を一回だけ回して差立てられたときの負荷状況に対する累積操業率グラフ（ステップＳ１４で作成）である。機械７の期間末の累積操業率が１００％を超えているので、計算上の計画対象期間を２６４tsまで延長した。必要に応じて、ステップＳ１３、Ｓ１４を繰り返し、計画対象期間の再設定を行うことができる。
【０１２１】
（3）ＬＤＣ法の計算過程
図７はステップＳ２１でＬＤＣ法により（１３）式を解が収束するまで反復させたときの制約（機械干渉禁止制約（４）式と、仕掛り品目在庫の品切れ禁止制約（５）式）違反数の推移である。図の黒い線が機械干渉禁止制約（（４）式）の推移を示し、灰色の線が仕掛り品目在庫の品切れ禁止制約（（５）式）の推移を示す。(a)から(e)は計算の打ち切り時点を、(f)はＬＤＣ法のみで実行可能解を算出した時点を示す。図１０（ａ）、（ｂ）はそれぞれ、ＬＤＣ法のみで実行可能解を算出したとき、すなわちＨ(０)法、ν＝８８８２（図７の(f)）の機械別、品目別のタイムスロット別のラグランジュ乗数（禁止制約(４)式、(５)式に対応するラグランジュ乗数μ・tkとμit）値である。
【０１２２】
ラグランジュ乗数は制約に対する双対コスト、すなわち、影の価格（shadow price）を表すことが知られている。したがって、これらのグラフから、何時、どの機械とどの品目に対して資源が不足し、調整が難航しているかの様子が概観できる。すなわち、図１０（ａ）から、計画対象期間全般にわたって機械７に高い負荷が掛っており、その機械の干渉を解消させることが困難であったことがわかる。一方、図１０（ｂ）からは、各品目に対するラグランジュ乗数の推移に周期性があることが読み取れる。
【０１２３】
これには二つ理由がある。第一は、入力データにおける毎日の出荷要求時点（表３の外部需要がある時点）が日によって変わらないで、それが丁度ラグランジュ乗数のグラフの山に対応していることによる。第二は、本発明においては前処理の段階でオフセット（手番）を考慮しないで所要量を出荷要求時点に対して展開し、それらを提案法のＨ(α)法自体が自動調整して品目間の処理の位相を決定する仕組みを内包しているために、どの品目についても出荷要求時点にラグランジュ乗数値のグラフの山が来ることによる。
【０１２４】
（4）ＬＤＣ法の反復に伴う累積操業率グラフの変化から見た提案法の納期遅れスケジューリング効果
図１１（ａ）は計算打ち切り基準α＝３(％)、つまりＨ(３)法、ν＝２９５９で計算を打ち切ったときの累積操業率グラフ（非実行可能解）であり、図１１（ｂ）はＨ(３)法、ν=２９５９からヒューリスティクスを用いて実行可能解を算出したときの累積操業率グラフである。図１１（ａ）では機械５は１５ts付近で、機械７は７tsから３２ts間、１７９tsから２６４ts間で累積操業率が１００％を越えている。ヒューリスティクスを用いて実行可能解を算出したときの図１１（ｂ）では、すべての機械について累積操業率は１００％以下に抑えられている。また、図１１（ｃ）はＨ(０)法、ν＝８８２２で実行可能解が算出されたときの累積操業率グラフであって、こちらも同様に１００％以下となっている。これは、本発明が、納期遅れスケジューリングに効いていることを示唆している。すなわち、その原理が有効に働いて、納期遅れを認めて工程能力を超える負荷の処理が先送りされている。また、一部に他の機械への処理の移動によって負荷調整が行われている。
【０１２５】
（5）納期遅れスケジュール結果の例
図８（ａ）はＨ(３)法、ν＝２９５９からヒューリスティクスを用いて実行可能解を算出したときの品目別在庫推移グラフ、図８（ｂ）はそのときの機械別品目別ガントチャートを示す。図９（ａ）はＨ(０)法、ν＝８８２２で実行可能解を算出したときの品目別在庫推移グラフ、図９（ｂ）はそのときの機械別品目別ガントチャートを示す。
【０１２６】
図８（ａ）、図９（ａ）は計画対象期間における品目別の在庫推移を図示したものである。図８（ａ）の在庫推移グラフから、４つの最終品目で合計１４箇所（納期遅れ総タイムスロット数は１８９）の納期遅れが発生していることがわかる。すなわち、品目１６については４箇所（ts＝４８〜５６、ts＝１４４〜１６６、ts＝１９２〜１９５、ts＝２４０〜２４８）、品目１８については２箇所（ts＝１９２〜２２５、ts＝２４０〜２６１）であり、品目１９、２０についても納期遅れが見られる。
【０１２７】
図８（ｂ）、図９（ｂ）のガントチャートから、機械ｋ、品目ｉ、タイムスロットｔの状態は、すべて読み取ることができる。例えば、図８（ｂ）の品目１９に注目すれば、機械７と機械８で処理され、ロットサイズは可変である。また、両機械にはほとんど遊休がないことが分かる。
【０１２８】
その他のＨ(α)法の結果については、いずれも同じような傾向を示すので、説明の便宜上最終結果のみの統計データを表５に掲げる。
【表５】
【０１２９】
（6）ＬＤＣ法及びＨ(α)法の比較
表５は（１）式の目的関数値とその内訳に関する比較である。ＬＤＣ法による結果と異なるαに対するＨ(α)法の結果との間に大きな差異は見られない。
【０１３０】
最後に、納期遅れの解の合理性を評価するために、次式（１４）によって納期遅れ対応後の機械別操業率と称する指標を定義する。
【数１５】
【０１３１】
図１１の例においては、機械７と機械８がボトルネック工程である。そこで、表６には機械７と機械８についてのみ、結果を掲げている。これらの結果から、次の特徴が見られる。第一に、ＬＤＣ法の打ち切り基準値αの変化に対しては大差がない。第二に、機械の遊休がほぼ極限まで下げられており、したがって、納期遅れは避けられないものの、納期遅れの少ない合理的な解が得られていると判断できる。第三に、納期遅れ総タイムスロット数については多少変動が見られるが、これは解法に伴う誤差変動によるものと考えられる。
【表６】
【０１３２】
図１２は本発明の一実施形態に係る多品目多工程ロットサイズスケジューリング装置の構成を示す。このスケジューリング装置は多工程から成る生産システムにおいて多様な注文を複数の品目に分類して切り換え生産をするためのスケジューリング（多品目多工程ロットサイズスケジューリング）の有する問題、つまり高次元時間最適化問題を解いて最適スケジュール（最適生産スケジュール）を決定するものである。この装置は全体を制御するＣＰＵ１０２、当該ＣＰＵ１０２が実行する最適化スケジューリングプログラム１１８を含む各種プログラム及びデータ等が記憶される主メモリ１０４とを備えている。本装置はまた、外部記憶装置としての例えば磁気ディスク装置（以下、ＨＤＤと称する）１１２と、記録媒体としての例えばＣＤ−ＲＯＭ１１６に予め格納されている情報を計算機内に読み込むことが可能なＣＤ−ＲＯＭ装置１０６とを有している。この例では、ＣＤ−ＲＯＭ１１６には、上述した複数の工程（多工程）、多機械（多設備）で複数の品目を生産する生産システムにおける多品目多工程ロットサイズスケジューリングを行うための最適化スケジューリングプログラム１１８が予め格納されている。この最適化スケジューリングプログラム１１８はＣＤ−ＲＯＭ装置１０６によりＣＤ−ＲＯＭ１１６から計算機内に読み込まれて、ＨＤＤ１１２に格納（インストール）されていものとする。ＣＰＵ１０２がＨＤＤ１１２から最適化スケジューリングプログラム１１８を主メモリ１０４上に読み込んで当該プログラム１１８を実行することにより、図１に示したフローチャートに従ったスケジューリング方法が実現される。
【０１３３】
本装置は更に、入力装置としてのキーボード１０８と、表示用の出力装置としてのディスプレイ１１０とを有している。ＣＰＵ１０２、主メモリ１０４、ＨＤＤ１１２、ＣＤ−ＲＯＭ装置１０６、キーボード１０８及びディスプレイ１１０はシステムバス１１４により相互接続されている。
【０１３４】
[４．２] 考察と検証
上述した例解の結果を考察して本発明の有効性を検証する。
【０１３５】
（1）なぜＨ(α)法によって納期遅れのある実行可能解を導くことができるか
ＬＤＣ法はラグランジュ緩和法の一つである。ラグランジュ緩和法が制約を満たすための効果的な方法であることは広く知られている。しかし、乗数の更新は他の乗数の更新とは独立になされる。制約付きの最適化問題が連続で凸である場合には、そのような取り扱いによっても最適解へ収束することが保証されている。
【０１３６】
ところが、スケジューリング問題においては、この種の数学的に収束を保証するための性質は成り立たない。したがって、他の乗数と独立に乗数の更新を行うラグランジュ緩和法によって解の収束を期待することには無理がある。
本問題においては、各機械ｋ、タイムスロットｔに対して機械干渉禁止制約（４）式に対応するラグランジュ乗数μ・tkが、あるいは各品目i、タイムスロットtに対して品切れ禁止制約（５）式に対応するラグランジュ乗数μitが、それぞれ、その他のラグランジュ乗数とは独立に更新される。このことは、それぞれある機械ｋとタイムスロットｔに対する機械干渉違反を解消する際に、近隣の機械干渉の状況を利用しないで処置をとる、あるいはある品目iとタイムスロットｔに対する仕掛かり品の品切れを解消する際に、近隣の仕掛かり品の品切れの情報を利用しないことを指す。
【０１３７】
そこで、この欠陥を解消するための容易な方法として、近傍の情報を利用して納期遅れのある実行可能解を生成するために状況に応じてバックワード法、フォワード法を併用するヒューリスティクス（Ｈ(α)法）を提案した。しかし、ヒューリスティクスの適用は既に反復打ち切り時における各制約の違反件数百分比αが十分に下がった段階での解の微調整であるから、目的関数値に与える影響は少なくて済み、納期遅れのある実行可能解を求めることができる。
【０１３８】
（2）なぜ合理的な（無駄な納期遅れの無い）解が得られるか
４．１節（6）で述べたとおり、納期遅れを来している工程の機械に対しては、納期遅れ対応後の機械別操業率がＬＤＣ法のみでなく反復打ち切り時における各制約の違反件数百分比αが５％以下の幅広い範囲に対しても、Ｈ(α)法が高い評価値を示した。
【０１３９】
それには次の三つの理由が考えられる。第一に、目的関数において遅れの発生に対して遅れコストが設定されていることである。したがって、できる限り遅れを発生させない力が働く。第二に、どの品目に対しても部品展開の段階でオフセット（手番）を０として取り扱っており、提案法には工程リードタイムの概念が無いので、仕掛かり品目が品切れを来さない限りその品目を作るための処理とそれを使ってなされる処理の位相を、同期化も含めて、近づけることができる。すなわち、計画対象期間内の処理を密にすることができる。第三に、ロットサイズ固定、リードタイム固定などの人為的な制約が置かれていないので、状況に応じてロットサイズを可変にすることができる。すなわち、解法自体に大きな処理の間の隙間を埋める力が働くと考えられる。
【０１４０】
以上説明したように本発明では納期遅れを許して実行可能解を求めるための多品目多段工程動的ロットサイズスケジューリング問題を納期遅れのない場合の解法に帰着させて解いた。これは大別して次の三つの付加的段階から構成される。先ず、計画対象期間末における累積負荷が累積工程能力を超える場合には、必要な工程能力を確保するために、計算上の計画対象期間を延長する。さらに、納期遅れの解を許すように、解の空間を拡張する。最後に、基本モデルの目的関数に納期遅れペナルティの項を追加する。
【０１４１】
数値計算については、ラグランジュ分解調整法にヒューリスティクスを併用する方法を用いた。
【０１４２】
なお、この発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【０１４３】
また、本発明はコンピュータに所定の手段を実行させるため、コンピュータを所定の手段として機能させるため、コンピュータに所定の機能を実現させるため、あるいはプログラムを記録したコンピュータ読取り可能な記録媒体としても実施することもできる。
【図面の簡単な説明】
【０１４４】
【図１】本発明の一実施形態による多品目多段工程動的ロットサイズスケジューリング方法の構成を示す図。
【図２】図１のステップＳ１の「負荷の把握と計画対象期間の調整」の手順を示す図。
【図３】図１のステップＳ２の「基本手法による最適化と制約充足の数値計算」の手順を示す図。
【図４】図１のステップＳ３の「Ｈ(α)法による実行可能解の導出」の手順を示す図。
【図５】例解の工程フローを示す図。
【図６】反復回数ν＝１のときの累積操業率グラフを示す図。
【図７】制約違反件数の推移を示す図。
【図８】計画対象期間にわたる品目別在庫推移グラフ及び機械別品目別ガントチャートデータを示す図。
【図９】計画対象期間にわたる品目別在庫推移グラフ及び機械別品目別ガントチャートデータを示す図。
【図１０】機械別タイムスロット別、品目別タイムスロット別のラグランジュ乗数値を示す図。
【図１１】計算を打ち切ったときの累積操業率グラフ（非実行可能解）、打ち切り後ヒューリスティクスを用いて実行可能解を算出したときの累積操業率グラフ、Ｈ(０)法で実行可能解が算出されたときの累積操業率グラフを示す図。
【図１２】本発明の一実施形態による多品目多段工程動的ロットサイズスケジューリング装置の構成を示す図。
【符号の説明】
【０１４５】
１０２…ＣＰＵ、１０４…主メモリ、１０６…ＣＤ−ＲＯＭ装置、１０８…キーボード、１１０…ディスプレイ、１１２…ＨＤＤ、１１４…システムバス、１１６…ＣＤ−ＲＯＭ、１１８…最適化スケジューリングプログラム。
【特許請求の範囲】
【請求項１】
複数の品目を複数の機械により複数の工程で生産する多品目多段工程生産システムに適用される生産スケジュールをコンピュータにより生成する多品目多段工程動的ロットサイズスケジューリング方法において、
計画対象期間を複数のタイムスロットに分割し、
機械と品目とがタイムスロットにおいて処理中であるか否かの関係を０−１決定変数を用いて表わし、
各品目の処理とそれに伴う仕掛かりの推移を前記決定変数及び段取りの残り時間を用いた仕掛かり推移方程式で記述し、
段取りの残り時間の推移を段取り推移方程式で記述し、
仕掛かり量の下限を負の値とし、納期遅れコストを考慮した前記仕掛かり推移方程式と前記段取り推移方程式とに関する目的関数を機械干渉、仕掛かり不足を無視して品目別の部分最適化を行い、全ての品目、タイムスロット、機械についての前記決定変数を求め、
計画対象期間末における累積操業率が１を超える場合は、オペレータに計算上の計画対象期間を延長させ、
延長された計画対象期間について機械干渉禁止制約と仕掛かり品目の実在庫の品切れ禁止制約が所定の条件を満たすまでラグランジュ分解調整法により前記目的関数を最適化し非実行可能解を求め、
実行不可能解を初期解として機械干渉を解消し、続いて仕掛かり不足を解消させるヒューリスティクスにより納期遅れを許した実行可能解を求めることを特徴とする多品目多段工程動的ロットサイズスケジューリング方法。
【請求項２】
前記実行可能解を求めるステップは、
全ての品目、機械、タイムスロットに対して、決定変数の値を読み取り、
決定変数と機械干渉制約とに基づいて機械干渉箇所を特定し、
機械干渉を起こしているロットをバックワード法、フォワード法等により移動して機械干渉を解消し、
決定変数と品切れ禁止制約とに基づいて仕掛かり品目の品切れ箇所を特定し、
仕掛かり不足を起こしている品目のロットを早める、遅らせる、そのロットと一つ前のロットの順序を入れ替える、あるいは後続直結品目のロット処理を遅らせることにより仕掛かり品目の品切れ箇所を解消することを特徴とする請求項１記載の多品目多段工程動的ロットサイズスケジューリング方法。
【請求項３】
前記仕掛かりは対象在庫点にある在庫と、当該在庫点から消費者に最も近い在庫点までの間に滞留している在庫とを含むことを特徴とする請求項１または請求項２記載の多品目多段工程動的ロットサイズスケジューリング方法。
【請求項４】
複数の品目を複数の機械により複数の工程で生産する多品目多段工程生産システムに適用される生産スケジュールをコンピュータにより生成する多品目多段工程動的ロットサイズスケジューリング装置において、
計画対象期間を複数のタイムスロットに分割し、機械と品目とがタイムスロットにおいて処理中であるか否かの関係を０−１決定変数を用いて表わし、各品目の処理とそれに伴う仕掛かりの推移を前記決定変数及び段取りの残り時間を用いた仕掛かり推移方程式で記述し、段取りの残り時間の推移を段取り推移方程式で記述し、仕掛かり量の下限を負の値とし、納期遅れコストを考慮した前記仕掛かり推移方程式と前記段取り推移方程式とに関する目的関数を機械干渉、仕掛かり不足を無視して品目別の部分最適化を行い、全ての品目、タイムスロット、機械についての前記決定変数を求める手段と、
計画対象期間末における累積操業率が１を超える場合は、オペレータに計算上の計画対象期間を延長させる手段と、
延長された計画対象期間について機械干渉禁止制約と仕掛かり品目の実在庫の品切れ禁止制約が所定の条件を満たすまでラグランジュ分解調整法により前記目的関数を最適化し非実行可能解を求める手段と、
実行不可能解を初期解として機械干渉を解消し、続いて仕掛かり不足を解消させるヒューリスティクスにより納期遅れを許した実行可能解を求める手段と、
を具備することを特徴とする多品目多段工程動的ロットサイズスケジューリング装置。
【請求項５】
前記実行可能解を求める手段は、
全ての品目、機械、タイムスロットに対して、決定変数の値を読み取る手段と、
決定変数と機械干渉制約とに基づいて機械干渉箇所を特定する手段と、
機械干渉を起こしているロットをバックワード法、フォワード法等により移動して機械干渉を解消する手段と、
決定変数と品切れ禁止制約とに基づいて仕掛かり品目の品切れ箇所を特定する手段と、
仕掛かり不足を起こしている品目のロットを早める、遅らせる、そのロットと一つ前のロットの順序を入れ替える、あるいは後続直結品目のロット処理を遅らせることにより仕掛かり品目の品切れ箇所を解消する手段と、
を具備することを特徴とする請求項４記載の多品目多段工程動的ロットサイズスケジューリング装置。
【請求項６】
前記仕掛かりは対象在庫点にある在庫と、当該在庫点から消費者に最も近い在庫点までの間に滞留している在庫とを含むことを特徴とする請求項４または請求項５記載の多品目多段工程動的ロットサイズスケジューリング装置。
【請求項１】
複数の品目を複数の機械により複数の工程で生産する多品目多段工程生産システムに適用される生産スケジュールをコンピュータにより生成する多品目多段工程動的ロットサイズスケジューリング方法において、
計画対象期間を複数のタイムスロットに分割し、
機械と品目とがタイムスロットにおいて処理中であるか否かの関係を０−１決定変数を用いて表わし、
各品目の処理とそれに伴う仕掛かりの推移を前記決定変数及び段取りの残り時間を用いた仕掛かり推移方程式で記述し、
段取りの残り時間の推移を段取り推移方程式で記述し、
仕掛かり量の下限を負の値とし、納期遅れコストを考慮した前記仕掛かり推移方程式と前記段取り推移方程式とに関する目的関数を機械干渉、仕掛かり不足を無視して品目別の部分最適化を行い、全ての品目、タイムスロット、機械についての前記決定変数を求め、
計画対象期間末における累積操業率が１を超える場合は、オペレータに計算上の計画対象期間を延長させ、
延長された計画対象期間について機械干渉禁止制約と仕掛かり品目の実在庫の品切れ禁止制約が所定の条件を満たすまでラグランジュ分解調整法により前記目的関数を最適化し非実行可能解を求め、
実行不可能解を初期解として機械干渉を解消し、続いて仕掛かり不足を解消させるヒューリスティクスにより納期遅れを許した実行可能解を求めることを特徴とする多品目多段工程動的ロットサイズスケジューリング方法。
【請求項２】
前記実行可能解を求めるステップは、
全ての品目、機械、タイムスロットに対して、決定変数の値を読み取り、
決定変数と機械干渉制約とに基づいて機械干渉箇所を特定し、
機械干渉を起こしているロットをバックワード法、フォワード法等により移動して機械干渉を解消し、
決定変数と品切れ禁止制約とに基づいて仕掛かり品目の品切れ箇所を特定し、
仕掛かり不足を起こしている品目のロットを早める、遅らせる、そのロットと一つ前のロットの順序を入れ替える、あるいは後続直結品目のロット処理を遅らせることにより仕掛かり品目の品切れ箇所を解消することを特徴とする請求項１記載の多品目多段工程動的ロットサイズスケジューリング方法。
【請求項３】
前記仕掛かりは対象在庫点にある在庫と、当該在庫点から消費者に最も近い在庫点までの間に滞留している在庫とを含むことを特徴とする請求項１または請求項２記載の多品目多段工程動的ロットサイズスケジューリング方法。
【請求項４】
複数の品目を複数の機械により複数の工程で生産する多品目多段工程生産システムに適用される生産スケジュールをコンピュータにより生成する多品目多段工程動的ロットサイズスケジューリング装置において、
計画対象期間を複数のタイムスロットに分割し、機械と品目とがタイムスロットにおいて処理中であるか否かの関係を０−１決定変数を用いて表わし、各品目の処理とそれに伴う仕掛かりの推移を前記決定変数及び段取りの残り時間を用いた仕掛かり推移方程式で記述し、段取りの残り時間の推移を段取り推移方程式で記述し、仕掛かり量の下限を負の値とし、納期遅れコストを考慮した前記仕掛かり推移方程式と前記段取り推移方程式とに関する目的関数を機械干渉、仕掛かり不足を無視して品目別の部分最適化を行い、全ての品目、タイムスロット、機械についての前記決定変数を求める手段と、
計画対象期間末における累積操業率が１を超える場合は、オペレータに計算上の計画対象期間を延長させる手段と、
延長された計画対象期間について機械干渉禁止制約と仕掛かり品目の実在庫の品切れ禁止制約が所定の条件を満たすまでラグランジュ分解調整法により前記目的関数を最適化し非実行可能解を求める手段と、
実行不可能解を初期解として機械干渉を解消し、続いて仕掛かり不足を解消させるヒューリスティクスにより納期遅れを許した実行可能解を求める手段と、
を具備することを特徴とする多品目多段工程動的ロットサイズスケジューリング装置。
【請求項５】
前記実行可能解を求める手段は、
全ての品目、機械、タイムスロットに対して、決定変数の値を読み取る手段と、
決定変数と機械干渉制約とに基づいて機械干渉箇所を特定する手段と、
機械干渉を起こしているロットをバックワード法、フォワード法等により移動して機械干渉を解消する手段と、
決定変数と品切れ禁止制約とに基づいて仕掛かり品目の品切れ箇所を特定する手段と、
仕掛かり不足を起こしている品目のロットを早める、遅らせる、そのロットと一つ前のロットの順序を入れ替える、あるいは後続直結品目のロット処理を遅らせることにより仕掛かり品目の品切れ箇所を解消する手段と、
を具備することを特徴とする請求項４記載の多品目多段工程動的ロットサイズスケジューリング装置。
【請求項６】
前記仕掛かりは対象在庫点にある在庫と、当該在庫点から消費者に最も近い在庫点までの間に滞留している在庫とを含むことを特徴とする請求項４または請求項５記載の多品目多段工程動的ロットサイズスケジューリング装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２００９−２５８８６３（Ｐ２００９−２５８８６３Ａ）
【公開日】平成２１年１１月５日（２００９．１１．５）
【国際特許分類】
【出願番号】特願２００８−１０５１３８（Ｐ２００８−１０５１３８）
【出願日】平成２０年４月１４日（２００８．４．１４）
【出願人】（０００１２５３６９）学校法人東海大学 (352)
【Ｆターム（参考）】
【公開日】平成２１年１１月５日（２００９．１１．５）
【国際特許分類】
【出願日】平成２０年４月１４日（２００８．４．１４）
【出願人】（０００１２５３６９）学校法人東海大学 (352)
【Ｆターム（参考）】
[ Back to top ]