跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/08/02 11:47
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:洪于婷
研究生(外文):Yu-TingHung
論文名稱:發展以NEH為基礎之演算法求解流程式生產問題
論文名稱(外文):A heuristic based on NEH for the flow shop scheduling problem
指導教授:張秀雲張秀雲引用關係
指導教授(外文):Shiow-Yun Chang
學位類別:碩士
校院名稱:國立成功大學
系所名稱:工業與資訊管理學系碩博士班
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:72
中文關鍵詞:流程式生產NEH總完工時間
外文關鍵詞:Flow shop schedulingNEHTotal completion time
相關次數:
  • 被引用被引用:0
  • 點閱點閱:512
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
  本研究考慮排序不變更的流程式生產排程(Permutation flow shop scheduling)問題,並探討此流程式生產問題的總完工時間(total completion time)。首先對此問題建立數學模式,由於此問題為一個NP-complete,數學模式僅在工件及機器數量少的情況下才能在短時間內求得最佳解,一旦工件及機台數量增加,無法在有限的時間內求得最佳解。故本研究改善Laha and Chakravorty在2011年所提出的演算法並發展以NEH演算法為基礎的啟發式演算法求解近似最佳解,使得演算法可行解更能增加其多樣性,進而使得近似解的品質能夠更加提升。
  本研究利用四種起始解產生方式進一步測試起始解的改變對演算法結果的影響,經過測試後發現,由Increasing及SPT產生起始解效果最好,此外,本研究加入了交換步驟改善Laha and Chakravorty演算法,使得演算法流程中所產生的可行解能夠更多樣化。先針對演算法內的參數做分析,再分析保留排序數量的多寡,再與標竿問題進行績效評估,以驗證演算法之有效性。
  績效評估結果顯示,本研究演算法在工件數20至100的範圍內會有較明顯的改善效果,而工件數超過100,隨著交換數量變多,演算法執行時間會因為大量計算而激增,且演算法執行時間浪費的成本可能遠超改善效果的時間,故本研究演算法在工件數小於100時會是較佳的選擇。

  This study considers a permutation flow shop scheduling problem and explores the total completion time of this problem. Because it is NP-complete problem, the optimal solution can be obtained in a short period of time only in the case of small number of jobs and machines by solving its mathematical model. Once the increase in the number of the jobs and the machines , the optimal solution can not be obtained within limited time. This study improves the algorithm proposed by Laha and Chakravorty in 2011 and based on NEH algorithm to solve this problem, it makes the algorithm feasible solution diversity, thus the quality of the approximate solution can be improved.
  This study tests four initial solutions (Increasing, Decreasing, SPT, LPT) and finds the quality resulted from Increasing and SPT work better. Besides, this study adds switching steps into the Laha and Chakravorty algorithm to make the feasible solution generate more diverse. After analysis the parameters within the algorithm, and apply them to obtain the reserve number, the proposal algorithm is apply to benchmark problems to verify the algorithm is effective.
  According to the results of performance evaluation, the proposal algorithm has obvious improvement for the problem with 20-100 jobs, once the number of jobs is over 100, with more switching, the algorithm execution time will increase quickly, the cost caused by execution time may be higher than the cost reduced by improvement time, so it is a good choice to use this algorithm when the number of jobs is less than 100.

摘要 i
Abstract ii
誌謝 iii
目錄 iv
表目錄 vii
圖目錄 ix
第一章 緒論 1
1.1 研究動機與目的 1
1.2 研究範圍 2
1.3 研究架構與流程 3
第二章 文獻探討 4
2.1 最佳化解法 4
2.2 啟發式解法 5
2.2.1 NEH演算法 5
2.2.2 基因演算法 8
2.2.3 禁忌搜尋法 9
2.2.4 模擬退火法 11
2.2.5 蟻群演算法 12
2.2.6 其他演算法 14
2.3 派工法則 15
2.4 小結 16
第三章 研究方法 17
3.1 研究限制 17
3.2 問題描述與模式建構 18
3.3 NEH演算法 19
3.3.1 NEH演算法之步驟 19
3.3.2 NEH演算法之簡例說明 20
3.4  Laha and Chakravorty演算法 22
3.5 發展演算法 23
3.5.1 演算法之簡例說明 26
第四章 數據分析與啟發式演算法績效評估 29
4.1 模式資料設定與作業環境 29
4.2 演算法績效評估方式 30
4.3 測試問題產生與數據分析 30
4.3.1 不同起始解之績效值比較 30
4.3.2 不同起始解對Laha and Chakravorty演算法架構績效的影響 32
4.3.3 N1變化對改進後演算法績效的影響 35
4.3.4 N2變化對改進過後演算法的執行時間之影響 42
4.3.5 參數確定下k值之分析 44
4.3.6 小問題下的Lingo與改進過後的演算法比較結果 45
4.3.7 標竿問題之比較 46
4.4 小結 48
第五章 結論 50
5.1 研究貢獻與限制 50
5.2 未來研究方向 51
參考文獻 52
附錄A 不同起始解所產生的績效值比較 56
附錄B 不同起始解在Laha and Chakravorty演算法結構之結果 68
附錄C 不同起始解在本研究演算法之影響 72

中文部分:
柯惠雯,結合模擬退火法與禁忌搜尋法在流程式生產排程之應用,大葉大學工業工程研究所碩士論文,民國89年。

英文部分:
Ben-Daya, M., & Al-Fawzan, M. (1998). A tabu search approach for the flow shop scheduling problem. European Journal of Operational Research, 109(1), 88-95.
Bertolissi, E. (2000). Heuristic algorithm for scheduling in the no-wait flow-shop. Journal of Materials Processing Technology, 107(1-3), 459-465.
Dong, X., Huang, H., & Chen, P. (2008). An improved NEH-based heuristic for the permutation flowshop problem. Computers & Operations Research, 35(12), 3962-3968.
Framinan, J., & Leisten, R. (2003). An efficient constructive heuristic for flowtime minimisation in permutation flow shops. Omega-International Journal of Management Science, 31(4), 311-317.
Ignall, E., & Schrage, L. (1965). Application of the branch and bound technique to some flow-shop scheduling problems. Operations Research, 13(3), 400-412.
Ishibuchi, H., Misaki, S., & Tanaka, H. (1995). Modified simulated annealing algorithms for the flow shop sequencing problem. European Journal of Operational Research, 81(2), 388-398.
Iyer, S. K., & Saxena, B. (2004). Improved genetic algorithm for the permutation flowshop scheduling problem. Computers & Operations Research, 31(4), 593-606.
Kalczynski, P. J., & Kamburowski, J. (2007). On the NEH heuristic for minimizing the makespan in permutation flow shops. Omega-International Journal of Management Science, 35(1), 53-60.
Kellegoz, T., Toklu, B., & Wilson, J. (2008). Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem. Applied Mathematics and Computation, 199(2), 590-598.
Laha, D., & Chakraborty, U. K. (2009). A constructive heuristic for minimizing makespan in no-wait flow shop scheduling. International Journal of Advanced Manufacturing Technology, 41(1), 97-109.
Laha, D., & Chakravorty, A. (2011). A new heuristic for minimizing total completion time objective in permutation flow shop scheduling. International Journal of Advanced Manufacturing Technology, 53(9-12), 1189-1197.
Laha, D., & Sapkal, S. U. (2011). An Efficient Heuristic Algorithm for m-Machine No-Wait Flow Shops. Proceedings of the International MultiConference of Engineers and Computer Scientists, 1, Hong Kong.
Laha, D., & Sarin, S. C. (2009). A heuristic to minimize total flow time in permutation flow shop. Omega-International Journal of Management Science, 37(3), 734-739.
Levner, E. (1969). Optimal planning of parts machining on a number of machines. Automation and Remote Control, 12(1), 1972-1978.
Li, X., Wang, Q., & Wu, C. (2009). Efficient composite heuristics for total flowtime minimization in permutation flow shops. Omega-International Journal of Management Science, 37(1), 155-164.
McCormick, S. T., Pinedo, M. L., Shenker, S., & Wolf, B. (1989). Sequencing in an assembly line with blocking to minimize cycle time. Operations Research, 37(6), 925-935.
Murata, T., Ishibuchi, H., & Tanaka, H. (1996). Multi-objective genetic algorithm and its applications to flowshop scheduling. Computers & Industrial Engineering, 30(4), 957-968.
Nawaz, M., Enscore Jr, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega-International Journal of Management Science, 11(1), 91-95.
Pan, Q. K., & Wang, L. (2011). Effective heuristics for the blocking flowshop scheduling problem with makespan minimization. Omega-International Journal of Management Science, 40(2), 218-229.
Pour, H. D. (2001). A new heuristic for the n-job, m-machine flow-shop problem. Production Planning & Control, 12(7), 648-653.
Rad, S. F., Ruiz, R., & Boroojerdian, N. (2009). New high performing heuristics for minimizing makespan in permutation flowshops. Omega-International Journal of Management Science, 37(2), 331-345.
Rajendran, C., & Ziegler, H. (2005). Two ant-colony algorithms for minimizing total flowtime in permutation flowshops. Computers & Industrial Engineering, 48(4), 789-797.
Reeves, C. R. (1995). A genetic algorithm for flowshop sequencing. Computers & Operations Research, 22(1), 5-13.
Ribas, I., Companys, R., & Tort-Martorell, X. (2010). Comparing three-step heuristics for the permutation flow shop problem. Computers & Operations Research, 37(12), 2062-2070.
Ronconi, D., & Armentano, V. (2001). Lower bounding schemes for flowshops with blocking in-process. Journal of the Operational Research Society, 52(11), 1289-1297.
Ronconi, D. P. (2004). A note on constructive heuristics for the flowshop problem with blocking. International Journal of Production Economics, 87(1), 39-48.
Ronconi, D. P. (2005). A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking. Annals of Operations Research, 138(1), 53-65.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
Vallada, E., & Ruiz, R. (2010). Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem. Omega-International Journal of Management Science, 38(1-2), 57-67.
Wang, L., Pan, Q. K., & Tasgetiren, M. F. (2011). A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem. Computers & Industrial Engineering, 61(1), 76-83.
Zhang, Y., Li, X., & Wang, Q. (2009). Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization. European Journal of Operational Research, 196(3), 869-876.
Zheng, D. Z., & Wang, L. (2003). An effective hybrid heuristic for flow shop scheduling. International Journal of Advanced Manufacturing Technology, 21(1), 38-44.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top