《ロットスケジューリング》

【ろっとすけじゅーりんぐ (lot scheduling)】

　ロット生産では段取り作業が必要なことから, 適切な大きさのロットサイズを決めることが生産スケジューリングにおける意思決定事項の一つとなる. 多品種生産では, 生産速度が有限であるため, ロットサイズとともに各ロットの生産順序も決める必要がある. ロットサイズと各ロットの生産順序を併せて決める問題をロットスケジューリング問題(economic lot scheduling)と呼ぶ. 各ロットの大きさと生産順序は, 生産能力, 生産速度, 納期(需要速度), 段取り時間, 在庫量といった要素を考慮し, 段取り費用, 在庫費用, 生産費用, 納期遅れ費用などの和を最小化するように決定される.

　ロットスケジューリング問題は以下の要素によって分類できる. (i) 計画期間の長さ:無限期間か有限期間か, (ii) 時間の連続性:連続時間か離散時間か, (iii) 品種数:単一品種か多品種か, (iv) 工程の型:単一段階か多段階か, 多段階工程の場合, 組立型か分解型か混合型か, (v) 需要速度:定常需要か動的需要か, (vi) 段取り時間:考慮するか考慮しないか, (vii) 納期遅れ:許すか許さないか.

　主なロットスケジューリング問題には, 以下のようなモデルがある [1] - [3].

(1) 単一工程・連続時間型モデル:

　各品種の需要速度は一定かつ既知であって, (i) 計画期間は連続な無限計画期間, (ii) 生産速度は一定, (iii) 段取り時間と費用は生産順序によらず一定, などの前提条件がおかれる. このような問題は連続時間ロットスケジューリング問題と呼ばれ, 生産される品種がある一定の投入順序にしたがって繰り返し生産されるようにスケジューリングするサイクリックスケジューリング方式が採用される. この方式は, 1製造サイクルの中に各品種の製造連が1つずつ含まれる基本サイクリックスケジューリング方式と, 1製造サイクルに含まれる製造連の数が品種毎に異なる変則サイクリックスケジューリング方式に分けられる. 変則サイクリックスケジューリング方式はさらに, 同じ品種の製造連はすべて同じ大きさのロットサイズとする固定ロットサイズ方式と, 同じ品種であっても製造連によってロットサイズが異なる可変ロットサイズ方式に分けられる.

　基本サイクリックスケジューリング方式における決定変数は, 生産サイクル 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle T\, } だけとなり, 以下のように得られる. いま, 品種 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } の単位期間当たり需要量を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r_i\, } , 段取り時間を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle s_i\, } , 単位生産時間を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p_i\, } , 1回当たり段取り費用を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c_{si}\, } , 単位保管費用を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c_{Ii}\, } とし, 目的関数を段取り費用と在庫費用の総和の時間平均

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle z = \sum_i \{ c_{si} /T + c_{Ii} r_i (1 - p_i r_i)T/2 \} \, }

とする. このとき, 品切れを許さないものとすれば, 問題は,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sum_i (s_i + p_i r_i T) \le T \, }

の範囲で 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle z\, } を最小化する 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle T^*\, } を求めればよく, 次式で与えられる.

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle T^* = \max \Big\{ \sqrt{ \frac{2\sum_i c_{si}}{\sum_i c_{Ii} r_i (1- p_i r_i)}}, \ \frac{\sum_i s_i}{1 - \sum_i p_i r_i} \Big\} }

このとき, 品種 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } の最適ロットサイズ 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle Q_i^*\, } は,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle Q_i^* = r_i T^* \, }

となる. 変則サイクリックスケジューリング方式では, 全ての品種について固定ロットサイズとしても, 在庫量の定式化そのものが難しい. 品種 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } の生産サイクル 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle T_i\, } を基本サイクル 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle T\, } の整数倍とするとき, すなわち,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle T_i = k_i T, \quad k_i \in \{ 1,2,\ldots \} \, }

の制約を設けると, 解析はやや容易となって, 動的計画法によるアプローチも可能となるが, それでもNP困難な問題である[4] [5].

(2) 多工程・連続時間型モデル:

　(1)のモデルを多工程問題に拡張したモデルであるが, 最適化解析は難しい. 機械加工型の多段階工程問題, 並列機械型多工程問題, 加工工程と組立工程をもつ多工程問題などの論文がある [6].

(3) 梯形型モデル:

　梯形型モデル(multi-echelon model)は, 図1に示すような(a) 組立型と(b) 分解型, ならびに組立型と分解型が複合した混合型に分類できる. 図中の番号は工程を表す. 例えば, 図1 (a)の第4工程は第1工程と第2工程で生産された部品をユニットに組み立てて, 第6工程に供給している. 組立型と分解型は, 理論的取り扱いが比較的容易で, 組立型においては, 任意の工程のロットサイズは直後工程でのロットサイズの整数倍とするのが最適となる [7].

図1：梯形型モデルの例

(4) 多品種・離散時間型モデル:

　0-1混合整数計画問題として定式化される有限計画期間のロットスケジューリング問題を離散時間ロットスケジューリング問題(discrete time lot scheduling)と呼ぶことがある. この問題は, 生産管理方式の1つであるMRP(materialrequirements planning system)の中心機能をなすプライオリティ計画(priority planning)の立案モデルとなる. しかし, 有限な生産能力を考慮した実務に耐える効率的アルゴリズムは開発されていない.

　単一工程に対する定式化は, 以下のように与えられる. ただし, 簡易化のため, (i) 需要量など入力データは確定的, (ii) 製品の品切れや遅れは許さない, (iii) 素材の入荷は考慮しない, といった前提を設ける. 記号は, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle T\, } を計画期間, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N\, } を品種数, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle t\, } 期の稼働可能時間を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b_t\, } , 品種 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } の段取り時間を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle s_{i}\, } , 単位生産時間を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p_{i}\, } , 1回当たり段取り費用を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c_{si}\, } , 単位保管費用を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c_{Ii}\, } , 品種 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } の 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle t\, } 期の需要量を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d_{it}\, } , 単位生産費用を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c_{pit}\, } , 生産量を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_{it}\, } , 期末在庫量を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle I_{it}\, } に設定する.

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{min.}\, }	構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \qquad z = \sum_{i=1}^N \sum_{t=1}^T \{c_{pit} x_{it} + c_{si}\delta(x_{it}) + c_{Ii} I_{it} \}\, }
構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{s. t. }\, }	構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sum_{i=1}^N (p_i x_{it} + s_i \delta(x_{it}) ) \le b_t \qquad (t=1,\ldots , T),\, }
	構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle I_{i,t-1} + x_{it} - I_{it} = d_{it} \qquad (t=1,\ldots , T; \; i=1, \ldots , N),\, }
	構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \delta(x) = \left\{ \begin{array}{ll} 1 & (x > 0), \\ 0 & (x = 0), \end{array} \right.\, }
	構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_{it}, I_{it} \ge 0 \qquad (t=1,\ldots , T; \; i=1,\ldots , N).\, }

　この定式化には柔軟性があり, 残業水準や労働水準の変更などを容易に考慮することができる. 問題はNP困難であり, 解法には, 列生成を使った線形近似解法, 双対緩和法, 発見的方法などがある [8].

　この問題は, 多段階生産システムの問題に拡張できる. フローショップの各ステージに同一の機械が複数台配置されたフレキシブル・フローラインにおける最適化解析も行われている [9].

---

参考文献

[1] 村松林太郎, 『生産管理の基礎』, 国元書房, 1970.

[2] L. A. Johnson and D. C. Montgomery, Operations Research in Production Planning, Scheduling, and Inventory Control, John Wiley & Sons, 1974.

[3] S. C. Graves, A. H. G. Rinnooy Kan and P. H. Zipkin, eds., Logistics of Production and Inventory, North-Holland, 1993.

[4] S. E. Elmaghraby, "The Economic Lot Scheduling Problem (ELSP): Review and Extensions,"Management Science, 24-6(1978), 587-598.

[5] W. Hsu, "On the General Feasibility Test of Scheduling Lot Sizes for Several Products on One Machine," Management Science, 29-1(1983), 93-105.

[6] A. Kimms, Multi-Level Lot Sizing and Scheduling, Physica-Verlag, 1997.

[7] W.B. Crowston, M. H. Wagner and A. Henshaw, "Economic Lot Size Determination in Multi-Stage Assembly Systems," Management Science, 19-5(1973), 517-527.

[8] W. W. Trigeiro, "A Dual-Cost Heuristic for the Capacitated Lot Sizing Problem," IIE Transaction, 19-1(1987), 67-72.

[9] D.Quadt, Lot-Sizing and Scheduling for Flexible Flow Lines, Springer, 2004.