Heuristic Strategies for the Single-Item Lot-Sizing Problem with Convex Variable Production Cost

This dissertation, "Heuristic Strategies for the Single-item Lot-sizing Problem With Convex Variable Production Cost" by Xin, Liu, 劉忻, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled Heuristic Strategies for the Single-Item Lot-Sizing Problem with Convex Variable Production Cost Submitted by Liu Xin For the Degree of Master of Philosophy at the University of Hong Kong in September 2005 This research is about the stochastic single-item lot-sizing problem, whose objective is to determine the quantities that will be produced in specific production periods so that the total production quantity will satisfy the demands while the total cost will be minimized. Particularly, the type of problem studied in this research is concerned with production with convex variable production costs. The costs involved in the computation of optimal lot sizes include the set-up cost for every occurrence of a production, the holding cost for products which are finished before their due date, the penalty cost for orders that are not satisfied on time and are therefore backordered, and the "excess capacity" cost for products that are produced by exceeding the regular capacity. Unfortunately, the search for optimal lot-sizing policy of the lot-sizing problem in this research is always found to be elusive. The computational effort for solving even small-scale problems is prohibitively large. This research is based on the work of Dellaert and Melo on the use of the Markov 3decision model for establishing the optimal policy. However, instead of obtaining the optimal solution in general, which is too complex in most practical situations, three approximate strategies including (, xTw, )-rule, the modified (, xTw, ) -rule and the least-cost-per-period (LCP) policy are proposed for obtaining good production lot sizes. The first one is a production strategy where the demands for a certain number of periods are produced with a fixed number of units produced for a non-dedicated stock. The second rule, which is a variation of the (, xTw, ) -rule, permits at most one period's demand to be satisfied. Particularly, it allows production using means (e.g., overtime or subcontracting) that exceeds the plant's regular capacity and therefore may reduce the holding and overtime cost. The third lot-sizing strategy is based on the well-known Silver-Meal algorithm but it differs from the latter with the consideration of cases that have backlogs and actions for future coming demands. A comprehensive set of test problems covering a wide variety of demand and cost parameters is used to compare the performance of the three proposed lot-sizing strategies. The numerical study reveals that the interaction of the cost, demand patterns and the regular capacity influences the performance of the heuristic strategies in such a way that in general there is no dominance of one rule over the others in every case. Also, the newly developed strategies have been shown to produce good performances. 4 DOI: 10.5353/th_b3642917 Subjects: Economic lot size - Mathematical models Production planning - Mathematical models Markov processes