以改良式基因演算法求解最小化的自動導引車系統週期時間

Abstract

自動導引車(Automated Guided Vehicle, AGV)是當今彈性製造系統(Flexible Manufacturing System, FMS)和自動化倉儲系統中很重要的作業設施。在生產的流程中，有效加工時間佔的比例通常不大， 相對花費在運送、等待的時間則佔有相當大的比例，甚至某些研究結果指出工件搬運成本佔總加工 成本可能高達20%到50%。因此，本研究針對生產系統中最常見的單迴圈(single loop) AGV 系統，在 AGV 車輛數已知的條件下，以ES (early start)為派遣法則(dispatching policy)，發展一出以最小化生產 週期，也就是最大化其有效產出(throughput)，為目標的數學模式。基於決策的複雜性，在規模稍微 擴大之後，本問題即無法找出精確解，本模式計劃發展一改良式基因演算法(Genetic Algorithm, GA) 來求解最佳的工件序列(job sequence)。演算法設計的最重要構想在利用線性代數中的排列矩陣 (permutation matrix)觀念，來改善GA 演算法中交配過程的的運算效率。此外，並將在運輸領域應用 相當普遍(如動態車輛調度、航機排班等問題)的時空網路(time-space network)，與生產設施的搬運問 題相結合，發展出一混合整數規劃 (Mixed Integer Programming, MIP)，藉以找出小型問題的最佳解及 中大型問題的目標值下限，來驗證所發展的改良式基因演算法是否有效。

AGV (Automated Guided Vehicle) is an important system for today’s manufacturing and warehousing operation. In the manufacturing process, the time spent on the actual operation of the machines is usually not very long. On the other hand, a significant portion of the whole process time is consumed for delivery and waiting. According to the results of some previous researches, the portion can be as high as 20% to 50%. Therefore, this study considers the most common single-loop AGV system and develop a mathematical model with minimizing the production cycle time (i.e., maximizing the production throughput) as the objective, given the predetermined AGV fleet size and the ES (early start) dispatching policy. Due to the complexity of the decisions, it is impossible to find the exact solution for the problems with large size. Thus, this study plans to design a modified genetic algorithm (GA) to determine a suitable job sequence. The key idea for designing the solution algorithm is to make use of the concept of permutation matrix from linear algebra to improve the computational efficiency of the crossover in GA. In addition, this study integrates the concept of time-space network, a technique widely-used in the field of transportation (such as dynamic vehicle re-location/dispatching and fleet management), with the delivery in a manufacturing system to develop a mixed integer programming (MIP) model. This MIP can be used to find the optimal solution of the small-size problems and is expected to derive the lower bound of the objective function value for the problems with medium and large size, so as to verify the effectiveness of the developed solution algorithm.