結合共享基因演算法與區段搜尋最佳化零工工廠排程問題

Job Shop Scheduling Optimization Using Sharing Genetic Algorithm with Sectional Search

陳彥竹(Yen-Chu Chen)

指導教授 ： 陸冠群

大同大學/工程學院/機械工程學系所/碩士(2009年)

摘要

零工工廠問題為最複雜且最困難的組合最佳化問題之一，其目的在於增加生產效率及降低製程時間，使能獲得最大利潤，在電腦科技的發達現在使的人工智慧也就是模擬生物演化的計算漸漸的運用在零工工廠問題上，且本文為了將零工工廠排程的問題得以簡單的供大眾使用所以結合了廣為大家所使用的MS Project及搭配內建的Visual Basic設計了基因演算法模組，並提出了加強基因演算法局域搜尋能力改良式基因演算法，最後再以FT及LA測試題目並與其他文獻比較來驗證該演算法的能力。

關鍵字

零工工廠 ； 基因演算法 ； 最佳化 ； 排程

並列摘要

Job shop problem is one of the most complex and difficult problem of combination of optimization, the purpose of this research is to increase production efficiency and lower down process time, so, it could get maximum profits. Advanced computer technology nowadays let artificial intelligence which means computation of simulated biological evolvements gradually be used on Job shop problem, also, this thesis in order to let Job shop problem could be used easily for public, so it combines comprehensive-used MS Project and apply genetic algorithm, and it brings up modified genetic algorithm to improve resource smooth function of original project, then it can shorten total factory hours, at the same time, Finally FT and LA testing subjects could verify credits of this thesis.

並列關鍵字

Genetic Algorithm ； MS Project ； schedule ； Jobshop ； niche scheme ； Optimization

參考文獻

[1] E.D. Taillard, Parallel taboo search techniques for the job shop scheduling problem, ORSA J. on Compute (1994) pp. 108–117.

[2] S.Y. Foo, Y. Takefuji and H. Szu, Scaling properties of neural networks for job shop scheduling, Neural Computing 8 (1) (1995) pp. 79–91.

[3] M. Dorigo, and L.M. Gambardella, Ant colony system, a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation 1 (1) (1997) pp. 53-66 .

[5] F.D. Croce, R. Tadei and G. Volta, A genetic algorithm for the job shop problem , Computers and Operations Research 22 (1995) pp.15–24 .

[7] R. Cheng, M. Gen, Y. Tsujimura, A tutorial survey of job shop scheduling problems using genetic algorithms, part Ⅱ, hybrid genetic search strategies, Computer & Industrial Engineering 37 (1999) pp. 51-55.