ラグランジアン・ヒューリスティック法に基づく並列機械多品目可変容量制約付きロットサイズ決定問題の解法  [in Japanese] A Solution Method for the Variable Capacitated Lot Sizing Problem on Parallel Machines Based on the Lagrangian heuristic  [in Japanese]

The capacitated lot sizing problem (CLSP) is one of the representative problems in mathematical planning, and it has various applications in many fields. Therefore, there have been many studies on this problem. However, the majority of these do not consider the overtime production which is performed routinely. In this study, we consider the capacitated lot sizing problem on parallel machines in taking variable capacity constraints into consideration. We propose 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 a Lagrangian relaxation problem. Next, we propose a method to determine a near-optimal solution for the problem by successively decreasing the difference between upper and lower bounds.