IMPROVED ALGORITHMS FOR ECONOMIC LOT-SIZE PROBLEMS
成果类型：
Article
署名作者：
AGGARWAL, A; PARK, JK
署名单位：
United States Department of Energy (DOE); Sandia National Laboratories; Massachusetts Institute of Technology (MIT)
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.41.3.549
发表日期：
1993
页码：
549-571
关键词：
摘要：
Many problems in inventory control, production planning, and capacity planning can be formulated in terms of a simple economic lot Size model Proposed independently by A. S. Manne (1958) and by H. M. Wagner and T. M. Whitin (1958). The Manne-Wagner-Whitin model and its variants have been studied widely in the operations research and management science communities, and a large number of algorithms have been proposed for solving various problems expressed in terms of this model, most of which assume concave costs and rely on dynamic programming. In this paper, we show that for many of these concave cost economic lot size problems, the dynamic programming formulation of the problem gives rise to a special kind of array, called a Monge array. We then show how the structure of Monge arrays can be exploited to obtain significantly faster algorithms for these economic lot size problems. We focus on uncapacitated problems, i.e., problems without bounds on production, inventory. or backlogging; capacitated problems are considered in a separate paper.