臺灣博碩士論文加值系統

產品製造與成品配送是供應鏈中相當重要的兩個階段，由於顧客需求的快速變動以及產品的高度客製化，現今許多企業採用接單式生產(make to order)或直接銷售(direct order)模式而被迫減少存貨，但同時仍必須快速回應顧客的要求以維持其競爭力。此種現象增加了供應鏈中產品製造與成品配送作業的互動，並提昇了整合這兩階段研究的實用性。
本研究探討整合供應鏈中產品製造與成品配送兩階段問題，在這種問題中，訂單會先在一組非等效平行機台上(unrelated parallel machine)進行加工，加工完畢後則由具容量限制的車輛配送至顧客的所在地。訂單的完工時間定義為送達顧客的時間，而問題的目標則是求出一個整合製造與配送的排程，以最小化加權後的總完工時間。
然而整合製造與配送兩階段問題的複雜度為未定多項式難度(NP-hard)，為了在合理的時間內求得品質良好的近似最佳解，本研究採用蟻群演算法(ant colony optimization)來求解此類問題，並透過電腦實驗來測試演算法的求解品質及穩健性，期望本研究結果能有助於提昇整合製造與配送兩階段問題的實用性及應用價值。

Due to the rapid-changing market demand and highly customized product requirements, many enterprises have adopted make-to-order or direct-order business model. In this type of business model, enterprises are forced to lower the amount of inventory needed across their supply chain but still have to be more responsive to customers’ requirements. Reduced inventory creates a closer interaction between production and distribution activities and thus increases the practical usefulness of integrated models.
We consider an integrated production and distribution problem at the individual job level in this study. In this problem, jobs are first processed by one of a set of unrelated parallel machines and then distributed by vehicles with limited capacity to the corresponding customer locations. The completion time of a job is defined as the time when it is delivered to its customer. The objective is to find a joint production and distribution schedule so that the total weighted completion time is minimized. The complexity of the studied problem is NP-hard. Therefore, we used an ant colony algorithm to solve this problem in order to find near-optimal solutions in reasonable computation times. Computational analysis is performed to evaluate the effectiveness and stability of the proposed approach. We expect our research results to help make the study of integrated production and distribution problems more practical and with better application values.

目錄
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究方法與流程 4
1.4 研究架構 4
第二章 文獻探討 6
2.1 非等效平行機台與車輛途程問題 6
2.1.1 非等效平行機台問題之相關文獻 6
2.1.2 車輛途程問題之相關文獻 8
2.2 蟻群演算法 13
2.2.1 蟻群演算法的理論 13
2.2.2 蟻群演算法的演算步驟 14
2.2.3 蟻群演算法的相關應用 17
2.2.3.1 蟻群演算法應用於排程問題 17
2.3 供應鏈整合之相關文獻 18
第三章 問題定義與研究方法 24
3.1 問題定義 24
3.2 演算法之設計 26
3.2.1 非等效平行機台問題之轉換 26
3.2.2 狀態轉移法則 27
3.2.3 費洛蒙更新法則 29
3.2.4 蟻群演算法架構 31
3.2.5 演算步驟範例說明 34
第四章 演算法測試與結果分析 41
4.1 參數設計 41
4.1.1 訂單權重參數(γ) 42
4.1.2 螞蟻數量(ANT) 42
4.1.3 費洛蒙濃度初始值( ) 43
4.1.4 費洛蒙濃度與能見度參數(α, β) 44
4.1.5 參數q0 44
4.1.6 區域費洛蒙殘留係數(ρ) 45
4.1.7 全域費洛蒙殘留係數ρ’ 46
4.1.8 迭代數(TN) 46
4.1.9 小結 47
4.2 ACO_PDP之求解品質測試－以特殊問題為例 49
4.3 測試問題設計 50
4.4 測試結果分析 53
4.4.2 機台數與求解品質之關係 55
4.4.3 訂單數與求解品質之關係 55
4.4.4 車輛容量限制與求解品質之關係 55
4.4.5 小結 56
第五章 結論與建議 57
5.1 結論 57
5.2 未來研究方向之建議 57
5.2.1 整合產品製造與成品配送兩階段問題方面 57
5.2.2 演算法方面 58
參考文獻 59

尹邦嚴、王敬育 (2004)。使用螞蟻族群最佳化求解資源分配問題。第一屆台灣作業研究學會學術研討會暨2004年科技與管理學術研討會。
周碩鴻 (2006)。應用基因演算法求解供應鏈中生產排程與物流配送兩階段總成本最小化問題。國立交通大學工業工程與管理學系，碩士論文。
陳明俊 (2004)。蟻群演算法於具非等效平行機台考量之排程問題研究。私立大葉大學工業工程學系，碩士論文。
陳昱皓 (2006)。塔布搜尋法於求解供應鏈中整合生產排程與成品配送兩階段問題。國立交通大學工業工程與管理學系，碩士論文。
蔡志強 (2003)。以蟻群系統建立物流宅配最佳化配送路徑規劃。國立屏東科技大學，工業管理系，碩士論文。
熊鴻鈞 (2003)。螞蟻族群演算法於生產排成之應用。國立暨南國際大學資訊管理學系，碩士論文。
羅敏華 (2003)。蟻群最佳化演算法於載重限制之車輛途程問題的研究。私立元智大學工業工程與管理研究所，碩士論文。
呂學君(2007)。應用禁忌搜尋法求解供應鏈中在考慮車容限制下整合產品製造與成品配送之問題。國立交通大學工業工程與管理學系，研究報告。
Allahverdi, A., J. Mittenthal. " Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time ". Naval Research Logistics, 41 (5), pp. 677-682, 1994.
Azizoglu, M., O. Kirka (1999). Scheduling jobs on unrelated parallel machines to minimize regular total cost functions. IIE Transactions, 31, 153–159.
Baker, B. M. and M. A. Ayechew (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30, 787-800.
Bauer, A., B. Bullnheimer, R. F. Hartl, and C. Strauss(1999). Minimizing total tardiness on a single machine using ant colony optimization. In Proceedings of the 1999 Congress on Evolutionary Computation (pp. 1445-1450). Piscataway, New Jersey: IEEE Press.
Bell, J. E., P. R. McMullen (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18, 41–48.
Bruno, L. G., Coffman, E. G. and Sethi, R. (1974). Scheduling independent tasks to reduce mean finishing time. Communications of the ACM, 17, 382–387.
Bullnheimer, B., R. F. Hartl, and C. Strauss (1997). Applying the ant system to the vehicle routing problem. Presented at the 2nd International Conference on Meta-heuristic-Mic97, Sophia-Antipolis, France.
Chang, Y. C. , C. Y. Lee (2003). Logistics scheduling: analysis of two-stage problems. Journal of System Science And Systems Engineering, 12 (4), 371-393.
Chang, Y. C. , C. Y. Lee (2004). Machine scheduling with job delivery coordination. European Journal of Operation Research, 158 (2), 470-487 .
Chen, Z. L., G. Vairaktarakis (2005). Integrated scheduling of production and distribution operations. Management Science, 51 (4), 614–628.
Christofides N., A. Mingozzi, and P. Toth (1981). Exact algorithm for the vehicle routing problem, based on spanning tree and shortest path relaxations. Mathematical Programming, 20, 255-282.
Clarke, G., J. W. Wright (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 568-581.
Colorni A., M. Dorigo, and V. Maniezzo (1991). Distributed optimization by ant colonies. F. J. Varela and P. Bourgine (Ed.), In Proceedings of the First European Conference on Artificial Life (pp. 134-142). Cambridge, Massachusetts: MIP Press.
Colorni, A., M. Dorigo, V. Maniezzo, and M. Trubian (1994). Ant system for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL), 34 (1), 39-53.
Dhaenens-Flipo, C., G. Finke (2001). An integrated model for an industrial production-distribution problem. International Journal of Production and Economics,74 (1-3), 93-101.
Dorigo, M., L. M. Gambardella (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.
Eilon, S., C .Watson-Grandy, N. Christofides (1971). Distribution management: mathematicak modeling and practical analysis. New York: Hanfer.
Garcia, J. M., S. Lozano (2005). Production and delivery scheduling problem with time windows. Computers & Industrial Engineering, 48, 733–742.
Gendreau, M., A. Hertz and G. Laporte (1994). A tabu search heuristic for the routing problem. Management Science, 40, 1276-1290.
Gillett, B. E., , L. R. Miller (1974). A heuristic algorithm for the vehicle dispatch problem. Operations Research, 22, 240-349.
Glass, C. A., C. N. Potts and P. Shade (1994). Unrelated parallel machine scheduling using local search. Mathematical and Computer Modeling, 20 (2), 41–52.
Hall, N. G. , C. N. Potts (2003). Supply chain scheduling: batching and delivery. Operations Research, 51, 566–584.
Hariri, A. M. A., C. N. Potts (1991). Heuristics for scheduling unrelated parallel machines. Computers and Operations Research, 18 (3), 323–331.
Horn, W. A. (1973). Minimizing average flow time with parallel machines. Operations Research, 21, 846–847.
Kim, D. W., K. H. Kim, W. Jang and F. F. Chen (2002). Unrelated parallel machine scheduling with setup times using simulated annealing. Robotics and Computer Integrated Manufacturing, 18 (3–4), 223–231.
Kolen, A. W. J., A. H. G. R. Kan and H. W. J. M. Trienkens (1987). Vehicle routing with time windows. Operations Research, 35 (2), 266-273.
Lee, Y.H., Bhaskaran, K., and Pinedo, M. (1997). A heuristic to minimize the total weighted tardiness with sequence dependent setups. IIE Transactions, 29, 45-52.
Lee, C. Y., Z. L. Chen (2001). Machine scheduling with transportation considerations. Journal of Scheduling, 4, 3–24.
Lenstra, J., A. Rinnooy Kan. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11, 221-227.
Li, C. L., G. Vairaktarakis, C. Y. Lee. (2003). Machine scheduling with deliveries to multiple customer locations. European Journal of Operational Research, 164, 39–51.
Mole, R.H., S.R. Jameson (1976). A sequential route-building algorithm employing a generalized savings criterion. Operational Research Quarterly, 27, 503-511.
Osman, I., (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41, 421-51
Garey R. and Johnson D. S. (1979). Computers and intractability: A guide to the theory of NP completeness. New York: W. H. Freeman and Company.
Renaud, J., G. Laporte and F. F. Boctor (1996). A tabu search heuristics for the multi-depot vehicle routing problems. Computer& Operations Research, 23 (3), 229-235.
Robusté, F., C. F. Daganzo, and R. Souleyrette II (1990). Implementing Vehicle Routing Models. Transportation Research, 24B, 263-286.
Sarmiento, A. M., R. Nagi (1999). A review of integrated analysis of production-distribution systems. IIE Transactions 31 (11), 1061-1074.
Srivastava, B. (1997). An effective heuristic for minimizing makespan on unrelated parallel machines. Journal of the Operational Research Society, 49, 886–894.

Stützle, T.(1998). An ant approach to the flow shop problem. In Proceedings of the 6th European Congress on Intelligent Techniques & Soft Computing(EUFIT'98) (pp. 1560-1564). Aachen: Verlag Mainz.
Suresh, V., C. Dipak (1994). Minimizing maximum tardiness for unrelated parallel machines. Production Economics, 34, 223-229.
Thomas, D. J. and P. M. Griffin. (1996). Coordinated supply chain management. European Journal of Operational Research, 94, 1-15.
Van Breedam, A. (1995) Improvement heuristics for the vehicle routing problem based on simulated annealing. European Journal of Operational Research, 86 (3), 480-490.
Weng, M. , J. Lu and H. Ren (2001). Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective. International Journal of Production Economics, 70, 215–226.
Willard J. A. G. (1989). Vehicle routing using γ-optimal tabu search, Master of Science Dissertation, The Management School, Imperial College, London.
Wren, A., A. Holliday (1972). Computer scheduling of vehicles form one or more depots to a number of delivery points. Operational Research Quarterly, 23, 333-344.