Perhaps the most widely studied and simplest combinatorial optimization problem in production planning, the uncapacitated economic lot sizing problem (UELSP) was rst solved in the 1958 seminal paper byWagner andWhitin [116]. Sometimes referred to as dynamic lot sizing (or requirements planning), this problem addresses the basic tradeo between production ordering costs and inventory holding costs for a single stage that faces dynamic and deterministic customer demands. The problem is divided into a contiguous set of discrete planning periods, and the goal is to meet all demands at minimum total production and inventory holding cost over a nite planning horizon consisting of the set of planning periods. In any planning period, an order cost exists for acquiring inventory, independent of the order quantity, and a holding cost is assessed against the inventory held in the period. While we will approach the problem as if placement of an order results in immediate replenishment (i.e., zero replenishment lead time), we can easily account for a positive constant replenishment lead time by osetting the orders placed in the zero-lead-time case by the constant lead time value.