Buradasınız

Anasayfa » Content

A deterministic algorithm for generating optimal three-stage layouts of homogenous strip pieces

Journal Name:

  • Journal of Industrial Engineering and Management

Publication Year:

  • 2014
DOI: 
http://dx.doi.org/10.3926/jiem.1127

Key Words:

Author NameUniversity of Author
Abstract (2. Language): 
Purpose: The time required by the algorithms for general layouts to solve the large-scale two-dimensional cutting problems may become unaffordable. So this paper presents an exact algorithm to solve above problems. Design/methodology/approach: The algorithm uses the dynamic programming algorithm to generate the optimal homogenous strips, solves the knapsack problem to determine the optimal layout of the homogenous strip in the composite strip and the composite strip in the segment, and optimally selects the enumerated segments to compose the three-stage layout. Findings: The algorithm not only meets the shearing and punching process need, but also achieves good results within reasonable time. Originality/value: The algorithm is tested through 43 large-scale benchmark problems. The number of optimal solutions is 39 for this paper’s algorithm; the rate of the rest 4 problem’s solution value and the optimal solution is 99. 9%, and the average consumed time is only 2. 18seconds. This paper’s pattern is used to simplify the cutting process. Compared with the classic three-stage, the two-segment and the T-shape algorithms, the solutions of the algorithm are better than that of the above three algorithms. Experimental results show that the algorithm to solve a large-scale piece packing quickly and efficiency.
Bookmark/Search this post with
FULL TEXT (PDF): 
PDF icon arastirmax-deterministic-algorithm-generating-optimal-three-stage-layouts-homogenous-strip-pieces.pdf
  • 5
1167
1182
  • English

REFERENCES

References: 

Alvarez-Valdes, R., Parajon, A., & Tamarit, J.M. (2002). A tabu search algorithm for large-scale
guillotine (un)constrained two-dimensional cutting problems. Computers & Operations
Research, 29, 925-47. http://dx.doi.org/10.1016/S0305-0548(00)00095-2
Beasley, J.E. (1985). Algorithms for unconstrained two-dimensional guillotine cutting. Journal
of the Operational Research Society, 36, 297-306. http://dx.doi.org/10.1057/jors.1985.51
Cui, Y. (2004a). Generating optimal T-shape cutting patterns for rectangular blanks. Journal of
Engineering Manufacture, 218, 857-866. http://dx.doi.org/10.1243/0954405041486037
Cui, Y. (2013). A new dynamic programming for three staged cutting patterns. Journal of
global optimization, 55, 349-357. http://dx.doi.org/10.1007/s10898-012-9930-3
Cui, Y., Wang, Z., & Li, J. (2005). Exact and heuristic algorithms for staged cutting problems.
Journal of Engineering Manufacture, 219, 201-208. http://dx.doi.org/10.1243/95440505X8136
Fayard, D., & Zissimopoulos, V. (1995). An approximation algorithm for solving unconstrained
two-dimensional knapsack problems. European Journal of Operational Research, 84,
618-632. http://dx.doi.org/10.1016/0377-2217(93)E0221-I
Gilmore, P.C., & Gomory, R.E. (1965). Multistage cutting problems of two and more
dimensions. Operations Research, 13, 94-119. http://dx.doi.org/10.1287/opre.13.1.94
Han, W., Bennell, J.A., & Zhao, X.Z. (2013). Construction heuristics for two-dimensional
irregular shape bin packing with guillotine constraints. European journal of operational
research, 230, 495-504. http://dx.doi.org/10.1016/j.ejor.2013.04.048
He, Y.H., & Wu, Y. (2013). Packing non-identical circles within a rectangle with open length.
Journal of global optimization, 56, 1187-1215. http://dx.doi.org/10.1007/s10898-012-9948-6
Hifi, M. (2001). Exact algorithms for large-scale unconstrained two and three staged cutting
problems. Computational Optimization and Applications, 18, 63-88.
http://dx.doi.org/10.1023/A:1008743711658
Hifi, M., & Zissimopoulos, V. (1996). A recursive exact algorithm for weighted two-dimensional
cutting. European Journal of Operational Research, 91, 553-564. http://dx.doi.org/10.1016/0377-
2217(95)00343-6
Huang, W., & Liu, J. (2006). A Deterministic Heuristic Algorithm Based on Euclidian Distance
for Solving the Rectangles Packing Problem. Chinese Journal of Computers, 29, 735-739.
Ji, J., Lu, Y., & Cha, J. (2012). A deterministic algorithm for optimal two-segment cutting
patterns of rectangular blanks. Chinese Journal of Computers, 35(1), 183-191.
http://dx.doi.org/10.3724/SP.J.1016.2012.00183
Jiang, X., Lv, X., & Liu, C. (2008). Optimal Packing of Rectangles with an Adaptive Simulated
Annealing Genetic Algorithm. Journal of Computer-Aided Design & Computer Graphics, 11,
1425-1431.
Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems, Berlin ： Springer.
http://dx.doi.org/10.1007/978-3-540-24777-7
Liu, Z., & Liu, J. (2011). Simulated Annealing Algorithm for Solving Circular Packing Problem.
Computer Engineering, 37, 197-199.
Seong, G.G., & Kang, M.K. (2003). A best-first branch and bound algorithm for unconstrained
two-dimensional cutting problems. Operations Research Letters, 31, 301-307.
http://dx.doi.org/10.1016/S0167-6377(03)00002-6
Thomas, J., & Chaudhari, N.S. (2013). Hybrid approach for 2D strip packing problem using
genetic algorithm. Advances in notes in computer science, 7902, 566-574.

Thank you for copying data from http://www.arastirmax.com