Premium
A primal‐dual algorithm for the dynamic lotsizing problem with joint set‐up costs
Author(s) -
Kirca Ömer
Publication year - 1995
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199508)42:5<791::aid-nav3220420506>3.0.co;2-8
Subject(s) - mathematical optimization , dual (grammatical number) , upper and lower bounds , branch and bound , set (abstract data type) , computer science , relaxation (psychology) , algorithm , linear programming relaxation , class (philosophy) , linear programming , joint (building) , mathematics , artificial intelligence , engineering , programming language , architectural engineering , art , mathematical analysis , social psychology , psychology , literature
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.