跳到主要內容

臺灣博碩士論文加值系統

(34.204.169.230) 您好!臺灣時間:2024/03/03 01:11
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:楊弘引
研究生(外文):Hong-In Yang
論文名稱:應用仿水流演算法求解訂單接受與平行機台排程問題
論文名稱(外文):A Water Flow-like Algorithm for Order Acceptance and Parallel Machine Scheduling
指導教授:吳政翰吳政翰引用關係
指導教授(外文):Gen-Han Wu
學位類別:碩士
校院名稱:國立東華大學
系所名稱:運籌管理研究所
學門:商業及管理學門
學類:行銷與流通學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
論文頁數:83
中文關鍵詞:平行機台排程訂單接受變動鄰域搜尋法仿水流演算法訂單式生產
外文關鍵詞:parallel machines schedulingorder acceptancevariable neighborhood searchwater flow-like algorithmmake-to-order
相關次數:
  • 被引用被引用:1
  • 點閱點閱:370
  • 評分評分:
  • 下載下載:34
  • 收藏至我的研究室書目清單書目收藏:1
現今消費型態改變,使得消費型電子產品的生命週期短縮,品項繁多,消費型電子產品如智慧型手機,發展太快速,多家品牌推不同型號類型商品,製造工業備受挑戰,然而其零件供應商來源大多相同,這種情形使得訂單式生產的供應商無法消化所有的訂單,只能選擇適合能獲利的訂單來安排其生產時序。
本研究在探討訂單式工廠如何透過最佳化方式,衡量工廠能力、訂單利潤與延遲交貨的懲罰之下選擇訂單 ,並在多部平行機台上安排其生產順序,求其生產排程之利潤最大化。針對上述問題,本研究提出仿水流演算法,輔以變動鄰域搜尋法加以求解,設計不同的鄰域搜尋機制,並討論演算法中參數的設置。藉由比較兩種仿水流演算法,來了解其在不同範例中的求解品質,結果顯示在大型問題中,WFA.II的求解品質皆比WFA.I好,兩者的解差距範圍在0.45%~38.06%。並將WFA.II與文獻中之粒子群演算法、和弦演算法比較其求解品質,結果顯示在WFA.II與這兩方法的結果差異不大,在大型問題中兩者的解差距範圍在0.17%~1.65%。

Nowadays, along with the change of consumption pattern、the shortening of life cycle and the diversity of consumer goods, the rapid development of consumer electronics products such as smartphones cause many brand companies to introduce different types of new products to the market. The manufacturing industries are rising challenging. However, most of such products come from the same suppliers. The make-to-order manufacturing plant can only select the suitable and profitable orders and arrange the production schedule for such selected orders due to the limited plant capacity.
This study focuses on the maximizing profit in the make-to-order environment and study how to select the orders via the optimization approach based on the plant resources, the order profits, and the tardiness penalties. Also, these selected orders are scheduled to the parallel machines. The water flow-like algorithms, embedded with variable neighborhood search based on different types of neighborhood mechanisms, are proposed to solve the aforementioned problem and to discuss the tuning parameters of the algorithms. The two kinds of water flow-like algorithms are compared, with other existing algorithms such as particle swarm optimization and harmony search, to find out their solution qualities in different sizes of problems. The computational results show that, in the large-sized problems, WFA.II is performing much better than WFA.I with a range of solution gaps, 0.45%~38.06%. WFA.II is also competitive as other existing approaches in the large-sized problems, with an extremely short range of solution gap, 0.17%~1.65%.

摘要 ii
Abstract iii
目錄 iv
圖目錄 vi
表目錄 viii
第一章 緒論 1
1.1 研究背景 1
1.2 問題描述 3
1.3 研究流程架構 4
第二章 文獻回顧 6
2.1 平行機台的生產排程問題 6
2.1.1 完全相同平行機台 6
2.1.2 等效平行機台 7
2.1.3 不相關平行機台 7
2.2 訂單接受與生產排程問題 8
2.3 啟發式演算法 9
2.3.1 變動鄰域搜尋法 9
2.3.2 仿水流演算法 11
第三章 數學模型 22
第四章 研究方法 26
4.1 編碼 26
4.2 鄰域 28
4.2.1 訂單插入法 28
4.2.2 機台修正法 29
4.2.3 訂單交換法 29
4.2.4 機台交換法 30
4.3 仿水流演算法 31
4.3.1 初始解與初始參數 31
4.3.2 分流與移動 33
4.3.3 匯流 41
4.3.4 蒸發與降水 41
4.4 仿水流演算法與鄰域搜尋(1) 43
4.5 仿水流演算法與鄰域搜尋(2) 47
第五章 實驗設計與分析 50
5.1 演算法之參數分析 50
5.1.1 分流相關參數分析 51
5.1.2 分流上限相關參數分析 53
5.1.3 降水參數分析 56
5.2 兩種仿水流演算法比較 58
5.3 仿水流演算法與粒子群演算法、和弦演算法之比較 59
第六章 結論與未來展望 64
參考文獻 65
附錄 68

林則孟 (2012)。生產計畫與管理(Ed 2),華泰文化。

楊烽正 (2011)。仿水流萬用啟發式優化演算法(2/3),行政院國家科學委員會專題研究計畫成果報告。

陳宗德 (2012)。在訂單式生產情境下考量訂單允收與平行機台排程之問題研究,國立東華大學運籌管理研究所碩士論文。

陳宏瑋 (2013)。訂單接受與平行機台排程問題之演算法比較,國立東華大學運籌管理研究所碩士論文。

Anghinolfi, D. and Paolucci, M. (2008). A new ant colony optimization approach for the single machine total weighted tardiness scheduling problem. International Journal of Operations Research, 5(1), 44-60.

Azizoglu, M. and Kirca, O. (1999). On the minimization of total weighted flow time with identical and uniform parallel machines. European Journal of Operational Research, 113(1), 91-100.

Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., and Stougie, L. (2000).Multiprocessor scheduling with rejection. SIAM Journal of Discrete Mathematics, 13(1), 64-78.

Behnamian, J., Zandieh, M., and Fatemi Ghomi, S. M. T. (2009). Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm. Expert Systems with Applications, 36(6), 9637-9644.

Cesaret, B., O˘guz, C., and Salman, F. S. (2012). A tabu search algorithm for order acceptance and scheduling. Computers and Operations Research, 39, 1197-1205.

Chang, C. C. and Li, F. C. (2013).Solving the wafer probing scheduling problem using water flow-like algorithm. The 6th IEEE International Workshop on Computational Intelligence and Applications, Hiroshima, Japan.

Driessel, R. and Mönch, L. (2011). Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times. Computers and Industrial Engineering, 61(2), 336-345.

Ghosh, J. B. (1997). Job selection in a heavily loaded shop. Computers and Operations Research 24(2), 141–145.
Guerrero, H. H. and Kern, G. M. (1988). How to more effectively accept and refuse orders. Production and Inventory Management Journal, 29, 59-63.

Hansen, P., Mladenovi´c, N., and Moreno Pérez, J.A. (2009). Variable neighborhood search: methods and applications. Annals of Operations Research 175, 367–407.

Horowitz, E. and Sahni, S. (1976). Exact and approximate algorithms for scheduling non-identical processors. Journal of the ACM, 23(2), 317-327.

Kashan, A. H. and Karimi, B. (2009). A discrete particle swarm optimization algorithm for scheduling parallel machines. Computers and Industrial Engineering, 56, 216-223.

Lee, W. C., Chuang, M. C., and Yeh, W. C. (2012). Uniform parallel-machine scheduling to minimize makespan with position-based learning curves. Computers and Industrial Engineering, 63(4), 813-818.

Liao, C. J. and Cheng, C. C. (2007). A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date. Computers and Industrial Engineering, 52, 404–413.

Min, L. and Cheng, W. (1999). A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines. Artificial Intelligence in Engineering, 13(4), 399-403.

Mladenovic, N. and Hansen, P. (1997). Variable neighborhood search. Operations Research, 24, 1097-1100.

O˘guz, C., Salman, F. S., and Yalcin, Z. B. (2010).Order acceptance and scheduling decisions in make-to-order systems. International Journal of Production Economics, 125(1), 200-211.

Piersma, N. and Van Dijk, W. (1996). A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search. Mathematical and Computer Modelling, 24(9), 11-19.

Sheikh, K. (2002). Manufacturing Resource Planning (MRP II) with Introduction to ERP, SCM, CRM, McGraw-Hill.
Slotnick, S. A. (2011). Order acceptance and scheduling: a taxonomy and review. European Journal of Operational Research, 212(1), 1-11.

Shim, S. O. and Kim, Y. D. (2007). Scheduling on parallel identical machines to minimize total tardiness. European Journal of Operational Research, 177(1), 135-146.

Shim, S. O. and Kim, Y. D. (2008). A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property. Computers and Operations Research, 35(3), 863-875.

Wu, T. H., Chung, S. H., and Chang ,C. C. (2010). A water
flow-like algorithm for manufacturing cell formation problems. European Journal of Operational Research, 205, 346-360.

Yang, F. C. and Wang, Y. P. (2007).Water flow-like algorithm for object grouping problems. Journal of Chinese Industrial Engineers, 24(6), 475-488.

Yazdani, M., Amiri, M.,and Zandieh, M.(2010) Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert Systems with Applications, 37, 678–687.

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