臺灣博碩士論文加值系統

在不同的生產系統中，因為製造機具或是物料特性，對於其生產排程具有不同的要求，如Blocking是本研究中排程問題所探討之特別現象。所謂Blocking現象是指工作一旦進入製造系統當中，在機器與機器之間不可以有閒置時間，即物料於走完其完整的途程中，不離開生產機具，而且在其完成途程的同時，也完成製程中所有工作。(Yao, et al., 2000)
本研究中所考慮的為二機開放工場且具有工作連接性限制現象的排程問題：假定工作在兩機台的處理時間均已給定，本研究的目標為將n個工作排入此二機開放工場排程中，求其總製程時間之極小化。而根據Graham., et al., (1979)所提出之排程問題標準化標記方法，我們將這個問題標記為O2|Blocking|Cmax問題。
相關文獻中曾經指出，在工作連接性限制的現象下，用於二機開放工場的排程問題，其複雜度(Complexity)為NP-hard，而本研究中使用了兩個啟發式演算法，利用MATLAB程式實際求解並測試O2|Blocking|Cmax問題，期望在兼顧解答品質與求解時間的雙重考慮之下，找出適合本研究問題的演算法，並建議決策者演算法中適用參數的設定，以期快速、有效針對此問題提供一個令決策者滿意的答案。
本研究中所探討第一種演算法，隨機搜尋演算法(Random Search Algorithm; RSA)是根據Yao, et al.(2000)所提出；第二種演算法是眾多文獻中均證明對於組合最佳化問題有相當優異求解能力之基因演算法(Genetic Algorithm)，本研究之主要貢獻除了實作程式外針對RSA參數部分進行敏感度分析。並且比較兩個演算法的解答品質(Solution Quality)與求解時間(Run-time)，提供決策者在不同決策環境下設定RSA演算法參數之法則。

In this paper, considering a two-machine scheduling problem in an openshop with blocking jobs. We are given the processing times of n blocking jobs on both machines, and the objective is to minimize the makespan. Symbolically, we are dealing with the problem O2|Blocking|Cmax.
Here tests two algorithms “Random Search Algorithm (RSA)” and “Genetic Algorithm (GA)” respectively. The results of RSA gave two parameters in adjust to algorithm,Υandβ. Decision table is also suggested in the thesis’ document. The result is that the performance of RSA is more efficiently than GA under these setting proposed in the paper to this problem.
The results from our numerical experiments suggest that one should use LOX (Linear Order Crossover) and PBM (Position-Based Mutation) as the genetic operators if one would like use the genetic algorithm (GA) to solve the O2|Blocking|Cmax problem. And, we state useful guidelines for parameter settings in GA, for instance, population size, crossover rate, mutation rate and number of generations, etc. From the 600 random examples, we also observe that the number of jobs and the variance of the processing time for the jobs significantly affect the performance of the GA. Indeed, our study provides valuable decision support information for the decision makers who uses the GA to improve the solution quality in solving the O2|Blocking|Cmax problem.

中文摘要I
英文摘要II
誌謝III
目錄IV
圖目錄VII
表目錄IX
第一章 緒論1
1.1前言1
1.2研究動機2
1.3 研究範圍與限制3
1.3.1. 流程工場、開放工場、零工工場4
1.3.2 不等候特性及工作連接性問題5
1.4研究架構6
1.5預期研究貢獻7
第二章 文獻探討9
2.1 排程問題概述9
2.2 二機開放工場具有工作連接性問題12
2.3 遺傳基因演算法及其在排程問題的應用14
2.3.1 遺傳基因演算法說明及應用14
2.3.2基因演算法應用於流程工場排程問題16
2.3.3基因演算法應用於零工工場排程問題16
2.3.3基因演算法應用於開放工場排程問題17
2.4 排程效率的衡量指標18
2.4.1解答品質及時間的衡量指標18
第三章 隨機搜尋演算法20
3.1隨機搜尋演算法簡介20
3.2 二機流程工場為基之演算法24
3.3二元最佳近似法28
3.3 隨機探索計畫31
3.5隨機搜尋演算法(RSA)相關設定33
3.4.1 RSA參數說明及設定34
3.4.2 RSA的終止條件36
第四章 遺傳基因演算法37
4.1 遺傳演算法簡介37
4.1.1 遺傳演算法架構37
4.1.2遺傳演算法的優缺點40
4.2遺傳演算法的運算機制及運算因子42
4.2.1編碼(Encoding )42
4.2.2染色體(Chromosome )43
4.2.3初始族群(Initialize Population )43
4.2.4適應函數(Fitness Function )44
4.2.5選擇與複製(Selection and Reproduction )45
4.2.6交配(Crossover)46
4.3遺傳演算法(GA)的設定51
4.3.1基本設定51
4.3.2 GA參數的設定52
4.3.3遺傳演算法的終止條件59
第五章 演算法之比較與數據分析61
5.1實證範例描述61
5.2演算法排程效率及綜合比較63
5.2.1隨機搜尋演算法排程結果63
5.2.2遺傳基因演算法的排程結果67
5.2.3兩演算法排程結果之比較71
第六章 結論及建議85
6.1 結論85
6.2未來研究方向86
參考文獻88
附錄A92
A.1 Gilmore &Gomory方法所描述問題及狀態敘述92
A.2 Gilmore &Gomory演算法範例(Numerical Example)98
附錄B106
B.1 使用RSA求解O2|Blocking|Cmax問題概念之介紹106

1.Adeli, H. and Hung, S. L., (1995), “Machine learning ：Neural networks, Genetic algorithm, and Fuzzy system”, New York: John Wiley & Sons, Inc,
2.Baker, K.R., (1974), Introduction to Sequencing and Scheduling, Wiley, New York
3.Bock, F., (1958), “An Algorithm for Solving Traveling Salesman and Related Network Optimization Problems”, 14th National Meeting of the ORSA, St. Louis, Mo., Oct. 24
4.Christofides, N. and Eilon, S. (1972), “Algorithms for large scale traveling salesman problem”, Operational Research Quarterly, 23, 511 - 518.
5.C. -F. Liaw, (2000), “A hybrid genetic algorithm for the open shop scheduling problem” European Journal of Operation Research Vol.124 pp.28-42
6.Cleveland, G. A. and S. F. Smith, (1989), “Using Genetic Algorithm to Solving Flow Shop Release” Proceeding of the Third International Conference Genetic Algorithm, pp.160-169.
7.Cores, A., (1958), A Method for Solving Traveling Salesman Problems, Operations Research Vol. 5, pp.791-812
8.Croce, F. D. Tadei, R. and Volta G., (1995), “A Genetic Algorithm for the JobShop problem, ” Computer and Operation Research vol. 22(1), pp.15-24
9.Falkenauler E. and Bouffouix S., (1991), “A Genetic Algorithm for JobShop Scheduling, ” Proceedings of the 1991 IEEE International Conference on Robotics and Automation Sacramento, April, pp. 824-829
10.Gilmore, P. C. and Gomory, R.E. (1964), “Sequencing a one state variable machine: a solvable case of the traveling salesman problem”, Operations Research, Vol. 12, pp.655 - 679.
11.Golden, B., L. Bodin, T. Doyle, and W. Stewart, Jr., (1980), “Approximate Traveling Salesman Algorithms”, Operation Research Vol. 28 pp.694-711
12.Goldberg, D. E., (1989), “Genetic Algorithm in Search, Optimization, and Machine Learning”, Addison—Wesley, Mitchell,
13.Goldberg, D. E., (1994), “Genetic and evolutionary algorithm come of age”, Communications of the ACM, Vol.37, No.3, pp.113 - 1(19
14.Glover, F. and Laguna M., (1993), “Tabu Search”, Chapter 3 in Annals of Operations Research, 41.
15.Gonzalez, T. and Sahni, S., (1976), “Open shop scheduling to minimize finish time”, Journal of the Association for Computing Machinery, 23, 665 - 697.
16.Graham, R.L., Lawler E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G. (1979), “Optimization and approximation in deterministic sequencing and scheduling: a survey”, Annals of Discrete Mathematics, 5, 287 - 326.
17.Gupta M. C., Gupta Y. P., and Kumar A., (1993), “Minimizing Flow time Variance in a Single machine system using Genetic Algorithms”. European Journal of Operation Research, Vol.86 pp. 289-303
18.Hall, N.G. and Sriskandarajah, C. (1996), “A survey of machine scheduling problems with Blocking and no-wait in process”, Operations Research, Vol. 44, pp. 510 - 525.
19.Hanselman, D. and Littlefield, B. (1996), Mastering Matlab: A Comprehensive Tutorial and Reference, Prentice Hall, Upper Saddle River, New Jersey.
20.Holland, J.H., (1992), Adaptation in Natural and Artificial System: an introductory analysis with applications to biology, control, and artificial intelligence, MIT press.
21.Johnson, S.M. (1954), “Optimal two and three-stage production schedules with setup times included”, Naval Research Logistics Quarterly, 1, 61 - 68.
22.Kammoun, H. and Sriskandarajah, C. (1993), “The complexity of scheduling jobs in repetitive manufacturing systems”, European Journal of Operational Research, 70, 350 - 364.
23.Kirkpatrick, S., C.D. Gelatt, Jr. and Vecchi M.P. (1983), “Optimization by simulated annealing”, Science, Vol. 220, pp.671-680.
24.Kyparisis, G.J. and Koulamas, C., (2000),"Open Shop Scheduling with Makespan And Total Completion Time Criteria," Computers & Operations Research, Vol.27, No.1, pp.15-27
25.Lawler, E. L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys, D.B., (1989), "Sequencing and Scheduling: Algorithms and Complexity," Report BS-R8909, Centre for Mathematics and Computer Science, P.O. Box 4079, 1009 AB Amsterdam, The Netherlands.
26.Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys D.B. (1985), The Traveling Salesman Problems, John Wiley & Sons, New York.
27.Lin, S., and B. W. Kernighan, (1973), “An Effective Heuristic Algorithm for the Traveling - Salesman Problem”, Operation Research Vol. 21, pp. 498-516
28.Lin, S., (1965), “Computer Solutions of the Traveling Salesman Problem”, Bell System Technical Journal Vol. 44, pp. 2245-2269
29.Logendran, R. and Sriskandarajah, C. (1993), “Two-machine group scheduling problem with Blocking and anticipatory setups”, European Journal of Operational Research, Vol.69, pp. 467 - 481.
30.Melanie, (1996). “An Introduction to Genetic Algorithm”, MIT Press,
31.Punnen, A.P. and Aneja, Y.P. (1995), “A tabu search algorithm for the resource-constrained assignment problem”, The Journal of the Operational Research Society, 46, 214 - 220.
32.Pinedo, M. (1995), “Scheduling: Theory, Algorithm, and Systems,” Prentice Hall, Englewood Cliffs, New Jersey.
33.Sahni, S. and Cho, Y. (1979), “Complexity of scheduling jobs with no-wait in process”, Mathematics of Operations Research, 4, 448 - 457.
34.Sriskandarajah, C. and Ladet, P. (1986), “Some no-wait shops scheduling problems: complexity aspects”, European Journal of Operational Research, 24, 424 - 438.
35.Tang, K.F., Man, K.S., and Kwong, S., (1996), “Genetic Algorithms ：concepts and applications”, IEEE Transactions On Industrial Electronics, Vol.43, No.5, pp.519 -533,
36.Vairaktarakis, G., and Sahni, S. (1995), “Dual criteria preemptive open-shop problems with minimum makespan”, Naval Research Logistics, Vol. 42, pp. 103-121.
37.Van Laarhoven, P.J.M. and Aarts, E.H.L. (1987), Simulated Annealing: Theory and Practice, Kluwer Academic Publishers, Dordrecht, The Netherland.
38.West, D. (1996), Introduction to Graph Theory, Prentice Hall, Upper Saddle River, New Jersey.
39.Whitley, D, T., Starkweather and D’Ann Fuquay,(1989), “Scheduling problems and Traveling Salesman: the genetic edge recombination operator,” Proceedings of the Third Inernational. Conference Genetic Algorithm, pp.133-140.
40.Yao, M. J., Hanijanto S., and Elmaghraby S. E., (2000), “Simple Heuristics for Thee two Machine Openshop Problem With Blocking”, Journal of the Chinese Insititute of Industrial Engineers, Vol. 17 No. 5 pp. 537-547.
41.王立志, (1994), 現場排程簡介, 東海大學工業工程系。
42.林信成、彭啟峰,(1994), OH ! Fuzzy 模糊理論剖析，第三波發行。
43.林恆貞,(1998), “重複性製造系統排程效率之比較─以No-wait Problem為例”,成功大學工業管理研究所碩士論文。
44.陳建良, (1995), “排程概述”, 機械工業雜誌, pp.122-133 ，12 月。
45.陳國偉, (1997), “平行-串連流程工廠中總延遲時間最小化之研究：IC 封裝作業之應用”, 國立雲林科技大學工業工程與管理研究所碩士論文。
46.鄧浩敦,(2000), “混合基因演算法於流程工場排程之應用”, 逢甲大學工業工程研究所碩士論文。
47.蘇木春、張孝德,(1997), 機器學習類神經網路、模糊系統以及基因演算法則，全華科技出版，。
48.楊宗銘,(1995), “遺傳演算法在多途程排程問題之探討”，中原大學工業工程研究所碩士論文。
49.羅友廷,(1999), “模糊多目標混合式遺傳演算法在零工式排程系統之應用”,東海大學工業工程研究所碩士論文
50.http://cindy.cis.nctu.edu.tw/ 交通大學資訊科學研究所。