抄録
この問題にはロットの順序やサイズなどの多様な決定の局面がある.本研究では, 問題に含まれるすべての決定の局面を, 全体最適化の視点から同時に解く方法として, ラグランジュ分解・調整法を提案する.先ず, 計画対象期間を極めて小さなタイムスロットに刻んで, 各品目の在庫の推移や段取時間の経過を陽に取り扱って, 問題を多次元の動的最適化問題に定式化する.次に問題の分離可能性と機械干渉に関する制約の存在とに注目して, 問題を品目別に分解した後, 各々の部分問題の動的計画法による解法とラグランジュ乗数の調整とを交互に繰り返すことによって, 機械干渉を解消して近似最適な解を導く, 最後にプリント配線基盤への部品装着工程における実用例を掲げる.
This paper treats the scheduling of multiple items on a single machine according to a sequence of shipment requirements for each item. In this problem, there exist various heterogeneous decision features such as lot sizing, lot sequencing, and so on. We present a Lagrangean decomposition coordination method that enables us to solve all of these decision features involved in this problem from the point view of the total optimization simultaneouly. First, by splitting the planning horizon into very small time slots, we treat both the inventory transition of each item and the time transition in each setup explicitly. In order to realize this, we assume that if an item is processed at a time slot, then its corresponding decision variable takes the value of unity or else null. By using those decision variables, the problem is formulated into a multi-dimensional dynamic optimization problem with constraints. Second, in order to dissolve the curse of dimensionality, paying attention to the separable property of the problem and the existence of the constraint related to machine interference of all time slots, we decompose the whole problem into sub-problems based on item. Third. along the line of the Lagrangean relaxation method, we trasform this constrained optimization problem into an iterative solution procedure of an unconstrained optimization one. The procedure in an iteration consists of solving each sub-problem for given Lagrange multiplier values and of coordinating those multiplier values. Dynamic programming with delay solves each sub-problem. A rule for updating the Lagrange multipliers is proposed. Finally, we illustrate a numerical example of practical use having been successfully applied to a process inserting parts onto printed circuit boards for computer printers.
