研究生: |
蕭聖勳 Sheng-Hsun Hsiao |
---|---|
論文名稱: |
以導引模擬退火法求解不可延遲流程型生產排程問題之研究 Solving No-wait Flow Shop Scheduling Problems by Guided Simulated Annealing |
指導教授: |
葉瑞徽
Ruey-Huei Yeh |
口試委員: |
林義貴
Yi-Kuei Lin 喻奉天 Vincent F. Yu |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2008 |
畢業學年度: | 96 |
語文別: | 中文 |
論文頁數: | 62 |
中文關鍵詞: | 不可延遲流程型生產排程 、最大完工時間 、模擬退火法 、導引模擬退火法 |
外文關鍵詞: | No-wait flow shop scheduling, Makespan, Simulated Annealing, Guided Simulated Annealing |
相關次數: | 點閱:227 下載:3 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
在排程問題領域當中,面對生產環境限制常會有各種不同的問題產生,而不可延遲的限制便是其中之一,不可延遲意謂著工件一旦開始進入製程加工,從進入機器設備到加工結束,每道製程必須緊密的連接,其中不能有任何的暫停或是中斷;例如,煉鋼廠、化學及半導體製程等。本研究主要考慮三機不可延遲流程型生產排程,研究目的為極小化最大完工時間。本研究使用一個新的最佳化演算法─「導引模擬退火法」,來求解此問題,並與傳統模擬退火法比較求解品質及求解效率。結果發現,利用加入導引函數的功能,在求解極小化最大完工時間不可延遲流程型生產排程之中型與大型排程問題上,無論是在求解品質或求解效率,導引模擬退火法皆優於傳統之模擬退火法,顯示加入導引函數後,確實提升了傳統方法之求解品質與效率。
In the field of scheduling problems, a no-wait restriction may occur in the production environment. A no-wait scheduling problem indicates that an operation once started on a machine cannot be interrupted before its completion. There are no buffers allowed within each operation from job release to completion due to some technological constraints. Some examples with the no-wait restriction are the production lines in steel factories, chemical process, semiconductor fabrication facilities, and so on. This study considers three-machine no-wait flow shop scheduling problems. A new optimization algorithm, the Guided Simulated Annealing (GSA) is adopted to solve this problem such that the makespan is minimized. This scheduling problem is solved by using GSA and Simulated Annealing (SA). In order to compare the performance of GSA and traditional SA, we used solution quality and computation efficiency as the measuring criteria. From the numerical examples, we found that GSA is superior to SA in both solution quality and computation efficiency under mid-size and large-size scheduling problems.
中文部分
[1] 李世炳、鄒忠毅(2002),「簡介導引模擬退火法及其應用」,中央研究院物理雙月刊,廿四卷二期,頁307-319。
[2] 李宛柔(2007),「以基因演算法求解不可延遲批次排程問題之研究」,台灣科技大學工業管理系碩士論文。
[3] 林政德(2005),「三階段流程工廠在無閒置時間下之排程問題」,中原大學工業工程學系碩士論文。
[4] 張嘉君(2003),「應用模擬退火法求解營建工程專案多重資源排程最佳化之研究」,朝陽科技大學營建工程系碩士論文。
[5] 楊盛發(2006),「雙機連續性流程工廠總延遲時間最小化之排程問題研究」,朝陽科技大學工業工程與管理系碩士論文。
[6] 盧研伯(2003),「混合式模擬退火法應用於具迴流特性流程工廠之研究」,台灣科技大學工業管理系碩士論文。
英文部分
[7] Aldowaisan, T. (2001), “A new heuristic and dominance relations for no-wait flowshops with setups,” Computers and Operations Research, 28 (6), pp. 563-584.
[8] Aldowaisan, T. and A. Allahverdi (2003), “New heuristics for no-wait flowshops to minimize makespan,” Computers & Operations Research, 30 (8), pp. 1219-1231.
[9] Bertolissi, E. (2000), “Heuristic algorithm for scheduling in the no-wait flow-shop,” Journal of Materials Processing Technology, 107 (1-3), pp. 459-465.
[10] Cerny, V. (1985), “Thermo dynamical approach to the traveing salesman problem: An efficient simulated algorithm,” Journal of Optimization Theory and Applications, 45 (1), pp. 41-51.
[11] Gangadharan, R. and C. Rajendran (1993), “Heuristic algorithms for scheduling in the no-wait flowshop,” International Journal of Production Economics, 32 (3), pp. 285-290.
[12] Garey, M.R., D.S. Johnson, and R. Sethi (1976), “Complexity of flowshop and jobshop scheduling,” Mathematics of Operations Research, 1 (2), pp. 117-129.
[13] Gilmore, P.C. and R.E. Gomory (1964), “Sequencing a one state-variable machine: A solvable case of the traveling salesman problem,” Operations Research, 12, pp. 655–679.
[14] Hall, H.G. and C. Sriskandarajah (1996), “A survey of machine scheduling problems with blocking and no-wait in process,” Operations Research, 44 (3), pp. 510-525.
[15] Johnson, S.M. (1954), “Optimal two- and three-stage production schedules with setup times included,” Naval Research Logistics Quarterly, 1 (1), pp. 61-68.
[16] Kirkpatrick, S., C.D. Gelatt Jr., and M.P. Vecchi (1983), “Optimization by simulated annealing,” Science, 220 (4598), pp. 671-680.
[17] Metropolis, N., A.W. Rosenblush, M.N. Rosenblush, A.H. Teller, and E. Teller (1953), “Equation of state calculations by fast computing machines,” The Journal of Chemical Physics, 21 (6), pp. 1087-1092.
[18] Ogbu, F.A. and D.K. Smith (1990). “The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem,” Computers & Operations Research, 17 (3), pp. 243-253.
[19] Osman, I.H. and C.N. Potts (1989). “Simulated annealing for permutation flow-shop scheduling,” Omega, 17 (6), pp. 551-557.
[20] Piehler, J. (1960), “Ein Beitrag zum Reinhenfolge Problem,” Unternehmensforschung Operations Research, 4 (3), pp. 138-142.
[21] Raaymakers, W.H.M. and J.A. Hoogeveen (2000), “Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing,” European Journal of Operational Research, 126 (1), pp. 131-151.
[22] Rajendran, C. (1994), “No-wait flowshop scheduling heuristic to minimize makespan,” Journal of the Operational Research Society, 45 (4), pp. 472–478.
[23] Reddi, S.S. and C.V. Ramamoorthy (1972). “On the flow-shop sequencing problems with no wait in process,” Operational Research Quarterly, 23 (3), pp. 323–331.
[24] Rock, H. and G. Schmidt (1983), “Machine aggregation heuristics in shop-scheduling,” Methods of Operations Research, 45, pp. 303–314.
[25] Rock, H. (1984) “Some new results in flow shop scheduling,” Zeitschrift für Operations Research, 28 (1), pp. 1-16.
[26] Rock, H. (1984), “The three-machine no-wait flow shop is NP-Complete,” Journal of the ACM, 33, pp. 336-345.
[27] Wang, T.-Y., Y.-H. Yang, and H.-J. Lin (2006), “Comparison of scheduling efficiency in two/three-machine no-wait flow shop problem using simulated annealing and genetic algorithm,” Asia-Pacific Journal of Operational Research, 23 (1), pp. 41-59.