Premium
A note on solving the concave cost dynamic lot‐sizing problem in almost linear time
Author(s) -
Evans James R.,
Saydam Cem,
McKnew Mark
Publication year - 1989
Publication title -
journal of operations management
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.649
H-Index - 191
eISSN - 1873-1317
pISSN - 0272-6963
DOI - 10.1016/0272-6963(89)90017-x
Subject(s) - computer science , computation , simple (philosophy) , sizing , mathematical optimization , extension (predicate logic) , microcomputer , path (computing) , argument (complex analysis) , algorithm , cost structure , mathematics , economics , art , telecommunications , philosophy , chip , biochemistry , chemistry , epistemology , microeconomics , visual arts , programming language
The heavily‐debated Wagner‐Whitin algorithm is known to produce optimal ordering policies for minimal‐cost dynamic lot‐sizing problems. In an earlier paper in this journal, Evans showed that the Wagner‐Whitin algorithm is essentially a shortest path computation on an acyclic network, and presented a simple O(n 2 ) computer implementation with low storage requirements. As an extension, in this paper we present a very fast microcomputer implementation of the algorithm for the case of concave procurement cost structures. Our extensive computational results show that for this cost structure, the algorithm will solve problems in linear time. A quasi‐theoretical argument is given to explain this behavior under the assumption that data are randomly distributed.