臺灣博碩士論文加值系統

排程問題是自動化系統裡一個重要的課題，它具有NP-complete與高度複雜度的特性。本文提出一個類神經網路與啟發式法則結合的方法於求解零工式排程問題。類神經網路採用限制滿足的類神經網路，且加入三個啟發式的法則，其中第一個啟發式法則的功能是減少搜尋空間；第二個啟發式法則的功能是消除僵持(deadlock) 現象；第三個啟發式法則的功能是從一可行解中獲得一個可移動排程解 (active schedule) 與另一組開始時間。用此架構分別針對標準型、非標準型與批量型零工式排程問題進行測試，來驗證此架構的性能。整體而言，此方法所求解的答案，有著最佳解比例高與得到較低平均總完成時間 (makespan) 的特性，而且受到問題規模大小的影響並不明顯，最後並將結果與其他類神經網路與一種啟發式演算法 (Giffler and Thompson) 的結果比較。結果顯示，採用提出的方法求解排程問題不失為一可行之方式。

In automation systems design, scheduling problems are an important topic. It is NP-complete or combinatorial explosive, and has a high complexity. In this thesis, a combined approach of a neural network and heuristic methods for solving job shop scheduling problems is developed. The type of Constraint satisfaction neural network (CSNN) is used, and combines three heuristic methods. The function of the first heuristic method is tried to decrease search space. The function of the second heuristic method is tried to eliminate “dead lock”. The function of the third heuristic method is tried to obtain an active schedule and another initial starting time from the feasible solution gained by the neural network. We examine the performance of the proposed approach as follows：(1) classical job shop scheduling problem, (2) non-classical job shop scheduling problem, and (3) job shop scheduling problem with the consideration of lot sizes. The results show that using the combined approach to solve job shop scheduling, it has characteristics of high rate to get optimal solutions and lower average makespan. Then, we will compare with other neural networks and a kind of heuristic method (Giffler and Thompson). Simulations have shown that the combined approach is efficient with respect to the quality of solutions.

摘要 i
ABSTRACT ii
Acknowledgements iv
Contents v
List of Tables vii
List of Figures viii
Chapter1 Introduction 1
1.1 MOTIVATION AND OBJECTIVE OF THE THESIS 1
1.2 SCOPE AND LIMITATION OF RESEARCH 3
1.3 THESIS ORGANIZATION 7
Chapter 2 Literature Review 8
2.1 LITERATURE REVIEW OF JOB SHOP SCHEDULING PROBLEM 8
2.1.1 Optimization Methods 9
2.1.2 Heuristic Methods 13
2.2 NEURAL NETWORKS 16
2.2.1 Models of A Biological Neuron 16
2.2.2 Properties of Neural Networks 17
2.2.3 Application Paradigms of Neural Models 21
Chapter 3 Network Model and Combined Approach 25
3.1 MATHEMATICAL FORMULATION OF JOB SHOP SCHEDULING 25
3.2 NEURAL UNITS 27
3.3 CONNECTIONS OF WEIGHTS AND BIASES 32
3.4 MECHANISMS OF RUNNING NEURAL NETWORKS 39
3.5 DESCRIPTION OF HEURISTICS AND COMBINED APPROACH 40
3.5.1 Heuristics 40
3.5.2 Combined Approach for Job Shop Scheduling 45
Chapter 4 Simulation Results and Compares 48
4.1 SIMULATION METHOD 48
4.1.1 Simulation Problems 48
4.1.2 Measure Criteria 49
4.2 SIMULATION RESULTS AND DISCUSSIONS 50
Chapter 5 Conclusions and Future Works 67
5.1 CONCLUSIONS 67
5.2 FUTURE WORKS 68
References 69
Appendix A The Kinds of Schedules 73
Appendix B Taguchi Method 75

[1] Nasrabadi, N.M., Choo, C.Y., 1992,“Hopfield network for stereo vision correspondence”, IEEE Transactions on Neural Networks, vol.3, no. 1, pp.5-13, Jan..[2] Nasrabadi, N. M., Li, W. , Epranian, B.G. , Butkus, C.A. , 1989,“Use of Hopfield network for stereo vision correspondence”, Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, vol.2 , pp.429-432 .[3] H.M. Tai, J. Wang, and K. Ashenayi, 1992,“A Neural Network-Based Tracking Control System”, IEEE Transactions on Industrial Electronics, vol.39, no.6, pp.504-510.[4] T. Fukuda and T. Shibata, 1992,“Theory and Applications of Neural Networks for Industrial Control Systems’’, IEEE Transactions on Industrial Electronics, vol.39, no.6, pp.472-489.[5] Baker, K. R., 1974, Introduction to Sequencing and Scheduling, Wiley, New York.[6] Rodammer, F. A., and K. P. White, 1988,“A Recent Survey of Production Scheduling’’, IEEE Transactions on Systems, Man, and Cybernetics, vol.18, no.6 pp.841-851.[7] D. N. Zhou, V. Cherkassky, T. R. Baldwin, 1991,“A Neural Network Approach to Job Shop Scheduling’’, IEEE Transactions on Neural Networks, vol.2, no.1, pp.175-179. [8] Graves, S. C., 1981,“A Review of Production Scheduling’’, Production Scheduling, pp.646-675.[9] French, S., 1982, Sequencing and Scheduling :An Introduction to the Mathematics of the Job-Shop, New York, Wiley.[10]Foo,Y. P. S. and Takefuji, Y., 1988 ,“Stochastic Neural Networks for Solving Job-Shop Scheduling: Part 1. Problem Representation’’, Proceedings of the IEEE International Conference on Neural Networks, vol.2 , pp.275-282.[11]Foo, Y. P. S. and Y. Takefuji, 1988,“Stochastic Neural Networks for Solving Job-Shop Scheduling: Part 2. Architecture and Simulations’’, Proceedings of the IEEE International Conference on Neural Networks, vol.2, pp.282-292.[12]Foo, Y. P. S. and Y. Takefuji, 1988,“Integer Linear Programming Neural Networks for Job-Shop Scheduling’’, Proceedings of the IEEE International Conference on Neural Networks, vol.2, pp.341-348.[13]Kosko, B., 1992, Neural Networks for Signal Processing, Prentice-Hall, New Jersey. [14]Hopfield, J. J. and D. W. Tank, 1985,“Neural Computation of Decision in Optimizing Problems’’, Biological Cybernetics, vol.52, pp.141-152.[15]Ramanujam, J and Sadayappan, P., 1988,“Optimization by Neural Networks’’, Proceedings of the IEEE International Conference on Neural Networks, vol.2, pp.325-332.[16]Conway, R. W., Maxwell, W. L., Miller, L. W., 1967, Theory of scheduling Reading , MA：Addison-Wesley.[17]Richard P. Lippmann, 1987,“An introduction to computing with neural nets’’, IEEE ASSP Magazine, pp.4-22.[18]Chuan-Yu Chang, 1995, Non-Energy Based Neural Networks for Scheduling Job Shops, M.S. Thesis of Dep. of Electrical Engineering at National Taiwan Ocean University, Keelung, Taiwan.[19]Kai-Jei Chang, 1992, Using The Hopfield Type Neural Networks to Solve The Job-Shop Scheduling problem, M.S. Thesis of Dep. of Industrial management at National Cheng Kung University, Tainan, Taiwan.[20]D. N. Zhou, V. Charkassky, T. R. Baldwin, and D. W. Hong, 1991,“Scaling Neural Network for job-shop scheduling’’, IEEE Transactions on Neural Networks, vol.2, no.1, pp. 175-197.[21]Chuan-Yu Chang and Mu-Der Jeng, 1995,“A New Neural Network Model for the Job-Shop Scheduling Problem’’, Proc. Int. Sym. on Artificial Neural Networks 94, Tainan, Taiwan, pp.645-650, Dec..[22]T. M. Willems and J. E. Rooda, 1994,“Neural networks for job-shop scheduling’’, Control Eng. Practice, vol.2, no.1, pp.31-39.[23]T. M. Willems and L. E. M. W. Brandts, 1995,“Implementing heuristics as an optimization criterion in neural networks for job-shop scheduling’’, Journal of Intelligent Manufacturing, vol.6, pp.377-387.[24]Haibin Yu, et al., 1997, “A Neural-Based Approach to Production Scheduling”, Proceedings of the American Control Conference Albuquerque, New Mexico, vol.2, pp.1027-1031.[25]Haibin Yu and Wei Liang, 2001, “Neural network and genetic algorithm-based hybrid approach to expanded job-shop scheduling”, Computers & Industrial Engineering, vol.39, pp.337-356.[26]S. Y. Kung, 1993, Digital neural networks, Prentice-Hall, New Jersey.[27]Simon Haykin, 1999, Neural networks, Prentice-Hall, New Jersey.[28]J. H. Chou, 2001, Handout of Quality Engineering, Dept. of MAE, National Kaohsiung first University of Science and Technology.[29]Simon Y. Foo, Lisa R. Anderson and Yoshiyasu Takefuji, 1990, “Analog Compone- nts for the VLSI of Neural Networks”, IEEE Circuits and Devices Magazine, vol.6, no.4, pp.18-26.