隨著全球航空運輸業愈趨發達，飛航安全的議題也愈來愈受到矚目，再加上歷史上有多次飛安事故皆由維修人員的維修疏失所導致，因此進行有效的維修人員管理乃一重要課題。本研究的研究對象為隨機需求下之停機線維修人員之人力指派，其中我們考量了兩種隨機因素，任一值勤班次之待修航機架次及每架待修航機所需之人工小時，首先我們採用兩階段隨機規劃法(Two-Stage Stochastic Programming with Recourse)建構一相對以往確定性模型更具有彈性與穩定性的指派模式，後再比較套裝軟體Gurobi、整數L-shaped方法及拉氏鬆弛演算法之求解效率，實證研究結果顯示整數L-shaped方法可大幅提升模型求解的速度，拉氏鬆弛演算法則沒有預期的效果。整數L-shaped方法甚至能求解出Gurobi無法於合理時間內求解出的問題，在這三種方法中，整數L-shaped方法更好。

With the increasing development of the global aviation industry, the issue of aviation safety has become increasingly more important, there have been many flight safety accidents due to negligence on the part of aircraft maintenance staff; therefore, effective crew management is also an important issue. Our objective is manpower assignments for line maintenance under stochastic demand, taking into account two types of stochastic factors: the number of aircraft needing repair and the man hours required for each aircraft in each shift. First, we use two-stage stochastic programming with recourse to construct a more flexible and stable scheduling model for line maintenance. After that, the efficiency of Gurobi, the integer L-shaped method, and the Lagrangian relaxation technique are compared. The empirical results showed that the integer L-shaped method can greatly improve the speed at which the solution is obtained, and that the Lagrangian relaxation technique did not have the expected effect. The integer L-shaped method can even solve a problem that Gurobi can't solve in a reasonable time. Among these three methods, the integer L-shaped method is better.

1.Benders, J.F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numer. Math., 4(1), 238-252.

2.Bertsekas, D.P., A. Nedić, and A.E. Ozdaglar. (2003). Convex Analysis and Optimization. Athena Scientific.

3.Birge, J.R. (1982). The value of the stochastic solution in stochastic linear programs with fixed recourse. Mathematical Programming, 24(1), 314-325.

4.Biesinger, Hu, and Raidl (2016). An Integer L-shaped Method for the Generalized Vehicle Routing Problem with Stochastic Demands. Electronic Notes in Discrete Mathematics, 52, 245-252.

5.Castillo-Villar, K. K., S. Eksioglu, and M. Taherkhorsandi. (2017). Integrating biomass quality variability in stochastic supply chain modeling and optimization for large-scale biofuel production. Journal of Cleaner Production, 149, 904-918.

6.Chao, C.W. (2013). The study on airline maintenance assignment-taking Kaohsiung International Airport as example. M.S. Thesis: Chang Jung Christian University.

7.Chen, C.-H., S. Yan, and M. Chen. (2010). Short-term manpower planning for MRT carriage maintenance under mixed deterministic and stochastic demands. Annals of Operations Research, 181(1), 67-88.

8.Chen, Y.-Y. and H.-Y. Fan. (2015). An Application of Stochastic Programming in Solving Capacity Allocation and Migration Planning Problem under Uncertainty. Mathematical Problems in Engineering, 2015, 16.

9.Cui, W., W. Yan, W.-J. Lee, X. Zhao, Z. Ren, and C. Wang. (2017). A two-stage stochastic programming model for optimal reactive power dispatch with high penetration level of wind generation. Journal of Electrical Engineering & Technology, 12(1), 53-63.

10.Cunha, P.S.A., F.M.P. Raupp, and F. Oliveira. (2017). A two-stage stochastic programming model for periodic replenishment control system under demand uncertainty. Computers & Industrial Engineering, 107, 313-326.

11.De Bruecker, P., J. Van den Bergh, J. Beliën, and E. Demeulemeester. (2015). A model enhancement heuristic for building robust aircraft maintenance personnel rosters with stochastic constraints. European Journal of Operational Research, 246(2), 661-673.

12.Dillon, M., F. Oliveira, and B. Abbasi. (2017). A two-stage stochastic programming model for inventory management in the blood supply chain. International Journal of Production Economics, 187, 27-41.

13.Eajal, A.A., M.F. Shaaban, K. Ponnambalam, and E.F. El-Saadany. (2016). Stochastic Centralized Dispatch Scheme for AC/DC Hybrid Smart Distribution Systems. IEEE Transactions on Sustainable Energy, 7(3), 1046-1059.

14.Escudero, L.F., A. Garín, M. Merino, and G. Pérez. (2007). The value of the stochastic solution in multistage problems. TOP, 15(1), 48-64.

15.Gans, N., H. Shen, Y.-P. Zhou, N. Korolev, A. McCord, and H. Ristock. (2015). Parametric Forecasting and Stochastic Programming Models for Call-Center Workforce Scheduling. Manufacturing & Service Operations Management, 17(4), 571-588.

16.Heijden, K.v.d. (1996). Scenarios: The Art of Strategic Conversation. Chichester: John Wiley & Sons.

17.Heilporn, G., Cordeau, J.-F., and Laporte, G. (2011). An integer L-shaped algorithm for the Dial-a-Ride Problem with stochastic customer delays. Discrete Applied Mathematics, 159(9), 883-895.

18.Held, M. and R. M. Karp (1971). The traveling-salesman problem and minimum spanning trees: Part II. Mathematical Programming, 1(1), 6-25.

19.Held, M., P. Wolfe and H.P. Crowder (1974). Validation of subgradient optimization. Mathematical Programming, 6(1), 62-88.

20.IATA. (2018). Annual Review. from: https://www.iata.org/publications/Pages/annual-review.aspx.

21.Jabarnejad, M. and J. Valenzuela. (2016). Optimal investment plan for dynamic thermal rating using benders decomposition. European Journal of Operational Research, 248(3), 917-929.

22.Karamyar, F., J. Sadeghi, and M.M. Yazdi. (2018). A Benders decomposition for the location-allocation and scheduling model in a healthcare system regarding robust optimization. Neural Computing and Applications, 29(10), 873-886.

23.Laporte, G. and F.V. Louveaux. (1993). The integer L-shaped method for stochastic integer programs with complete recourse. Operations Research Letters, 13(3), 133-142.

24.Laporte, G., F. Louveaux, L. Van Hamme (2002). An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research, 50(3), 415-423.

25.Liu, C.C. (2013). Optimal work shift scheduling and fatigue minimization. M.S. Thesis: National Cheng Kung University.

26.Louveaux, F. and J.R. Birge. (1997). Introduction to Stochastic Programming. New York: Springer-Verlag.

27.Louveaux, F. and Salazar-González. (2018). Exact approach for the vehicle routing problem with stochastic demands and preventive returns. Transportation Science, 52(6), 1463-1478.

28.Marufuzzaman, S.D. Eksioglu, and Y. Huang. (2014). Two-stage stochastic programming supply chain model for biodiesel production via wastewater treatment. Computers & Operations Research, 49, 1-17.

29.Miller-Hooks, E., Zhang, X., and Faturechi, R. (2012). Measuring and maximizing resilience of freight transportation networks. Computers & Operations Research, 39(7), 1633-1643.

30.Mohammadi, S., S. Soleymani, and B. Mozafari. (2014). Scenario-based stochastic operation management of MicroGrid including Wind, Photovoltaic, Micro-Turbine, Fuel Cell and Energy Storage Devices. International Journal of Electrical Power & Energy Systems, 54, 525-535.

31.Oğuz, M., T. Bektaş, and J.A. Bennell. (2018). Multicommodity flows and Benders decomposition for restricted continuous location problems. European Journal of Operational Research, 266(3), 851-863.

32.Papavasiliou, A., Y. Mou, L. Cambier, and D. Scieur. (2018). Application of Stochastic Dual Dynamic Programming to the Real-Time Dispatch of Storage Under Renewable Supply Uncertainty. IEEE Transactions on Sustainable Energy, 9(2), 547-558.

33.Parisio, A. and C. Neil Jones. (2015). A two-stage stochastic programming approach to employee scheduling in retail outlets with uncertain demand. Omega, 53, 97-103.

34.Qadrdan, M., J. Wu, N. Jenkins, and J. Ekanayake. (2014). Operating Strategies for a GB Integrated Gas and Electricity Network Considering the Uncertainty in Wind Power Forecasts. IEEE Transactions on Sustainable Energy, 5(1), 128-138.

35.Rahmaniani, R., T.G. Crainic, M. Gendreau, and W. Rei. (2017). The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259(3), 801-817.

36.Rawls, C. G. and M. A. Turnquist. (2010). Pre-positioning of emergency supplies for disaster response. Transportation Research Part B: Methodological, 44(4), 521-534.

37.Rezaee, A., F. Dehghanian, B. Fahimnia, and B. Beamon. (2017). Green supply chain network design with stochastic demand and carbon price. Annals of Operations Research, 250(2), 463-485.

38.Salavati-Khoshghalb, Gendreau, Jabali, and Rei. (2017). An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy. European Journal of Operational Research, 273(1), 175-189.

39.Soares, J., B. Canizes, M.A.F. Ghazvini, Z. Vale, and G.K. Venayagamoorthy. (2017). Two-Stage Stochastic Model Using Benders’ Decomposition for Large-Scale Energy Resource Management in Smart Grids. IEEE Transactions on Industry Applications, 53(6), 5905-5914.

40.Sungur, B. and Y. Yavuz. (2015). Assembly line balancing with hierarchical worker assignment. Journal of Manufacturing Systems, 37, 290-298.

41.Su, Y.L. (2010). The two-stage stochastic programming model for a green production planning with stochastic EUAs price. M.S. Thesis: National Cheng Kung University.

42.Tang, C.H. and Hsu I.S. (2016). A manpower supply model for aircraft line maintenance under stochastic personnel demands. Journal of the Chinese Institute of Transportation, Vol. 28(No. 3), pp. 267-293.

43.Van Slyke and Wets. (1969). L-shaped linear programs with applications to optimal control and stochastic programming. SIAM Journal on Applied Mathematics, 17, 638-663.

44.Wu, Y. T. (2012). Physical distribution network planning for supply chain in uncertain demand. M.S. Thesis: National Kaohsiung First University of Science and Technology.

45.Yang, T.-H., S. Yan, and H.-H. Chen. (2003). An airline maintenance manpower planning model with flexible strategies. Journal of Air Transport Management, 9(4), 233-239.

46.Yang, T.H. and Lai Y.W. (2005). Airline personnel assignment for short-term maintenance plan. Transportation Planning Journal, Vol. 34(No. 4), pp. 525-548.