遞迴演算法求解多階最佳經濟批量

Optimizing Multilevel Lot-Sizing Problems with a Recursive Algorithm

本文針對物料需求計畫多階段作業及多計畫期的最佳動態經濟批量，克服電腦主記憶體空間限制，以較少主記憶體空間的遞迴演算法及資料庫，建立求解任何多階段及多計畫期作業之最低總成本的最佳解模式，有別於一般近似解。文獻上對於16 階以上大型產品結構的最佳批量問題，常因過於複雜而造成主記憶體不足的困擾，因而常採取近似解法（heuristic approach）。本文則推導出前後計畫期可行解的遞迴關係、前後階段作業可行解的遞迴關係，以及具遞迴關係的最佳解模式，減少了很多加法項數、比較項數；此外，經由建立資料庫，進一步減少電腦主記憶體儲存空間，而免於因求最佳解而主記憶體不足的困擾。

This paper develops a recursive algorithm and database concept tosolve the optimal multilevel lot-sizing problem with less computer memoryin material requirement planning systems. This algorithm is different fromthe heuristics approach. A few studies in the literature discuss the optimallot size when the levels of the product structure are more than 16 levels.Most of the available studies use the heuristic approach due to the shortageof computer memory. This paper develops several recursive relations offeasible policy between adjacent periods and adjacent levels, to establishthe optimal model and reduce the computation and comparison. Theoptimum solution with recursive relations will yield an efficientcomputation and use less computer memory through establishing adatabase.