doi: 10.3934/jimo.2018160

A hybrid chaos firefly algorithm for three-dimensional irregular packing problem

1. 

School of Computer Sciences and information, Anhui Normal University, Anhui Provincial Key Laboratory of Network and Information Security, Wuhu, 241000, China

2. 

Department of Mathematics and Statistics, Curtin University, Perth, WA 6845, Australia

* Corresponding author: Lin Jiang

Received  March 2017 Revised  April 2018 Published  October 2018

Fund Project: The first author is supported by NSFC grant (61871412, 61772034, 61572036, 61672039, 61473326), Anhui Provincial Natural Science Foundation(1708085MF156, 1808085MF172), Australian Research Council Linkage Program LP140100873

The packing problem study how to pack multiple objects without overlap. Various exact and approximate algorithms have been developed for two-dimensional regular and irregular packing as well as three-dimensional bin packing. However, few results are reported for three-dimensional irregular packing problems. This paper will develop a method for solving three-dimensional irregular packing problems. A three-grid approximation technique is first introduced to approximate irregular objects. Then, a hybrid heuristic method is developed to place and compact each individual objects where chaos search is embedded into firefly algorithm in order to enhance the algorithm's diversity for optimizing packing sequence and orientations. Results from several computational experiments demonstrate the effectiveness of the hybrid algorithm.

Citation: Chuanxin Zhao, Lin Jiang, Kok Lay Teo. A hybrid chaos firefly algorithm for three-dimensional irregular packing problem. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2018160
References:
[1]

Y. AbdelsadekF. HerrmannI. Kacem and B. Otjacques, Branch-and-bound algorithm for the maximum triangle packing problem, Computers & Industrial Engineering, 81 (2015), 147-157. doi: 10.1016/j.cie.2014.12.006.

[2]

R. Alvarez-ValdesA. Martinez and J. M. Tamarit, A branch and bound algorithm for cutting and packing irregularly shaped pieces, Computers & Operations Research, 145 (2013), 463-477. doi: 10.1016/j.ijpe.2013.04.007.

[3]

I. Araya and M. C. Riff, A beam search approach to the container loading problem, Computers & Operations Research, 43 (2014), 100-107. doi: 10.1016/j.cor.2013.09.003.

[4]

T. Back, Evolutionary algorithms in theory and practice: Evolution strategies, evolutionary programming, genetic algorithms, The Clarendon Press, Oxford University Press, New York, 1996.

[5]

J. C. Bean, Genetic algorithms and random keys for sequencing and optimization, ORSA Journal on Computing, 6 (1994), 150-160. doi: 10.1287/ijoc.6.2.154.

[6]

E. K. BurkeR. S. R. HellierG. Kendall and G. Whitwell, Irregular packing using the line and arc no-fit polygon, Operations Research, 58 (2010), 948-970. doi: 10.1287/opre.1090.0770.

[7]

P. ChenZ. FuA. Lim and B. Rodrigues, The two dimensional packing problem for irregular objects, International Journal on Artificial Intelligent Tools, 13 (2004), 429-448. doi: 10.1142/S0218213004001624.

[8]

N. ChernovY. Stoyan and T. Romanova, Mathematical model and efficient algorithms for object packing problem, Computational Geometry, 43 (2010), 535-553. doi: 10.1016/j.comgeo.2009.12.003.

[9]

D. CinarJ. A. OliveiraY. I. Topcu and P. M. Pardalos, A priority-based genetic algorithm for a flexible job shop scheduling problem, Journal of Industrial and Management Optimization, 12 (2016), 1391-1415. doi: 10.3934/jimo.2016.12.1391.

[10]

L. D. S. Coelho and V. C. Mariani, Firefly algorithm approach based on chaotic Tinkerbell map applied to multivariable PID controller tuning, Computers & Mathematics with Applications, 64 (2012), 2371-2382. doi: 10.1016/j.camwa.2012.05.007.

[11]

T. Dereli and G. S. Das, A hybrid 'bee(s) algorithm' for solving container loading problems, Applied Soft Computing, 11 (2011), 2854-2862. doi: 10.1016/j.asoc.2010.11.017.

[12]

T. Dokeroglu and A. Cosar, Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms, Computers & Industrial Engineering, 75 (2014), 176-186. doi: 10.1016/j.cie.2014.06.002.

[13]

A. Elkeran, A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering, European Journal of Operational Research, 231 (2013), 757-769. doi: 10.1016/j.ejor.2013.06.020.

[14]

I. FisterS. M. Kamal and I. Fister, A review of chaos-based firefly algorithms: Perspectives and research challenges, Applied Mathematics and Computation, 252 (2015), 155-165. doi: 10.1016/j.amc.2014.12.006.

[15]

J. F. Gonçalves and M. G. Resende, A biased random key genetic algorithm for 2D and 3D bin packing problems, International Journal of Production Economics, 145 (2013), 500-510.

[16]

H. Hasni and H. Sabri, On a hybrid Genetic Algorithm for solving the container loading problem with no orientation constraints, Journal of Mathematical Modelling and Algorithms in Operations Research, 12 (2013), 67-84.

[17]

W. Huang and K. He, A new heuristic algorithm for cuboids packing with no orientation constraints, Computers & Operations Research, 36 (2009), 425-432. doi: 10.1016/j.cor.2007.09.008.

[18]

R. Karmakar and S. Chattopadhyay, Window-based peak power model and Particle Swarm Optimization guided 3-dimensional bin packing for SoC test scheduling, Integration, the VLSI Journal, 50 (2015), 61-73. doi: 10.1016/j.vlsi.2015.01.006.

[19]

P. LaxmiS. Indira and K. Jyothsna, Ant colony optimization for optimum service times in a Bernoulli schedule vacation interruption queue with balking and reneging, Journal of Industrial and Management Optimization, 12 (2016), 1199-1214. doi: 10.3934/jimo.2016.12.1199.

[20]

T. W. LeungK. C. Chi and M. D. Troutt, A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics, Journal of Industrial and Management Optimization, 4 (2008), 53-66. doi: 10.3934/jimo.2008.4.53.

[21]

S. C. H. LeungY. Lin and D. Zhang, Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem, Computers & Operations Research, 39 (2012), 678-686. doi: 10.1016/j.cor.2011.05.025.

[22]

Y. K. Lin and C. S. Chong, A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem, Journal of Industrial and Management Optimization, 12 (2016), 703-717. doi: 10.3934/jimo.2016.12.703.

[23]

A. LodiS. Martello and M. Monaci, Two dimensional packing problems: A survey, European Journal of Operational Research, 141 (2002), 241-252. doi: 10.1016/S0377-2217(02)00123-6.

[24]

Q. Long and C. Wu, A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization, Journal of Industrial and Management Optimization, 10 (2014), 1279-1296. doi: 10.3934/jimo.2014.10.1279.

[25]

Q. LongC. WuT. Huang and X. Wang, A genetic algorithm for unconstrained multi-objective optimization, Swarm and Evolutionary Computation, 22 (2015), 1-14. doi: 10.1016/j.swevo.2015.01.002.

[26]

S. Martello and M. Monaci, Models and algorithms for packing rectangles into the smallest square, Computers & Operations Research, 63 (2015), 161-171. doi: 10.1016/j.cor.2015.04.024.

[27]

A. Moura and J. F. Oliveira, Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms, Computers & Industrial Engineering, 75 (2014), 176-186.

[28]

E. OsabaX. S. YangF. DiazE. OnievaA. D. Masegosa and A. Perallos, A discrete firefly algorithm to solve a rich vehicle routing problem modelling a newspaper distribution system with recycling policy, Soft Computing, 21 (2017), 5295-5308. doi: 10.1007/s00500-016-2114-1.

[29]

J. SenthilnathS. N. Omkar and V. Mani, Clustering using firefly algorithm: Performance study, Swarm and Evolutionary Computation, 1 (2011), 164-171. doi: 10.1016/j.swevo.2011.06.003.

[30]

S. TaoC. WuZ. Sheng and X. Wang, Stochastic Project Scheduling with Hierarchical Alternatives, Applied Mathematical Modelling, 58 (2018), 181-202. doi: 10.1016/j.apm.2017.09.015.

[31]

S. TaoC. WuZ. Sheng and X. Wang, Space-Time Repetitive Project Scheduling Considering Location and Congestion, Journal of Computing in Civil Engineering, 32 (2018), 04018017. doi: 10.1061/(ASCE)CP.1943-5487.0000745.

[32]

H. Terashima-MarínP. RossC. J. Farías-ZárateE. López-Camacho and M. Valenzuela-Rendón, Generalized hyper-heuristics for solving 2D Regular and irregular Packing Problems, Annals of Operations Research, 179 (2010), 369-392. doi: 10.1007/s10479-008-0475-2.

[33]

A. Trivella and D. Pisinger, The load-balanced multi-dimensional bin-packing problem, Computers & Operations Research, 74 (2014), 152-164. doi: 10.1016/j.cor.2016.04.020.

[34]

W. K. WongX. X. WangP. Y. MokS. Y. S. Leung and C. K. Kwong, Solving the two-dimensional irregular objects allocation problems by using a two-stage packing approach, Expert Systems with Applications, 36 (2009), 3489-3496. doi: 10.1016/j.eswa.2008.02.068.

[35]

X. S. Yang, Swarm-based metaheuristic algorithms and no-free-lunch theorems, in Theory and New Applications of Swarm Intelligence(Eds. R. Parpinelli and H. S.Lopes), Intech Open Science, 192 (2012), 1-2. doi: 10.1016/j.ins.2012.02.002.

[36]

X. S. Yang and X. He, Firefly algorithm: Recent advances and applications, International Journal of Swarm Intelligence, 1 (2013), 36-50. doi: 10.1504/IJSI.2013.055801.

[37]

M. A. Zaman and M. A. Matin, Nonuniformly spaced linear antenna array design using firefly algorithm, International Journal of Microwave Science and Technology, 2012 (2012), Article ID 256759, 8 pages. doi: 10.1155/2012/256759.

[38]

C. Zhao, C. Wu, J. Chai, X. Wang, X. Yang and J. M. Lee, et al., Decomposition-based multi-objective firefly algorithm for RFID network planning with uncertainty, Applied Soft Computing, 55 (2017), 549-564.

[39]

C. Zhao, C. Wu, X. Wang, W. K. Ling, K. L.Teo and J. M. Lee, et al., Maximizing lifetime of a wireless sensor network via joint optimizing sink placement and sensor-to-sink routing, Applied Mathematical Modelling, 49 (2017), 319-337. doi: 10.1016/j.apm.2017.05.001.

show all references

References:
[1]

Y. AbdelsadekF. HerrmannI. Kacem and B. Otjacques, Branch-and-bound algorithm for the maximum triangle packing problem, Computers & Industrial Engineering, 81 (2015), 147-157. doi: 10.1016/j.cie.2014.12.006.

[2]

R. Alvarez-ValdesA. Martinez and J. M. Tamarit, A branch and bound algorithm for cutting and packing irregularly shaped pieces, Computers & Operations Research, 145 (2013), 463-477. doi: 10.1016/j.ijpe.2013.04.007.

[3]

I. Araya and M. C. Riff, A beam search approach to the container loading problem, Computers & Operations Research, 43 (2014), 100-107. doi: 10.1016/j.cor.2013.09.003.

[4]

T. Back, Evolutionary algorithms in theory and practice: Evolution strategies, evolutionary programming, genetic algorithms, The Clarendon Press, Oxford University Press, New York, 1996.

[5]

J. C. Bean, Genetic algorithms and random keys for sequencing and optimization, ORSA Journal on Computing, 6 (1994), 150-160. doi: 10.1287/ijoc.6.2.154.

[6]

E. K. BurkeR. S. R. HellierG. Kendall and G. Whitwell, Irregular packing using the line and arc no-fit polygon, Operations Research, 58 (2010), 948-970. doi: 10.1287/opre.1090.0770.

[7]

P. ChenZ. FuA. Lim and B. Rodrigues, The two dimensional packing problem for irregular objects, International Journal on Artificial Intelligent Tools, 13 (2004), 429-448. doi: 10.1142/S0218213004001624.

[8]

N. ChernovY. Stoyan and T. Romanova, Mathematical model and efficient algorithms for object packing problem, Computational Geometry, 43 (2010), 535-553. doi: 10.1016/j.comgeo.2009.12.003.

[9]

D. CinarJ. A. OliveiraY. I. Topcu and P. M. Pardalos, A priority-based genetic algorithm for a flexible job shop scheduling problem, Journal of Industrial and Management Optimization, 12 (2016), 1391-1415. doi: 10.3934/jimo.2016.12.1391.

[10]

L. D. S. Coelho and V. C. Mariani, Firefly algorithm approach based on chaotic Tinkerbell map applied to multivariable PID controller tuning, Computers & Mathematics with Applications, 64 (2012), 2371-2382. doi: 10.1016/j.camwa.2012.05.007.

[11]

T. Dereli and G. S. Das, A hybrid 'bee(s) algorithm' for solving container loading problems, Applied Soft Computing, 11 (2011), 2854-2862. doi: 10.1016/j.asoc.2010.11.017.

[12]

T. Dokeroglu and A. Cosar, Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms, Computers & Industrial Engineering, 75 (2014), 176-186. doi: 10.1016/j.cie.2014.06.002.

[13]

A. Elkeran, A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering, European Journal of Operational Research, 231 (2013), 757-769. doi: 10.1016/j.ejor.2013.06.020.

[14]

I. FisterS. M. Kamal and I. Fister, A review of chaos-based firefly algorithms: Perspectives and research challenges, Applied Mathematics and Computation, 252 (2015), 155-165. doi: 10.1016/j.amc.2014.12.006.

[15]

J. F. Gonçalves and M. G. Resende, A biased random key genetic algorithm for 2D and 3D bin packing problems, International Journal of Production Economics, 145 (2013), 500-510.

[16]

H. Hasni and H. Sabri, On a hybrid Genetic Algorithm for solving the container loading problem with no orientation constraints, Journal of Mathematical Modelling and Algorithms in Operations Research, 12 (2013), 67-84.

[17]

W. Huang and K. He, A new heuristic algorithm for cuboids packing with no orientation constraints, Computers & Operations Research, 36 (2009), 425-432. doi: 10.1016/j.cor.2007.09.008.

[18]

R. Karmakar and S. Chattopadhyay, Window-based peak power model and Particle Swarm Optimization guided 3-dimensional bin packing for SoC test scheduling, Integration, the VLSI Journal, 50 (2015), 61-73. doi: 10.1016/j.vlsi.2015.01.006.

[19]

P. LaxmiS. Indira and K. Jyothsna, Ant colony optimization for optimum service times in a Bernoulli schedule vacation interruption queue with balking and reneging, Journal of Industrial and Management Optimization, 12 (2016), 1199-1214. doi: 10.3934/jimo.2016.12.1199.

[20]

T. W. LeungK. C. Chi and M. D. Troutt, A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics, Journal of Industrial and Management Optimization, 4 (2008), 53-66. doi: 10.3934/jimo.2008.4.53.

[21]

S. C. H. LeungY. Lin and D. Zhang, Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem, Computers & Operations Research, 39 (2012), 678-686. doi: 10.1016/j.cor.2011.05.025.

[22]

Y. K. Lin and C. S. Chong, A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem, Journal of Industrial and Management Optimization, 12 (2016), 703-717. doi: 10.3934/jimo.2016.12.703.

[23]

A. LodiS. Martello and M. Monaci, Two dimensional packing problems: A survey, European Journal of Operational Research, 141 (2002), 241-252. doi: 10.1016/S0377-2217(02)00123-6.

[24]

Q. Long and C. Wu, A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization, Journal of Industrial and Management Optimization, 10 (2014), 1279-1296. doi: 10.3934/jimo.2014.10.1279.

[25]

Q. LongC. WuT. Huang and X. Wang, A genetic algorithm for unconstrained multi-objective optimization, Swarm and Evolutionary Computation, 22 (2015), 1-14. doi: 10.1016/j.swevo.2015.01.002.

[26]

S. Martello and M. Monaci, Models and algorithms for packing rectangles into the smallest square, Computers & Operations Research, 63 (2015), 161-171. doi: 10.1016/j.cor.2015.04.024.

[27]

A. Moura and J. F. Oliveira, Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms, Computers & Industrial Engineering, 75 (2014), 176-186.

[28]

E. OsabaX. S. YangF. DiazE. OnievaA. D. Masegosa and A. Perallos, A discrete firefly algorithm to solve a rich vehicle routing problem modelling a newspaper distribution system with recycling policy, Soft Computing, 21 (2017), 5295-5308. doi: 10.1007/s00500-016-2114-1.

[29]

J. SenthilnathS. N. Omkar and V. Mani, Clustering using firefly algorithm: Performance study, Swarm and Evolutionary Computation, 1 (2011), 164-171. doi: 10.1016/j.swevo.2011.06.003.

[30]

S. TaoC. WuZ. Sheng and X. Wang, Stochastic Project Scheduling with Hierarchical Alternatives, Applied Mathematical Modelling, 58 (2018), 181-202. doi: 10.1016/j.apm.2017.09.015.

[31]

S. TaoC. WuZ. Sheng and X. Wang, Space-Time Repetitive Project Scheduling Considering Location and Congestion, Journal of Computing in Civil Engineering, 32 (2018), 04018017. doi: 10.1061/(ASCE)CP.1943-5487.0000745.

[32]

H. Terashima-MarínP. RossC. J. Farías-ZárateE. López-Camacho and M. Valenzuela-Rendón, Generalized hyper-heuristics for solving 2D Regular and irregular Packing Problems, Annals of Operations Research, 179 (2010), 369-392. doi: 10.1007/s10479-008-0475-2.

[33]

A. Trivella and D. Pisinger, The load-balanced multi-dimensional bin-packing problem, Computers & Operations Research, 74 (2014), 152-164. doi: 10.1016/j.cor.2016.04.020.

[34]

W. K. WongX. X. WangP. Y. MokS. Y. S. Leung and C. K. Kwong, Solving the two-dimensional irregular objects allocation problems by using a two-stage packing approach, Expert Systems with Applications, 36 (2009), 3489-3496. doi: 10.1016/j.eswa.2008.02.068.

[35]

X. S. Yang, Swarm-based metaheuristic algorithms and no-free-lunch theorems, in Theory and New Applications of Swarm Intelligence(Eds. R. Parpinelli and H. S.Lopes), Intech Open Science, 192 (2012), 1-2. doi: 10.1016/j.ins.2012.02.002.

[36]

X. S. Yang and X. He, Firefly algorithm: Recent advances and applications, International Journal of Swarm Intelligence, 1 (2013), 36-50. doi: 10.1504/IJSI.2013.055801.

[37]

M. A. Zaman and M. A. Matin, Nonuniformly spaced linear antenna array design using firefly algorithm, International Journal of Microwave Science and Technology, 2012 (2012), Article ID 256759, 8 pages. doi: 10.1155/2012/256759.

[38]

C. Zhao, C. Wu, J. Chai, X. Wang, X. Yang and J. M. Lee, et al., Decomposition-based multi-objective firefly algorithm for RFID network planning with uncertainty, Applied Soft Computing, 55 (2017), 549-564.

[39]

C. Zhao, C. Wu, X. Wang, W. K. Ling, K. L.Teo and J. M. Lee, et al., Maximizing lifetime of a wireless sensor network via joint optimizing sink placement and sensor-to-sink routing, Applied Mathematical Modelling, 49 (2017), 319-337. doi: 10.1016/j.apm.2017.05.001.

Figure 1.  Grid representation of a cylinder
Figure 2.  Encoding of the firefly individual
Figure 3.  A procedure of back bottom left placement for 3D irregular packing
Figure 4.  Architecture of the chaos firefly algorithm for packing problem
Figure 5.  An example of comparison between random sequence packing result and optimized sequence packing result
Figure 6.  The comparison packing result of instance 6 without rotation
Figure 7.  The comparison packing result of instance 8 with rotation
Figure 8.  Algorithm convergence over 9 instances
Table 1.  Data sets specification
Instance Type Number Rotation Object scale
1 cylinder 1 50 0 ${50^ * }{50^ * }50$
2 cylinder 2 80 0 ${50^ * }{50^ * }50$
3 cylinder 3 100 0 ${50^ * }{50^ * }50$
4 irregular 1 (cylinder, complex structure) 50 0 ${50^ * }{50^ * }50$
5 irregular 2 (cylinder, complex structure) 80 0 ${50^ * }{50^ * }50$
6 irregular 3 (cylinder, complex structure) 100 0 ${50^ * }{50^ * }50$
7 irregular 4 (cylinder, complex structure) 40 0, 3 ${50^ * }{50^ * }50$
8 irregular 5 (cylinder, complex structure) 60 0, 3 ${50^ * }{50^ * }50$
9 irregular 6 (cylinder, complex structure) 80 0, 3 ${50^ * }{50^ * }50$
Instance Type Number Rotation Object scale
1 cylinder 1 50 0 ${50^ * }{50^ * }50$
2 cylinder 2 80 0 ${50^ * }{50^ * }50$
3 cylinder 3 100 0 ${50^ * }{50^ * }50$
4 irregular 1 (cylinder, complex structure) 50 0 ${50^ * }{50^ * }50$
5 irregular 2 (cylinder, complex structure) 80 0 ${50^ * }{50^ * }50$
6 irregular 3 (cylinder, complex structure) 100 0 ${50^ * }{50^ * }50$
7 irregular 4 (cylinder, complex structure) 40 0, 3 ${50^ * }{50^ * }50$
8 irregular 5 (cylinder, complex structure) 60 0, 3 ${50^ * }{50^ * }50$
9 irregular 6 (cylinder, complex structure) 80 0, 3 ${50^ * }{50^ * }50$
Table 2.  Parameters of the hybrid firefly algorithm
Parameter Value
population size $number\times$(1+$r_{max}$)
$T_0$ 0.064
Temperature update ratio 1.6
Iteration 300
Parameter Value
population size $number\times$(1+$r_{max}$)
$T_0$ 0.064
Temperature update ratio 1.6
Iteration 300
Table 3.  The maximal height and the efficiency achieved by three algorithms in 10 runs
Instance GA PSO FA HFA
Height efficiency Height efficiency Height efficiency Height efficiency
1 122 52.5% 120 55.4% 117 56.8% 120 55.4%
2 169 68.0% 171 67.2% 170 67.6% 167 68.8%
3 222 64.0% 219 64.9% 221 64.4% 219 64.9%
4 210 50.1% 207 50.8% 215 48.9% 198 53.1%
5 366 53.3% 363 54.3% 365 53.4% 356 55.4%
6 446 51.8% 439 52.6% 448 51.5% 442 52.2%
7 160 59.9% 160 59.9% 161 59.6% 157 61.1%
8 230 61.0% 231 60.7% 234 59.9% 225 62.3%
9 310 58.9% 308 59.3% 304 60.1% 304 60.1%
Instance GA PSO FA HFA
Height efficiency Height efficiency Height efficiency Height efficiency
1 122 52.5% 120 55.4% 117 56.8% 120 55.4%
2 169 68.0% 171 67.2% 170 67.6% 167 68.8%
3 222 64.0% 219 64.9% 221 64.4% 219 64.9%
4 210 50.1% 207 50.8% 215 48.9% 198 53.1%
5 366 53.3% 363 54.3% 365 53.4% 356 55.4%
6 446 51.8% 439 52.6% 448 51.5% 442 52.2%
7 160 59.9% 160 59.9% 161 59.6% 157 61.1%
8 230 61.0% 231 60.7% 234 59.9% 225 62.3%
9 310 58.9% 308 59.3% 304 60.1% 304 60.1%
Table 4.  The statistical performance of the algorithm without rotation
Ins. GA PSO FA HFA
Best Avg Stdev Best Avg Stdev Best Avg Stdev Best Avg Stdev
1 120 122.1 2.172 120 121.3 1.341 117 120.8 2.049 120 120.3 0.547
2 171 172.5 2.918 171 172.1 2.121 170 172.5 3.140 167 170 2.387
3 220 224.6 2.671 219 223.1 1.923 221 222.3 2.100 219 221.2 1.483
4 210 219.8 3.019 207 218.6 2.074 215 220.9 8.648 198 215.2 6.638
5 362 371.1 4.017 363 371.4 6.058 365 368.8 6.025 356 365.5 2.191
6 445 465.2 8.423 439 461.2 8.820 448 459.4 9.597 442 452 4.264
7 162 168.1 9.150 160 168.2 9.517 161 167.6 8.961 157 162.9 4.868
8 232 245.1 6.901 231 242 7.615 234 244.2 3.421 225 234.2 2.863
9 311 314.6 6.119 308 313.8 5.354 304 316.2 7.190 304 307.6 3.050
Ins. GA PSO FA HFA
Best Avg Stdev Best Avg Stdev Best Avg Stdev Best Avg Stdev
1 120 122.1 2.172 120 121.3 1.341 117 120.8 2.049 120 120.3 0.547
2 171 172.5 2.918 171 172.1 2.121 170 172.5 3.140 167 170 2.387
3 220 224.6 2.671 219 223.1 1.923 221 222.3 2.100 219 221.2 1.483
4 210 219.8 3.019 207 218.6 2.074 215 220.9 8.648 198 215.2 6.638
5 362 371.1 4.017 363 371.4 6.058 365 368.8 6.025 356 365.5 2.191
6 445 465.2 8.423 439 461.2 8.820 448 459.4 9.597 442 452 4.264
7 162 168.1 9.150 160 168.2 9.517 161 167.6 8.961 157 162.9 4.868
8 232 245.1 6.901 231 242 7.615 234 244.2 3.421 225 234.2 2.863
9 311 314.6 6.119 308 313.8 5.354 304 316.2 7.190 304 307.6 3.050
Table 5.  Comparison between the proposed approach and placement strategy
Instance enclosure without rotation enhance(%) with rotation enhance(%)
1 124.2 120.3 3.14% N/A N/A
2 173.4 170.0 1.96% N/A N/A
3 225.3 221.2 1.82% N/A N/A
4 225.2 215.2 4.44% 210.2 2.32%
5 381.6 365.5 4.40% 358.3 1.97%
6 466.3 452.0 3.16% 445.9 1.35%
7 170.9 162.9 4.68% 156.4 3.99%
8 246.0 234.2 4.80% 230.6 1.54%
9 319.6 307.6 3.90% 301.7 1.92%
Instance enclosure without rotation enhance(%) with rotation enhance(%)
1 124.2 120.3 3.14% N/A N/A
2 173.4 170.0 1.96% N/A N/A
3 225.3 221.2 1.82% N/A N/A
4 225.2 215.2 4.44% 210.2 2.32%
5 381.6 365.5 4.40% 358.3 1.97%
6 466.3 452.0 3.16% 445.9 1.35%
7 170.9 162.9 4.68% 156.4 3.99%
8 246.0 234.2 4.80% 230.6 1.54%
9 319.6 307.6 3.90% 301.7 1.92%
[1]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018142

[2]

Mao Chen, Xiangyang Tang, Zhizhong Zeng, Sanya Liu. An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2018164

[3]

Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193

[4]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015

[5]

Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-25. doi: 10.3934/jimo.2018041

[6]

Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008

[7]

Ming-Jong Yao, Tien-Cheng Hsu. An efficient search algorithm for obtaining the optimal replenishment strategies in multi-stage just-in-time supply chain systems. Journal of Industrial & Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11

[8]

Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191

[9]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[10]

Leong-Kwan Li, Sally Shao, K. F. Cedric Yiu. Nonlinear dynamical system modeling via recurrent neural networks and a weighted state space search algorithm. Journal of Industrial & Management Optimization, 2011, 7 (2) : 385-400. doi: 10.3934/jimo.2011.7.385

[11]

David Julitz. Numerical approximation of atmospheric-ocean models with subdivision algorithm. Discrete & Continuous Dynamical Systems - A, 2007, 18 (2&3) : 429-447. doi: 10.3934/dcds.2007.18.429

[12]

Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial & Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651

[13]

Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521

[14]

Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial & Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31

[15]

Meng Yu, Jack Xin. Stochastic approximation and a nonlocally weighted soft-constrained recursive algorithm for blind separation of reverberant speech mixtures. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1753-1767. doi: 10.3934/dcds.2010.28.1753

[16]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117

[17]

Jinling Wei, Jinming Zhang, Meishuang Dong, Fan Zhang, Yunmo Chen, Sha Jin, Zhike Han. Applications of mathematics to maritime search. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 957-968. doi: 10.3934/dcdss.2019064

[18]

Wenxun Xing, Feng Chen. A-shaped bin packing: Worst case analysis via simulation. Journal of Industrial & Management Optimization, 2005, 1 (3) : 323-335. doi: 10.3934/jimo.2005.1.323

[19]

Shinji Imahori, Yoshiyuki Karuno, Kenju Tateishi. Pseudo-polynomial time algorithms for combinatorial food mixture packing problems. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1057-1073. doi: 10.3934/jimo.2016.12.1057

[20]

Xueting Tian. Topological pressure for the completely irregular set of birkhoff averages. Discrete & Continuous Dynamical Systems - A, 2017, 37 (5) : 2745-2763. doi: 10.3934/dcds.2017118

2017 Impact Factor: 0.994

Article outline

Figures and Tables

[Back to Top]