進階搜尋


 
系統識別號 U0026-2506201219355000
論文名稱(中文) 以拉式鬆弛法求解混合性商品裝配線排程問題-以台灣門鎖製造商為例
論文名稱(英文) A Lagrangian Relaxation Approach to the Mixed-product Assembly Line Sequencing Problem: A Case Study of a Door-Lock Company in Taiwan
校院名稱 成功大學
系所名稱(中) 交通管理學系碩博士班
系所名稱(英) Department of Transportation & Communication Management Science
學年度 100
學期 2
出版年 101
研究生(中文) 朱奕銘
研究生(英文) Yi-Ming Chu
電子信箱 julian.chu208@gmail.com
學號 r56991199
學位類別 碩士
語文別 英文
論文頁數 70頁
口試委員 口試委員-林珮珺
口試委員-陳秀華
指導教授-林東盈
中文關鍵字 混合性商品裝配線排程問題  整數規劃  拉氏鬆弛法  門鎖產業 
英文關鍵字 Mixed-product assembly line sequencing  Integer programming  Lagrangian relaxation heuristic  Door lock 
學科別分類
中文摘要 在各項產業中,客製化、多元化商品已成為許多企業的主要策略,本文探討台灣門鎖產業製造商於混和性商品裝配線上的指派與排程問題。門鎖產業的特性為每項產品所需要的零件種類繁多,製程複雜,故整體的製程安排與工作指派將直接影響企業的營運成本。本研究針對亞洲門鎖產業前三大的製造商-F公司作深入探討。以外銷為主的F公司主要產品為家用及商用門鎖、關門器等五金製品,在全時界各地都可以看見F公司相關系列產品,知名度相當高。本研究在需求與產能的限制之下,藉由建構一整數規劃之數學模式,以求解及探討製程安排與工作指派對整體存貨,人力以及延遲交貨等營運成本的影響。再以隱含式列舉演算法加快求解速度並改善求解效率,使此問題能夠擴大規模,更貼近實務需求。
英文摘要 This thesis investigates the mixed-product assembly line sequencing problem for a door lock manufacturing company in Taiwan. Companies in the door lock industry schedule their production processes to minimize their costs while meeting customer demand. The variance and diversity of lock components complicate the mixed-product assembly line sequencing problem and directly influence the material requirement planning and human resources costs. The assembly line sequencing problem of one of the largest ironware manufacturing companies in Asia, company F, is studied and an integer programming mathematical model with constraints on production lines, labor, warehouse capacity, and order fulfillment rates is formulated to minimize the total cost. A heuristic based on the Lagrangian relaxation principle is devised to solve this mixed-product assembly line sequencing problem. The efficiency of the proposed Lagrangian relaxation heuristic is evaluated by comparing its solutions with those obtained using CPLEX. The results show that the proposed heuristic solves the real-world problem almost 15 times faster than CPLEX in terms of CPU time, with equal solution quality. The salient results and practical issues involved in this unique problem are discussed in detail.
論文目次 Table of Contents
1. Introduction 1
1.1. Motivation 1
1.2. Purpose 1
1.3 Research Process 5
2. Literature Review 7
2.1 Assembly Line Sequencing Problem 7
2.2 Workforce Scheduling 11
2.3 Lagrangian Relaxation 15
3. Mathematical Formulation 19
3.1 Model Assumptions 19
3.2 Notation 21
3.3 Mathematical Model 23
4. Heuristic Design 27
4.1 LR Problem 27
4.2 LR Heuristic 34
4.3 Local Search 39
4.4 Subgradient Method 41
5. Computational Experiments 44
5.1 Computational Results 44
5.2 Sensitivity Analyses 49
5.2.1 Demand Fluctuation 50
5.2.2 Daily Demand Fulfillment 53
5.2.3 Delay Cost 56
5.2.4 Production Capacity 60
6. Conclusions and Future Research 62
7. Acknowledgements 64
References 65
參考文獻 1. Al-E-Hashem, S., Malekly, H., & Aryanezhad, M. B. (2011), "A multi-objective robust optimization model for multi-product multi-site aggregate production planning in a supply chain under uncertainty,"International Journal of Production Economics, 134(1) pp.28~42.
2. Ahuja, R. K. , Magnanti, T. L., Orlin, J. B. (1993) Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River.
3. Alsheddy, A., & Tsang, E. P. K. (2011), "Empowerment scheduling for a field workforce,"Journal of Scheduling, 14(6) pp.639~654.
4. Barutcuoglu, S., & Azizoglu, M. (2011), "Flexible assembly line design problem with fixed number of workstations,"International Journal of Production Research, 49(12) pp.3691~3714.
5. Bautista, J., & Cano, A. (2011), "Solving mixed model sequencing problem in assembly lines with serial workstations with work overload minimisation and interruption rules,"European Journal of Operational Research, 210(3) pp.495~513.
6. Bianco, L., & Caramia, M. (2011), "Minimizing the completion time of a project under resource constraints and feeding precedence relations: a Lagrangian relaxation based lower bound,"4or-a Quarterly Journal of Operations Research, 9(4) pp.371~389.
7. Boysen, N., Fliedner, M., & Scholl, A. (2007), "A classification of assembly line balancing problems,"European Journal of Operational Research, 183(2) pp.674~693.
8. Brucker, P., Qu, R., & Burke, E. (2011), "Personnel scheduling: Models and complexity,"European Journal of Operational Research, 210(3) pp.467~473.
9. Bukchin, J., Dar-El, E. M., & Rubinovitz, J. (2002), "Mixed model assembly line design in a make-to-order environment,"Computers & Industrial Engineering, 41(4) pp.405~421.
10. Bukchin, J., & Masin, M. (2004), "Multi-objective design of team oriented assembly systems,"European Journal of Operational Research, 156(2) pp.326~352.
11. Castillo, I., Joro, T., & Li, Y. Y. (2009), "Workforce scheduling with multiple objectives,"European Journal of Operational Research, 196(1) pp.162~170.
12. Celano, G., Costa, A., Fichera, S., & Perrone, G. (2004), "Human factor policy testing in the sequencing of manual mixed model assembly lines,"Computers & Operations Research, 31(1) pp.39~59.
13. Chan, F. T. S., Wang, Z., & Zhang, J. (2007), "A two-level hedging point policy for controlling a manufacturing system with time-delay, demand uncertainty and extra capacity,"European Journal of Operational Research, 176(3) pp.1528~1558.
14. Chen, C. T., & Huang, S. F. (2006), "Order-fulfillment ability analysis in the supply-chain system with fuzzy operation times,"International Journal of Production Economics, 101(1) pp.185~193.
15. Dematta, R. (1994), "A lagrangean decomposition solution to a single line multiproduct scheduling problem,"European Journal of Operational Research, 79(1) pp.25~37.
16. Ding, F. Y., & He, J. (2008), "A heuristic procedure for the automobile assembly-line sequencing problem considering multiple product options,"International Journal of Production Research, 46(20) pp.5827~5847.
17. Eliiyi, D. T., & Oezlen, M. (2008), "A Lagrangean relaxation approach for the mixed-model flow line sequencing problem,"Computers & Operations Research, 35(3) pp.933~943.
18. Frangioni, A., & Gallo, G. (1999), "A bundle type dual-ascent approach to linear multicommodity min-cost flow problems,"Informs Journal on Computing, 11(4) pp.370~393.
19. Fumero, F. (2001), "A modified subgradient algorithm for Lagrangean relaxation,"Computers & Operations Research, 28(1) pp.33~52.
20. Giard, V., & Jeunet, J. (2010), "Optimal sequencing of mixed models with sequence-dependent setups and utility workers on an assembly line,"International Journal of Production Economics, 123(2) pp.290~300.
21. Hallgren, M., & Olhager, J. (2006), "Differentiating manufacturing focus,"International Journal of Production Research, 44(18-19) pp.3863~3878.
22. Krishnamoorthy, M., Ernst, A. T., & Baatar, D. (2012), "Algorithms for large scale shift minimisation personnel task scheduling problems,"European Journal of Operational Research, 219(1) pp.34~48.
23. Li, H., & Womer, K. (2009), "Scheduling projects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm,"Journal of Scheduling, 12(3) pp.281~298.
24. Little, D., & Hemmings, A. (1994), "Automated assembly scheduling - a review,"Computer Integrated Manufacturing Systems, 7(1) pp.51~61.
25. Lovgren, R. H., & Racer, M. J. (2000), "Algorithms for mixed-model sequencing with due date restrictions,"European Journal of Operational Research, 120(2) pp.408~422.
26. Martins, A. X., Duhamel, C., Mahey, P., Saldanha, R. R., & de Souza, M. C. (2012), "Variable neighborhood descent with iterated local search for routing and wavelength assignment,"Computers & Operations Research, 39(9) pp.2133~2141.
27. Mohan, S. (2008), "Scheduling part-time personnel with availability restrictions and preferences to maximize employee satisfaction,"Mathematical and Computer Modelling, 48(11-12) pp.1806~1813.
28. Nazarian, E., Ko, J. H., & Wang, H. (2010), "Design of multi-product manufacturing lines with the consideration of product change dependent inter-task times, reduced changeover and machine flexibility,"Journal of Manufacturing Systems, 29(1) pp.35~46.
29. Rekiek, B., De Lit, P., & Delchambre, A. (2000), "Designing mixed-product assembly lines,"IEEE Transactions on Robotics and Automation, 16(3) pp.268~280.
30. Rizk, N., Martel, A., & Ramudhin, A. (2006), "A Lagrangean relaxation algorithm for multi-item lot-sizing problems with joint piecewise linear resource costs,"International Journal of Production Economics, 102(2) pp.344~357.
31. Russell, M. L., & Meller, R. D. (2003), "Cost and throughput modeling of manual and automated order fulfillment systems,"IIE Transactions, 35(7) pp.589~603.
32. Srivastava, B., & Chen, W. H. (1996), "Batching in production planning for flexible manufacturing systems,"International Journal of Production Economics, 43(2-3) pp.127~137.
33. Suhail, A. (1983), "Realiability and Optimization Considerations in A Conveyor-Paced Assembly Line System,"International Journal of Production Research, 21(5) pp.627~640.
34. Sural, H., Denizel, M., & Van Wassenhove, L. N. (2009), "Lagrangean relaxation based heuristics for lot sizing with setup times,"European Journal of Operational Research, 194(1) pp.51~63.
35. Then, X. S., & Tsai, F. C. (2008), "The optimal production plan under limited production capacity at any point in time,"Journal of the Operations Research Society of Japan, 51(1) pp.81~94.
36. Tseng, Y.-J., Kao, H.-T., & Huang, F.-Y. (2010), "Integrated assembly and disassembly sequence planning using a GA approach,"International Journal of Production Research, 48(20) pp.5991~6013.
37. Wang, X., & Cheng, T. C. E. (2009), "Logistics scheduling to minimize inventory and transport costs,"International Journal of Production Economics, 121(1) pp.266~273.
38. Zhao, X. B., & Ohno, K. (2000), "Properties of a sequencing problem for a mixed model assembly line with conveyor stoppages,"European Journal of Operational Research, 124(3) pp.560~570.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2014-07-03起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2014-07-03起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw