以改良式基因演算法求解最小化的自動導引車系統週期時間
摘要
自動導引車(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),藉以找出小型問題的最佳解及
中大型問題的目標值下限,來驗證所發展的改良式基因演算法是否有效。
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),藉以找出小型問題的最佳解及
中大型問題的目標值下限,來驗證所發展的改良式基因演算法是否有效。