- 學位論文
應用高頻項目集探勘求解彈性製造系統中的作業指派及空間分配問題
Applying frequent itemset mining to solve operation assignment and capacity allocation problem in flexible manufacturing systems
摘要
我們討論彈性製造系統(FMS)中的作業及刀具指派問題，我們假設系統中的機器有著作業時間及刀具容納空間的限制，而每種作業都有其特定的權重。我們希望找出一個方法，該方法能適當的指派作業及刀具至系統中使得被指派作業能為系統帶來最高的權重。在文中我們說明了本問題為NP-hard問題。 本研究建構了一個以資料探勘為基礎的方法求解最高權重的作業指派及空間分配問題，為了比較本方法的求解績效，本研究運用過去文獻中提出的禁忌搜尋法來求解相同問題。最後實驗結果顯示本研究提出的方法可以效率的求得最佳解，而禁忌搜尋法只能求得近似最佳解，因而證明本方法較禁忌搜尋法優良。
並列摘要
We consider the problem of operation assignment and capacity allocation arising in a flexible manufacturing system. We assume that the operating time of Computer Numerically Controlled (CNC) machine and its capacity for tools are both limited. Besides, the weights of all operations are given. Our target is to find a good approach which can select proper operations and assign them together with their required tools to CNC machine so as to maximize the total weight of selected operations for FMSs. In this study, we show that the problem is NP-hard and develop a novel approach based on frequent itemset mining to solve the problem. For comparing the performance of our approach, we consider a heuristic and a tabu search algorithm presented by literature to solve the above problem. The results of our computational tests have revealed that our approach could produce optimal solutions very quickly. It shows our approach is better than the tabu search approach.