順序依存型段取り時間を考慮した多品目容量制約付きロットサイズ決定問題の近似最適解法  [in Japanese] A Near-Optimal Solution for the Capacitated Lot Sizing Problem with Sequence-Dependent Setup Times  [in Japanese]

多期間にわたって複数の品目を1台の機械で生産する.各期間における各品目の需要量は既知であり,各品目とも需要量に対する生産の遅れは許されない.また,各期間の生産時間は所与の規定時間以下でなければならない.このとき,生産費用,在庫保管費用,段取り費用の総和が最小となるように,各期間で生産すべき品目とそのロットサイズを同時に決定する問題を多品目容量制約付きロットサイズ決定問題という.この問題に関してはこれまでに数多くの研究があるが,それらの多くは各品目の生産順序に依存する段取り時間を場に考慮していない.そこで当研究では,各品目の生産順序に依存する段取り時間を考慮した場合の多品自容量制約付きロットサイズ決定問題を考える.つまり,生産費用,在庫保管費用,段取り費用の総和が最小となるように,各期間で生産すべき品目とそのロットサイズ,および各品目の生産順序を同時に決定する問題を考え,この問題のラグランジアン・ヒューリスティッタ法に基づく近似最適解法を提案する.最初に,この問題を混合0-1整数計画問題に定式化する.次いで,単一品目動的ロットサイズ決定問題と割当問題を解いてこの問題の下界値を求める方法を示したあと,それを組み込んだこの問題の近似最適解法を提案する.そして最後に,提案法の有効性を数値実験を通して検証する.

The capacitated lot sizing problem (CLSP) consists of simultaneously determining the items that should be produced in each period and lot sizes so as to satisfy a known demand in each period and minimize the sum of the production, inventory holding and setup costs when multiple items are produced by a single machine over a finite number of periods. So far, there have been many studies on this problem. However, the majority of these do not consider the setup time which is dependent on the production sequence of each item. In this study, we consider the capacitated lot sizing problem in taking this setup time into consideration. Namely, we consider the problem of simultaneously determining the items that should be produced in each period, lot sizes and production sequence of each item so as to minimize the sum of the production, inventory holding and setup costs. This study proposes a near-optimal solution for this problem based on the Lagrangian heuristic. Initially, we formulate the problem as a mixed 0-1 integer programming problem, and present a method to determine the lower bound of the problem by solving the single item dynamic lot sizing problem and the assignment problem. We then propose a method to determine a near-optimal solution for the problem by successively decreasing the difference between the upper and lower bounds. Finally, we verify the effectiveness of the proposed method through computational experiments.