跳到主要內容

臺灣博碩士論文加值系統

(44.192.22.242) 您好!臺灣時間:2021/08/01 13:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:黃雅萱
研究生(外文):HUANG, YA-HSUAN
論文名稱:最小化最大完工時間之多3D列印機台排程問題
論文名稱(外文):Minimizing Makespan in Multiple 3D Printing Machines Scheduling Problems
指導教授:應國卿應國卿引用關係
指導教授(外文):YING, KUO-CHING
口試委員:黃乾怡林詩偉應國卿
口試委員(外文):HUANG, CHIEN-YILIN, SHIH-WEIYING, KUO-CHING
口試日期:2021-05-25
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:工業工程與管理系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2021
畢業學年度:109
語文別:中文
論文頁數:52
中文關鍵詞:排程3D列印機批次加工生產問題反覆貪婪演算法
外文關鍵詞:Scheduling3D Printing MachinesBatch Process Processing ProblemIterated Greedy algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:17
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
3D列印排程問題為近年來排程研究的重點方向之一,儘管在文獻中已經有對3D列印機台的結構進行了充分的研究,但目前為止尚未有關於大量零件在多台3D列印機台上製造的排程問題(Multi-3D Printing Machines Scheduling Problems, M3DPMSP)之研究,目的是最佳化處理時間相關性能指標。因此針對M3DPMSP問題在生產製造時為數台相同之3D列印平行機台及多個有限制大小的底板進行所有零件的生產,求解目標為最大完工時間(Makespan)最小化。本研究將提出此問題的混合整數規劃(Mixed Integer Linear Programming, MILP)模式及利用反覆貪婪(Iterated Greedy, IG)演算法為基礎,加入不同規則的區域搜尋來增加擾動,提出了適合此問題的修改型反覆貪婪(Modify Iterated Greedy, MIG)演算法用以求解。
The 3D printing scheduling problem is one of the critical directions of scheduling research. To the best of the author’s knowledge, there is no research with respect to scheduling a large number of parts on multi-3D printing machines. Therefore, The M3DPMSP problem, Multi-identical 3D printing parallel machines and multi-build platforms with restricted sizes are used for overall parts production, and objective is to minimizing Makespan. In this study, we propose the Modify Iterated Greedy algorithm to solve this problem based on the Mixed Integer Linear Programming model and the Iterated Greedy algorithm, and combine different rules of Local Search to increase the shaking.
摘 要 i
ABSTRACT ii
誌謝 iii
目 錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 4
1.3 研究範圍與限制 5
1.4 研究流程 6
第二章 文獻探討 8
2.1 3D列印機台排程問題 8
2.2 批次加工生產排程問題 12
2.3 反覆貪婪演算法(IG) 15
2.3.1 生成初始解 16
2.3.2 解構階段 17
2.3.3 建構階段 18
2.3.4 區域搜尋 18
2.3.5 接受機制 19
第三章 研究方法 21
3.1 數學符號之定義 21
3.2 M3DPASP之MILP模型 23
3.3 修改型反覆貪婪演算法 25
3.3.1 編碼方式 26
3.3.2 生成初始解 29
3.3.3 解構階段 29
3.3.4 建構階段 31
3.3.5 區域搜尋 32
3.3.6 接收機制 34
3.3.7 終止運算條件 34
第四章 實驗結果與分析 36
4.1 測試題庫說明 36
4.2 實驗結果 38
4.2.1 求解績效分析 38
4.2.2 演算法的統計檢定 42
4.2.3 演算法與MILP模型比較 44
第五章 結論與建議 45
5.1 結論 45
5.2 建議 46
參考文獻 48

參考文獻
Arroyo, J. E. C., & Leung, J. Y. T. (2017). An effective iterated greedy algorithm for scheduling unrelated parallel batch machines with non-identical capacities and unequal ready times. Computers & Industrial Engineering, 105, 84-100.
Arroyo, J. E. C., & Leung, J. Y. T. (2017). Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times. Computers & Operations Research, 78, 117-128, February.
Arroyo, J. E. C., Leung, J. Y. T., & Tavares, R. G. (2019). An iterated greedy algorithm for total flow time minimization in unrelated parallel batch machines with unequal job release times. Engineering Applications of Artificial Intelligence, 77, 239-254.
Bose, S., & Bandyopadhyay, A. (2019). Additive manufacturing: the future of manufacturing in a flat world. In Additive manufacturing (pp. 451-461). CRC Press.
Campbell, I., Diegel, O., Kowen, J., & Wohlers, T. (2017). Wohlers Report 2017 3D Printing and Additive Manufacturing State of the Industry: Annual Worldwide Progress Report.
Chandru, V., Lee, C. Y., & Uzsoy, R. (1993). Minimizing total completion time on batch processing machines. The International Journal Of Production Research, 31(9), 2097-2121.
Chang, P. Y., Damodaran, P., & Melouk, S. (2004). Minimizing makespan on parallel batch processing machines. International Journal of production research, 42(19), 4211-4220.
Chen, J. C., & Gabriel, V. S. (2016). Revolution of 3D printing technology and application of Six Sigma methodologies to optimize the output quality characteristics. In 2016 IEEE International Conference on Industrial Technology (ICIT) (pp. 904-909). IEEE, March.
Cheng, B., Wang, Q., Yang, S., & Hu, X. (2013). An improved ant colony optimization for scheduling identical parallel batching machines with arbitrary job sizes. Applied Soft Computing, 13(2), 765-772.
Damodaran, P., Hirani, N. S., & Velez-Gallego, M. C. (2009). Scheduling identical parallel batch processing machines to minimise makespan using genetic algorithms. European Journal of Industrial Engineering, 3(2), 187-206.
Damodaran, P., Vélez-Gallego, M. C., & Maya, J. (2011). A GRASP approach for makespan minimization on parallel batch processing machines. Journal of Intelligent Manufacturing, 22(5), 767-777.
Fanjul-Peyro, L., & Ruiz, R. (2010). Iterated greedy local search methods for unrelated parallel machine scheduling. European Journal of Operational Research, 207(1), 55-69.
Fidelis, M. B., & Arroyo, J. E. C. (2017). Meta-heuristic algorithms for scheduling on parallel batch machines with unequal job ready times. In 2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC) (pp. 542-547). IEEE, October.
Framinan, J. M., Perez-Gonzalez, P., & Fernandez-Viagas, V. (2019). Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures. European Journal of Operational Research, 273(2), 401-417.
Freens, J. P., Adan, I. J., Pogromsky, A. Y., & Ploegmakers, H. (2015). Automating the production planning of a 3D printing factory. In 2015 Winter Simulation Conference (WSC) (pp. 2136-2147). IEEE, December.
Hatami, S., Ruiz, R. and Andrés-Romano, C. (2015), "Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times," International Journal of Production Economics, vol. 169, pp. 76-88.
I. Kucukkoc, Q. Li, D. Zhang“Increasing the Utilisation of Additive Manufacturing and 3D Printing Machines Considering Order Delivery Times, 3 (2016), pp. 195-201 Innsbruck, Austria, Feb.
Jacobs, L. W., & Brusco, M. J. (1995). Note: A local‐search heuristic for large set‐covering problems. Naval Research Logistics (NRL), 42(7), 1129-1140.
Jia, Z. H., & Leung, J. Y. T. (2015). A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes. European Journal of Operational Research, 240(3), 649-665.
Kashan, A. H., Karimi, B., & Jenabi, M. (2008). A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes. Computers & Operations Research, 35(4), 1084-1098.
Kim, J., Park, S. S., & Kim, H. J. (2017). Scheduling 3D printers with multiple printing alternatives. In 2017 13th IEEE Conference on Automation Science and Engineering (CASE) (pp. 488-493). IEEE, August.
Koh*, S. G., Koo, P. H., Ha, J. W., & Lee, W. S. (2004). Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families. International Journal of Production Research, 42(19), 4091-4107.
Lee, C. Y., Cheng, T. C. E., & Lin, B. M. T. (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. Management Science, 39(5), 616-625.
Lin, Y. K., & Hsieh, F. Y. (2014). Unrelated parallel machine scheduling with setup times and ready times. International Journal of Production Research, 52(4), 1200-1214.
Mathirajan, M., & Sivakumar, A. I. (2006). A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. The International Journal of Advanced Manufacturing Technology, 29(9-10), 990-1001.
Matin, H. N., Salmasi, N., & Shahvari, O. (2017). Makespan minimization in flowshop batch processing problem with different batch compositions on machines. International Journal of Production Economics, 193, 832-844.
Mokotoff, E. (2001). Parallel machine scheduling problems: A survey. Asia-Pacific Journal of Operational Research, 18(2), 193-242.
Ngo, T. D., Kashani, A., Imbalzano, G., Nguyen, K. T., & Hui, D. (2018). Additive manufacturing (3D printing): A review of materials, methods, applications and challenges. Composites Part B: Engineering, 143, 172-196.
Oh, Y., Witherell, P., Lu, Y., & Sprock, T. (2020). Nesting and Scheduling Problems for Additive Manufacturing: A Taxonomy and Review. Additive Manufacturing, 101492.
Oh, Y., Zhou, C., & Behdad, S. (2018). Production planning for mass customization in additive manufacturing: build orientation determination, 2D packing and scheduling. In ASME 2018 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers Digital Collection, August.
Osman, I. H., & Potts, C. N. (1989). Simulated annealing for permutation flow-shop scheduling. Omega, 17(6), 551-557.
Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European journal of operational research, 177(3), 2033-2049.
Ruiz, R., Pan, Q. K., & Naderi, B. (2019). Iterated Greedy methods for the distributed permutation flowshop scheduling problem. Omega, 83, 213-222.
Wu, W. Z., Geng, P., Zhao, J., Zhang, Y., Rosen, D. W., & Zhang, H. B. (2014). Manufacture and thermal deformation analysis of semicrystalline polymer polyether ether ketone by 3D printing. Materials Research Innovations, 18(sup5), S5-12.
Yılmaz, Ö. F. (2020). Examining additive manufacturing in supply chain context through an optimization model. Computers & Industrial Engineering, 142, 106335.
Ying, K. C. (2012). Scheduling identical wafer sorting parallel machines with sequence-dependent setup times using an iterated greedy heuristic. International Journal of Production Research, 50(10), 2710-2719.
Zhang, J., Yao, X., & Li, Y. (2020). Improved evolutionary algorithm for parallel batch processing machine scheduling in additive manufacturing. International Journal of Production Research, 58(8), 2263-2282.
Zhang, Y., Gupta, R. K., & Bernard, A. (2016). Two-dimensional placement optimization for multi-parts production in additive manufacturing. Robotics and Computer-Integrated Manufacturing, 38, 102-117.

電子全文 電子全文(網際網路公開日期:20230731)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top