上海交通大学学报(英文版) ›› 2012, Vol. 17 ›› Issue (1): 39-044.doi: 10.1007/s12204-012-1227-7
HAN Yi (韩 毅), CAI Jian-hu (蔡建湖), IKOU Kaku, LI Yan-lai (李延来) CHEN Yi-zeng (陈以增), TANG Jia-fu (唐加福)
收稿日期:
2010-07-02
出版日期:
2012-02-29
发布日期:
2012-03-21
通讯作者:
CAI Jian-hu (蔡建湖),
E-mail:caijh@zjut.edu.cn
HAN Yi (韩 毅), CAI Jian-hu (蔡建湖), IKOU Kaku, LI Yan-lai (李延来) CHEN Yi-zeng (陈以增), TANG Jia-fu (唐加福)
Received:
2010-07-02
Online:
2012-02-29
Published:
2012-03-21
Contact:
CAI Jian-hu (蔡建湖),
E-mail:caijh@zjut.edu.cn
摘要: Abstract: This paper presents a comparative study of evolutionary algorithms which are considered to be effective in solving the multilevel lot-sizing problem in material requirement planning (MRP) systems. Three evolutionary algorithms (simulated annealing (SA), particle swarm optimization (PSO) and genetic algorithm (GA)) are provided. For evaluating the performances of algorithms, the distribution of total cost (objective function) and the average computational time are compared. As a result, both GA and PSO have better cost performances with lower average total costs and smaller standard deviations. When the scale of the multilevel lot-sizing problem becomes larger, PSO is of a shorter computational time.
中图分类号:
HAN Yi (韩 毅), CAI Jian-hu (蔡建湖), IKOU Kaku, LI Yan-lai (李延来) CHE. Evolutionary Algorithms for Solving Unconstrained Multilevel Lot-Sizing Problem with Series Structure[J]. 上海交通大学学报(英文版), 2012, 17(1): 39-044.
HAN Yi (韩 毅), CAI Jian-hu (蔡建湖), IKOU Kaku, LI Yan-lai (李延来) CHEN Yi-zeng (陈以增), TANG Jia-fu (唐加福). Evolutionary Algorithms for Solving Unconstrained Multilevel Lot-Sizing Problem with Series Structure[J]. Journal of shanghai Jiaotong University (Science), 2012, 17(1): 39-044.
1 Afentakis P, Gavish B, Karmarkar U. Computationally efficientoptimal solutions to the lot-sizing problem in multistage assemblysystems [J]. Management Science, 1984, 30(2): 223-239.2 Barany I, Van Roy T J, Wolsey L A. Uncapacitated lotsizing: The convex hull of solutions [J]. MathematicalProgramming Studies, 1984, 22: 32-43.3 Ball M O, Magnanti T L, Monma C L, et al. Handbooks inoperations research and management science: Network routing [M].Amsterdam: Elsevier, 1995.4 Crowston W B, Wagner M H. Dynamic lot size models formulti-stage assembly systems [J]. Management Science, 1973, 20(1): 14-21.5 Constantino M. Lower bounds in lot-sizing models: A polyhedral study[J]. Mathematics of Operations Research, 1998, 23(1):101-118.6 Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by acolony of cooperating agents [J]. IEEE Trans on System, Man,and Cybernetics, 1996, 26(1): 28-41.7 Dellaert N, Jeunet J. Solving large unconstrained multilevellot-sizing problems using a hybrid genetic algorithm [J]. International Journal of Production Research, 2000, 38(5):1083-1099.8 Eberhart R, Kennedy J. A new optimizer using particle swarm theory[C]// Proceedings of 6th International Symposium on MicroMachine and Human Science. Nagoya, Japan: IEEE, 1995: 39-43.9 Eppen G D, Martin R K. Solving multi-item capacitated lot-sizingproblems using variable redefinition [J]. Operations Research,1987, 35(6): 832-848.10 Goldberg D E. Genetic algorithms in search, optimization and machinelearning [M]. Boston: Addison-Wesley, 1989.11 Glover F, Kelly J P, Laguna M. Genetic algorithm and Tabu search:Hybrid for optimizations [J]. Computers \& OperationsResearch, 1995, 22(1): 111-134.12 Holland J H. Adoption in natural and artificial systems [M].Michigan: The University of Michigan Press, 1975.13 Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulatedannealing [J]. Science, 1983, 220(4598): 671-680.14 Karmarkar U S, Schrage L. The deterministic dynamic product cyclingproblem [J]. Operations Research, 1985, 33(2): 326-345.15 Kennedy J, Eberhart R. Particle swarm optimization [C]// Proceedings of IEEE International Conference on Neural Networks.Perth, WA, Australia: IEEE, 1995: 1942-1948.16 Kennedy J, Spears W M. Matching algorithms to problems: Anexperimental tests of the particle swarm and some genetic algorithmson the multimodal problem generator [C]// Proceedings of IEEEInternational Conference on Evolutionary Computation. Anchorage,USA: IEEE, 1998: 78-83.17 Kaku I, Xiao Y, Xia G. The deterministic annealing algorithms forvehicle routing problems [J]. International Journal of SmartEngineering System Design, 2003, 5(4): 327-339.18 Lin F, Kao C, Hsu C. Applying the genetic approach to simulatedannealing in solving some NP-hard problems [J]. IEEETransactions on Systems, Man and Cybernetics, 1993, 23(6):1752-1766.19 Millonas M M. Swarms, phase transition, and collective intelligence [M]. Boston: Addison-Wesley, 1994.20 Mitchell M. An introduction to genetic algorithms [M]. Cambridge:MIT Press, 1996.21 Pochet Y, Wolsey L A. Lot size model with backlogging: Strongformulations and cut planes [J]. Mathematical Programming,1988, 40(1-3): 317-335.22 Rutenbar R A. Simulated annealing algorithms: An overview [J]. IEEE Circuits and Devices Magazine, 1989, 5(1): 19-26.23 Su J, Hu A, He Z. Solving a kind of nonlinear programming problemsvia analog neural networks [J]. Neurocomputing, 1998, 18(1-3): 1-9.24 Shi Y, Eberhart R C. A modified particle swarm optimizer [C]// Proceedings of IEEE International Confeence on EvolutionaryComputation. Anchorage, USA: IEEE, 1998: 69-73.25 Suganthan P N. Particle swarm optimizer with neighborhood operator[C]// Proceedings of the Congress on Evolutionary Computation.Washington, USA: IEEE, 1999: 1958-1962.26 Shi Y, Eberhart R C. Parameter selection in particle swarmoptimization [C]// Proceedings of the 7th Annual Conference onEvolutionary Programming. Berlin, Germany: Springer-Verlag, 1998:591-600.27 Tang O. Simulated annealing in lot sizing problems [J]. International Journal of Production Economics, 2004, 88(2):173-181.28 Veral E A, Laforge R L. The performance of a simple incrementallot-sizing rule in a multilevel inventory environment [J]. Decision Sciences, 1985, 16(1): 57-72.29 Wolsey L A. Uncapacitated lot-sizing problems with start-up costs[J]. Operations Research, 1989, 37(5): 741-747.30 Wolsey L A. Solving multi-item lot-sizing problems with a MIP solverusing classification and reformulation [J]. ManagementScience, 2002, 48(12): 1587-1602.31 Wagner H M, Whitin T M. Dynamic version of the economic lot sizemodel [J]. Management Science, 1958, 5(1): 89-96.32 Yelle L E. Materials requirements lot sizing: A multilevel approach[J]. International Journal of Production Research, 1979, 17(3): 223-232.33 Zangwill W I. Minimum concave cost flows in certain networks [J]. Management Science, 1968, 14(7): 429-450.34 Zangwill W I. A backlogging model and a multi-echelon model of adynamic economic lot size production system---A network approach[J]. Management Science, 1969, 15(9): 506-527. |
[1] | PENG Pai, CHEN Cong , YANG Yongsheng . Particle Swarm Optimization Based on Hybrid Kalman Filter and Particle Filter [J]. J Shanghai Jiaotong Univ Sci, 2020, 25(6): 681-688. |
[2] | QIN Zhichang, XIN Ying, SUN Jianqiao . Multi-Objective Optimal Feedback Controls for Under-Actuated Dynamical System[J]. Journal of Shanghai Jiao Tong University(Science), 2020, 25(5): 545-552. |
[3] | LIU Kai (刘凯), WU Yang (吴阳), GE Zhishang (葛志尚), WANG Yangwei (王扬威), XU Jiaqi (许嘉. Adaptive Multi-Objective Optimization of Bionic Shoulder Joint Based on Particle Swarm Optimization[J]. Journal of Shanghai Jiao Tong University (Science), 2018, 23(4): 550-. |
[4] | JIAO Qinglong (焦庆龙), XU Da (徐达). A Discrete Bat Algorithm for Disassembly Sequence Planning[J]. sa, 2018, 23(2): 276-285. |
[5] | YANG Zhengwu (杨政武), HUO Hong (霍宏), FANG Tao*(方涛). Automatically Finding the Number of Clusters Based on Simulated Annealing[J]. 上海交通大学学报(英文版), 2017, 22(2): 139-147. |
[6] | BIAN Li1* (边 莉), BIAN Chen-yuan1 (边晨源), WANG Shu-min2 (王书民). Large Thinned Array Design Based on Multi-objective Cross Entropy Algorithm[J]. 上海交通大学学报(英文版), 2015, 20(4): 437-442. |
[7] | MAO Li1 (毛力), SONG Yi-chun1* (宋益春), LI Yin1 (李引),YANG Hong2 (杨弘), XIAO Wei2 (肖炜). Research of Improved Fuzzy c-means Algorithm Based on a New Metric Norm[J]. 上海交通大学学报(英文版), 2015, 20(1): 51-55. |
[8] | YU Hai-yang1* (于海洋), ZHANG Shi-lian1 (张世联), LI Cong2 (李聪), WU Shao-bo1 (武少波). Particle Swarm Approach for Structural Optimization of Battleship Strength Deck Under Air Blast[J]. 上海交通大学学报(英文版), 2014, 19(4): 481-487. |
[9] | WANG Ying-lin1,2 (王英林), XU He-ming2* (徐鹤鸣). Multiobjective Particle Swarm Optimization Without the Personal Best[J]. 上海交通大学学报(英文版), 2014, 19(2): 155-159. |
[10] | QU Guo-dong* (屈国栋), LOU Zhang-hua (楼章华). Application of Particle Swarm Algorithm in the Optimal Allocation of Regional Water Resources Based on Immune Evolutionary Algorithm[J]. 上海交通大学学报(英文版), 2013, 18(5): 634-640. |
[11] | LI Xiang-bao* (李祥宝), JI Rui (季睿), YANG Yu-pu (杨煜普). Optimization for PID Controller of Cryogenic Ground Support Equipment Based on Cooperative Random Learning Particle Swarm Optimization[J]. 上海交通大学学报(英文版), 2013, 18(2): 140-146. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||