動態批量平行演算法之探討

摘要

由於批量之決定影響生產系統之效率甚大，故在MRP架構中一直扮演著很重要的角色。雖然目前已有不少這方面之研究，大部份的最佳批量演算法卻受限於龐大之計算量而較不受實務界重視。隨著平行處理機的性能價格比日漸提昇，如何運用平行演算法以求解如動態批量這樣計算繁雜的問題便是一値得重視的研究方向。本文提出了二個動態批量平行演算法，在問題大小爲n時，前者複雜度爲O(n{su2})（如果有n個處理器），後者則爲O(n{su3}/p+np{su2})（如果有P個處理器，且P<<n），並分别舉例說明之。本文也探討了所提演算法之效率及後續硏究方向。

Abstract

Lot sizing in an MRP environment is an important problem because the decisions can highly affect the performance of a production system. Though there are many research conducted in recent years to find the optimum of the lot sizing models, the practicality of the algorithms is hindered by the huge amount of computer resources required to solve the models, even for a modest problem. Since the powerful parallel computers are becoming cost-effective nowadays, it is necessary to explore paraIlel algorithms that can be used to solve these laborious computational problems. This paper presents two parallel algorithms for solving dynamic lot sizing problem using the cost path concept. Given n is the size of the problem. it is shown that the first proposed parallel algorithm is O(n ²) with n processors and the second proposed parallel algorithm is with p processors (p<<n). Comparison analysis of the proposed parallel algorithms and some future research directions are also provided.

關鍵詞:

• 物料需求規劃
• 平行演算法
• 平行計算之複雜度

Key words:

• MRP
• parallel algorithm
• complexity