以基因演算法產生工件序列來最小化自動導引車(AGV)之週期時間

Abstract

自動導引車(Automated Guided Vehicle, AGV)是當今彈性製造系統(Flexible Manufacturing System, FMS)和自動化倉儲系統中很重要的作業設施。在生產的流程中，有效加工時間佔的比例通常不大，相對花費在運送、等待的時間則佔有相當大的比例，甚至某些研究結果指出工件搬運成本佔總加工成本可能高達20%到50%。 因此，本研究針對生產系統中常見的單迴圈(single loop) AGV系統，在AGV車輛數為1台，加工機台為2台的條件下，以ES (early start)為派遣法則(dispatching policy)，發展出一以最小化生產週期，也就是最大化其有效產出(throughput)，為目標的數學模式。實務上，最小工件集合(Minimal Job Set, MJS)的數目均大於50，通常以最佳解(optimal solution)的精確求解方法(exact-solution method)較不可行，因而本模式以基因演算法(Genetic Algorithm, GA)來產生工件序列(job sequence)，以處理問MJS數目在100以內的實際狀況。 演算法設計的主要目標，除了求解品質外，求解效率亦需兼顧在一設定時間，以供決策者迅速做出必要的決定。此外，並將在運輸領域應用相當普遍(如動態車輛調度、航機排班等問題)的時空網路(time-space network)，與生產設施的搬運問題相結合，發展出一混合整數規劃 (Mixed Integer Programming, MIP)，藉由Lingo 8.0以找出小型問題的最佳解及放鬆整數限制後的目標值下限，來驗證所提出的基因演算法是否有效。數值測試的結果發現求解品質誤差範圍均在1%內，而求解時間則在1分鐘內。在未來研究可以本研究為基礎，延伸問題的規模，即處理更多AGV及機台數量之問題。

AGV (Automated Guided Vehicle) plays an important role for today’s manufacturing and warehousing systems. In a manufacturing process, the time actually spent on the machines is sometimes not very long; on the other hand, a significant portion of the whole process time is consumed for transporting and waiting. Therefore, this study considers a common single-loop AGV system and develops a mathematical model aiming to minimize the production cycle time (i.e., to maximize the production throughput), given the predetermined ES (Early Start) AGV dispatching policy. Due to the complexity of the decisions, it is impossible to find the optimal solution for the problems with large size. Thus, this study designs a genetic algorithm to determine the sequence for the jobs in an MJS (Minimal Job Set) so as to reduce the AGV cycle time. This study also develops a mixed integer programming (MIP) model, which can find the optimal solution of small-size problems. In addition, its linear program (LP) relaxation is found to be a very tight lower bound. In order to verify the effectiveness of the developed solution algorithm, a series of test problems are designed for a system with two machines and one AGV. Based on the result of the numerical experiment, it is found the solution generated by the heuristic algorithm is very close to the optimal solution, normally within 1% in terms of the objective function value. Besides, the solution quality is not sensitive to the problem size, and the computation time is acceptable for the realistic operation in the field.