請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/29872
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳靜枝(Ching-Chin Chern) | |
dc.contributor.author | Ling-Chieh Kung | en |
dc.contributor.author | 孔令傑 | zh_TW |
dc.date.accessioned | 2021-06-13T01:22:39Z | - |
dc.date.available | 2007-07-23 | |
dc.date.copyright | 2007-07-23 | |
dc.date.issued | 2007 | |
dc.date.submitted | 2007-07-16 | |
dc.identifier.citation | [1] 吳宏祐,「先進規劃排程中考慮公平性與切單限制之主規劃排程演算法」,台灣大學資訊管理研究所碩士論文,民國94年。
[2] 林仲輝,「考慮共用料之供應鏈網路主規劃排程演算法」,台灣大學資訊管理研究所碩士論文,民國93年。 [3] 徐昆羿,「供應鏈網路之轉換:以最短路徑演算法解決廠商組合問題」,台灣大學資訊管理研究所碩士論文,民國89年。 [4] 傅光宇,「供應鍊管理之主規劃排程演算法:考慮整備成本與時間對決策之影響」,台灣大學資訊管理研究所碩士論文,民國94年。 [5] 黃慨郁,「供應鍊網路中考量回收機制之主規劃排程演算法」,台灣大學資訊管理研究所碩士論文,民國95年。 [6] Azaieza, M.N. and S.S.A. Sharifb, “A 0-1 Goal Programming Model for Nurse Scheduling,” Computers and Operations Research, Vol. 32, pp. 491-507, 2005. [7] Brah, S.A. and L.L. Loo, “Theory and Methodology: Heuristics for Scheduling in a Flow Shop with Multiple Processors,” European Journal of Operational Research, Vol. 113, pp. 113-122, 1999. [8] Chan W.T. and H. Hao, “An Application of Genetic Algorithm to Precast Production Scheduling,” Computers and Structures, Vol. 79, pp. 1605-1616, 2001. [9] Chen, S.Y., and C.C. Chern, “Shortest Path for a Supply Chain Network,” Proceedings of the 4th Asian Pacific Decision Sciences Institute Conference, Shanghai, China, pp. 579-582, 1999. [10] Chern, C.C. and C.H. Hsieh, “A Heuristic Master Planning Algorithm to Schedule Orders Under Due Date Requirements and Capacity Limits,” Proceedings of the 33rd Annual Meeting of Decision Science Institute, San Diego, California, USA, pp. 1842-1847, 2002. [11] Chern, C.C., and J.S. Hsieh, “A Heuristic Algorithm for Master Planning that Satisfies Multiple Objectives,” to be coming in Computers and Operatons Research, 2007. [12] Chern, C. C., and I. C. Yang, “A Heuristic Master Planning Algorithm for Supply Chains that Considers Substitutions and Commonalities,” Proceedings of the 36th Annual Meeting of Decision Science Institute, San Antonio, Texas, USA, pp. 25431-25436, 2006. [13] Chopra, S. and P. Meindl, Supply Chain Management: Strategy, Planning, and Operation, Prentice Hall, 2004. [14] Clark, A.R. “Optimization Approximations for Capacity Constrained Material Requirements Planning,” International Journal of Production Economics, Vol. 84, pp. 115-131, 2003. [15] Foster, T.A. “Supply Chain Top 100 Software Vendors,” Logistic Management, Vol. 42, pp. S3–S12, 2002. [16] Frederix, F. “An Extended Enterprise Planning Methodology for the Discrete Manufacturing Industry,” European Journal of Operation Research, Vol. 129, pp. 317-325, 2001. [17] Hall, L.A., “Approximability of Flow Shop Scheduling,” Mathematical Programming, Vol. 82, pp. 175-190, 1998. [18] Johnson, S.M., “Optimal Two and Three-Stage Production Schedules with Setup Times Included,” Naval Research Logistics Quarterly, Vol. 1, pp. 61-67, 1956. [19] Kallrath, J. and T.I. Maindl, Real Optimization with SAP® APO, Springer, 2006. [20] Kalpic, D., V. Mornar, and M. Maranovic, “Case Study Based On a Multi-period Multi-criteria Production Planning Model,” European Journal of Operational Research, Vol. 87, pp. 658-669, 1995. [21] Kreipl, S. and M. Pinedo, “Planning and Scheduling in Supply Chain: An Overview of Issues in Practice.” Production and Operations Management, Vol. 13, No. 1, pp. 77-29, 2004. [22] Lazansky J., Z. Kouba, V. Marık, and T. Vlcek, “Production Planning Systems with AI Philosophy.” Expert System with Applications, Vol. 8, No. 2, 255-262, 1995. [23] Lefrancois, P., L. Cloutier, and B. Montreuil, “An Agent-driven Approach to Design Factory Information Systems,” Computers in Industry, Vol. 32, pp. 197-217, 1996. [24] Mertins, K., M. Rabe, and W. Muller, “Designing a Computer-aided Manufacturing Systems Engineering Process,” Journal of Materials Processing Technology, Vol. 76, pp. 82-87, 1998. [25] Min, H. and G. Zhou, “Supply Chain Modeling: Past, Present and Future,” Computer and Industrial Engineering, Vol. 43, pp. 231-249, 2002. [26] Negenman, E.G., “Theory and Methodology: Local Search Algorithms for the Multiprocessor Flow Shop Scheduling Problem,” European Journal of Operational Research, Vol. 128, pp. 147-158, 2001. [27] Nyhuis F. “Controlling and Monitoring Functions as Supplement to MRPXX-systems,” Journal of Materials Processing Technology, Vol. 107, 2000, pp. 439-449. [28] Oguz, C., and M.F. Ercan, “Scheduling Multiprocessor Tasks in a Two-Stage Flow-Shop Environment,” Computers and Industrial Engineering, Vol. 33, No. 1-2, pp. 269-272, 1997. [29] Ozdamar, L., M.A. Bozyel, and S.I. Birbil. “A Hierarchical Decision Support System for Production Planning (with Case Study),” European Journal of Operational Research, Vol. 104, pp. 403-422, 1998. [30] Pinedo, M., Scheduling: Theory, Algorithms, and Systems, Prentice Hall, 2002. [31] Pinedo, M. and M. Singer, “A Shifting Bottleneck Heuristic for Minimizing the Total Weighted Tardiness in a Job Shop,” Naval Research Logistics, Vol. 46, pp. 1-12, 1999. [32] Reeves, C.R., editor, Modern Heuristic Techniques for Combinatorial Problems, Blackwell Scientific Publications, 1993. [33] Rohde, J., H. Meyr, and M. Wagner. “Die Supply Chain Planning Matrix,” PPS-Management, Vol. 5, pp. 10-15, 2000. [34] Simchi-Levi, D., P. Kaminsky, and E. Simchi-Levi, Designing and Managing the Supply Chain: Concepts, Strategies, and Case Studies, McGraw-Hill, 2001. [35] Sheikh, K. Manufacturing Resource Planning (MRP II) With an Introduction to ERP, SCM, and MRP, McGraw-Hill, 2003. [36] Stadtler, H. and C. Kilger, editors. Supply Chain Management and Advanced Planning: Concepts, Models, Software and Case Studies, Springer, 2005. [37] Tadei, R., M. Trubian, J. L. Avenda˜no, F. D. Croce, and G. Menga. “Aggregate Planning and Scheduling in the Food Industry: A Case Study,” European Journal of Operational Research, Vol. 87, pp. 564-573, 1995. [38] Tahmassebi, T. “Industrial Experience with a Mathematical-programming Based System for Factory Systems Planning / Scheduling,” Computers and Chemical Engineering, Vol. 20, pp. 1565-1570, 1996. [39] Tanev, I.T., T. Uozumi, and Y. Morotome, “Hybrid Evolutionary Algorithm-based Real-world Flexible Job Shop Scheduling Problem: Application Service Provider Approach,” Applied Soft Computing, Vol. 5, pp. 87-100, 2004. [40] Vercellis, C. “Multi-plant Production Planning in Capacitated Self-configuring Two-stage Serial Systems,” European Journal of Operational Research, Vol. 119, pp. 451-460, 1999. [41] Wolff, R.W., Stochastic Modeling and the Theory of Queues, Prentice Hall, 1989. [42] Yang, W. and L. Ching-Jong, “Survey of Scheduling Research Involving Setup Times,” International Journal of Systems Science, Vol. 30, No. 2, pp.143-155, 1999. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/29872 | - |
dc.description.abstract | 隨著商業活動日趨複雜,今日各企業必須與供應鏈內其他成員密切合作,以整合的方式追求供應鏈整體利益的最大化,才能提高自身競爭力與顧客滿意度,供應鏈管理也因此成為重要的研究課題。產生中長期、整合性的供應鏈規劃後,工廠必須更進一步產生短期、詳細的生產排程,才能配合整合性規劃。有別於不考慮順序的整合性規劃,工作間的先後順序影響短期生產排程的品質,使最佳化的困難度大幅提高。基於工廠規劃的重要性與困難度,本研究以工廠規劃問題的最佳化為研究目標。
本研究屬於先進規劃排程中之工廠規劃。主規劃產生供應鏈各成員中期的採購、生產與配銷計畫後,會對各工廠指定每期各商品的生產量,工廠規劃再依照產品結構、製造流程將各商品的需求轉換成工作。一個工作會被指定目標開始時間與目標結束時間,且含有多個階段;每個階段需要佔用特定工作站中任一機台若干時間,並且須在其先行階段產生足夠在製品後才能進行。因此,工廠規劃問題即為一複雜化之順序相關工作排程問題。 本研究對工廠規劃問題提出一多目標模型:最小化總延遲時間,最小化總流程時間,以及最小化總提前時間。工廠規劃問題雖可以混合整數規劃模型求得最佳解,但在規模龐大時,需要花費大量時間求解或完全無法求得解答,因此本研究提出ㄧ啟發性工廠規劃演算法,以求有效率地求得趨近最佳解之可行排程。 本啟發性工廠規劃演算法包含三階段:工作站排序、工作排序,以及工作排程。工作站排序會將工作站依工作負荷排序,以找出工廠中的瓶頸工作站。各工作依照其對瓶頸工作站的依賴度排序,依賴度愈高的工作優先權愈高。本研究提出一瓶頸導向排程演算法,完成工作排序後,將各工作依序排入工作行程。瓶頸導向排程演算法包含三個循環,第一循環將不切單下能不提前也不延後的工作排入,第二循環將切單後能不提前也不延後的工作排入,第三循環則將剩下的工作都排入。在排入一個工作的各階段時,皆以最小化此工作之流程時間的方式進行。 從三個角度出發的數值分析為本研究在時間與品質的成果提供佐證。情境分析包含十六種情境,交叉比較後能得出本研究適用的生產環境;效率分析證明本研究的求解時間和解品質與問題大小為線性關係;實例測試則驗證了本研究在實際製造產業中的可行性。這些數值分析顯示,本研究提出之工廠規劃演算法確實適於解決具一般性之工廠規劃問題。 | zh_TW |
dc.description.abstract | In resent years, supply chain management (SCM) has become an emerging issue discussed widely. Each member involved in supply chain operations makes efforts to reduce its costs and maximize its profits. This study belongs to the Factory Planning (FP) level in Advanced Planning and Scheduling (APS), a supply chain planning model. After the Master Planning (MP) level completes a mid-term plan for members involved in supply chain operations, each manufacturer is assigned a production quantity for each product in each mid-term period. According to the product structure and routing of each product, the FP level models the production by designing jobs. Each job consists of several stages while each stage occupies several short-term periods at a specific work center and can start to work only after its preceding stages produce enough WIP. An FP problem is thus a generalized sequence-dependent job scheduling problem with its sequence-dependent nature make it an NP-hard problem and increases the difficulty of optimization. According to the importance and difficulty, this study focuses on optimizing scheduling problems inside factories.
FP problems discussed in this study have three objectives: minimizing delay time, minimizing cycle time, and minimizing advance time. Although FP problems can be formulated by an MIP model, the number of binary variables is too large for the MIP model to solve FP problems in an acceptable time. Therefore, this study develops a heuristic FP algorithm, Heuristic Factory Planning Algorithm (HFPA), to find a near-optimal solution. HFPA contains three phases: work center sorting, job sorting, and job scheduling. HFPA first sorts work centers according to their work loads and finds the bottleneck work center. It then sorts jobs and gives higher priority to those jobs depending on the bottleneck work center more. After determining the order of jobs, the Bottleneck-Oriented Scheduling Algorithm (BOSA) is performed to schedule jobs one by one in three iterations. In the first iteration, it schedules jobs which can be scheduled in their preferred interval without splitting; in the second iteration, it schedules jobs which can be scheduled in their preferred interval with splitting; in the third iteration, it schedules all remaining jobs by advancing or delaying them. BOSA also minimize cycle time of this job when scheduling stages of a job. HFPA can produce near-optimal or optimal solutions when the capacity is loose, the production type is flow shop, the bottleneck is significant, and the stage structure is complex. Each of the first three factors dominates the fourth factor and amplifies each other. However, comparing to the exponentially-growing solving time of exact algorithms such as MIP, HFPA is a polynomial time algorithm and requires only very less time to solve an FP problem. Therefore, HFPA can also perform well when the size of problem increases such that the solving time and the objective values do not grow exponentially. In conclusion, HFPA is suitable for solving general FP problems effectively and efficiently. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T01:22:39Z (GMT). No. of bitstreams: 1 ntu-96-R94725008-1.pdf: 859501 bytes, checksum: bfaf6f2be365f53e4c2e5c9c88b96dee (MD5) Previous issue date: 2007 | en |
dc.description.tableofcontents | List of Figures vii
List of Tables ix Chapter 1 Introduction 1 1.1 Background and Motivation 1 1.2 Research Objectives 3 1.3 Research Scope and Limitation 5 Chapter 2 Literature Review 7 2.1 Supply Chain Management 7 2.2 Advanced Planning and Scheduling 8 2.3 Factory Planning 10 2.3.1 Importance and Difficulties of Factory Planning 10 2.3.2 System-Oriented Approaches 10 2.3.3 Algorithm-Oriented Approaches 11 2.4 Methodologies for Solving Planning Problems 12 2.4.1 Linear Programming and Mixed Integer Programming 12 2.4.2 Genetic Algorithm 13 2.4.3 Lagrangean Relaxation 14 2.4.4 Other Heuristic Algorithms 15 Chapter 3 Problem Description and Formulation 17 3.1 Problem Description 17 3.1.1 Planning Time Buckets 17 3.1.2 Factory and Work Center 18 3.1.3 Job 18 3.1.4 Stage Structure 20 3.1.5 Stages in Sequence and Stages in Pipeline 21 3.1.6 Scheduling 22 3.1.7 Setup Time 23 3.2 Assumptions 24 3.3 Factory Planning 25 3.3.1 Notations 26 3.3.2 Constraints 27 3.3.3 Objective Functions 31 3.3.4 Complexity Analysis 33 3.4 Factory Planning with Continuity 33 3.4.1 Notations 33 3.4.2 Constraints 36 3.4.3 Objective Functions 38 3.4.4 Complexity Analysis 38 3.5 Limitations of Mixed Integer Programming Models 39 Chapter 4 Heuristic Factory Planning Algorithm (HFPA) 40 4.1 Work Center Sorting (P1) 42 4.2 Job Sorting (P2) 45 4.3 Bottleneck-Oriented Scheduling Algorithm (P3) 49 4.3.1 The All-Job Level of BOSA 50 4.3.2 The One-Job Level of BOSA 51 4.3.3 Combining the Two Levels of BOSA 56 4.3.4 Example of Scheduling the Sequential FP Problem 58 4.3.5 Example of Scheduling the Complex FP Problem 61 4.4 HFPA with Continuity and HFPA for Rolling Schedule 63 4.4.1 HFPA with Continuity 63 4.4.2 HFPA for Rolling Schedule 65 4.5 Complexity Analysis 66 Chapter 5 System Illustration and Model Analysis 68 5.1 System Illustration 68 5.1.1 Data Structure 69 5.1.2 System Prototype 70 5.2 Scenario Design 73 5.2.1 Factor Description 73 5.2.2 Dimensions of Scenario Design 75 5.2.3 Description of Scenarios 76 5.3 Planning Example 79 5.3.2 Planning by HFPA 82 5.3.2 Planning by MIP 82 5.3.3 Planning by FIFO, EDD, and LPT 82 5.3.4 Comparison of All Methods 83 5.4 Computational Analysis 84 5.4.1 Results of the Sixteen Scenarios 84 5.4.2 Solution Quality 85 5.4.3 Solving Time 92 5.4.4 Conclusion 94 5.5 Efficiency Analysis 94 5.6 Testing on a Real-World Case 96 5.7 Analysis of Differences from Optimal Solutions 99 Chapter 6 Conclusion and Future Work 102 6.1 Conclusion 102 6.2 Future Work 103 Bibliography 105 Appendix A Scenarios of Computational Analysis 108 Appendix B Planning Results of Scenarios 113 | |
dc.language.iso | en | |
dc.title | 供應鏈管理之工廠規劃演算法 | zh_TW |
dc.title | A Heuristic Factory Planning Algorithm for Supply Chain Management | en |
dc.type | Thesis | |
dc.date.schoolyear | 95-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 蔣明晃(Ming-Huang Chiang),許鉅秉(Jiuh-Biing Sheu),林我聰(Woo-Tsong Lin),陳炳宇(Bing-Yu Chen) | |
dc.subject.keyword | 供應鏈管理,先進規劃排程,多目標最佳化,工廠規劃,生產規劃排程,啟發式演算法, | zh_TW |
dc.subject.keyword | Supply Chain Management,Advanced Planning and Scheduling,Multi-objective Optimization,Factory Planning,Production Planning and Scheduling,Heuristic Algorithm, | en |
dc.relation.page | 126 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2007-07-18 | |
dc.contributor.author-college | 管理學院 | zh_TW |
dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-96-1.pdf 目前未授權公開取用 | 839.36 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。