A primal-dual algorithm for the dynamic lotsizing problem with joint set-up costs

In this article the multi-item dynamic lotsizing problem with joint set-up costs (LPJS) is considered. A tight formulation of the problem and the dual of the linear relaxation of this formulation is presented. A procedure to solve this dual problem is developed where the solution provides a strong lower bound for the LPJS. This lower bound is used in a branch and bound procedure to find an optimal solution to the problem. The extensive computational experiments with this procedure revealed that it outperforms the other available branch and bound algorithm in the literature. With the proposed algorithm the average time requirement was about 113 seconds on a 486DX33 processor for solving a difficult class of LPJS problems that have 50 items and 24 periods. © 1995 John Wiley & Sons, Inc.     

An optimal procedure for the coordinated replenishment dynamic lot‐sizing problem with quantity discounts

We consider in this paper the coordinated replenishment dynamic lot‐sizing problem when quantity discounts are offered. In addition to the coordination required due to the presence of major and minor setup costs, a separate element of coordination made possible by the offer of quantity discounts needs to be considered as well. The mathematical programming formulation for the incremental discount version of the extended problem and a tighter reformulation of the problem based on variable redefinition are provided. These then serve as the basis for the development of a primal‐dual based approach that yields a strong lower bound for our problem. This lower bound is then used in a branch and bound scheme to find an optimal solution to the problem. Computational results for this optimal solution procedure are reported in the paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 686–695, 2000