臺灣博碩士論文加值系統

航空工業為一具戰略性的高科技產業，乃整體工業發展之重要指標。面對今日激烈的全球競爭，各國莫不戮力提昇其水準。而發動機的維修排程，則為此中一重要的課題。
就當前的趨勢以觀，企業獲利之來源，多賴有效率的營運管理。如何整合現有的技術、人力，並輔以相關之配套措施，誠為攸關企業存亡的關鍵因素之一。在有限的資源下，一有效率的發動機維修排程，將可降低企業之營運成本，並可提升其維修能量。
在本研究中，我們討論了發動機維修作業中的拆解過程。我們將其視為一零工式生產排程問題，並且發展了此課題的混合整數規劃(mixed integer programming, MIP)數學模式。為了測試本模式之實用性，我們針對A引擎維修公司內部的拆解過程予以測試。
在此情況下，模式的求解結果，除了能夠縮短A公司引擎拆解的完成時間外，還可以極小化系統所需之人力。此求解結果兼具效能與品質兩方面之功用。另一方面，我們尚建議A公司一個新的排程策略，依據此策略所得到的排程結果，將可為A公司提升更多的營運效能。

　　The developing of aviation industry, a strategic industry with advance technology, is the key point for the whole industry. In order to be globally competitive, many countries are eager to find out innovative ways to improve the development efficiency. The engine maintenance schedule is one of the concerned issues.
　　Nowsdays the competence of an enterprise is partly shifted to the capability of aligning the operations management. It is important to effectively integrate the current technologies and human resources while aided with assistance from the related coordinating measures. Under the presumption of finite resources, an efficient engine maintenance schedule for a company can reduce the operation cost and expand the business.
　　In this research, we discuss the engine disassembly process, which is one of the tasks of engine maintenance process. We consider the engine disassembly process that could be viewed as a job shop scheduling problem. We develop a mixed integer programming (MIP) model for engine disassembly process. To illustrate the applicability of the MIP model, we present a case study on the engine disassembly process taken from an engine maintenance company (company A).
　　We prove that the solutions of current situation for company A not only can speed up the finish time for engine disassembly, also can minimize worker demand. The results are satisfactory in terms of both efficiency and quality of the solution. In addition, we suggest company A a policy in order to promote the efficiency. The solution of modified situation can bring much more benefit for company A.

CHAPTER 1 INTRODUCTION 1
1.1 RESEARCH MOTIVATIONS 1
1.2 BRIEFING OF THE CURRENT OPERATION 1
1.3 RESEARCH OBJECTIVES 2
1.4 RESEARCH SCOPE 3
1.5 ORGANIZATION 3
CHAPTER 2 LITERATURE REVIEW 4
2.1 REVIEW OF JOB SHOP SCHEDULING PROBLEM WITH GENERAL FORM 5
2.2 REVIEW OF JOB SHOP SCHEDULING PROBLEM WITH RELAXED FORM 8
2.3 SUMMARY 9
CHAPTER 3 REVIEW OF CURRENT STATUS 11
3.1 ENGINE DISASSEMBLY PROCESS 11
3.2 OPERATION DATA FOR COMPANY A 15
3.2.1Standard disassembly process time 15
3.2.2 Definition of working hour and assignment times 16
3.2.3 Machine number and worker demand 17
CHAPTER 4 A MIXED INTEGER PROGRAMMING MODEL FOR ENGINE DISASSEMBLY PROCESS 19
4.1 A MIXED INTEGER PROGRAMMING FORMULATION FOR SUB-MODEL 1 20
4.2 A MIXED INTEGER PROGRAMMING FORMULATION FOR SUB-MODEL 2 24
CHAPTER 5 SOLUTIONS FOR THE ENGINE DISASSEMBLY PROCESS 27
5.1 SOLUTIONS FOR ONE-ENGINE SITUATION WITH 2 SHIFTS A DAY POLICY 29
5.1.1 The earliest disassembly time for one-engine 29
5.1.2 The minimum worker demand for system 32
5.1.3 Summary of solutions for one-engine situation with 2 shifts a day policy 32
5.2 SOLUTIONS FOR ONE-ENGINE SITUATION WITH 8 SHIFTS A DAY POLICY 33
5.2.1 The earliest disassembly time for one-engine 34
5.2.2 The minimum worker demand for system 34
5.2.3 Summary of solutions for one-engine situation with 8 shifts a day policy 35
5.3 SOLUTIONS FOR MULTI-ENGINE SITUATION WITH NON-OVERLAP AND 2 SHIFTS A DAY POLICY 36
5.3.1 The earliest disassembly time for engines 36
5.3.2 The minimum worker demand for system 36
5.3.3 Summary of solutions for multi-engine situation with non-overlap and 2 shifts a day policy 40
5.4 SOLUTIONS FOR MULTI-ENGINE SITUATION WITH NON-OVERLAP AND 8 SHIFTS A DAY POLICY 41
5.4.1 The earliest disassembly time for engines 41
5.4.2 The minimum worker demand for system 42
5.4.3 Summary of solutions for multi-engine situation with non-overlap and 8 shifts a day policy 45
5.5 SOLUTIONS FOR MULTI-ENGINE SITUATION WITH OVERLAP AND 2 SHIFTS A DAY POLICY 46
5.5.1 The earliest disassembly time for engines 46
5.5.2 The minimum worker demand for system 52
5.5.3 Summary of solutions for multi-engine situation with overlap and 2 shifts a day policy 55
5.6 SOLUTIONS FOR MULTI-ENGINE SITUATION WITH OVERLAP AND 8 SHIFTS A DAY POLICY 56
5.6.1 The earliest disassembly time for engines 56
5.6.2 The minimum worker demand for system 61
5.6.3 Summary of solutions for multi-engine situation with overlap and 8 shifts a day policy 64
5.7 SUMMARY OF SOLUTIONS FOR THIS CHAPTER 65
CHAPTER 6 CONCLUSIONS AND SUGGESTIONS 70
6.1 CONCLUSIONS 70
6.2 SUGGESTIONS 71
REFERENCES 73

1. Beasley, J. E. and Cao, B., “A Tree Search Algorithm for the Crew Scheduling Problem”, European Journal of Operational Research, Vol. 94, No. 3, pp. 517-526, 1996.
2. Chang, J., “Optimization of aviation pilot scheduling”, master thesis, National Central University, Taoyuan, Taiwan, R. O. C., 1996. (in Chinese)
3. Using the CPLEX Callable Library, CPLEX Optimization, Inc., 1998.
4. Weng, W. D., “The Rostering of Crew for Airline Operations: An Equitability System Approach”, master thesis, National Chiao Tung University, Hsinchu, Taiwan, R. O. C., 1997. (in Chinese)
5. Chen, Y. C., “The planning of airline maintenance manpower supply”, master thesis, National Central University, Taoyuan, Taiwan, R. O. C., 2001. (in Chinese)
6. Han, C. Y., “ Analysis of Genetic Algorithms for Job Shop Scheduling Problem with Set-up Time and Time Interval Due-date”, master thesis, Yuan Ze University, Taoyuan, Taiwan, R. O. C., 2001. (in Chinese)
7. Bertsimas, D. and Gamarnik, D., “Asymptotically Optimal Algorithms for Job Shop Scheduling and Packet Routing”, Journal of Algorithms, Vol. 33, No. 2, pp. 296-318, 1999.
8. Nuijten, W. P. M. and Aarts, E. H. L., “A computational study of constraint satisfaction for multiple capacitated job shop scheduling”, European Journal of Operational Research, Vol. 90, No. 2, pp. 269-284, 1996.
9. Tarantilis, C. D. and Kiranoudis, C. T., “A list-based threshold accepting method for job shop scheduling problems”, International Journal of Production Economics, Vol. 77, No. 2, pp. 159-171, 2002.
10. Sabuncuoglu, I. and Bayiz, M., “Job shop scheduling with beam search”, European Journal of Operational Research, Vol.118, No. 2, pp. 390-412, 1999.
11. Kumar, N. S. Hemant and Srinivasan, G., “A genetic algorithm for job shop scheduling - A case study”, Computers in Industry, Vol. 31, No. 2, pp. 155-160, 1996.
12. Jansen, K. and Porkolab, L., “Polynomial time approximation schemes for general multiprocessor job shop scheduling”, Journal of Algorithms, Vol. 45, No. 2, pp. 167-191, 2002.
13. Carlier, J. and Pison, E., “An algorithm for solving the job-shop problem”, Management Science, Vol. 35, pp. 167-176, 1989.
14. Lenstra, J., “Sequencing by enumerative method”, Technical Report, Mathematical Center Tract 69, Mathematisch Centrum, 1976.
15. Agnetis, A. and Oriolo, G., “The Machine Duplication Problem in a Job Shop with Two Jobs”, International Transactions in Operational Research, Vol. 2, No. 1, pp. 45-60, 1995.
16. Chang, Y. C., "Job Shop Scheduling with Due Date and Utilization Consideration”, master thesis, National Yunlin University of Science & Technology, Yunlin, Taiwan, R. O. C., 1998. (in Chinese)
17. Hsu, J. L., “Impact of Lot-Streaming in Job Shop Production System”, master thesis, Da-Yeh University, Changhua, Taiwan, R. O. C., 2000. (in Chinese)
18. Hsiao, Y. M., “Application of Genetic Algorithm in Job-Shop Scheduling”, master thesis, Yuan Ze University, Taoyuan, Taiwan, R. O. C., 2000. (in Chinese)
19. Yang, F. C., “Ant Colony Optimization Based Extended Job Shop Scheduler”, master thesis, Nation Taiwan University, Taipei, Taiwan, R. O. C., 2002. (in Chinese)
20. Ho, C. H., “Research on the Hybrid Genetic Algorithm in Re-entrant Job Shop Problem ”, master thesis, Nation Taiwan University of Science & Technology, Taipei, Taiwan, R. O. C., 2000. (in Chinese)
21. Steinhöfel, K., Albrecht, A. and Wong, C.K., “ Fast parallel heuristics for the job shop scheduling problem”, Computers and Operations Research, Vol. 29, pp. 151-169, 2002.
22. Verhoeven, “ Tabu search for resource-constrained scheduling”, European Journal of Operational Research, Vol. 106, pp. 266-276, 1998.
23. Lenstra J. K., Rinnooy Kan A. H. G. and Brucker P., “Complexity of machine scheduling problem”, Annals of Discrete Mathematics, Vol. 1,pp.343-362, 1977.
24. Gray M. R. and Johnson D. S., “ Computers and Intractability: A Guide to the Theory of NP-Completeness”, Freeman, San Francisco, 1979.
25. Zäpfel, G. and Wasner, M., “ A heuristic solution concept for a generalized machine sequencing problem with an application to radiator manufacturing”, International Journal of Production Economics, Vol. 68, pp. 199-213, 2000.
26. Mascis, A. and Pacciarelli, D., “Job-shop scheduling with blocking and no-wait constraints”, European Journal of Operational Research, Vol. 143, No. 3, pp. 498-517, 2002.
27. Huang, H. C., “A Hybrid Genetic Algorithm for No-Wait Job Shop Problems”, master thesis, Nation Taiwan University of Science & Technology, Taipei, Taiwan, R. O. C., 2002. (in Chinese)