臺灣博碩士論文加值系統

本研究主要探討雙機流程工廠(Two-machine Flow shop)群組排程(Group Scheduling)總完工時間最小化之問題，且考慮了工作順序相依整備時間(Sequence-Dependent Setup Times)、工作順序相依拆卸時間(Sequence-Dependent Removal Times)及工作轉換時間(Transportation Times)等。群組排程問題是屬於NP-hard問題，而本研究的群組排程問題較之傳統群組排程問題更具一般性。
本研究提出一種新的粒子群演算法(Particle Swarm Optimization, PSO)編碼方式來求解雙機群組流程工廠排程問題，可同時求解群組與群組之間的排序以及群組內工作的排序，我們測試了162個隨機產生的測試問題，測試問題群組數最大為15，群組內的工作數最多為10，為了衡量所提PSO解題品質，本研究亦提出三種下界(Lower Bound)做為比對基準。從有限的數值模擬結果顯示，PSO於求解各種規模問題，解題品質相當良好，且本研究所提出三種下界亦能有效的作為衡量基準。

This paper investigates the two-machine flow shop group scheduling problem with job transportation times between machines, sequence-dependent setup and removal times. The objective is to minimize the total completion time. As known, this problem is a NP-hard problem that generalizes the typical two-machine group scheduling problems. In this paper, a PSO based algorithm with an effective coding scheme is proposed to effectively solve various 162 instances with group numbers up to 15. Note that the proposed coding scheme simultaneously determines the sequence of jobs in each group and the sequence of groups. In addition, three different lower bounds are developed to evaluate the effectiveness of the PSO algorithm. Limited numerical results show that the proposed PSO algorithm performs well for all test problems.

目錄
中文摘要 ............................................. i
英文摘要 ............................................. ii
誌謝 ............................................. iii
目錄 ............................................. iv
表目錄 ............................................. vi
圖目錄 ............................................. vii
一、緒論.............................................. 1
1.1 研究背景與動機機...................................1
1.2 研究範圍與目的的.................................. 3
1.3 研究架構與流程程.................................. 3
二、文獻整理與探討.................................... 5
2.1 排程問題的分類.................................... 5
2.2 工作順序相依整備時間、拆卸時間及移轉時間.......... 6
2.3 群組排程問題...................................... 8
三、研究方法......................................... 10
3.1 問題符號說明.................................. 10
3.2 問題描述及研究限制............................ 11
3.3 衡量指標與目標函數............................ 12
3.4 粒子群演算法.................................. 13
3.5 粒子群演算法應用相關範圍.......................17
3.6 應用的粒子群演算法編碼技巧.....................20
3.7 應用的粒子群演算法編碼技巧實例說明.............20
3.8 三種下界計算說明...............................21
3.8.1 第一種下界計算方式說明.......................23
3.8.2 第二種下界計算方式說明.......................23
3.8.3 第三種計算方式說明...........................24
3.9 實際範例模擬數據說明.........................25
四、數據模擬結果及分析.................................27
4.1 測試問題說明...................................27
4.2 測試問題參數設定及電腦硬體說明.................28
4.3 測試問題數據模擬結果及分析.....................30
五、研究結論與未來研究建議.............................42
參考文獻 ..............................................44
英文大綱
簡歷

表目錄
表1 運用SPV編碼方式轉換位置值之工作排程...............18
表2 運用ROV編碼方式轉換位置值之工作排程...............19
表3 粒子群演算法應用範圍之中文學位論文文..............19
表4 4個工作加工時間及轉換時間之數據...................22
表5 5個群組16個工作處理時間及工作轉換時間之模擬數據...25
表6 在第1部機器及第2部機器上的工作順序相依整備時間....25
表7 在第1部機器及第2部機器的後續工作順序相依拆卸時間..25
表8 小規模測試問題群組數及工作數......................27
表9 中規模測試問題群組數及工作數......................27
表10 大規模測試問題群組數及工作數......................27
表11 小規模測試問題編號及27種區間組合方式..............29
表12 表12-18之測試問題數據模擬結果整理.................30
表13 小規模測試問題數據模擬結果-1......................32
表14 小規模測試問題數據模擬結果-2..................... 33
表15 中規模測試問題數據模擬結果-1......................34
表16 中規模測試問題數據模擬結果-2......................35
表17 大規模測試問題數據模擬結果-1......................36
表18 大規模測試問題數據模擬結果-2..................... 37
表19 小規模測試問題最佳群組排序及CPU TIME..............38
表20 中規模測試問題最佳群組排序及CPU TIME..............39
表21 大規模測試問題最佳群組排序及CPU TIME-1........... 40
表22 大規模測試問題最佳群組排序及CPU TIME-2........... 41

圖目錄
圖1 研究流程圖....................................... 4
圖2 粒子群搜尋法示意圖............................... 14
圖3 PSO流程圖.........................................16
圖4 最佳工作排序為3-2-4-1，總完工時間為21............ 22
圖5 最佳工作排序為3-2-4-1右移結果.....................22
圖6 第i 個群組的Hi、Bi及TLi.......................... 22
圖7 最佳工作排序右移後加上工作整備時間及拆卸時間..... 23

參考文獻

中文部分

1.田國興(1999)，有設置時間之流程型工廠多階段平行機台總排z程時間，中原大學，碩士論文。
2.林伯睿(2008)，應用多目標粒子群演算法於緊急訂單重排程問題，雲林科技大學，碩士論文。
3.駱芳梧(2001)，考量整備及拆卸時間之開放型工廠排程問題研究，大葉大學，碩士論文。
4.賴阮明(2008)，整合粒子群最佳化與蜂群演算法求解彈性零工式生產排程問題之研究，台北科技學，碩士論文。
5.劉清祥(2004)，粒子群演算法於結構設計及零工式排程之應用，海洋大學，碩士論文。
6.郭奕宏(2009)，粒子群最佳化及其應用，台灣科技大學，博士論文。
7.黃浰娟(2006)，粒子群優法於有限資源多專案排程問題之應用研究，屏東科技大學，碩士論文。
8.邱文宏(2006)，使用粒子群最佳化於高優先權工作排程，交通大學，碩士論文。
9.冼祐臣(2008)，粒子群演算法於火力機組排程問題之研究，中原大學，碩士論文。
10.張鈺芳(2007)，考量整備時間與迴流限制之多階平行機台生產排程問題探討，雲林科技大學，碩士論文。
11.鄭舜源(2006)，應用限制式粒子群基因演算法於解決排程問題之研究，清雲科技大學，碩士論文。
12.鄒佳臻(2007)，粒子群演算法結合低閒置策略於生產排程之應用，中原大學，碩士論文。
13.陳建成(2009)，應用粒子群最佳化於單機排程問題之研究，台灣科技大學，碩士論文。
14.沈銘倫(2008)，應用模擬退火法與離散粒子群演算法在排列流程式排程問題研究，台北科技大學，碩士論文。
15.游擱鴻(1997)，以啟發式方法求解不相關平行機台排程問題，朝陽大學，碩士論文。
16.吳兆凱(2001)，發展具Holonic概之兩階段排程法，屏東科技大學，碩士論文。
17.王慶宗(2004)，應用群組技術減少生產調整時間之研究-以軟質膠布為例，東華大學，碩士論文。

英文部分

1.Aldowaisan, T. and Allahverdi, A. (1988), “Total flowtime in no-wait flowshops with separated setup times,” Computers and Operations Research, 25, pp.757-765.
2.Allahverdi, A., Ng, C.T., Cheng, T.C.E., and Kovalyov, M.Y. (2008), “A survey of scheduling problems with setup times or costs,” European Journal of Operational Research, 187, pp.985-1032.
3.Buzacott, JA. and Dutta, SK. (1971), “Sequencing many jobs on a multi-purpose facility, ”Naval Research Logistics Quarterly, 18,pp.75-82.
4.Baker, KR. (1990), “Scheduling groups of jobs in the two machine flowshop,” Mathematical and Computer Modelling, 13, pp.29-36.
5.Bean, J.C. (1994), “Genetic algorithm and random keys for sequencing and optimization,”ORSA Journal on Computing, 6(2), pp.154-160.
6.Carter,C.F.,Jr.(1972), “Trends in Machine Tool Development Applications, ” Proceeding of 2nd International Conference on Product Development and Manufacturing Technology, London : MacDonald & Co.
7.Corwin, BD. and Esogbue, AO. (1974), “Two-machine flowshop scheduling problems with sequence dependent setup times: A dynamic programming approach,” Naval Research Logistics Quarterly, 21, pp.515-524.
8.Cao, J. and Bedworth, DC. (1992), “Flow shop scheduling in serial multi-product processes with transfer and set-up times,” International Journal of Production Research, 30, pp.1819-1830.
9.Clerc, M. (2007), “Discrete particle swarm optimization for traveling salesman problem,” (http://clerc.maurice.free.fr/pso/).
10.Eberhart, R. C.and Kennedy, J. (1995), “A New Optimizer Using Particle Swarm Theory,” Proc. of the Sixth Int. Symposium on Micromachine and Human Science, Nagoya, Japan. pp. 39-43.
11.Garey, MD., Johnson, DS.and Sethi ,R.(1976) , “The complexity of flowshop and jobshop scheduling, ” Mathematics of Operations Research,1(2),pp.117-129.
12.Graham,R.L.,Lawler,E.L.,Lematra,J.K.,andRinnooyKan,A.H.G.(1979), “Optimization and approximation in deterministic sequencing and scheduling : a survey ,”Annals of Discrete Mathematics,5,pp.287-326.
13.Gupta, JND, Strusevich, VA.and Zwaneveld, C.(1997), “ Two-stage no-wait scheduling models with setup and removal times, ” Computers and Operations Research ,24,pp.1025-1031.
14.Ham, I., Hitomi, K. and Yoshida,T. (1985) Group technology: applications to production management. Hingham MA: Kluwer Academic Publishers.
15.Johnson, S. M. (1954), “Optimal two-and three-stage production schedules with setup times included,” Naval Research Logistics Quarterly, 1, pp.61-68.
16.Jain, A.S. and Meeran, S. (1999), “Deterministic job-shop scheduling: past ,present and future,” European Journal of Operational Research,113,pp.390-434.
17.Lin, S. and Kernighan, B. W. (1973), “An Effective Heuristic Algorithm for the Traveling Salesman Problem,” Operations Research, 21, pp.448-516.
18.Liu, Z., Yu, W. and Cheng, T. C. E. (1999), “Scheduling Groups of Unit Length Jobs on Two Identical Parallel Machines,” Information Processing Letters, 69(6), pp.275-281.
19.Lian Z., Jiao, B., and Gu, X. (2006), “A similar particle swarm optimization algorithm for job-shop scheduling to minimize makespan,”Applied Mathematics and Computation, 183(2), pp. 1008-1017.
20.Logendran, R., Salmasi, N. and Sriskandarajah, C. (2006), “Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups,” Operations Research, 33, pp.158-180.
21.Lian, Z., Gu, X. and Jiao, B. (2006), “A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan,” Applied Mathematics Computation, 175(1), pp.773–785.
22.Liu,B., Wang, L. and Jin ,YH.(2008), “An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers, ”Computers Operations Research ,35(9),pp.2791-2806.
23.Maggu, P. L. and Das, G. (1980), “On 2×n Sequencing Problem with Transportation Times of Jobs,” Pure and Applied Mathematic Sciences, 12, pp.1-6.
24.Nasser S., Rasaratnam, L. and Mohammad RS. (2010), “Total flow time minimization in a flowshop sequence-dependent group scheduling problem,” Computers Operations Research, 37(1), pp.199-212
25.Ozgur, C. O. and Brown, J. R. (1995), “A Two-Stage Traveling Salesman Procedure for the Single Machine Sequence-Dependent Scheduling Problem,” Omega, International Journal Management Science, 23(2), pp.205-219.
26.Presby, JT., Wolfson, ML. (1967), “An algorithm for solving job sequencing problems,” Management Science, 13, pp.454-464.
27.Panwalkar, S.S., Dudek, R.A., and Smith, M.L. (1973), “Sequencing research and the industrial scheduling problem,” Symposium on the theory of scheduling and its applications, pp. 29-38.
28.Sahni,S. and Cho,Y. (1979), “Complexity of scheduling shops with no-wait in process, ” Mathematics of Operations Research, 4 , pp.448-457.
29.Shi, Y. and Eberhart, R.C. (1998), “Parameter selection in Particle swarm optimization. In: PortoVW, Saravanan N, Waagen D, Eiben AE, editors. Proceedings of 7th International conference on evolutionary programming,” New York: Springer, pp. 591-600.
30.Schaller, JE. , Gupta, JND.and Vakharia, AJ. (2000), “Scheduling a flowline manufacturing cell with sequence dependent family setup times,” European Journal of Operational Research, 125, pp.324-329.
31.Salman, A., Ahmad, I., and Al-Madani, S. (2002), “Particle swarm optimization for task assignment problem,” Microprocessors and Microsystems,pp. 363-371.
32.Taha, H. (1971), “Sequencing by implicit ranking and zero-one polynomial programming,” AIIE Transactions, 3, pp.299-301.
33.Tasgetiren, M. F., Sevkli, M., Ling,Y.C., and Gencyilmaz, G. (2004), “Particle swarm Optimization algorithm for permutation flowshop sequencing problem, ” Lecture Notes in Computer Science. Springer -Verlag, 3172, pp. 382-390.
34.Van den Bergh F and Engelbrecht AP(2000), “Cooperative learning in neural network using particle swarm optimizers, ” South African Computer Journal ,26,pp.84-90.
35.Wortman, DB. (1992), “Managing capacity: getting the most from your firm''s assets,” Industrial Engineering, 24, pp.47-49.
36.Yang, D. L. and Chern, M. S. (2000), “Two-Machine Flowshop Group Scheduling Problem,” Computers and Operations Research, 27(10), pp.975-985.
37.Yoshida, T. and Hitomi, K. (1979), “Optimal two-stage production scheduling with setup times separated,” IIE Transactions, 11, pp.261-263.
38.Yoshida, H., Kawata K., Fukuyama, Y. and Nakanishi, Y. (2000), “A particle swarm optimization for reactive power and voltage control considering voltage security assessment,” IEEE Power System, 15, pp. 1232-1239.
39.Zolfaghari, S. and Liang, M. (1999), “Jointly Solving the Group Scheduling and Machining Speed Selection Problems: a Hybrid Tabu Search and Simulated Annealing Approach,” International Journal of Production Research, 37 (10), pp.2377-2397.