單元形成問題之求解模式與演算法

Abstract

單元形成問題是單元製造系統(CMS)設計最重要且最複雜的部分，可分成考量二元零件－機器關係矩陣的標準單元形成問題及考量多項生產資料之廣義單元形成問題二大類。雖然在標準單元形成問題部分，已經有很多方法被提出，但在廣義單元形成問題部分，鮮少有方法同時整合CMS設計的三大步驟：單元形成、單元佈置及單元內機器擺設並考量生產資料，含多途程、需求量、零件加工順序及機器可靠度。 有鑑於此，本論文首先結合相似係數法及萬用啟發式演算法，包括模擬退火法、仿水流優化演算法和禁忌搜尋演算法，發展出有效的混合式兩階段方法來有效求解標準單元形成問題。對於廣義單元形成問題，本文整合了CMS設計的三大步驟並考量生產資料，含多途程、需求量、零件加工順序及機器可靠度，提出一個兩階段的多目標數學規劃模式。接著，採用以廣義相似係數法及萬用啟發式演算法為基底的混合式演算法來有效的求解此多目標數學規劃模式。 不同於其他的方法，本論文所提出的單元形成方法不但整合了CMS設計的三大步驟且單元數可經由決策者輸入或根據最佳目標解自動產生。實驗分析和比較的結果展現本文所提的兩階段多目標數學規劃模式及三個演算法的有效性，並顯示這些演算法可以在很短的電腦執行時間內提供一個穩健的製造單元形成規劃。

Cell formation problem (CFP) is the first and most difficult aspect of constructing a preliminary cellular manufacturing system (CMS). The CFP can be classified into two main categories: the standard CFP represented by a binary machine-part incidence matrix and the generalized CFP with more factors and system constraints considerations. Although many studies have been done on standard CFP, generalized CFP had received less attention. Very little has been done to integrate the three basic steps (e.g., cell formation, cell layout, and intracellular machine layout) in the design of CMS. Based on the above discussion, a two-stage hybrid algorithm merging a similarity coefficient method (SCM)-based clustering algorithm and meta-heuristics, including simulated annealing (SA), water flow-like algorithm (WFA) and tabu search (TS) is first presented to solve standard CFP quickly and effectively. In regard to the generalized CFP, a two-stage multi-objective mathematical programming model is first formulated to integrate cell formation, cell layout, and intracellular machine layout simultaneously with the considerations of alternative process routings, operation sequences, production volume, production times, and machine reliability. A two-stage hybrid approach integrating a generalized SCM-based clustering algorithm and SA/TS/WFA method is then proposed to solve this generalized CFP model quickly and effectively. Unlike most existing methods, the proposed approach not only integrates the three basic steps in the design of CMS but also automatically calculates and determines the number of cells (NC) to achieve the best objective value. Illustrative examples, comparisons, and experimental analyses demonstrate the effectiveness of the proposed models and solution algorithms. The proposed approaches can be used to solve real-life CFP in factories by providing robust manufacturing cell formation in a short execution time.