Evolutionary Algorithms for Solving Unconstrained Multilevel Lot-Sizing Problem with Series Structure

doi:10.1007/s12204-012-1227-7

上海交通大学学报（英文版） ›› 2012, Vol. 17 ›› Issue (1): 39-044.doi: 10.1007/s12204-012-1227-7

Evolutionary Algorithms for Solving Unconstrained Multilevel Lot-Sizing Problem with Series Structure

HAN Yi (韩毅), CAI Jian-hu (蔡建湖), IKOU Kaku, LI Yan-lai (李延来) CHEN Yi-zeng (陈以增), TANG Jia-fu (唐加福)

(1. College of Economics and Management, Zhejiang University of Technology, Hangzhou 310023, China; 2. Research Center for Technology Innovation and Enterprise Internationalization, Zhejiang University of Technology, Hongzhou 310023, China; 3. Department of Management Science and Engineering, Akita Prefectural University, Honjo 015-0055, Japan; 4. School of Logistics, Southwest Jiaotong University, Chengdu 610031, China; 5. College of International Business and Management, Shanghai University, Shanghai 200444, China; 6. Institute of Systems Engineering, Northeastern University, Shenyang 110004, China)

收稿日期:2010-07-02 出版日期:2012-02-29 发布日期:2012-03-21
通讯作者: CAI Jian-hu (蔡建湖), E-mail:caijh@zjut.edu.cn

Evolutionary Algorithms for Solving Unconstrained Multilevel Lot-Sizing Problem with Series Structure

HAN Yi (韩毅), CAI Jian-hu (蔡建湖), IKOU Kaku, LI Yan-lai (李延来) CHEN Yi-zeng (陈以增), TANG Jia-fu (唐加福)

(1. College of Economics and Management, Zhejiang University of Technology, Hangzhou 310023, China; 2. Research Center for Technology Innovation and Enterprise Internationalization, Zhejiang University of Technology, Hongzhou 310023, China; 3. Department of Management Science and Engineering, Akita Prefectural University, Honjo 015-0055, Japan; 4. School of Logistics, Southwest Jiaotong University, Chengdu 610031, China; 5. College of International Business and Management, Shanghai University, Shanghai 200444, China; 6. Institute of Systems Engineering, Northeastern University, Shenyang 110004, China)

Received:2010-07-02 Online:2012-02-29 Published:2012-03-21
Contact: CAI Jian-hu (蔡建湖), E-mail:caijh@zjut.edu.cn

摘要/Abstract

摘要： 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.

关键词: simulated annealing (SA), genetic algorithm simulated annealing (SA), genetic algorithm(GA), particle swarm optimization (PSO), multilevel lot-sizing Problem

Abstract: 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.

Key words: simulated annealing (SA), genetic algorithm(GA), particle swarm optimization (PSO), multilevel lot-sizing Problem

中图分类号:

TP29

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 efficient
optimal solutions to the lot-sizing problem in multistage assembly
systems [J]. Management Science, 1984, 30(2): 223-239.

2 Barany I, Van Roy T J, Wolsey L A. Uncapacitated lot
sizing: The convex hull of solutions [J]. Mathematical
Programming Studies, 1984, 22: 32-43.

3 Ball M O, Magnanti T L, Monma C L, et al. Handbooks in
operations research and management science: Network routing [M].
Amsterdam: Elsevier, 1995.

4 Crowston W B, Wagner M H. Dynamic lot size models for
multi-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 a
colony of cooperating agents [J]. IEEE Trans on System, Man,
and Cybernetics, 1996, 26(1): 28-41.

7 Dellaert N, Jeunet J. Solving large unconstrained multilevel
lot-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 Micro
Machine and Human Science. Nagoya, Japan: IEEE, 1995: 39-43.

9 Eppen G D, Martin R K. Solving multi-item capacitated lot-sizing
problems using variable redefinition [J]. Operations Research,
1987, 35(6): 832-848.

10 Goldberg D E. Genetic algorithms in search, optimization and machine
learning [M]. Boston: Addison-Wesley, 1989.

11 Glover F, Kelly J P, Laguna M. Genetic algorithm and Tabu search:
Hybrid for optimizations [J]. Computers \& Operations
Research, 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 simulated
annealing [J]. Science, 1983, 220(4598): 671-680.

14 Karmarkar U S, Schrage L. The deterministic dynamic product cycling
problem [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: An
experimental tests of the particle swarm and some genetic algorithms
on the multimodal problem generator [C]// Proceedings of IEEE
International Conference on Evolutionary Computation. Anchorage,
USA: IEEE, 1998: 78-83.

17 Kaku I, Xiao Y, Xia G. The deterministic annealing algorithms for
vehicle routing problems [J]. International Journal of Smart
Engineering System Design, 2003, 5(4): 327-339.

18 Lin F, Kao C, Hsu C. Applying the genetic approach to simulated
annealing in solving some NP-hard problems [J]. IEEE
Transactions 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: Strong
formulations 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 problems
via 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 Evolutionary
Computation. 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 swarm
optimization [C]// Proceedings of the 7th Annual Conference on
Evolutionary 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 incremental
lot-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 solver
using classification and reformulation [J]. Management
Science, 2002, 48(12): 1587-1602.

31 Wagner H M, Whitin T M. Dynamic version of the economic lot size
model [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 a
dynamic 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.

Evolutionary Algorithms for Solving Unconstrained Multilevel Lot-Sizing Problem with Series Structure

Evolutionary Algorithms for Solving Unconstrained Multilevel Lot-Sizing Problem with Series Structure

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

本文评价