臺灣博碩士論文加值系統

在電腦整合製造中，有效的專案開發管理與生產系統自動化排程是至關重要的。在本論文中針對不同的專案管理與生產排程案例，提出了一個可描述具不同目標函數與拘束條件的排程問題之整合理論。基因演算法(genetic algorithm)因其強健性與有效性，已被廣泛應用於各式排程問題中。大部分生產排程研究所提出的染色體編碼方法主要針對執行權重進行優化。然而許多實際專案、生產排程中所遭遇的問題需要更進一步去分析、優化。本論文提出之排程整合理論，除了將不同專案、生產排程之特色統一描述外，以基因演算法做為優化工具，並針對不同排程問題之特殊性質進行彈性編碼。
本論文中以三個不同性質的專案、生產排程來驗證整合理論之可行性。第一個案例為彈性資源投入之專案排程。藉由基因演算法編碼來優化資源投入，可大幅改善專案執行資源使用效率，並且在資源有限的拘束條件下，亦可縮短專案執行總時間。第二個案例為一封閉烤爐自動生產。由於此案例硬體設施上的限制，必須考量設備的預留空間，以避免生產流程鎖死的發生。另外生產亦需確保一定的產品品質，故本排程整合理論將基因演算法之編碼同時決定生產的執行權重以及可容許過度加工之時間，並將設備預留時間設定為表定生產時間加上容許過度加工以及運輸時間。如此可確保一定的生產品質，並且可使設備應用上更彈性，生產時間可進一步地縮短。最後一個案例為多目標之生產排程，並且需另外考量設備基準一致性以及按照工時長短來安排日夜輪班。本排程整合理論亦可處理此複雜排程特性，並且在縮短總工時、符合交單期限、降低生產中斷次數此三項目標函數表現上，皆比傳統生產上慣用之派遣法則為優。藉由上述三個不同性質的排程案例，可表現出此整合理論之彈性、可適用性與有效性。

Efficient project and production scheduling are necessary for the development of computer integrated manufacturing (CIM). A formulation based on genetic algorithm (GA) is proposed to describe the objective function and constraint equations of project and production scheduling problem. Effectiveness of the formulation is validated by numerical results. In the first example, project scheduling for activity duration and resource input can optimize the makespan and achieve resource leveling simultaneously. Numerical results show that the formulation can improve the resource utilization compared with the fuzzy Gantt chart method. In the 2nd example, the formulation is applied to production scheduling problem with considering quality and deadlock. Numerical results show that the formulation can optimize the makespan while meeting the quality requirement and preventing the process deadlock. The last example is production scheduling with multi-objective function of minimum makespan, order delivery delay and processing interruption. The constraint equations consist of sequence relationship, resource limitation, machine consistency, and day/night shift. Numerical results show that the formulation is better than the dispatching rules such as longest processing time (LPT) and shortest processing time (SPT) in either single objective function or multi-objective function. The proposed formulation is shown effective in project and production scheduling problems in CIM.

Abstract i
Contents ii
List of Tables iv
List of Figures v
Nomenclature vii
Chapter I Introduction 1
1.1 Motivation 1
1.2 Literature Review 2
1.2.1 Computer integrated manufacturing 2
1.2.2 Project planning and production scheduling 4
1.2.3 Genetic algorithm application to scheduling 6
1.3 Outline 8
Chapter II Formulation and Scope in Computer Integrated Manufacturing 10
2.1 Formulation of Developing CIM 10
2.2 CIM Project Scope 13
2.3 Genetic Algorithm 15
Chapter III Project Scheduling with Resource Constraints and Fuzzy Gantt Chart 27
3.1 Introduction 27
3.2 Estimation of Resource Requirements 29
3.3 Project Scheduling with Resource Constraints 30
3.4 Summary 34
Chapter IV Production Scheduling with Quality and Deadlock Constraints 40
4.1 Introduction 40
4.2 Scheduling Problems 41
4.3 Application of GA for Production Scheduling 44
4.4. Numerical Results 46
4.5 Summary 50
Chapter V Multi-Objective Production Scheduling by Genetic Algorithm 57
5.1 Introduction 57
5.2 Multi-Objective Production Scheduling. 58
5.3 Multi-Objectives Scheduling by Genetic Algorithm 60
5.4 Results and Discussion 63
5.5 Summary 64
Chapter VI Summary and Conclusions 71
References 74

Adibi, M. A., Zandieh, M., and Amiri, M., “Multi-Objective Scheduling of Dynamic Job Shop Using Variable Neighborhood Search, Expert Systems with Applications, Vol. 37, No. 1, pp. 282-287, 2010.
Akhshabi, M., “A Genetic Algorithm for Solving a New Mathematical Model of Single Machine Scheduling with Three Criteria, Australian Journal of Basic and Applied Sciences, Vol. 4, No. 11, pp. 5564-5570, 2010.
Araz, O. U., “Real-Time Controlled Multi-objective Scheduling Through ANNs and Fuzzy Inference Systems: The Case of DRC Manufacturing, Lecture Notes in Computer Science, Vol. 4490, pp. 973-976, 2007.
Aydin, M. E. and Oztemel, E., “Dynamic Job-Shop Scheduling Using Reinforcement Learning Agents, Robotics and Autonomous Systems, Vol. 33, No. 2-3, pp. 169-178, 2000.
Bierwirth, C., “A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms, OR Spektrum, Vol. 17, pp. 87-92, 1995.
Brucker, P., Drexl, A., Mohring, R., Neumann, K., and Pesch, E., “Resource-Constrained Project Scheduling: Notation, Classification, Models, and Methods, European Journal of Operational Research, Vol. 112, No. 1, pp. 3-41, 1999.
Cavory, G., Dupas, R., and Goncalves, G., “A Genetic Approach to Solving the Problem of Cyclic Job Shop Scheduling with Linear Constraints, European Journal of Operational Research, Vol. 161, No. 1, pp. 498-517, 2005.
Chen, H. X. and Luh, P. B., “An Alternative Framework to Lagrangian Relaxation Approach for Job Shop Scheduling, European Journal of Operational Research, Vol. 149, No. 3, pp. 499-512, 2003.
Chen, J. C., Wu, C. C., Chen, C. W., and Chen, K. H., “Flexible Job Shop Scheduling with Parallel Machines Using Genetic Algorithm and Grouping Genetic Algorithm, Expert Systems with Applications, Vol. 39, No. 11, pp. 10016-10021, 2012.
Chen, S. H., Chang, C. K., and Kuo, C. L., “Optimal Scheduling in Color Filter Manufacturing, Journal of the Chinese Institute of Industrial Engineers, Vol. 22, No. 4, pp. 301-308, 2005.
Cheng, R., Gen, M., and Tsujimura, Y., “A Tutorial Survey of Job-Shop Scheduling Problems Using Genetic Algorithms—I. Representation, Computers ＆ Industrial Engineering, Vol. 30, No. 4, pp. 983-997, 1996.
Chiang, T. C., Shen, Y. S., and Fu, L. C., “Adaptive Lot/Equipment Matching Strategy and GA Based Approach Optimized Dispatching and Scheduling in a Wafer Probe Center, in Proc 2004 IEEE International Conference on Robotics and Automation, pp. 3125-3130, April 2004.
Cooper, D. F., “Heuristics for Scheduling Resource-Constrained Projects: An Experimental Investigation, Management Science, Vol. 22, No. 11, pp. 1186-1194, 1976.
Croce, F. D., Tadei, R., and Volta, G., “A Genetic Algorithm for the Job Shop Problem, Computers ＆ Operations Research, Vol. 22, No. 1, pp. 15-24, 1995.
Driessei, R. and Mönch, L., “Simulation Framework for Complex Manufacturing Systems with Automated Material Handling, Proceedings of the 2007 Winter Simulation Conference, pp. 1713-1721, December 2007.
Ebben, M. J. R., Heijden, M. C., and Harten, A, “Dynamic Transport Scheduling under Multiple Resource Constraints, European Journal of Operational Research, Vol. 167, No. 2, pp. 320-335, December 2005.
Elazouni, A. M. and Gab-Allah, A. A., “Finance-Based Scheduling of Construction Projects Using Integer Programming, Journal of Construction Engineering and Management-ASCE, Vol. 130, No. 1, pp. 15-24, 2004.
Fathi, H. and Afshar, A., “GA-based Multi-objective Optimization of Finance-based Construction Project Scheduling, Journal of Civil Engineering, Vol. 14, No. 5, pp. 627-638, September 2010.
Filho, U. M. S., Vieira, D. R., and Pécora, J. E., “Simulation of the Handling of Pre-Painted Coils in a Brazilian Steel Industry, The 8th International Conference on Logistics and SCM Research, October 2010.
Fung, I. W. H., Huang, C., and Tam, C. M., “Application of GA Optimization for Solving Precedent Relationship Problem in Project Scheduling, Mathematical and Computer Modeling, Vol. 57, No. 9-10, pp. 2067-2081, 2013.
Gebauer, H. and Fischer, T., “Exploring Service Needs in the Chinese Manufacturing Industry, Chinese Management Study, Vol. 3, No. 2, pp. 143-154, 2009.
Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, New York, 1989.
Gunasekaran, A., “Implementation of Computer-Integrated Manufacturing: a Survey of Integration and Adaptability Issues, Int. J. of Computer Integrated Manufacturing, vol. 10, no. 1-4, pp. 266-280, 1997.
Gunasekaran, A., Marri, H. B., and Lee, B., “Design and Implementation of Computer Integrated Manufacturing in Small and Medium-Sized Enterprise: A Case Study, Int. J. of Advanced Manufacturing Technology, Vol. 16, pp. 46-54, 2000.
Hao, X. and Lin, L., “Job Shop Rescheduling by Using Multi-objective Genetic Algorithm, 2010 40th International Conference on Computers and Industrial Engineering, Kitakyushu, July 2010.
Hartmann, S., “A Self-Adapting Genetic Algorithm for Project Scheduling under Resource Constraints, Naval Research Logistics, Vol. 49, No. 5, pp. 433-448, 2002.
Hinterding, R., “Gaussian Mutation and Self-adaption for Numeric Genetic Algorithms, IEEE International Conference on Evolutionary Computation, pp. 384-389, 1995.
Ho, N. B. and Tay, J. C., “Evolving Dispatching Rules for Solving the Flexible Job-Shop Problem, Evolutionary Computation, The 2005 IEEE Congress on, Vol. 3, pp. 2848-2855, 2005.
Hoitomt, D. J., Luh, P. B., and Pattipati, K. R., “A Practical Approach to Job-Shop Scheduling Problems, IEEE Transactions on Robotics and Automation, Vol. 9, No. 1, pp. 1-13, 1993.
Ipsilandis, P. G., “Multiobjective Linear Programming Model for Scheduling Linear Repetitive Projects, Journal of Construction Engineering and Management-ASCE, Vol. 133, No. 6, pp. 417-424, 2007.
Jarboui, B., Damak, N., Siarry, P., and Rebai, A., “A Combinatorial Particle Swarm Optimization for Solving Multi-Mode Resource-Constrained Project Scheduling Problems, Applied Mathematics and Computation, Vol. 195, No. 1, pp. 299-308, 2008.
Jain, A. S. and Meeran, S., “Deterministic Job-Shop Scheduling: Past, Present and Future, European Journal of Operational Research, Vol. 113, pp. 390-434, 1999.
Jiang, G. and Shi, J., “Exact Algorithm for Solving Project Scheduling Problems under Multiple Resource Constraints, Journal of Construction Engineering and Management, Vol. 131, No. 9, pp. 986-992, 2005.
Käschel, J., Teich, T, Köbernik, G., and Meier, B., “Algorithm for the Job Shop Scheduling Problem - A Comparison of Different Methods, European Symposium on Intelligent Techniques, Greece, Jun 1999.
Ke, H. and Liu, B. D., “Project Scheduling Problem with Mixed Uncertainty of Randomness and Fuzziness, European Journal of Operational Research, Vol. 183, No. 1, pp. 135-147, 2007.
Kibira, D. and McLean, C., “Virtual Reality Simulation of a Mechanical Assembly Production Line, Proceedings of the 2002 Winter Simulation Conference, pp. 1130-1137, December 2002.
Kim, J. L. and Ellis, R. D., “Permutation-Based Elitist Genetic Algorithm for Optimization of Large-Sized Resource-Constrained Project Scheduling, Journal of Construction Engineering and Management, Vol. 134, No. 11, pp. 904-913, November 2008.
Kumar, N. S. H. and Srinivasan, G., “A Genetic Algorithm for Job Shop Scheduling – A Case Study, Computers in Industry, Vol. 31, pp. 155-160, 1996.
Laborie, P., “Algorithms for Propagating Resource Constraints in AI Planning and Scheduling: Existing Approaches and New Results, Artificial Intelligence, Vol. 143, pp. 151-188, 2003.
Larrañaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., and Dizdarevic, S., “Genetic Algorithms for the Traveling Salesman Problem: A Review of Representations and Operators, Artificial Intelligence Review, Vol. 13, pp. 129-170, 1999.
Liao, D. Y. and Wang, C. N., “Differentiated Preemptive Dispatching for Automatic Materials Handling Services in 300 mm Semiconductor Foundry, Int. J. of Advanced Manufacturing Technology, vol. 29, pp. 890-896, 2006.
Liu, H., Jiang, Z., and Fung, R. Y. K., “Performance Modeling, Real-Time Dispatching and Simulation of Wafer Fabrication Systems Using Timed Extended Object-Oriented Petri Nets, Computers ＆ Industrial Engineering, Vol. 56, pp. 121-137, 2009.
Liu, Y., “Different Initial Solution Generators in Genetic Algorithms for Solving the Probabilistic Traveling Salesman Problem, Applied Mathematics and Computation, Vol. 216, pp. 125-137, 2010.
Liu, Y. C., “Buffer Sizing Technique for Fuzzy Critical Chain Scheduling, Proc. of 2nd Intl. Conf. on Uncertainty Theo., pp. 5-10, Tibet, August 2011.
Liu, Y. C., Sun, S. H., Yang, S. M., and Chuang, C. Y., “Application of Genetic Algorithm in Production Scheduling: A Case Study on the Food Processing Business, INFORMATION - An International Interdisciplinary Journal, November 2012(Accepted).
Liu, Y. C., Yang, S. M., and Chuang, C. Y., “Application of Genetic Algorithm and Fuzzy Gantt Chart to Project Scheduling with Resource Constraints, Journal of Aeronautics Astronautics and Aviation, March 2013(Submitted).
Liu, Y. C., Yang, S. M., and Lin, Y. T., “Fuzzy Finish Time Modeling for Project Scheduling, Journal of Zhejiang University-Science A, Vol. 11, No. 12, pp. 946-952, 2010.
Long, L. D. and Ohsato, A., “A Genetic Algorithm-based Method for Scheduling Repetitive Construction Projects, Automation in Construction, Vol. 18, No. 4, pp. 499-511, July 2009.
Lu, M. and Lam, H., “Critical Path Scheduling under Resource Calendar Constraints, Journal of Construction Engineering and Management, Vol. 134, No. 1, pp. 25-31, 2008.
Marvel, J. H. and Standridge, C. R., “A Simulation-Enhances Lean Design Process, J. of Industrial Engineering and Management, Vol. 2, no. 1, pp. 90-113, 2009.
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.
Mauguiere, P., Billaut, J. C., and Bouquard, J. L., “New Single Machine and Job-Shop Scheduling Problems with Availability Constraints, Journal of Scheduling, Vol. 8, No. 3, pp. 211-231, 2005.
Merkle, D., Middendorf, M., and Schmeck, H., “Ant Colony Optimization for Resource-Constrained Project Scheduling, IEEE Transactions on Evolutionary Computation, Vol. 6, No. 4, pp. 333-346, 2002.
Mirabi, M., “A new Meta-heuristic for Scheduling of Single Machine Problem with Sequence-Dependent Setups, Australian Journal of Basic and Applied Sciences, Vol. 4, No. 2, pp. 247-256, 2010.
Moon, C., Kim, J. S., and Gen, M., “Advanced Planning and Scheduling Based on Precedence and Resource Constraints for e-Plant Chain, International Journal of Production Research, Vol. 42, No. 15, pp. 2941-2955, 2004.
Ramzan, M., Jaffar, A., Iqbal, A., Anwar, S., Rauf, A., and Shahid, A. A., “Project Scheduling Conflict Identification and Resolution Using Genetic Algorithms (GA), Telecommunication Systems, Vol. 51, No. 2-3, pp. 167-175, 2012.
Schuster, C. J. and Framinan, J. M., “Approximative Procedures for No-Wait Job Shop Scheduling, Operations Research Letters, Vol. 31, No. 4, pp. 308-318, 2003.
Sha, D. Y., Lin, J. T., and Yang, C. J., “The Evaluation of Search Range Assignment in 300 mm Automated Material Handling System (AMHS), Int. J. of Advanced Manufacturing Technology, vol. 35, pp. 697-710, 2008.
Shao, X., Li, X., Gao, L., and Zhang, C., “Integration of Process Planning and Scheduling—A Modified Genetic Algorithm-Based Approach, Computers ＆ Operation Research, Vol. 36, 2082-2096, 2009.
Shin J. G. and Sohn S. J., “Evolutionary Simulation-Based-Design (ESBD) Methodology for Large Computer Integrated Manufacturing Systems, Int. J. of Computer Integrated Manufacturing, Vol. 14, No. 4, pp. 385-398, 2001.
Shukla, S. K., Son, Y. J., and Tiwari, M. K., “Fuzzy-Based Adaptive Sample-Sort Simulated Annealing for Resource-Constrained Project Scheduling, International Journal of Advanced Manufacturing Technology, Vol. 36, No. 9-10, pp. 982-995, 2008.
Srikanth, R., George, R., Warsi, N., Prabhu, D., Petry, F. E., and Buckles, B. P., “A Variable-length Genetic Algorithm for Clustering and Classification, Pattern Recognition Letters, Vol. 16, pp. 789-800, 1995.
Wang, L. and Zheng, D. Z., “An Effective Hybrid Optimization Strategy for Job-Shop Scheduling Problems, Computers ＆ Operations Research, Vol. 28, No. 6, pp. 585-596, 2001.
Xia, W. J. and Wu, Z. M., “An Effective Hybrid Optimization Approach for Multi-Objective Flexible Job-Shop Scheduling Problems, Computers ＆ Industrial Engineering, Vol. 48, No. 2, pp. 409-425, 2005.
Yamada, T. and Nakano, R., “A Genetic Algorithm Applicable ro Large-Scale Job-Shop Problems, Proceeding of: Parallel Problem Solving from Nature, pp. 283-292, 1992.
Zhang, H. and Gen, M., “Multistage-Based Genetic Algorithm for Flexible Job-Shop Scheduling Problem, Journal of Complexity International, Vol. 11, pp. 223-232, 2005.
Zhou, Y. and Chuan, K. B., “Computer-Integrated Manufacturing in China, A Report of Industrial Field Survey, Int. J. of Operations ＆ Production Management, Vol.22, No. 3, pp. 271-288, 2002.
Zhu, G., Bard, J. F., and Yu, G, “Disruption Management for Resource-Constrained Project Scheduling, Journal of the Operational Research Society, Vol. 56, No. 4, pp. 365-381, 2005.
Zitzler, E., Laumanns, M, and Thiele, L., “SPEA2: Improving the Strength Pareto Evolutionary Algorithm, Technical Report 103, Computer Engineering and Communication Networks Lab, Zurich, 2001.
Zitzler, E. and Thiele, L., “Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach, IEEE Transactions on Evolutionary Computation, Vol. 3, No. 4 pp. 257-271, 1999.