次梯度方法
拉格朗日松弛
数学优化
启发式
对偶间隙
解算器
尺寸
整数规划
计算机科学
调度(生产过程)
放松(心理学)
数学
最优化问题
社会心理学
艺术
视觉艺术
心理学
作者
Kevin A. Bunn,José A. Ventura
标识
DOI:10.1080/00207543.2023.2237120
摘要
In this work, we study the multi-product dynamic lot-sizing problem with capacity constraints and batch ordering. This problem arises in short to medium range production scheduling for several products over a finite number of periods to meet known demand. Each period has a capacity for placing orders, and every order for each product must have a fixed quantity, or batch size, though multiple orders can be placed for each product. We define three mixed-integer linear programming (MILP) models and apply Lagrangian relaxation to formulate the corresponding dual problems by relaxing the capacity constraints. The aim is to identify the dual problem that is the easiest to solve and provides the solution with the smallest duality gap. Subgradient optimisation is applied to solve the preferred Lagrangian dual model, which uses one of two heuristics to find good feasible solutions. We also show that the special case, where the batch sizes for all products are the same, can be modeled as a transportation problem. A set of numerical experiments is designed to compare the performance of the Lagrangian relaxation approach with a commercial MILP solver to identify the version of the subgradient algorithm and the MILP model that provide the best solutions.
科研通智能强力驱动
Strongly Powered by AbleSci AI