透過您的圖書館登入
IP:54.159.116.24
  • 學位論文

在不同鬆緊度限制式範圍下一般化指派問題求解效能影響分析

The Analysis of Solution Efficiency under Different Constraint Tightness for GAP

指導教授 : 林逾先
若您是本文的作者,可授權文章由華藝線上圖書館中協助推廣。

摘要


真實世界中,許多決策制定問題均包含有一般化指派問題(Generalized assignment problem, GAP)的本質。一般化指派問題已證實屬於NP-hard之組合最佳化問題;除問題規模外,限制式之鬆緊度亦是影響問題複雜度的重要因子。 本研究以未執行過之大型專案,其主要多項關鍵工作須指派給專案執行者去完成,且追求總花費成本最小化之情境,建構小型一般化指派問題模式進行研究。 在實證分析方面,針對五種不同比例一般限制式上、下界限差異值範圍,均在鬆緊度30%至70%之間設計17種不同等級鬆緊度,且各設計10組例題(合計850個測試例題),藉由應用整數線性規劃、分枝界限法,以LINGO軟體之求解迭代平均值做為衡量求解效能之指標,並將不同鬆緊度之求解效能實證結果,以迴歸分析方法進行分析。 研究結果發現:(1)當鬆緊度接近50%時,將可以最少的求解迭代值得到全域最佳解;(2)當範圍愈大時,鬆緊度愈緊或愈鬆時,求解效能較為費時;且不同鬆緊度對求解效能之影響,以二次多項式迴歸模式進行預測之能力愈佳;(3)當範圍愈小時,鬆緊度程度為緊或鬆時之求解效能,與程度為中等時之求解效能,則逐漸無明顯差異變化之趨勢。 本研究可供管理實務界於降低問題複雜度,及供學術研究界於發展新的求解方法之參考。

並列摘要


In the real world, many decision-making problems are related to the Generalized Assignment Problem(GAP). GAP is a combinatorial problem that belongs to NP-hard. In addition to problem scale, constraint tightness is also a significant factor that affects problem complexity. This research constructs GAP model for a large project where there are some critical jobs to be executed. These jobs are to be assigned to the available agents to complete with minimum cost objectivity. In the experimental evaluation analysis, this research designs five ranges with different proportion between lower and upper limits. A total of 17 different tightness levels ranging from 30% to 70% are designed at each range to generate 10 instances (A total of 850 test problem are generated).These test problems are solved using LINGO software by recording the number of iterations needed during the branch and bound procedure before reaching the optimal solution. The results of this computational experiment reveal the followings. (1)It needs less iterations to find global optimum when tightness close to 50%. (2)With the increase of large proportion range, more solution efficiency is needed when the tightness is in between medium to tight or the tightness is too loose. Second order polynomial regression model can be used to predict the relationship between constraint tightness and solution efficiency. (3)With the decrease of proportion range, solution efficiency becomes less significant under various tightness. The findings of this research can provide adequate suggestions to business and research field.

參考文獻


[7] 蔣宗哲,半導體製造系統之多目標排程,博士論文,國立台灣大學資訊工程研究所,2007。
[9] M. Albareda-Sambola, M. H. van der Vlerk and E. Fernández,“Exact solutions to a class of stochastic generalized assignment problems,”European Journal of Operational Research, vol. 173, no.2, 2006, pp. 465-487.
[10] J. W. Ohlmann and J. C. Bean, “Resource-constrained management of heterogeneous assets with stochastic deterioration,” European Journal of Operational Research, vol. 199, 2009, pp. 198-208.
[11] E. Y. H. Lin, “Multiple choice programming:a state-of-the-art review,” International Transactions in Operational Research, vol. 1, no.4, 1994, pp.409-421.
[13] H. Müller-Merbach,“Heuristic procedures for solving combinatorial optimization problems in transportation,”Transportation Research, vol. 10, no. 6, 1976, pp. 377-378.

延伸閱讀