The Application Of Combinatorial Optimization In The Economic Lot-sizing Problem

ELS problem is economic lot-sizing problem or dynamic lot-sizing problem, ELS or DLS for short. Production and inventory management are some of those areas where the study of lot-sizing models is originating from. One of simplest lot-sizing models assumes stationarity of the demand rate and production costs. It is called an Economic Order Quantity (EOQ) model. While in practical production and inventory management, the ELS models with dynamic demand rate and costs are more useful. In this thesis, we will consider two class of ELS models where demand and costs may change from period to period.Three chapters are included in this thesis.In the first chapter, we introduce the development of inventory management, basic background of economic lot-sizing problem and some useful definitions about the complexity of the algorithms.In the second chapter, we show a single product no-backlogging ELS problem with a class of multi-breakpoint discount cost structures. When the order quantity is in different intervals, different discount rates are given. The vectors of each interval are called as breakpoints.This chapter is an extension of a single product no-backlogging ELS problem with one breakpoint discount cost function. For this problem we analyze the optimality properties and develop an optimal algorithm whose running time is bounded by O(n³+mn²), in which n is the number of periods in planning horizon, and m is the number of breakpoints. In the third chapter , we propose a perishable inventory ELS problem with backlogging, where the cost functions of ordering, holding and backlogging penalty-are economies of scale functions. We call the product (or inventory) perishable product (or inventory) if the product tends to deteriorate when it is holding in the warehouse, the deteriorate proportion relates to the holding time. The function f(x) is called economies of scale function, if it satisfies the following two conditions:(1) f(x) defined in [0, +∞) is a non-decreasing function, and f(0) = 0.(2) The average function f(x) = (f(x))/x is a non-increasing function in (0, +∞).It has been showed that a perishable inventory ELS problem with economiesof scale function cost structures is an NP-hard problem. For the no-backlogging case of this problem, Chu et al.(2005. Naval Research Logistics) has proposed an approximation algorithm which can obtain an approximate solution with the worst case ratio (4(2)^1/2 + 5)/7. In this chapter, we extend it to the case with backlogging, and give an approximation algorithm with polynomial running time. We get the same result and show that this bound is tight.