基于擴展?fàn)顟B(tài)任務(wù)網(wǎng)的制造供應(yīng)鏈計劃 - 圖文-

1、 1636 Journal of Software 軟件學(xué)報 Vol.18, No.7, July 2007 知 ,由于采用更新參考解集中的最差解 ,在經(jīng)過少數(shù)重連操作后 ,PR-G 的參考解集的所有解都變得相同 ,其原因 是 ,某些超級精英解在進化過程中迅速將自己的屬性擴散到參考解集的其他解中 ,使得進化過程過早收斂 , 這也 證明了本文提出的基于多樣性的參考解集更新策略的有效性和重要性. Table 1 Comparisons of computation results obtained by five algorithms on all instances 表1 不同算法在計算實例上獲

2、得的結(jié)果比較 Best 0.29 0.12 0.35 0.59 0.62 0.74 0.94 0.98 1.02 1.20 1.51 1.18 1.33 1.86 1.73 1.53 1.76 2.23 0.90 1.79 1.64 Tabu Worst Best 2.58 1.11 3.25 1.35 2.54 1.89 3.17 1.84 3.04 1.76 3.26 1.93 4.03 2.16 3.45 2.66 3.54 2.76 3.52 2.85 3.36 2.56 3.57 2.35 3.71 2.16 3.12 2.57 3.54 2.33 3.40 2.55 4.10 3.

3、01 3.44 2.79 3.64 2.69 3.15 2.62 3.89 2.77 PR-G Worst Best 3.25 1.89 2.85 1.52 3.48 1.03 2.35 2.10 2.21 1.74 2.59 1.55 3.39 1.08 2.92 1.24 3.67 1.32 2.78 1.29 2.62 1.42 3.01 1.63 2.81 2.37 3.12 2.43 2.94 1.67 2.47 1.41 3.02 1.56 2.13 1.27 3.53 1.80 3.81 2.32 3.21 1.93 PR-U Worst Best 0.67 0 0.77 0 0

4、.98 0 0.20 0 0.35 0 0.47 0 1.05 0 0.55 0.012 0.44 0 0.59 0.018 0.48 0.033 0.51 0.019 0.39 0 0.21 0.085 0.45 0.053 0.21 0.075 0.32 0.11 0.18 0.094 0.57 0.14 1.03 0.16 0.81 0.099 PR-D Worst Best 0 0 0 0 0 0 0.12 0 0.20 0 0.18 0 0.46 0 0.31 0 0.087 0 0.48 0 0.27 0 0.35 0 0.34 0 0.097 0 0.24 0 0.192 0 0

5、.26 0 0.15 0 0.42 0 0.37 0 0.49 0 GA Worst 0.76 0.56 0.62 2.36 2.56 2.61 2.50 2.12 2.14 2.42 2.66 2.24 1.72 2.35 2.10 2.34 2.56 2.78 2.25 2.98 2.83 Num 2 3 4 5 6 7 8 No. 2-1 2-2 2-3 3-1 3-2 3-3 4-1 4-2 4-3 5-1 5-1 5-3 6-1 6-2 6-3 7-1 7-2 7-3 8-1 8-2 8-3 Best 104 05 111 21 115 69 165 60 169 82 170 25

6、 227 84 210 46 220 76 282 70 274 61 291 04 351 35 363 43 357 97 438 29 451 23 421 59 522 50 546 18 523 23 為進一步了解路徑重連算法的進化計算過程,圖 6 給出了 PR-D 算法、 PR-G 算法和 GA 算法在求解實例 5-1 時所具有的解收斂曲線(100 代進化過程 .對于路徑重連算法,用兩個解的一次重連作為一個進化代(PR 算法 和 GA 算法的一個進化代的耗用時間不一樣,且對于 100 代進化過程,PR-D 算法和 PR-U 算法所獲得的解一致, 故只標(biāo)注出 PR-D 算法.從圖 6

7、 可以看出,PR-D 算法的搜索過程不僅速度快,很快就達到了 GA 算法的相同解質(zhì) 量,而且收斂代數(shù)跨度大,即能夠改善解的進化過程長,故其獲得的解的質(zhì)量比 GA 算法要好很多.對于 PR-G 算 法 , 雖然其收斂速度也很快 , 但是在經(jīng)過少數(shù)進化代數(shù)后 , 其解不再改善 , 出現(xiàn)這種情況也是由于參考解集多樣 性迅速降低的原因. 圖 7 給出了 PR-D 算法和 PR-U 算法在求解實例 5-1 的全過程中參考解集的最優(yōu)解和最差解的變化趨勢(分 別用 PR-D(worst,PR-D(best,PR-U(worst和 PR-U(best表示 .從圖 7 可以看出,PR-D 算法和 PR-U 算法

8、在進化 前期趨勢相同,其原因是在 PR-D 算法沒有調(diào)用分散性解變異策略以前,PR-D 算法和 PR-U 算法一樣,而由于路 徑重連算法是一種確定性演化算法,故在初始參考解集相同的條件下,其進化過程相同.在 PR-D 算法中,當(dāng)重連 解不能進一步改善最好解時 ,調(diào)用多樣性策略 ,故 PR-D(best 和 PR-D(worst進一步改善 (進化曲線繼續(xù)向上波 動 .此外 ,比較 PR-U(best曲線和 PR-D(worst曲線可知 ,在結(jié)束進化時 ,PR-D 算法的參考解集的最差解也接近 PR-U 算法的最好解,從另一角度說明了 PR-D 中分散性解變異策略的有效性. 比較 GA 和 Tab

9、u 搜索算法,PR-D 算法消耗的總時間更長,將 GA 和 Tabu 搜索算法的最大計算代數(shù)均設(shè)為 100,在實例 5-1 上,GA 和 Tabu 搜索算法的計算時間分別為 17s 和 29s,而 PR-D 算法需要 3 分鐘.PR-D 算法需要 更多計算時間的原因是起始解與向?qū)Ы庵g的連接過程比較耗時.然而,PR-D 算法獲得與 GA 算法相同的解的 質(zhì)量的計算時間卻相當(dāng)短,如圖 6 所示,僅僅需要約 10s 的時間 PR-D 算法即可獲得與 GA 算法相當(dāng)?shù)慕獾馁|(zhì)量, 這表明,PR-D 算法在計算效率上仍然具有競爭力,但大部分時間用于后續(xù)的解改善過程. 蘇生 等:基于擴展?fàn)顟B(tài)任務(wù)網(wǎng)的制造供

10、應(yīng)鏈計劃 1637 28100 28000 27900 27800 27700 27600 27500 27400 27300 27200 27100 27000 28400 28200 Objective function value GA PR-G PR-D 27800 27600 27400 27200 27000 26800 26600 26400 26200 0 20 40 60 80 100 0 100 200 300 400 500 Evolutionary generation Evolutionary generation PR-U (worst PR-U (best PR-

11、D (worst PR-D (best Objective function value Fig.6 The evolutionary process of PR-D, PR-G and GA PR-D,PR-G 和 GA 算法的 進化過程 Fig.7 圖7 The evolution processes of the best solution and PR-D 和 PR-U 的參考解集中最好解與最差解的 演化過程 the worst solution in the reference set of PR-D and PR-G 圖6 5 結(jié) 論 本文提出了一種統(tǒng)一描述具有復(fù)雜產(chǎn)品結(jié)構(gòu) (包括

12、裝配型、分解型和多輸入多輸出型等 的生產(chǎn)任務(wù)、存 儲任務(wù)和不同模式 (包括單種物料獨立運輸模式和多種物料組合運輸模式 的運輸任務(wù)的過程模型擴展?fàn)?態(tài)任務(wù)網(wǎng) ,并建立了基于擴展?fàn)顟B(tài)任務(wù)網(wǎng)的制造供應(yīng)鏈計劃問題模型 .為有效求解此模型 ,提出了特殊的問題編 碼機制和具有多樣性檢測的參考解集更新策略與分散性解變異策略的路徑重連算法 . 通過計算實例證明了路 徑重連算法的有效性 ,并分析了不同策略條件下路徑重連算法的進化過程 .然而 ,路徑重連算法的總計算時間偏 長,下一步我們將重點研究其計算效率問題. 此外 , 還可以通過在不同任務(wù)間或者不同周期間微調(diào)任務(wù)分配量來進一步優(yōu)化結(jié)果 , 如基于分配數(shù)量的鄰

13、 域搜索,但由于本文的重點在于路徑重連算法,故不強調(diào)這種微調(diào). 本文也只重點研究供應(yīng)鏈集成計劃 ,不涉及企業(yè)間的協(xié)調(diào)和協(xié)商問題 . 基于協(xié)商的供應(yīng)鏈計劃是另一個研 究方向. References: 1 2 3 4 5 6 7 8 Erenguc SS, Simpson NC, Vakharia AJ. Integrated production/distribution planning in supply chains: An invited review. European Journal of Operational Research, 1999,115(2:219236. Guinet

14、 A. Multi-Site planning: A transshipment problem. Intl Journal of Production Economics, 2001,74(1-3:2132. Jolayemi JK, Olorunniwo FO. A deterministic model for planning production quantities in a multi-plant, multi-warehouse environment with extensible capacities. Intl Journal of Production Economic

15、s, 2004,87(2:99113. Özdamar L, Yazgac T. A hierarchical planning approach for a production-distribution system. Intl Journal of Production Research, 1999,37(16:37593772. Chen HL, Zhang J, Ma DZ. Research on supply chain collaborative planning based on cost and time balance optimization. Compute

16、r Integrated Manufacturing Systems, 2004,10(12:15181522 (in Chinese with English abstract. Gen M, Syarif A. Hybrid genetic algorithm for multi-time period production distribution planning. Computers and Industrial Engineering, 2005,48(4:799809. Wu SD, Golbasi H. Multi-Item, multi-facility supply cha

17、in planning: Models, complexities, and algorithms. Computational Optimization and Applications, 2004,28(3:325356. Fang SC, Qi L. Manufacturing network flows: A generalized network flow model for manufacturing process modeling. Optimization Methods and Software, 2003,18(2:143165. 1638 Journal of Soft

18、ware 軟件學(xué)報 Vol.18, No.7, July 2007 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Mo J, Qi L, Wei Z. A manufacturing supply chain optimization model for distilling process. Applied Mathematics and Computation, 2005,171(1:464485. Sakawa M, Nishizaki I, Uemura Y. Fuzzy programming and profit and cos

19、t allocation for a production and transportation problem. European Journal of Operational Research, 2001,131(4:115. Glover F. Tabu search for nonlinear and parametric optimization (with links to genetic algorithms. Discrete Applied Mathematics, 1994,49(1-3:231255. Glover F, Laguna M, Martí R. F

20、undamentals of scatter search and path relinking. Control and Cybernetics, 2000,29(3:653684. Laguna M, Marti R. GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS Journal on Computing, 1999,11(1:4452. Resende MGC, Ribeiro CC. A GRASP with path-relinking for private vir

21、tual circuit routing. Networks, 2003,41(2:104114. Estefania P, Isaac P, Vicente C, Rafael M. GRASP and path relinking for the matrix bandwidth minimization. European Journal of Operational Research, 2004,153(1:200210. Aiex RM, Resende MGC, Pardalos PM. GRASP with path relinking for three-index assig

22、nment. Journal on Computing, 2005,17(2: 224247. Sin CH, Michel G. Path relinking for the vehicle routing problem. Journal of Heuristics, 2006,12(1-2:5572. Zhang GQ, Lai KK. Combining path relinking and genetic algorithms for the multiple-level warehouse layout problem. European Journal of Operationa

23、l Research, 2006,169(2:413425. Yagiura M, Ibaraki T, Glover F. A path relinking approach with ejection chains for the generalized assignment problem. European Journal of Operational Research, 2006,169(2:548569. Cotta C. Scatter search with path relinking for phylogenetic inference. European Journal

24、of Operational Research, 2006,169(2: 520532. Diaz JA, Fernandez E. Hybrid scatter search and path relinking for the capacitated p-median problem. European Journal of Operational Research, 2006,169(2:570585. Festa P, Pardalos PM, Resende MGC, Ribeiro CC. Randomized heuristics for the max-cut problem. Optimization Methods and Software, 2002,7(6:10331058. Kondili