Multi-resource Generalized Assignment Problem－Fleet Scheduling Problem

[[abstract]]製造業在滿足市場需求的前提下，必須善加利用資源以降低成本，進而提高競爭優勢。本研究考量在多產品種類的生產環境下，管理者進行工作指派時須考量主要與其他輔助設備的可用時數、原物料供應量、各種生產方式之資源消耗情況，因此製造資源之分配是否恰當與整體效益有密不可分的關係，管理者進一步希望在長期運作下，能平均使用主要資源，以減少機件耗損與維持最大產能。本研究針對上述之多資源指派問題進行定義，依資源平準與批量分割概念建構一多資源工作指派之數學規劃模式，並提出計算簡便之啟發式解法，依資源供應量與資源需求量多寡分別對機器設備與產品訂單進行處理排序，且考慮多資源限制下相互進行指派，讓擁有較多資源數量機器設備先行生產資源需求量較多之產品訂單，使所有資源使用消耗情況達到平準控制，避免長期使用下發生部分資源超支使用或庫存過多情況發生。 本研究利用不同問題範例進行實驗測試，求解大型問題時，啟發式解法之求解品質與最佳解雖然有差距，但是在時效性上有絕對優勢，而且以長期多次工作指派之情境來考量，追求單次求解品質並非是最優先目的，在長期運作下，啟發式解法仍可獲得相當理想的結果。本研究以戰鬥機任務派飛為例，進行十年的長期模擬評估，在滿足產品訂單（飛行課目）需求長期指派下，運用啟發式解法確實能使機器設備時數（飛機時數）資料得以平準收歛，且輔助資源（飛機結構點強度）也能獲得有效控制，增加未來指派彈性，降低維修成本並使戰機達到經濟使用年限。[[abstract]]The manufacturing industry has to utilize resources in order to lower costs while meeting market demand, and then improve the competitive advantage. Under the environment of production of many product categories, the paper considers that the management must to consider the consumptive condition of equipment available hours、material demand and auxiliary resources. So the distribution of producible resources and whole benefit has closely relationship. The management hopes to balance the main resources during the long-term application, and reduces the mechanics wastage to keep optimal production capacity. The paper applies resource leveling/smoothing problem and lot splitting to define a MRGAP mathematical programming model, and to establish the algorithm which to calculate simply. The permutation of Equipments and product apply in accordance with resource supply and demand, and constraints of multi-resources limitation to assign. Let Equipment which has more resources products order which has more resources demand is a top priority. The consumptive condition of all resources can balance, and avoid resources uses not enough or stocks too much during the long-term application. This research uses different problem example to experiment. When solving the large-scale problem, the algorithm has absolute advantage in solve time even if it has the difference with the optimal solution. The quality of single assignment for algorithm is not the first purpose. To assign many times during the long- term plan still obtain perfect result. The research also conducts a 10-years simulation based on the Fleet Scheduling Problem. The simulation result shows that our algorithm not only meets the product order demand（mission requirements）consistently but also effectively controls the available equipment（flight） hours and the auxiliary resources（airframe degradation）throughout the time span. It will increase assignable flexibility, and the reduction of the maintain costs to meet the longer economical life