《国立虎尾科技大学鼓励性研究计画成果报告》由会员分享，可在线阅读，更多相关《国立虎尾科技大学鼓励性研究计画成果报告（9页珍藏版）》请在金锄头文库上搜索。
1、 1國立虎尾科技大學鼓勵性研究計畫成果報告 計畫名稱：基因演算法在航空公司機隊維修排程最佳化之應用 Application of the Genetic Algorithm on the Airline Maintenance Scheduling Optimization 計畫類類別：個別型計畫 計畫編號：TCS93251 執行期間：93/08/01 94/07/31 執行單位：國立虎尾科技大學 飛機工程系 計畫主持人：劉 昇 祥 助理教授 本成果報告包括以下應繳交之附件： 赴國外出差或研習心得報告一份 赴大陸地區出差或研習心得報告一份 出席國際學術會議心得報告及發表之論文各一份 國際合作研
2、究計畫國外研究報告書一份 中 華 民 國 9 4 年 08 月 3 1 日 2國立虎尾科技大學鼓勵性研究計畫成果報告 基因演算法在航空公司機隊維修排程最佳化之應用 基因演算法在航空公司機隊維修排程最佳化之應用 Application of the Genetic Algorithm on the Airline Maintenance Scheduling Optimization 計畫編號：TCS93251 執行期限：93 年 08 月 01 日至 94 年 07 月 31 日 主持人：劉昇祥 助理教授 國立虎尾科技大學 飛機工程系 一、中、英文摘要一、中、英文摘要 飛機定期維修排程問題，係
3、在一設定的排程 時間範圍內，依據民航法規要求、原製造廠規範、 及其累計飛行時數，安排飛機進廠維修。在實務 上，由於航空公司機隊飛機數量眾多，如何配合 公司營運需求及棚場容量限制，在不違反法規， 避免超點營運下拿捏得宜，規劃定期維護時機， 以盡量提高其機隊使用率，降低操作成本，是航 空公司所關心的重點。 本研究主要目的在發展一個以基因演算法則 為基礎的啟發式演算法，以航空公司觀點，在棚 場容量限制下，探討機隊進廠維修的最佳時程。 在數學模式中目標函數的設定上，在於提高整體 機隊之使用率。研究結果經由實務案例，與實際 航空公司修護管制人員人工排程結果相驗證。比 較分析排程結果，確能在合理的計算時間
4、內，獲 致較佳排程結果，符合航空業界需求。 關鍵詞關鍵詞：維修排程、 基因演算法、啟發式演算法、 目標函數 Abstract Airline fleet maintenance problems are defined as, within a predetermined time domain in the future, arranging the due time and durations of the aircrafts for their scheduled maintenance checks in accordance with requirements by civil av
5、iation regulations, original manufacturers criteria and accumulated aircraft flight hours and cycles. In practice, an airline usually possess a fleet that have various number of aircrafts. The key concern is to arrange an optimal maintenance schedule for every aircraft of the fleet, under hangar cap
6、acity restriction and operation needs without overdue, to maximize their utilization rates, thus minimizing their operation costs. In this study, a genetic algorithm based on heuristics is developed to solve fleet maintenance scheduling problems to meet airline needs. Under the restrictions of hanga
7、r capacities, an optimal schedule is built. The objective function of the mathematical model is to increase the utilization rate of the fleet. The constructed mathematical model is then applied in a practical airline case. Computational results are compared with those made by airline maintenance con
8、trollers. Through comparison on the resultant schedules, it is shown that current model can give better result in acceptable computational time and meet airline demands. Keywords: Maintenance scheduling problems, Genetic algorithm, Heuristics, Objective function 二、緣由與目的 二、緣由與目的 在航空公司營運成本中，飛機維修成本約佔飛
9、機總使用成本之 18-25%，其中飛機（含零組件） 修護又佔飛機總維修成本約 69% （其餘 31%為航材 庫存成本），佔有相當大比例1，如何在維持飛航 安全及飛機可靠性的前提下，作適當的維修排程， 以提高飛機可用率、降低修護成本，提升公司獲 利，是每個航空公司所關心的問題。 航空公司飛機進廠維修排程問題存在已久，航 機維護排程問題，係指在一預設的時域內，依據民 航法規要求、原製造廠規範、及各架飛機累計之飛 行時數/起降次數，安排在適當的時間進廠維護。妥 善的進廠排程，除了賦予的單位維修成本降低，更 有利於確保機隊正常調度、消耗性器材庫存管理及 人力資源管理等好處。實務上，許多國籍航空公司 的
10、機隊進廠維修排程，是由專業修護管制人員以人 工的方式完成，然而由於航空公司機隊飛機數量眾 多，排程工作除需同時考量機隊數量、棚廠限制、 人力資源、法規要求與修護工作種類等複雜的限制 條件外，還需力求符合營運部門的機隊需求，綜合 來說，這些人工管制方式不但費時耗力，且受限於 限制因素太多，很難去作縝密的長期維護排程規 劃；且排程結果亦僅為一組可行的方案，很難從經 濟層面評估排程結果的良窳。 相對而言，如何有效率找出機隊各飛機之最佳 進廠時機，建立可行且長程的排程，對航空修護單 位存在其需要性與重要性。良好的飛機維護排程除 了 可 以 預 防 因 為 人 為 疏 忽 而 發 生 飛 機 超 點 （
11、Overdue）營運的違規事件，進廠排程時若能在 操作成本（包含營運及維修成本）最小化的考量3下，同時考量排程的合理性等，將可使維修棚廠以 及機隊的營運效益達到最佳狀況。 有關航空方面排程管理的研究起源甚早，由於 在實務上，航空公司機隊管理的諸多需求中，如航 路 設 計 (fleet routing) 、 班 表 規 劃 (flight scheduling)、飛機指派(fleet assignment)、組員管理 (crew scheduling) 、 維 護 排 程 （ maintenance scheduling） ，乃至維護工作指派 (Job assignment)、 維護人力規劃（m
12、anpower planning）等，從學術的 角度而言，個別的問題均深具研究價值，而當其中 數種需求須合併考量時，研究難度更具挑戰性，因 此吸引國內外許多學者投入相關研究。 航 路 設 計 與 班 表 規 劃 (fleet routing & scheduling)的相關研究是早期學者主要的投入領 領，在這方面的研究包括 Levin 2以整數規劃 （Integer Programming）的數學模式，搭配分歧界 限法(Branch and Bound)演算法，以及 Desaulniers 3 以具時間限制之多工流量管制(time-constrained multi-commodity net
13、work flow formulation) 法求解 等；在飛機指派(fleet assignment)問題方面，則有包 括 Hane et al. 4, Abara 5及 Subramanian 6等，以 線性規劃模式搭配不同演算法研究；相較於於其他 領域的研究，單就維護排程方面的研究較少，大多 都是僅針對短期維護搭配其它需求排程，如 Feo & Bard 7 以 混 合 整 數 規 劃 （ Mixed Integer Programming）的數學模式研究含短期維護排程之 班表規劃，Hane et al. 4 以線性規劃（Linear Programming）的數學模式搭配不同演算法研究含
14、 短期維護排程之飛機指派問題。結論均表示，當排 程項目數量龐大時，以線性規劃（或整數規劃）的 數學模式求解最佳化排程，無論搭配何種演算法， 都會面臨求解困難，或是計算時間過長的缺點。其 它與維護排程之相關研究如文獻8-11所示。 如同前述，航機維護排程問題在數學模式中目 標函數的建立上，一般而言並非十分困難，但由於 這類最佳化問題的性質，多屬於複雜度甚高的 NP-Hard 整數規劃問題，當變數數量龐大時，在求 最佳解時會有求解困難或計算效率不彰的缺點。由 於此類大型問題多係屬應用型研究，在實務上重視 在計算效率與最佳解之間取得平衡，並不特別強調 最佳解，因此目前研究人員廣泛應用各種啟發式演 算
15、法，諸如模擬退火法 （Simulated Annealing） 12、 禁制蒐尋法 ( Tabu Search)13、基因演算法 (Genetic Algorithm) 14 等 ， 或 使 用 動 態 規 劃 （Dynamic Programming） 15、人工智慧 （Artificial Intelligence）16等方法，來改善計算效率。 綜上文獻回顧，本研究的目的在於針對目前演 算法應用於大型排程問題的限制及飛機定期維護 工作的特性，發展一個以基因演算法為基礎的排程 分析，研究其使用於航機維護排程問題時之效能， 作為後續研究的基礎，以應用於航空公司工程管理 決策支援系統之建構。 三
16、、結果與討論三、結果與討論 如圖一所示，飛機維護排程問題，可以定義 為在一預設的時域範圍 T 內，將 N 項工作在不同 時間點，安排在 M 個處理器執行的規劃，在這 N 項工作裏，其中有些工作的安排可能有時間順序的 關係。以數學規劃的觀點而言，維護排程最佳化進 行的方式，是設定一個目標函數，在滿足所有資源 限制的條件下，使目標函數極大化或極小化，求取 在此一目標函數值下，各項工作執行的最佳優先順 序。 不同目標函數的選擇，排程結果會有不同的 特性。一般而言，考量的因素不外乎從飛機使用 率、棚場使用率、維護成本，或整體操作成本（含 維護及營運成本）等觀點，來設定目標函數，端視 排程管理人員的優先考量因素而定，沒有孰是孰 非。由於本研究探討的問題特性同時涉及機隊之 長、中、短期排程，經過審慎評估，認為在目標函 數的選取上，若純以飛機使用率為考量標準
