臺灣博碩士論文加值系統

在過去幾十年中，製造商為了追求生產流程的效率，大量生產(mass production)一直是生產系統中所使用的生產型態。在製造業最重要的一環是生產管理，而生產管理中非常重要的一個領域就是排程(scheduling)，其主要是探討如何將製造資源(機台、設備、人力)妥善地分配給一群待處理的工作，以達到最大的目標效益。大多數機台的成本都非常昂貴，若是在生產上有任何一個環節決策不佳，必將會造成不必要的額外損失。
現在的生產觀念是基於滿足消費者需求的觀念，所被市場需求的產品也就朝向多樣少量的零工式生產(Job Shop)。在各個產品彼此競爭共同的資源下，再加上快速回應市場的交期等原因造成生產環境的不確定性，都使得生產排程問題的複雜度大增，同時也使得零工式的生產排程的研究令人注意。因此，學者紛紛投入零工式生產排程問題的研究領域，為的就是提高生產競爭力，然而，零工式生產排程問題(Job-Shop Scheduling Problem；JSSP)是公認為困難與複雜的NP-hard問題之一，要在有限的計算時間內尋找大型問題的最佳化解往往是不可行的。
本文提出細菌演算法求解零工工廠排程的問題，細菌演算法為一種求取最佳化的方法，其為仿照細菌的一些演化現象的一種演算法，並且結合當雄性細菌傳送一段基因給雌性細菌時，這些雌性細菌擁有雄性細菌的特性之後將會轉化成雄性細菌，換句話說，藉此機制細菌的特色可以感染到整個細菌池，以及運用細菌突變的特殊運算。所以本文將選用細菌演算法作為求解零工式的工作排程問題之啟發式演算法，並對演算法中的參數做比較，最後，本文引用著名的範例來評價細菌演算法的成效。經實驗題組證實，本文提出之雛型可快速地求得中小型問題之最佳解。

In past decades, manufacturer in order to ensure the efficiency of production process, mass production is adapted. In the manufacturing industry, production management plays an important role and the core job of the production management is production scheduling. How to arrange and assign limited resource (machines, equipment, and manpower) to achieve optimal output is a critical issue.
Now, the production schema is changed to satisfying the demands of customers. Job shop had become an important production methodology to fit the rapidly change of the market demand. Hence, there are a lots of scholars study the Job-Shop Scheduling Problem in order to improve the throughput and shorten the production competition. But the Job-Shop Scheduling Problem is one of the difficulty and complex problems, and it is also one of the NP-hard problems. To achieve optimal solution is very time-consuming.
This paper proposed the bacterial evolutionary algorithm to solve the Job-Shop Scheduling Problem. Numerous well-studied benchmark examples were utilized to evaluate the effectiveness of the proposed method. And analytical parameter design for the proposed algorithm was also presented in this paper. Experiments had shown that the proposed algorithm is very efficient for small and medium size problems.

目 次
摘要 i
Abstract ii
目 次 iii
圖 次 v
表 次 vii
第一章 緒論 1
第一節 研究背景與動機 1
第二節 研究目的 1
第三節 研究範圍與限制 2
第四節 研究方法與架構 4
第二章 文獻探討 6
第一節 排程的介紹 6
第二節 零工工廠排程介紹 7
第三節 最佳化演算法的介紹 11
第四節 排程績效評估準則 20
第三章 細菌與細菌進化演算法 22
第一節 細菌概述 22
第二節 細菌進化演算法 28
第四章 演算法模型與實證 32
第一節 演算法模型 32
第二節 實驗結果與探討 35
第五章 結論 56
第一節 結論 56
第二節 未來展望 56
參考文獻 58

王進德(2006)。類神經網路與模糊控制理論入門與應用。台北市：全華科技圖書股份有限公司。
蘇木春、張孝德(2004)。機械學習：機器學習：類神經網路、模糊系統以及基因演算法則(修訂二版)。台北市：全華科技圖書股份有限公司。
李世威 (2006)。利用細菌進化演算法來處理零工工廠的工作排程問題。未出版之碩士論文，私立大同大學機械工程研究所，台北市。
林純行 (2003)。多階平行機器零工式多目標排程之模式化與系統之研究。未出版之碩士論文，私立東海大學工業工程學系，台中市。
柯惠雯 (2000)。結合模擬退火法與禁忌搜尋法在流程式生產排程之應用。未出版之碩士論文，大葉大學工業工程研究所，彰化縣。
趙良輝、鄧飛其(2007, Jun.)。一種求解作業車間調度問題的混合遺傳演算法。Systems Engineering and Electronics, 29(6), 899-902。
劉清祥(2005)。粒子群演算法於結構設計及零工式排程之應用。未出版之碩士論文，國立台灣海洋大學系統工程暨造船學系，基隆市。
鍾承志(2004)。多目標零工式平行機台排程之研究-應用蟻群最佳化演算法。未出版之碩士論文，私立東海大學工業工程與經營資訊學系，台中市。
韓駿逸 (2001)。基因演算法解算交期限制零工型排程問題之效果分析。未出版之碩士論文，元智大學工業工程研究所，桃園縣。
蘇恆磊 (2002)。遺傳演算法於零工式生產排程系統之應用。未出版之碩士論文，國立海洋大學系統工程暨造船學系，基隆市。
Baker, K. R (1974). Introduction to Sequence and Scheduling. New York: Wiley.
Baker, R. K. (1984). Sequence rules and due-date assignments in a job shop. Management Science, 30(9), 1093-1104.
Chao, X., & Pinedo, M. (1999). Operations scheduling with applications in manufacturing and services. Boston: McGRAW-Hill.
Goldberg, D. E. (1989). Genetic algorithm in search optimization, and machine learning. Mitchell: Addison-Wessley.
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B.(1993). Sequencing and scheduling: Algorithms and complexity. S. Caralina, S.C.: Graves.
Luh, G.. C., & Lee, S. W., (2006). A bacterial evolutionary algorithm for the job shop scheduling problem. Journal of the Chinese Institute of Industrial Engineers, 23(3), 185-191.
Manne, A. S. (1960). On the job-shop scheduling problem. Operations Research, 8, 219-223.
Mattfeld, D. C., & Vaessens, R. J. M. (2003). Job shop problem test instances set. Retrieved 2005, from http://www.ms.ic.ac.uk/jeb/pub/jobshop1.txt
Mellor, P. (1966). A review of job shop scheduling . Operational Research, 17(2), 191-170.
Nakano, R. & Yamada, T. (1991), Conventional Genetic Algorithm for Job-Shop Problems, Proceedings of the 4th International Conference on Genetic Algorithms and their Applications, SanDiego, U.S.A., 474-479.
Nawa, N. E., & Furuhashi, T. (1999). Fuzzy system parameter discovery by bacterial evolutionary algorithm. IEEE Tr. Fuzzy System, 7, 608-616.
Nawa, N. E., & Furuhashi, T. (1998 October 11-14). Bacterial Evolutionary Algorithm for Fuzzy System Design. In Proceedings of the 1998 IEEE Int. Conf. on Systems, Man, and Cybernetics (SMC'98), San Diego, California, USA.
Nawa, N. E., Hashiyama, T., Furuhashi, T., & Uchikawa, Y. (1997). Fuzzy logic controllers generated by pseudo-bacterial genetic algorithm. In Proceedings of IEEE International Conference on Neural Networks, 4(4), 2408-2413.
Nawa, N. E., Furuhashi, T., Hashiyama, T., & Uchikawa, Y. (1999). A study on the discovery of relevant fuzzy rules using pseudo-bacterial genetic algorithm. In IEEE Transactions on Industrial Electronics , 46(6), 1080-1089.
Schultz, S. R., Hodgson, T. J., & King, R. E. (2002). On solving the classic job shop makespan problem by minimizing Lmax. IIE Annual Conference and Exhibition, Orlando, FL..
Soproni, P., Botzheim, J., Cinkler, T., & Kóczy, L. T. (2007 November). Grooming-Enhanced Multicast in Multilayer Networks with Bacterial Evolutionary Algorithm. 8th International Symposium of hungarian Researchers on Computational Intelligence and Informatics 15-17 November, Budapest, 211-225.
Wang, L., & Zheng, D. (2001). An effective hybrid optimizatiom strategy for job-shop scheduling problems. Computers & Operations Research, 28, 558-596.
Wang S. F., & Zou Y. R. (2003). Techniques for the job shop scheduling problem. a survey. Syst Eng Theor Pract, 23(1), 49-55.
Werner, J. C., Aydin, M. E. & Fogarty, T. C. (2000). Evolving genetic algorithm for Job Shop Scheduling problems. Proceedings of ACDM 2000 PEDC, Unviersity of Plymouth, UK.
Xing, L. N., Chen, Y. W., & Shen, X. S. (2006). A constraint satisfaction adaptive neural network with dynamic model for job-shop scheduling problem. Electronic Edition, 3973, 927-932.
Xu, X. D., & Li, C. X. (2006). Research on immune genetic algorithm for solving the job-shop scheduling problem. International journal of advanced manufacturing technology, 34(7-8), 783-789.
Zhang, C. Y., Li, P. G., Rao, Y. Q., & Guan, Z. L. (in press,2008). A very fast TS/SA algorithm for the job shop scheduling problem. Computers & Operations Research, 35, 282-294.