跳到主要內容

臺灣博碩士論文加值系統

(35.175.191.36) 您好!臺灣時間:2021/07/30 18:25
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳軍翰
研究生(外文):Chun-Han Chen
論文名稱:具訂單拒絕之流程型製造單元排程
論文名稱(外文):Flowshop manufacturing cell scheduling problems with rejection
指導教授:應國卿應國卿引用關係
口試委員:張玉鈍黃乾怡
口試日期:2012-07-16
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:工業工程與管理系碩士班
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:81
中文關鍵詞:和絃演算法流程型製造單元工廠順序相依整備時間拒絕訂單
外文關鍵詞:Harmony SearchSequence-dependent family setup timesFlowshop manufacturing cellRejection
相關次數:
  • 被引用被引用:2
  • 點閱點閱:182
  • 評分評分:
  • 下載下載:24
  • 收藏至我的研究室書目清單書目收藏:0
群組製造 (cellular manufacturing) 已普遍運用於高度客製化及複雜化的小至中批量生產,實務上的廣泛運用使得具有順序相依整備時間之流程型製造單元排程問題 (flowline manufacturing cell scheduling problem with sequence-dependent family setup times) 成為近年來排程領域活躍的研究課題之一。本研究擬探討具有訂單拒絕之流程型製造單元排程問題,因在有限產能的限制下,實務上廠商不一定能在要求的期限內完成所有的訂單,若超過最後期限可能會造成顧客的不滿,導致懲罰成本的發生,所以若能拒絕無法順利完成的訂單會增加公司的獲利能力,因此,引發本研究探討具有訂單拒絕之流程型製造單元排程問題並提出和弦演算法,用以求解最大化總收益問題,以使得多樣少量的生產能得到類似大量生產型態的經濟效應。為了驗證此演算法,在小問題上,我們與最佳解法做比較以驗證其求解績效,由實驗結果得知在小問題上其差異不大但隨著工件數增加,原始的和弦的求解品質會越來越差,我們相信此研究可以帶給之後想要繼續往下做的人一點啟發。

The Flowshop manufacturing cell scheduling problem (FMCSP) with sequence-dependent family setup times (SDFSTs) has become a key area in the field of scheduling. We want to discuss the FMCSPs with rejection because the company capacity is limited in the real word. We can not satisfy every customer. Therefore, we need to know how to choose the right orders, because if we can not finish the product before the customer’s deadline, the product will lose its value. Moreover, the customers will lose their confidence toward us.
In this study, a harmony search algorithm was presented for this problem is to maximize total revenue. To validate the performance of the proposed approach, we use Harmony Search, Revised Harmony Search, Brute-Force Search to deal with small problem. On the other hand, to deal the big problem, we use HS and RHS to compare their efficiency. The computational results showed that the RHS significantly outperforms the original HS in big problems. It is believed that it can serve as a new benchmark approach for future research.


摘 要............................... i
ABSTRACT............................. ii
誌謝................................. iii
目錄................................. iv
表目錄............................... vi
圖目錄............................... vii
第一章 緒論......................... 1
1.1 問題背景與動機................ 1
1.2 研究目的...................... 2
第二章 文獻探討...................... 6
2.1 流程型製造單元排程問題........ 6
2.2拒絕訂單之文獻................. 10
2.3 和弦演算法(HS)................ 13
2.3.1 和弦演算法背景及原理...... 13
2.3.2 和弦演算法之步驟與流程.... 15
2.3.3 和弦演算法之相關應用...... 22
第三章 研究方法...................... 23
3.1 數學符號之定義................ 23
3.2流程型製造單元排程問題之數學模式 26
3.3改良式和弦演算法之設計......... 29
3.3.1 RHS之虛擬程式碼........... 31
3.3.2 初始解建構之方法.......... 32
3.3.3和弦演算法之編碼........... 32
3.3.4和弦演算法新解產生之方法... 34
3.3.5拒絕訂單的方法............. 35
3.3.6和弦演算法演算過程......... 37
第四章 實驗結果及分析............... 38
4.1 設計實驗部分.................. 38
4.2 迭代數分析.................... 39
4.3 小型問題實驗結果分析.......... 49
4.4 大型問題實驗結果分析.......... 56
4.5 統計檢定...................... 68
4.6拒絕率分析..................... 70
第五章 結論與建議.................... 72
5.1 結論.......................... 72
5.2 研究貢獻...................... 72
5.3 未來研究與建議................ 73
參考文獻............................. 74


[1] J.N.D. Gupta and W.P. Darrow, "The two-machine sequence dependent flowshop scheduling problem," European Journal of Operational Research, Vol. 24, No. 3, 1986, pp. 439-446
[2]M. Frosolini, M. Braglia and F.A. Zammori, "A modified harmony search algorithm for the multi-objective flowshop scheduling problem with due dates," International Journal of Production Research, Vol 49, No. 20, 2011, pp. 5957-5985
[3] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G.R. Kan "Optimization and approximation in deterministic sequencing and scheduling: a survey," Annals of Discrete Mathematics, Vol. 5, 1979, pp. 287-326
[4] A. Allahverdi, J.N.D. Gupta and T. Aldowaisan "A review of scheduling research involving setup considerations," International Journal of Management Science, Vol. 27, No. 2, 1999, pp. 219-239
[5] T.C.E. Cheng, J.N.D. Gupta and G. Wang "A review of flowshop scheduling research with setup times," Production and Operations Management, Vol. 9. No. 3, 2000, pp. 262-282
[6] S.H. Hendizadeh, H. Faramarzi, S.A. Mansouri, J.N.D. Gupta, and T.Y. ElMekkawy, "Meta-heuristics for scheduling a flowline manufacturing cell with sequence dependent family setup times," International Journal of Production Economics, Vol. 111, No. 2, 2008, pp. 593-605
[7] S.W. Lin, J.N.D. Gupta, K.C. Ying, Z.J. Lee, "Using simulated annealing to schedule a flowshop manufacturing cell with sequence-dependent family setup times," International Journal of Production Research, Vol. 47, No. 12, 2009, pp. 3205-3217
[8] S.R. Das and C. Canel, "An algorithm for scheduling batches of parts in a multi-cell flexible manufacturing system," Int. J. Production Economics, Vol. 97, 2005, pp. 247-262
[9] J.N.D. Gupta and J.E. Schaller, "Minimizing flow time in a flowline manufacturing cell with family setup times," Journal of the Operational Research Society, Vol. 57, 2006, pp. 563-576
[10] J.E. Schaller, J.N.D. Gupta, and A.J. Vakharia, "Scheduling a flowline manufacturing cell with sequence dependent family setup times," European Journal of Operational Research, Vol. 125, No. 2, 2000, pp. 324-339
[11] H.G. Campbell, R.A. Dudek and M.L. Smith, "A heuristic algorithm for the n-job, m-machine sequencing problem," Management Science, Vol. 16, 1970, pp. B630-B637
[12] M. Nawaz, E. Enscore and I. Ham, "A heuristic algorithm for the m-machine, n-job flow shop sequencing problem," International Journal of Management Science, Vol. 11, 1983, pp. 91-95
[13] R.A. Ruben ,C.T. Mosier and F. Mahmoodi, "A comprehensive analysis of group scheduling heuristics in a job shop cell," International Journal of Production Research, Vol. 31, No. 6, 1993, pp. 1343-1369
[14] G.V. Frazier, "An evaluation of group scheduling heuristics in a flow-line manufacturing cell," International Journal of Production Research, Vol. 34, No. 4, 1996, pp. 959-976
[15] V. Reddy and T.T. Narendran, "Heuristics for scheduling sequence-dependent set-up jobs in flow line cells," International Journal of Production Research, Vol. 41, No. 1, 2003, pp. 193-206
[16] K.C. Ying, S.W. Lin and Z.J. Lee, "Hybrid-directional planning: improving improvement heuristics for scheduling resource-constrained projects," The International Journal Of Advanced Manufacturing Technology, Vol. 41, No. 3, 2009, pp. 358-366
[17] W. H. Yang, "Group Scheduling in a Two-Stage Flowshop," The Journal of the Operational Research Society, Vol. 53, 2002, pp. 1367-1373
[18] M. Solimanpur, P. Vrat and R. Shankar, "A heuristic to minimize makespan of cell scheduling problem," International Journal of Production Economics Vol. 88, No. 3, 2004, pp. 231-241
[19] J. Schaller, "Scheduling on a single machine with family setups to minimize total tardiness," International Journal of Production Economics, Vol. 105, No. 2, 2007, pp. 329-344
[20] R. Logendran, S. Carson and E. Hanson, "Group scheduling in flexible flow Shops, " International Journal of Production Economics, Vol. 96, No. 2, 2005, pp. 143-155
[21] P.M. Franca, J.N.D. Gupta, A.S. Mendes, P. Moscato and K.J. Veltink," Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups," Computers & Industrial Engineering, Vol. 48, No. 3, 2005, pp. 491-506.
[22] R. Logendran, P. DeSzoeke and F. Barnard, "Sequence-dependent group scheduling problems in flexible flow shops," International Journal of Production Economics, Vol. 102, No. 1, 2006a, pp. 66-86.
[23] R. Logendran, N. Salmasi and C. Sriskandarajah, "Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups," Computers & Operations Research, Vol. 33, No. 1, 2006b, pp. 158-180.
[24] S.H. Hendizadeh, T.Y. ElMekkawy and G.G. Wang, "Bi-criteria scheduling of a flowshop manufacturing cell with sequence dependent setup times," European Journal of Industrial Engineering, Vol. 1, No. 4, 2008, pp. 391-413.
[25] N. Salmasi, R. Logendran and M.R. Skandari, "Total flow time minimization in a flowshop sequence-dependent group scheduling problem," Computers & Operations Research, Vol. 37, No. 1, 2010, pp. 199-212.
[26] S.W. Lin, J.N.D. Gupta, K.C. Ying and Z.J. Lee, "Using simulated annealing to schedule a flowshop manufacturing cell with sequence-dependent family setup times," International Journal of Production Research, Vol. 47, No. 12, 2009, pp. 3205-3217.
[27] H.M. Cheng and K.C. Ying, "Minimizing makespan in a flow-line manufacturing cell with sequence dependent family setup times, " Expert Systems with Applications, Vol. 38, No. 12, 2011, pp. 15517-15522.
[28] S. W. Lin and K.C. Ying, "Scheduling a bi-criteria flowshop manufacturing cell with sequence-dependent family setup times, " European Journal of Industrial Engineering (in press)
[29] S. Slotnick, T. Morton, "Selecting jobs for a heavily loaded shop with lateness penalties," Computers and Operations Research, Vol 23, No.2, 1996, pp. 131-140.
[30] J. Ghosh. "Job selection in a heavily loaded shop," Computers and Operations Research, Vol 24, No.2, 1997, pp. 141-145.
[31] S. Slotnick, T. Morton, "Order acceptance with weighted tardiness," Computers and Operations Research, Vol. 34, No.10, 2007, pp. 3029-3042.
[32] W. Rom, S. Slotnick, "Order acceptance using genetic algorithms," Computers and Operations Research, Vol. 36, No.1, 2009, pp. 1758-1767.
[33] B. Cesaret, C. Oğuz, F. S. Salman," A tabu search algorithm for order acceptance and scheduling, " Computers and Operations Research, Vol. 39, No.6, 2012, pp. 1197-1205.
[34] Y. Bartal, S. Leonardi, A.S. Spaccamela, J. Sgall, and L. Stougie, "Multi- processor scheduling with rejection," SIAM Journal on Discrete Mathematics, Vol. 13, 2000, pp. 67-78.
[35] S.S. Seiden, "Preemptive multiprocessor scheduling with rejection," Theoretical Computer Science, Vol. 262, No 1, 2001, pp. 437-458.
[36] H. Hoogeveen, M. Skutella and G.J. Woeginger, "Preemptive scheduling with rejection," Mathematical Programming, Vol. 94, No. 2-3, 2003, pp. 361-374
[37] L. Lu, L. Zhang and J. Yuan, "The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan," Theoretical Computer Science, Vol. 396, No. 1, 2008, pp. 283-289.
[38] L. Lu, T.C.E. Cheng, J. Yuan and L. Zhang, "Bounded single-machine parallel-batch scheduling with release dates and rejection," Computers & Operations Research, Vol. 36, No. 10, 2009, pp. 2748-2751.
[39] Y. Cheng and S. Sun "Scheduling linear deteriorating jobs with rejection on a single machine," European Journal of Operational Research, Vol. 194, 2007 pp. 18-27.
[40] Z. Cao and X. Yang "A PTAS for parallel batch scheduling with rejection and dynamic job arrivals," Theoretical Computer Science, Vol. 410, 2009, pp. 2732-2745.
[41] N. Bansal, A. Blum, S. Chawla, and K. Dhamdhere, "Scheduling for flow time with admission control," Lecture Notes in Computer Science, Vol. 2832, 2003, pp. 43-54.
[42] D.W. Engels, D.R. Karger, S.G. Kolliopoulos, S. Segupta, R.N. Uma and J. Wein, "Techniques for scheduling with rejection," Journal of Algorithms, Vol. 49, 2003, pp. 175-91.
[43] D.P. Bunde, "Scheduling on a single machine to minimize total flow time with job rejections," In Proceedings of the 2nd Multidisciplinary International Conference on Scheduling, Theory & Applications, Stern School of Business, New York, 18-21 July 2005, pp. 562-572.
[44] G. Dosa, and Y. He, "Preemptive and non-preemptive online algorithms for scheduling with rejection of two uniform machines," Computers and Operations Research, Vol. 76, No. 1, 2006, pp. 149-164.
[45] Z.W. Geem, J.H. Kim and G.V. Loganathan "A New Heuristic Optimization Algorithm: Harmony Search," Society for Modeling and Simulation Interational, Vol. 76, No. 2, 2001, pp. 60-68.
[46] S. Kirkpatrick, C. Gelatt, and M. Vecchi, "Optimization by Simulated Annealing," Science, Vol. 220, No. 4598, 1983, pp. 671-680.
[47] M. Dorigo, C.Blum, Ant colony optimization: A survey," Theoretical Computer Science, Vol. 344, No. 2, 2005, pp. 243-278.
[48] M.G.H. Omran, M. Mahdavi, "Global-best harmony search," Applied athematics and Computation, Vol. 198, 2008, pp. 643-656.
[49] Z.W. Geem, "Novel derivative of harmony search algorithm for discrete design variables, "Applied Mathematics and Computation, Vol. 199, No 1, 2008 pp. 223-230.
[50] K. Gao, Q. Pan, J. Li, Y. He, "A novel grouping harmony search algorithm for the no-wait flow shop scheduling problems with total flow time criteria," International Symposium on Computer, Communication, Control and Automation, Vol. 37, No. 12, 2010, pp. 76-80.
[51] Q.K. Pan, P.N. Suganthan, J.J. Liang , M.F. Tasgetiren, "A local-best harmony search algorithm with dynamic sub-harmony memories for lot-streaming flow shop scheduling problem," Expert Systems with Applications, Vol. 38, No. 4, 2010, pp. 1-8.
[52] F. Glover, "Heuristic for Integer Programming Using Surrogate Constraints," Decision Sciences, Vol. 8, No. 1, 1977, pp. 156-166.
[53] E.F. Stafford and F.T. Tseng "Two models for a family of flowshop sequencing problems, "European Journal of Operational Research, Vol. 142, No. 2, 2002, pp. 282-293.
[54] L. Wang, Q.K. Pan, M.F. Tasgetiren, "Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms," Expert Systems with Applications, Vol. 37, No. 12, 2010, pp. 7929-7936.
[55] F. Glover and R. Marti, "Tabu Search," Operations Research/Computer Science Interfaces Series, Vol. 36, No. 2, 2006, pp. 53-69.
[56] L.B. Booker, D.E. Goldberg, J.H. Holland," Classifier systems and genetic algorithms," Artificial Intelligence, Vol. 40, No.1-3, 1989, pp. 235-282.
[57] M. Mahdavi, M. Fesanghary and E. Damangir," An improved harmony search algorithm for solving optimization problems," Applied Mathematics and Computation, Vol. 188, No. 2, 2007, pp. 1567-1579.
[58] C. Oğuz, F. S. Salman, and Z.B. Yalçın," Order acceptance and scheduling decisions in make-to-order systems," International Journal of Production Economics, Vol. 125, No.1, 2010, pp. 200-211.
[59] J.M.S. Valente, R.A.F.S. Alves, "Filtered and recovering beam search algorithms for the early/tardy scheduling problem with no idle time," Computers & Industrial Engineering, Vol. 48, No.2, 2005, pp. 363-375


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top