臺灣博碩士論文加值系統

因應目前製造環境競爭激烈及市場需求急遽變化的當下，企業面臨產品生命週期縮短及顧客需求滿意度提高的情形，企業在產業供應鏈的整合變得重要。例如在同一工業區的組裝廠，因即時生產的因素，在力求零庫存的情況下，如何有效結合排程與配送，以達到最小化延遲時間是許多公司所重視。
本研究討論結合時窗限制並整合平行機台排程與車輛途程問題，並求其在單一機器種類、多機台、多訂單、相依整備時間、多車輛、多客戶、時窗限制問題下的最小化總延遲時間。並針對此一生產排程與車輛途程問題其兩階段決策的特性，提出一巢狀式變動鄰域搜尋法來解決此一問題，將其外層為決定訂單所對應之生產機台，內層為決定訂單所對應之運送車輛，以求其整體最佳化。透過小問題的獨立實驗與最佳解來評估其方法優劣，並藉由大問題測試此演算法的求解能力，來驗證此演算方法之可行性。

Nowadays the manufacturing environment becomes competitive and the market demands change rapidly. Enterprises are facing with shorter product life cycles and higher levels of customer requirements and satisfaction degree. Hence, the integration of supply chain becomes important. For example, in an assembly plant, due to the factors of real-time production and zero inventory, how to effectively combine scheduling and distribution and to achieve a minimum of delay time is important.
This study discusses the integrated parallel machine scheduling and vehicle routing problem with time window and considers these issues of single machine type, multi-machine, multi-order, dependent setup time, multi-vehicle, and time window to minimize the total weighted tardiness. In addition, this study develops a nested variable neighborhood search method to solve this integrated problem. Through small-scale problems, the proposed approach is compared with the optimal solution obtained from the branch and bound method. It can also be found that the proposed nested variable neighborhood search can obtain the feasible solution quickly and effectively from the outcomes of large-scale problems.

摘要 I
Abstract II
謝誌 III
目錄 IV
圖目錄 VI
表目錄 IX
第一章 緒論 1
1.1研究背景 1
1.2研究動機 4
1.3研究目的與問題 5
1.4研究方法 5
1.5研究架構 6
第二章 文獻回顧 9
2.1排程相關問題 9
2.1.1完全相同平行機台 9
2.1.2等效平行機台 10
2.1.3不相關平行機台 11
2.2車輛途程相關問題 14
2.3生產排程與車輛途程相關問題 16
2.4變動鄰域搜尋法相關問題 18
第三章 研究方法 23
3.1問題敘述 23
3.1.1平行機台排程與車輛途程 23
3.1.2問題假設 25
3.1.3數學模型 27
3.2編碼與起始解產生方式 30
3.2.1平行機台排程初始化設定 30
3.2.2車輛途程初始化設定 32
3.3 VNS基本架構 33
3.3.1 VNS-I鄰域結構 35
3.3.2 VNS-II鄰域結構 42
3.4震動 49
3.5 Nested VNS 演算架構 50
第四章 實驗設計與分析 55
4.1參數設定 55
4.2實驗分析 57
4.2.1小問題實驗分析 57
4.2.2大問題實驗分析 65
4.3分析結果 71
第五章 結論與未來展望 73
參考文獻 75
附錄 81

陳宗德(2012)。在訂單式生產情境下考量訂單允收與平行機台排程之問題研究。 國立東華大學運籌管理研究所碩士論文。
盧芊竹(2012)。整合生產排程與車輛途程之數學規劃研究。國立東華大學運籌管理研究所碩士論文。
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.
Baker, B. M. and Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers &; Operations Research, 30(5), 787-800.
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.
Belfiore, P. and Yoshida Yoshizaki, H. T. (2009). Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil. European Journal of Operational Research, 199(3), 750-758.
Brandão, J. (2004). A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research, 157(3), 552-564.
Brandão, J. and Mercer, A. (1997). A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. European Journal of Operational Research, 100(1), 180-191.
Chen, H. K., Hsueh, C. F., and Chang, M. S. (2009). Production scheduling and vehicle routing with time windows for perishable food products. Computers &; Operations Research, 36(7), 2311-2319.
Chen, J. F. and Wu, T. H. (2006). Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints. Omega,34(1), 81-89.
Chen, Y. Y., Cheng, C. Y., Wang, L. C., and Chen, T. L. (2013). A hybrid approach based on the variable neighborhood search and particle swarm optimization for parallel machine scheduling problems—A case study for solar cell industry. International Journal of Production Economics, 141(1), 66-78.
Chiang, W. C. and Russell, R. A. (2004). A metaheuristic for the vehicle-routeing problem with soft time windows. Journal of the Operational Research Society, 55(12), 1298-1310.
Dessouky, M. M., Dessouky, M. I., and Verma, S. K. (1998). Flowshop scheduling with identical jobs and uniform parallel machines. European Journal of Operational Research, 109(3), 620-631.
Fleszar, K., Osman, I. H., and Hindi, K. S. (2009). A variable neighbourhood search algorithm for the open vehicle routing problem. European Journal of Operational Research, 195(3), 803-809.
Hemmelmayr, V. C., Doerner, K. F., and Hartl, R. F. (2009). A variable neighborhood search heuristic for periodic routing problems. European Journal of Operational Research, 195(3), 791-802.
Horowitz, E. and Sahni, S. (1976). Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM (JACM), 23(2), 317-327.
Jeon, G., Leep, H. R., and Shim, J. Y. (2007). A vehicle routing problem solved by using a hybrid genetic algorithm. Computers &; Industrial Engineering, 53(4), 680-692.
Kim, D. W., Kim, K. H., Jang, W., and Frank Chen, F. (2002). Unrelated parallel machine scheduling with setup times using simulated annealing. Robotics and Computer-Integrated Manufacturing, 18(3), 223-231.
Kim, D. W., Na, D. G., and Frank Chen, F. (2003). Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective. Robotics and Computer-Integrated Manufacturing, 19(1), 173-181.
Kytöjoki, J., Nuortio, T., Bräysy, O., and Gendreau, M. (2007). An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Computers &; Operations Research, 34(9), 2743-2757.
Lee, W. C., Chuang, M. C., and Yeh, W. C. (2012). Uniform parallel-machine scheduling to minimize makespan with position-based learning curves. Computers &; Industrial Engineering, 63(4), 813-818.
Liaw, C. F., Lin, Y. K., Cheng, C. Y., and Chen, M. (2003). Scheduling unrelated parallel machines to minimize total weighted tardiness. Computers &; Operations Research, 30(12), 1777-1789.
Liu, S. C. and Chen, A. Z. (2012). Variable neighborhood search for the inventory routing and scheduling problem in a supply chain. Expert Systems with Applications, 39(4), 4149-4159.
Maloni, M. J. and Benton, W. C. (1997). Supply chain partnerships: opportunities for operations research. European Journal of Operational Research, 101(3), 419-429.
Marinakis, Y., Marinaki, M., and Dounias, G. (2010). A hybrid particle swarm optimization algorithm for the vehicle routing problem. Engineering Applications of Artificial Intelligence, 23(4), 463-472.
Meyr, H., Wagner, M., and Rohde, J. (2002). Structure of advanced planning systems. Supply Chain Management and Advanced Planning, Springer Berlin Heidelberg.
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.
Mladenović, N. and Hansen, P. (1997). Variable neighborhood search. Computers &; Operations Research, 24(11), 1097-1100.
Nait Tahar, D., Yalaoui, F., Chu, C., and Amodeo, L. (2006). A linear programming approach for identical parallel machine sch eduling with job splitting and sequence-dependent setup times. International Journal of Production Economics, 99(1), 63-73.
New, S. J. and Payne, P. (1995). Research frameworks in logistics: three models, seven dinners and a survey. International Journal of Physical Distribution &; Logistics Management, 25(10), 60-77.
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.
Pisinger, D. and Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers &; Operations Research, 34(8), 2403-2435.
Ruiz, R., Maroto, C., and Alcaraz, J. (2006). Two new robust genetic algorithms for the flowshop scheduling problem. Omega, 34(5), 461-476.
Ruiz-Torres, A. J., Lopez, F. J., and Ho, J. C. (2007). Scheduling uniform parallel machines subject to a secondary resource to minimize the number of tardy jobs. European Journal of Operational Research, 179(2), 302-315.
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 &; Operations Research, 35(3), 863-875.
Stadtler, H. (2002). Basics of supply chain management. In: Stadtler, H., Kilger, C. (Eds.), Supply Chain Management and Advanced Planning––Concepts, Models, Software and Case Studies, Berlin, 7–28.
Taillard, É., Badeau, P., Gendreau, M., Guertin, F., and Potvin, J. Y. (1997). A tabu search heuristic for the vehicle routing problem with soft time windows.Transportation Science, 31(2), 170-186.
Ullrich, C. A. (2012). Integrated machine scheduling and vehicle routing with time windows. European Journal of Operational Research.
Vahdani, B., Tavakkoli-Moghaddam, R., Zandieh, M., and Razmi, J. (2012). Vehicle routing scheduling using an enha nced hybrid optimization approach. Journal of Intelligent Manufacturing, 23(3), 759-774.
Weng, M. X., Lu, J., and Ren, H. (2001). Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective. International Journal of Production Economics, 70(3), 215-226.