臺灣博碩士論文加值系統

近年來國際間的生產導向以顧客需求為主要目標，所以企業生產模式轉為多樣少量的模式，導致生產者必須經常性的更換製程方法與機器模組，因此探討整備時間（set-up time）納入生產排程問題之研究也日益增加。故本論文主要解決的目標是，單機生產排程之延遲時間最小化與整備時間最小化雙目標之問題研究。希望藉由霍普菲爾-坦克神經網路來解決此雙目標之排程性的問題，在小工件模擬排程實驗時使用整數線型規劃做為最佳解之驗證，經由模擬後發現小工件時神經網路與整數線型規劃所獲得最佳解之誤差並不大，最大誤差約為2.6％，但解題時間卻比LINGO少很多倍。大工件則採神經網路與Apparent Tardiness Cost and Setup(ATCS)啟發式法則作解題品質的比較，發現神經網路所獲得的解的品質比ATCS啟發解來的更好。

The major tendency orientation of the production system has been changed to meet the customer demand in the recent years. It results in frequent changeovers in the production process. Consequently, many enterprises have switched systems from large- quantity production into the small-size large-variety mode. The research of scheduling concerning the setup time is getting more and more. According to this situation, a Hopfield-Tank Neural Network (HTNN) was applied to a single machine scheduling problem with minimizing the tardiness and the setup time is addressed in this thesis. When the problem size is small, the result of the HTNN is not far away from the optimal solutions acquired by using LINGO. The maximal error approximates to 2.6% and the computation of HTNN takes much less time. When the problem size is large, the HTNN was compared with the Apparent Tardiness Cost and Setup (ATCS) rule. The experimental result indicated that HTNN is superior to the ATCS in the quality of solution.

目 錄
中文摘要…………………………………………………………………………………i
英文摘要………………………………………………………………………………ii
誌謝……………………………………………………………………………………iii
目錄……………………………………………………………………………………iv
表目錄…………………………………………………………………………………vi
圖目錄…………………………………………………………………………………vii
第一章 緒論…………………………………………………………………………01
1.1 研究的背景與動機…………………………………………………………01
1.2 研究目的……………………………………………………………………03
1.3研究的範圍與流程流程……………………………………………………03
1.4研究方法……………………………………………………………………03
1.5研究架構……………………………………………………………………04
第二章 文獻探討………………………………………………………………………06
2.1各類之類神經網路在排程問題上之應用……………………………………04
2.2霍普菲爾-坦克類神經網路之最佳化問題應………………………………..10
2.3霍普菲爾-坦克類神經網路之排程問題應用………………………………12
2.4整備時間與絕對偏差最小化之文獻探討…………………………………04
2.4.1整備時間之文獻探討…………………………………………………15
2.4.1排程問題之絕對偏差最小化相關文獻………………………………15
第三章 問題定義………………………………………………………………20
3.1 欲解決單機排程問題之描述………………………………………………21
3.2 假設條件……………………………………………………………………21
3.3 欲解決單機排程衡量準則…………………………………………………22
第四章 研究方法………………………………………………………………24
4.1類神經網路的簡介…………………………………………………………24
4.1.1 類神經網路的演進過程…………………………………………24
4.1.2類神經網路的模型與結構……………………………………………27
4.1.3 類神經網路的基本模型…………………………………………24
4.2霍普菲爾-坦克類神經網路…………………………………………………………34
4.2.1霍普菲爾-坦克類神經網路的崛起簡介………………………………34
4.2.2霍普菲爾-坦克類神經網路之架構……………………………………35
4.2.3霍普菲爾-坦克類神經網路的學習與回想過程………………………35
4.2.4霍普菲爾-坦克類神經網路的應用……………………………………36
4.2.4.1銷售員問題簡介與假設……………………………………36
4.2.4.2銷霍普菲爾-坦克類神經網路在TSP問題上之基本步驟…36
4.3 霍普菲爾-坦克類神經網路使用在排程的概念………………………………40
4.3.1概述……………………………………………………………………40
4.3.2簡例與實做……………………………………………………………43
4.3.3網路建構方法與手算簡例……………………………………………41
4.3.3.1網路建構……………………………………………………..41
4.3.3.2網路建構的流程…………………………………………..42
4.3.3.3網路運作與簡算實例…………………………………………43
4.4 霍普菲爾-坦克網路的評價…………………………………………………47
4.5 預期目標……………………………………………………………………47
4.6 ATCS啟發式準則…………………………………………………………49
4.6.1調整後ATCS的由來…………………………………………………49
4.6.2 調整型ATCS的符號說明……………………………………………49
4.6.3調整後ATCS的步驟…………………………………………………51
第五章 實驗結果與分析………………………………………………………………55
5.1 問題產生與實驗方法………………………………………………………55
5.2實驗數據與結果分析……………………………………………………54
5.2.1小工件與最佳解之實例驗證…………………………………………56
5.2.2 大工件之實例模擬…………………………………………………58
5.2.2.1 ATCS與霍普菲爾坦克模擬實驗與比較…………………58
第六章 結論與未來發展………………………………………………………63
6.1 結論…………………………………………………………………63
6.2 未來發展……………………………………………………………64
參考文獻………………………………………………………………………65

參 考 文 獻
1. 林瑞明，『在物流系統中具有優先次序之車輛路徑指派問題探討』，元智大學工業工程研究所，碩士論文，桃園，民國八十四年。
2. 吳家增，「模擬退火法應用在絕對偏差最小化之單機排程問題」，私立元智大學，碩士論文，民國86年6月。
3. 吳統鈞，『以神經網路做混合生產線產品投入順序之研究』，國立交通大學管理科學研究所，碩士論文，新竹，民國八十二年。
4. 黃柏仁，『在類神經網路的模式下建構一具有時效性及資源限制之可插斷是及時排程器』，國立成功大學工程科學研究所，碩士論文，台南，民國八十四年。
5. 張凱傑，『以Hopfield型類神經網路法求解訂單式生產排程』，國立成功大學工業管理研究所，碩士論文，台南，民國八十一年。
6. 葉怡成，類神經網路模式應用與實作，六版，台北，儒林圖書有限公司，民國八十九年。
7. Abe, S. “ Theories on the Hopfield Neural Networks,” Proceedings of International Joint Conference on Neural Networks, pp.577-564, 1989.
8. Adamopoulos G.I. and C.P. Pappis, “ Scheduling Jobs with Different, Job-dependent Earliness and Tardiness Penalties Using the SLK Method, ” European Journal of Operational Research, 88, pp.336-344, 1996.
9. Ali Allahverdi, et al., “ A Review of Scheduling Research Involving Setup Consideration, ” OMEGA, 27, pp.219-239, 1999.
10. Arizono, I., A. Yamamoto, and H. Ohta, “Scheduling for Minimizing total Actual Flow Time by Neural Networks,” International Journal of Production Research, VOL. 30, NO.30, pp.503-511, 1992.
11. Behzad, K.P., B.Kamgar-Parsi, “On problem solving with Hopfield Neural Networks,” Biological Cybernetics, 62,pp.415-423, 1990
12. Bizzarri, A. R. “Convergence Properties of a modified Hopfield-Tank Model,” Biological Cybernetics, 64,pp.293-300.
13. Bovet D.P. and M. Petrini, “ Evaluation of Scheduling Algorithms for Resources, ” European Journal of Operational Research, 5, pp.182-192, 1980.
14. Candance A.Y. and Y.D. Kim, “ Algorithms for a Class of Single-Machine Weighted Tardiness and Earliness Problems, ” European Journal of Operational Research, 52, pp.167-178, 1991.
15. Cervantes, J. H., and R. R. Hildebrant, “Comparison of Three Neural Base Computation Schemes,” ICNN-87Ⅲ, pp.657-672, 1987.
16. Chen, R. M., and Y. M. Hung, “Competitive neural network to solve scheduling problems,” ELSEIER 37,pp.177-196, November 2001.
17. Chi X. et al., “ Scheduling about a Common Due Date with Job-dependent Asymmetric Earliness and Tardiness Penalties, ” European Journal of Operational Research, 98, pp. 154-168, 1997.
18. Christos K., “ The Total Tardiness Problem：Review and Extensions, ” Operations Research, 42, pp.1025-1041, 1994
19. Dagli, K. R., S. Lammers, and M. Vellanki, “ Intelligent Scheduling in Manufacturing Using Neural Networks,” Intelligent Scheduling, 1,pp.69-79, 1991.
20. David, E. V. D. B., and T. K. Miller, “A Traveling Salesman Objective Function That Works,” ICNN-88Ⅱ, pp.299-303, 1988.
21. Dingwei Wang et al., “Scheduling Grouped Jobs on Single Machine with Genetic Algorithm,” Computers & Industrial Engineering, 36, pp.309-324, 1999.
22. Foo F.C. and J.G. Wager, “ Setup Times in Cyclic and A Cyclic Group Technology Scheduling Systems,” International Journal of Production Research, 21, pp.63-73, 1983
23. Foo, Y. P. S., and Y. Takefuji, “Stochastic Neural Network foe Solving Job-Shop Scheduling: Part1. Problem Representation,” Proceedings of the IEEE International Conference on Neural Networks, 2, pp275-282, 1988.
24. Foo, Y. P. S., and Y. Takefuji, “ Integer Linear Programming Neural Networks for Job Shop Scheduling,” IEEE International Conference on Neural Networks, 2, pp.341─348, 1988.
25. Gavett J.W., “ Three Heuristic Rules for Sequencing Jobs to a Single Production Facility, ” Management Science, 11, pp.B166-B176, 1965.
26. Herrmann J.W. and C.Y. Lee, “ Solving a Class Scheduling Problem with a Genetic algorithm, ” ORSA Journal on Computing, 7, pp.443-453, 1995.
27. Kahng, A. B., “Traveling Salesman Heuristics and Embedding Dimension in the Hopfield Model,” ICNN-87Ⅲ, pp.513-520, 1987.
28. Kamgar-Parsi B., “An Efficient Model of Neural Network for Optimization,” ICNN-87Ⅲ, pp.785-790, 1987.
29. Kim, S. Y., Y. H. Lee, and D. Agnihotri, “A Hybrid Approach to Sequence Jobs Using Heuristic Rules and Neural Network,” Production Planning and Control, 6(5), pp.445-454, 1995.
30. Lippmann, R. P., “An Introduction to Computing with Neural Nets”, IEEE ASSP Magazine,” pp.4-22, April 1987.
31. Lockett A.G. and A.P. Muhlemann, “ A Scheduling Problem Involving Sequence Dependent Changeover Times,”Operations Research, 20, pp.895-902, 1972.
32. Mason A.J., “ Genetic Algorithm and Scheduling Problems,” PHD thesis, Department of Management Sciences, University of Cambridge, UK, 1992.
33. Mendes, A. D. S., and L. M. Agilera, “ A Hopfield Neural Network Approach to The Single Machine Scheduling Problem” 1998.
34. OW, P.S. and Morton, T.E.“ The Single Machine Early/Tardy Problems,”Management Science, 35, pp.177-191, 1989.
35. Park Y., S. Kim, and Y. H. Lee, “Scheduling Jobs on Parallel Machines Applying Neural Network and Heuristic Rules,” Computer & Industrial Engineering, 38, pp.189-202, March 2000.
36. Picard J.C. and M. Queyranne, “ The Time-dependent Traveling Salesman Problem and its Application to the Tardiness Problem in One Machine Scheduling,” Operations Research, 26, pp.86-110, 1978.
37. Presby J.T. and M.L. Wolfson, “ An Algorithm for Solving Job Sequencing Problems,” Management Science, 13, pp. B454-B464, 1967.
38. Sabuncuoglu, I., and B. Gurgun, “A Neural Network Model for Scheduling Problems, ” European Journal of Operational Research, 93, pp.288-299, 1996.
39. Sen T. et al., “ Minimizing a Weighted Quadratic Function of Job Lateness in the Single Machine System,” International Journal of Production Economics, 42, pp.237-243, 1995.
40. Tan K.C. and R. Narasimhan, “ Multi-objective Sequencing with Sequence Dependent Setup Times,” International Journal of operational Quantitative Manage, 3, pp.69-84, 1997.
41. Tan K.C. et al., “ A Comparison of Four Methods for Minimizing Total Tardiness on a Single Processor with Sequence Dependent Setup Times,” OMEGA, 28, pp.313-326, 2000.
42. Ten Kate H.A. et al., “ Minimizing Total Earliness, Tardiness and Setup Cost,” Research Report, NO.RR1991-12. School of Management and Organization, University of Groningen, Holland, 1991.
43. Wilson, V., and G. S. Pawley, “On the Stability of the Traveling Salesman Problem Algorithm of Hopfield and Tank,” Biological Cybernetics, 58, pp63-70, 1988.
44. Young Hoon Lee et al., “ A Heuristic to Minimize the Total Weighted Tardiness with Sequence-Dependent Setups, “ IIE Transactions, 29, pp.45-52, 1997.