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

doi:10.1007/s12204-012-1227-7

Journal of shanghai Jiaotong University (Science) ›› 2012, Vol. 17 ›› Issue (1): 39-044.doi: 10.1007/s12204-012-1227-7

• Articles • Previous Articles Next Articles

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)
(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: 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

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

CLC Number:

TP29

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.

References

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]	SUN Xin, WANG Simin, XIE Jingdong, JIANG Hailin, WANG Sen. Improved Transformer-PSO Short-Term Electricity Price Prediction Method Considering Multidimensional Influencing Factors [J]. Journal of Shanghai Jiao Tong University, 2024, 58(9): 1420-1431.
[2]	JI Yuheng, LI Chuntong, LUO Xiaomeng, YANG Xuelian, WANG Deyu. Layout Optimization Design of Human Machine Interface in Wheelhouse Based on Ergonomics [J]. Journal of Shanghai Jiao Tong University, 2024, 58(2): 201-210.
[3]	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.
[4]	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.
[5]	LI Chunxiang,PEI Yangcongqi,YIN Xiao. Nonstationary Non-Gaussian Wind Pressure Prediction Using Hermite Combination Kernel Based EMD-WT-LSSVM [J]. Journal of Shanghai Jiaotong University, 2019, 53(10): 1249-1258.
[6]	LIU Kai (刘凯), WU Yang (吴阳), GE Zhishang (葛志尚), WANG Yangwei (王扬威), XU Jiaqi (许嘉琪), LU Yonghua (陆永华), ZHAO Dongbiao (赵东标). 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-.
[7]	JIAO Qinglong (焦庆龙), XU Da (徐达). A Discrete Bat Algorithm for Disassembly Sequence Planning [J]. Journal of Shanghai Jiao Tong University (Science), 2018, 23(2): 276-285.
[8]	HU Xinming,WANG Deyu. Optimization of Ship Structures Using Ensemble of Surrogates with Recursive Arithmetic Average and Sequential Optimization and Reliability Assessment [J]. Journal of Shanghai Jiaotong University, 2017, 51(2): 150-.
[9]	YANG Zhengwu (杨政武), HUO Hong (霍宏), FANG Tao*(方涛). Automatically Finding the Number of Clusters Based on Simulated Annealing [J]. Journal of shanghai Jiaotong University (Science), 2017, 22(2): 139-147.
[10]	Li Q.; Zhou K.; Yao G.. Combustion optimization model for NOx reduction with an improved particle swarm optimization [J]. J Shanghai Jiaotong Univ Sci, 2016, 21(5): 569-575.
[11]	Zhao C.; Hu H.. Urban end distribution optimization under e-commerce environment [J]. J Shanghai Jiaotong Univ Sci, 2016, 21(5): 513-523.
[12]	HE Tao,HU Jie,XIA Peng,GU Chaochen. Feature Selection of Emg Signal Based on ReliefF Algorithm and Genetic Algorithm [J]. Journal of Shanghai Jiaotong University, 2016, 50(02): 204-208.
[13]	BIAN Li1* (边莉), BIAN Chen-yuan1 (边晨源), WANG Shu-min2 (王书民). Large Thinned Array Design Based on Multi-objective Cross Entropy Algorithm [J]. Journal of shanghai Jiaotong University (Science), 2015, 20(4): 437-442.
[14]	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]. Journal of shanghai Jiaotong University (Science), 2015, 20(1): 51-55.
[15]	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]. Journal of shanghai Jiaotong University (Science), 2014, 19(4): 481-487.

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

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

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles 0

Metrics

Comments