段取時間のある多品目多段工程動的ロットサイズスケジューリング : ラグランジュ分解調整法  [in Japanese] Multi-item, Multi-stage Dynamic Lot Size Scheduling with Setup Time : Lagrangean Decomposition Coordination Methods  [in Japanese]

一般型製品構成を持ち順序依存型でない段取り時間を伴う多品目の多段工程非一様型並列機械から成る生産システムの動的ロットサイズスケジューリング問題の近似解法を提案する.本解法の構成は, 細かなタイムバケットによる問題の0-1計画法への定式化と梯状在庫の利用, 狭義ラグランジュ分解調整法から成る.最後に数値例を取り扱って提案する方法を検証する.

This paper addresses the dynamic lot size scheduling problem for processing multiple items in a multi-stage production system so as to minimize the total cost, consisting of setup costs and holding costs, over the planning horizon under the constraint of shipment requirements. In this problem, there exists various heterogeneous decision features such as lot sizing, lot sequencing, dispatching and so on. We present a Lagrangean decomposition coordination method that enables us to simultaneously solve all of these decision features involved in this problem without specifying or awakening to them one by one. First, splitting the planning horizon into very small time slots, we denote a state of processing as to each item on each machine at the time slot by using a binary decision variable that takes the value of unity if it is processed, or zero if not. Second, dealing with the transition of the inventory state of each item and the time transition of each setup explicitly, we formulate the problem into a multi-dimensional dynamic optimization problem with constraints. Third, paying attention to the separable property of the problem and the existence of interaction constraints related to machine interferences and work-in-process inventory balances, we decompose the whole problem into item-based sub-problems to dissolve the curse of dimensionality. At the aim of guaranteeing the decomposability, problem formulation is made by the concepts of echelon inventory. Each sub-problem is reformulated into the dynamic programming of one dimension. The computational procedure consists of solving sub-problems for given Lagrangean multiplier values and coordinating those values, which is repeated until the interaction constraints are satisfied. Finally, we verify the presented method by solving an illustrated example.