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

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

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 為進(jìn)一步了解路徑重連算法的進(jìn)化計(jì)算過(guò)程,圖 6 給出了 PR-D 算法、 PR-G 算法和 GA 算法在求解實(shí)例 5-1 時(shí)所具有的解收斂曲線(100 代進(jìn)化過(guò)程 .對(duì)于路徑重連算法,用兩個(gè)解的一次重連作為一個(gè)進(jìn)化代(PR 算法 和 GA 算法的一個(gè)進(jìn)化代的耗用時(shí)間不一樣,且對(duì)于 100 代進(jìn)化過(guò)程,PR-D 算法和 PR-U 算法所獲得的解一致, 故只標(biāo)注出 PR-D 算法.從圖 6

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

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

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

10、應(yīng)鏈計(jì)劃 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 算法的 進(jìn)化過(guò)程 Fig.7 圖7 The evolution processes of the best solution and PR-D 和 PR-U 的參考解集中最好解與最差解的 演化過(guò)程 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ù)、存 儲(chǔ)任務(wù)和不同模式 (包括單種物料獨(dú)立運(yùn)輸模式和多種物料組合運(yùn)輸模式 的運(yùn)輸任務(wù)的過(guò)程模型擴(kuò)展?fàn)?態(tài)任務(wù)網(wǎng) ,并建立了基于擴(kuò)展?fàn)顟B(tài)任務(wù)網(wǎng)的制造供應(yīng)鏈計(jì)劃問(wèn)題模型 .為有效求解此模型 ,提出了特殊的問(wèn)題編 碼機(jī)制和具有多樣性檢測(cè)的參考解集更新策略與分散性解變異策略的路徑重連算法 . 通過(guò)計(jì)算實(shí)例證明了路 徑重連算法的有效性 ,并分析了不同策略條件下路徑重連算法的進(jìn)化過(guò)程 .然而 ,路徑重連算法的總計(jì)算時(shí)間偏 長(zhǎng),下一步我們將重點(diǎn)研究其計(jì)算效率問(wèn)題. 此外 , 還可以通過(guò)在不同任務(wù)間或者不同周期間微調(diào)任務(wù)分配量來(lái)進(jìn)一步優(yōu)化結(jié)果 , 如基于分配數(shù)量的鄰

13、 域搜索,但由于本文的重點(diǎn)在于路徑重連算法,故不強(qiáng)調(diào)這種微調(diào). 本文也只重點(diǎn)研究供應(yīng)鏈集成計(jì)劃 ,不涉及企業(yè)間的協(xié)調(diào)和協(xié)商問(wèn)題 . 基于協(xié)商的供應(yīng)鏈計(jì)劃是另一個(gè)研 究方向. 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é)報(bào) 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