臺灣博碩士論文加值系統

本研究以Dorigo (1997)所提出的螞蟻演算法（ACS）為排程機制，運用多重法則的能見度設計並結合立即重排機制，建構一動態零工型排程系統。探討在不同的排程限制下能見度的設計，對螞蟻演算法在最小化最大完工時間(Cmax)和最小化平均流程時間( )兩項績效指標績效的優劣影響。螞蟻演算法在排程問題中，能見度為可以提供一個有效方式來辨別各作業之間重要性的機制，因此能見度的設計是影響螞蟻演算法績效的決策關鍵。在本研究證實，不同的績效指標下能見度設計確實是影響排程績效的重要因子。績效指標為最小化最大完工時間，MRT_MIT螞蟻演算法在不同的排程限制下都顯示有穩定的良好績效。績效指標最小化平均流程時間，會隨著不同的排程限制組合而有所改變，在操作時間範圍較大以及製程數範圍較小的情況下為SPT_MIT_JWT螞蟻演算法有較佳的績效，而操作時間範圍較小以及製程數範圍較大的情況為LRT_MIT_JWT螞蟻演算法有較佳績效。此研究結果可提供日後針對探討螞蟻演算法在解決不同的排程問題時，應用不同能見度設置改善以往直接使用能見度SPT所間接影響的缺失。

In this study, we combine ant colony optimization（ACO）with three multi-factor desirability heuristics to reschedule dynamic job shop problems to minimize makespan（Cmax）and mean flow-time（ ）. Our multi-factor heuristics are elaborations of commonly-used dispatching rules. The experimental results show that different heuristics can optimize performance for different criteria: MRT_MIT produces the best stability and the best Cmax , but MRT_MIT never optimizes . Problems with long processing times and few operations obtain the best from SPT_MIT_JWT, and problems with short processing times and many operations obtain the best from LRT_MIT_JWT. The results of this study show how to use multi-factor heuristics to control desirability calculations within ACO programs that schedule job shops with dynamic job arrival.

誌謝 i
摘要 ii
Abstract iii
目錄 iv
圖目錄 vi
表目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究假設 3
1.4 研究流程 4
第二章 文獻探討 6
2.1 生產排程問題 6
2.2 零工型排程問題 8
2.3 螞蟻演算法 12
2.3.1 原理與概念 12
2.3.2 演算法架構 13
2.3.2.1 螞蟻系統（AS） 14
2.3.2.2 螞蟻族群系統（ACS） 16
2.4 螞蟻演算法在零工型排程問題之應用 19
第三章 研究方法 23
3.1 模擬環境設置及前提假設 23
3.2 螞蟻演算概念排程機制 24
3.2.1 演算法初始化 24
3.2.2 建構螞蟻路徑 26
3.3多重法則能見度設計 27
第四章 動態排程環境模擬系統 34
4.1動態排程環境 34
4.2發展模擬模式 35
4.3動態零工型排程模擬系統 37
4.4模試驗證 38
第五章 數據分析 40
5.1績效指標-Cmax 40
5.2績效指標- 42
第六章 結論與未來研究方向 47
6.1 結論 47
6.2未來研究方向 48
參考文獻 49
附錄 56

Allahverdi, A. and Tatari, M. F., 1996. Simulation of different rules in stochastic flowshops. Computers and Industrial Engineering, 31(1/2), 209-212.
Appold, S. J., Harrison, B. and Kelley, M. R., 1993. Spatially proximate inter-organizational networks, agglomeration economics, and technological performance in U.S. manufacturing. Annual meeting of the association of American geographers
Al-Hakim, L., 2001. An analogue genetic algorithm for solving job shop scheduling problems. International Journal of Production Research, 39, 1537-1548.
Amirthagadeswaran, K. S. and Arunachalam, V. P., 2006. Improved solutions for job shop scheduling problems through genetic algorithm with a different method of schedule deduction. International Journal of Advanced Manufacturing Technology, 28(5-6), 532-540.
Aydin, M. E. and Fogarty, T. C., 2004. A simulated annealing algorithm for ulti-agent systems: a job-shop scheduling application. Journal of Intelligent anufacturing, 15(6), 805-814.
Adams, J., Balas, E. and Zawack, D., 1988. The shifting bottleneck procedure for job shop scheduling. Management Science, 34, 391-401.
Allidaee, B. and Ramakrishnan, K. R., 1996. A computational experiment of covert-auclass of rules for single machine tardiness scheduling problem. Computers Industrial Engineering, 90, 201-209.
Averill, M. Law, 2007. Simulation Modeling and Analysis. McGraw-Hill,508-517.
Barrett, R. and Kadipasaoglu, S. N., 1999. Evaluation of Dispatching Rules in a Dynamic Flow Shop. Production and Inventory Management Journal, 31:1, 54-58.
Baker, K. R. and Kanet, J. J., 1983. Job shop scheduling with modified due dates. Journal of Operations Management, 4(1), 11-22.
Balas, E., Lenstra, J. K. and Vazacopoulos, A., 1995. The one-machine problem withdelayed precedence constraints and its use in job shop scheduling. Management Science, 41, 94-109.
Balas, E. and Vazacopoulos, A., 1998. Guided local search with shifting bottleneck for job shop scheduling. Management Science, 44, 262-275.
Bauer, A., Bullnheimer, B., Hartl, R. F. and Strauss, C., 1999. Minimizing total tardiness on a single machine using ant colony optimization. Proceedings of the 1999 Congress on Evolutionary Computation, IEEE Press, 1445-1450.
Conway, R. W., 1965. Priority dispatching and work- in-process inventory in a job shop. Journal of Industrial Engineering,16, 123-130, 228-237.
Chang, P. T. and Lo, Y. T., 2001. Modeling of job-shop scheduling with multiple quantitative and qualitative objectives and a GA/TS mixture approach. International Journal of Computer Integrated Manufacturing, 14(4), 367-384.
Colorni, A., Dorigo, M., Maniezzo, V. and Trubian, M., 1994. Ant system for job-shop scheduling. JORBEL — Belgian Journal of Operations Research Statistics and Computer Science, 34,39–53.
Church, L. K. and Uzsoy, R., 1992. Analysis of periodic and event-driven rescheduling policies in dynamic shops. Int J Comput Integr Manuf, 5(3), 153–163.
Dennis, P. C. and Shannon, R. E., 1995. Introduction to simulation using SIMAN. McGraw-Hill, New York.
Dominic, P. D. D., Kaliyamoorthy S. and Saravana Kumar M., 2004. Efficient dispatching rules for dynamic job shop scheduling. Int J Adv Manuf Technol, 24, 70-75.
Dorigo, M., 1992. Optimization, learning and natural algorithm. Ph.D., Thesis, DEI, Politecnico di Milano, Italy .
Dorigo, M., Maniezzo, V. and Colorni, A., 1996. Ant system: optimization by a colony of cooperating agents Systems. Man and Cybernetics, Part B. IEEE Transactions, 26(1), 29-41.
Dorigo, M. and Gambardella, L. M., 1997. Ant colony system: A cooperative learning approach to the travelling salesman problem. IEEE Trans Evolut Comput, 1(1), 53-66.
Dorigo, M., Caro, G. D. and Gambarsella, L. M., 1999. Ant algorithms for discrete optimization. Artificial Life,5, 137-172.
Dorigo, M. and Stutzle, T., 2004. Ant Colony Oprtimization.
Dell’ Amico, M. and Trubian, M., 1993. Applying tabu search to the job shop scheduling problem. Annals of Operations Research, 41, 231-252.
Dauzere-Peres, S. and Lasserre, J., 1993. A modified shifting bottleneck procedure for job shop problem. International Journal of Production Research, 31, 923-932.
Dutta, A., 1990. Reacting to scheduling exceptions in FMS environments. IIE Transact, 22(4), 300–314.
Garey, M. R., Johnson, D. S. and Sethi, R., 1976. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1, 117-129.
Garey, M. R. and D. S. Johnson., 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, CA.
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A Marchetti-Spaccamela and M. Protasi., 2003. Complexity and Approximation: Combinatorial Optimization problems and Their Approximability Properties. Springer-Verlag, Berlin.
Geyik, F. and Cedimoglu, I. H., 2004. The strategies and parameters of tabu search for job-shop scheduling. Journal of Intelligent Manufacturing, 15(4), 439-448.
Gambardella, L. M., Taillard, E. and Dorigo, M., 1999. Ant colonies for the quadratic assignment problem. Journal of Operational Research Society, 50, 167-176.
Gambardella, L. M. and Dorigo, M., 2000. An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem. Journal on Computing,12(3), 327-355.
Herrmann, J. W., 2001. Improving Manufacturing System Performance through Rescheduling. Computer Integrated Manufacturing Laboratory, University of Maryland, June 21.
Hunsucker, J. L. and Shah, J. R., 1994. Comparative performance analysis of priority rules in a constrained flow shop with multiple processors environment. European Journal of Operational Research, 72, 102-114
Haupt, R., 1989. A Survey of Priority Rule-Based Scheduling. OR Spektrum,11, 3-16.
Jain, A. S. and S. Meeran., 1998. A State of the Art Review of Job-Shop Scheduling Techniques. Technical Report, Department of Applied Physics, Electronic and Mechanical Engineering University of Dundee, Dundee, Scotland, UK.
Holloway, C. A. and Nelson, R. T., 1974. Job shop scheduling with due dates and variable processing times. Manag Sci, 120(9), 26–75.
Liu, K. C., 1998. Dispatching rules for stochastic finite capacity scheduling. Computers and Industrial Engineering, 35(1), 113-116.
Liu, S. Q., Ong, H. L. and Ng, K. M., 2005. Metaheuristics for minimizing the makespan of the dynamic shop scheduling problem. Advances in Engineering Software, 36(3), 199-205.
Muth, J. F. and G. L. Thompson, 1963. Industrial Scheduling, Prentice Hall Englewood Cliffs. New Jersey, 225-251.
Muhleman, A. P., Lockett, A. G., and Farn, C. K.,1982. Job shop scheduling heuristics and frequency of scheduling. International Journal Production Research,20(2), 227-241.
Mohanasundarama, K. M., Viswanathkumarb, K. N. G., Radhakrishnana, P. and Rajendranb, C., 2002. Scheduling rules for dynamic shops that manufacture multi-level jobs. Computers & Industrial Engineering, 44, 119-131
Narasimhan, S. L. and Mangiameli, P. M., 1987. A comparison of sequencing rules for a two-stage hybrid flow shop. Decision Sciences,18, 250-265.
Nowicki, E. and Smutnicki, C., 1996. A fast tabu search algorithm for the job shop problem. Management Science, 42, 797-813.
Nowicki, E. and Smutnicki, C., 2005. An advanced tabu search algorithm for the job shop problem. Journal of Scheduling, 8(2), 145-159.
Pinedo, M., 1995. Scheduling : theory, algorithms, and systems. Prentice Hall, Inc., 118-141.
Parunak, H. V. D., 1991. Characterizing the Manufacturing Scheduling Problem. Journal of Manufacturing Systems,10, 241-259.
Ponnambalam, S. G., Jawahar, N. and Senthil Kumar, B., 2002. Estimation of optimum genetic control parameters for job shop scheduling. International Journal of Advanced Manufacturing Technology, 19, 224-234.
Pezzella, F. and Merelli, E., 2000. A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operational Research, 120, 297-310.
Ponnambalam, S. G., Jawahar, N. and Aravindan, P., 1999. A simulated annealing algorithm for job shop scheduling. Production Planning and Control, 10, 767-777.
Roy, B. and Sussmann, B., 1964. Les problems d’ordonnancement avec contraintes disjunctives. Notes DS N.9 Bis, SEMA, Montrouge.
Rangsaritratsamee, R., William, G., Ferrell, J. and Mary, B. K., 2004. Dynamic rescheduling that simultaneously considers efficiency and stability. Computers & Industrial Engineering, 46, 1-15.
Rangsaritratsamee, R., and Ferrell, W. G., 2005. Scheduling for efficiency and stability in the dynamic job shop. International Journal of Industrial Engineering-Theory Applications and Practice, 12(3), 206-217.
R. Jagadeesh and A. Subash Babu., 1994. Process Capability Assessment With Tool Wear: An Investigative Study. International Journal of Quality & Reliability Management, 11(2), 51-62.
Sarper, H. and Henry, M., 1999. Combinatorial evaluation of six dispatching rules in a dynamic two-machine flow shop. Omega, 24(1), 73-81.
Sadeh, N., 1991. Lookahead Techniques for Micro-Opportunistic Job Shop Scheduling. Ph.D., CMU-CS-91-102, School of Computer Science, Carnegie Mellon University,Pittsburgh.
Subramaniam, V., Lee, G. K., Ramesh, T., Hong, G. S. and Wong, Y. S., 2000. Machine selection rules in a dynamic job shop. International Journal of Advanced Manufacturing Technology, 16(12), 902-908.
Sumramaniam V., L. G. K., Hong G. S., Wong Y. S. and Ramesh T., 2000. Dynamic selection of dispatching rules for job shop scheduling. PRODUCTION PLANNING & CONTROL, 11(1), 73-81.
Szelke, E. and Kerr, R. M., 1994. Knowledge-based reactive scheduling. Prod Plan Control, 5(2), 124–145.
Taillard, É. D., 1994. Parallel taboo search Techniques for the job shop scheduling problem. ORSA Journal on Computing, 6, 108-117.
Van Laarhoven P. J. M., Aarts, E. H. L. and Lenstra, J. K., 1992. Job shop scheduling by simulated annealing. Operations Research, 40, 113-125.
Vogel, A., Fischer, M., Jaehn, H. and Teich, T., 2002. Real-world shop floor scheduling by ant colony optimization. in ANTS 2002, In: M. Dorigo, M. Middendorf and T. Stu‥ tzle. eds. LNCS 2463, 173–198.
Vieira G. E., Hermann J. W. and Lin E., 2000. Predicting the performance of rescheduling strategies for parallel machine systems. Journal of Manufacturing Systems, 19 (4), 256-266.
Waikar, A. M., Sarker, B. R. and Lal, A. M., 1995. A comparative study of some priority dispatching rules under different shop loads. Production Planning & Control, 6(4), 301-310.
Wang, L. and Zheng, D. Z., 2001. An effective optimization strategy for job shop scheduling problems. Computers and Operations Research, 28, 585-596.
Yang, S. and Wang, D., 2000. Constraint Satisfaction Adaptive Neural Network and Heuristics Combined Approaches for Generalized Job-Shop Scheduling. IEEE Transactions on Neural Networks,11(2),474-486.
Yih, L. C. and Sullivan, R. S., 1990. Scheduling generation in a dynamic job shop. Int J Prod Res, 28(1), 65–74.
Ying, K. C. and Liao, C. J., 2003. An ant colony system approach for scheduling problems. Production Planning & Control,14(1), 68-75.
Zukui Li, and Marianthi Ierapetritou., 2008. Process scheduling under uncertainty: Review and challenges. Computers and Chemical Engineering, 32, 715-727.
Zhou, H., Feng, Y. and Han, L., 2001. The hybrid heuristic genetic algorithm for job shop scheduling. Computers and Industrial Engineering, 40, 191-200.
Zwaan, S.V.D. and Marques, C., 1999. Ant colony optimization for job shop scheduling. In: Proceedings of the ’99 workshop on genetic algorithms and artificial life (GAAL’99), Lisbon, Portugal.
Zhou, R., Nee, A. Y. C. and Lee H. P., 2009. Performance of an ant coloncy optimisation algorithm in dynamic job shop scheduling problems. International Journal of Production Research, 47(11), 1 June 2009, 2903-2920.
王立志，1999。系統化運籌與供應鏈管理。台中市：滄海書局。
林則孟，2002。系統模擬理論與應用。台中市：滄海書局。
林我聰，1994。現場排程專家系統-應用個體導向技術建立之研究。台北市：資訊與電腦公司出版。
呂里國，1999。複合式生產系統工令指派模式之研究。碩士論文，國立中山大學，高雄市。
周書賢，2001。多能工派工法則之模擬比較-以面臨緊急訂單之流線型生產系統。碩士論文，朝陽科技大學，台中縣。
諶承正，2001。運用系統模擬與基因演算法執行限制理論於流線型生產。碩士論文，國立台北科技大學，台北市。
柯惠雯，2002。結合模擬退火法與禁忌搜尋法在流程式生產排程之應用。碩士論文，大葉大學，彰化縣。
王治平，2003。實際零公式生產排程問題的派工法則。碩士論文，國立政治大學，台北市。
江朋南，2003。蟻族系統在零工型排程問題之應用。碩士論文，國立台灣科技大學，台北市。
楊家冠、曾和枝、陳建良、王正文，1995。製造業生產排程問題。機械工業雜誌。