关键词: 生产计划, 调度, CLSP, 启发式, 分枝定界, 列生成

Abstract: A Branch-and-Price approach was presented to solve the classical capacitated single-level multi-item dynamic lot-sizing problems, also called as CLSP. Its objective is to minimize the sum of set-up and inventory-holding costs over the horizon under consideration, such as demands, capacity restrictions, etc. CLSP is frequently encountered in the most industry settings and well known as NP-Hard problem. The Branch-and-Price approach, a generalization of branch-and-bound with LP relaxation, allows column generation to be applied throughout explored nodes in the branch-and-bound tree. An implementation of the branch-and-price approach was described in detail. Two groups of examples were computed to verify the correctness and advantages of the suggested approach.