|Table of Contents|

A Random Key Genetic Algorithm for Two-Dimensional Layout of Defective Plate(PDF)

南京师范大学学报（工程技术版）[ISSN:1006-6977/CN:61-1281/TN]

Issue:
2023年02期
Page:
25-31
Research Field:
计算机科学与技术
Publishing date:

Info

Title:
A Random Key Genetic Algorithm for Two-Dimensional Layout of Defective Plate
Author(s):
Zhan Weiming1; 2; Wang Jia1; 2
(1.Intelligence Finance Research and Development Center in Hebei Province,Baoding 071051,China)
(2.School of Computer and Information Engineering,Hebei Finance University,Baoding 071051,China)
Keywords:
layout problem; random key genetic algorithm; rectangular parts; defective plate
PACS:
TP391
DOI:
10.3969/j.issn.1672-1292.2023.02.004
Abstract:
In this paper we discusse the problem of two-dimensional layout of defective plate,that is,cutting several kinds of rectangular parts with a plate with defective area. There is no limit on the number of rectangular parts allowed to be cut from the plate,and the optimization goal is to maximize the total value of rectangular parts cut from the plate. The placement rule and random key genetic algorithm are combined to solve the layout. The placement rule is used to determine the placement position of the rectangular parts to be arranged on the plate,and the random key genetic algorithm is used to determine the layout sequence and layout parameters of the rectangular parts. The free space and defect area of the plate are treated with maximum free space technology. In order to improve the search range of genetic algorithm for solution space,two different heuristics are adopted in the placement rules:the bottom-left and the left-bottom. With the benchmark examples in the literature,the method in this paper is compared with the method in the literature through numerical experiments. The experimental results show that this method has less calculation time and higher layout value.

References:

[1]BORTFELDT A,WINTER T. A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces[J]. International Transactions in Operational Research,2009,16(6):685-713.
[2]BIRGIN E G,LOBATO R D,MORABITO R. Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm[J]. Journal of the Operational Research Society,2012,63(2):183-200.
[3]WEI L J,LIM A. A bidirectional building approach for the 2D constrained guillotine knapsack packing problem[J]. European Journal of Operational Research,2015,242(1):63-71.
[4]WEI L J,HU Q,LIM A,et al. A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem[J]. European Journal of Operational Research,2018,270(2):448-474.
[5]季君,邢斐斐,黄敦华,等. 一种分阶段式匀质块最优矩形件排样方法[J]. 锻压技术,2021,46(2):46-51.
[6]董德威,颜云辉,王展. 存在表面缺陷原材料的矩形件优化排样问题研究[J]. 东北大学学报(自然科学版),2012,33(9):1323-1326.
[7]AFSHARIAN M,NIKNEJAD A,WÄSCHER G. A heuristic,dynamic programming-based approach for a two-dimensional cutting problem with defects[J]. OR Spectrum,2014,36(4):971-999.
[8]唐伟萍,王坤,黄欣. 矩形件二维正交排样的一种混合遗传算法[J]. 锻压技术,2021,46(10):106-111.
[9]BEAN J C. Genetic algorithms and random keys for sequencing and optimization[J]. ORSA Journal on Computing,1994,6(2):154-160.
[10]CARRABS F. A biased random-key genetic algorithm for the set orienteering problem[J]. European Journal of Operational Research,2021,292(3):830-854.
[11]ANDRADE C E,TOSO R F,GONÇALVES J F,et al. The multi-parent biased random-key genetic algorithm with implicit path-relinking and its real-world applications[J]. European Journal of Operational Research,2021,289(1):17-30.
[12]PINTO B Q,RIBEIRO C C,ROSSETI I,et al. A biased random-key genetic algorithm for routing and wavelength assignment under a sliding scheduled traffic model[J]. Journal of Global Optimization,2020,77(4):949-973.
[13]OLIVEIRA B B,CARRAVILLA M A,OLIVEIRA J F,et al. A C++ application programming interface for co-evolutionary biased random-key genetic algorithms for solution and scenario generation[J]. Optimization Methods and Software,2021,37(3):1065-1086.
[14]FORREST S. Genetic algorithms[J]. ACM Computing Surveys(CSUR),1996,28(1):77-80.
[15]JENNINGS P C,LYSGAARD S,HUMMELSHJ J S,et al. Genetic algorithms for computational materials discovery accelerated by machine learning[J]. NPJ Computational Materials,2019(1):746-751.
[16]LAI K K,CHAN J W M. Developing a simulated annealing algorithm for the cutting stock problem[J]. Computers & Industrial Engineering,1997,32(1):115-127.
[17]CARNIERI C,MENDOZA G A,LUPPOLD W G. Optimal cutting of dimension parts from lumber with a defect:a heuristic solution procedure[J]. Forest Products Journal,1993,43(9):66-75.
[18]王洁,陶涛,陈星艳,等. 蚁群算法在定制家具矩形零件排样中的应用[J]. 林业工程学报,2022,7(1):192-196.
[19]王静静,瞿少成,李科林. 一种基于并行交叉遗传算法的二维不规则排样问题求解[J]. 计算机应用与软件,2020,37(7):188-193.
[20]VIANNA A C G,ARENALES M N. O problema de corte de placas defeituosas[J]. Pesquisa Operacional,2006,26:185-202.
[21]NEIDLEIN V,VIANNA A C G,ARENALES M M,et al. The two-dimensional,rectangular,guillotineable-layout cutting problem with a single defect[R]. Magdeburg:Otto-von-Guericke University Magdeburg,2008.
[22]AFSHARIAN M,NIKNEJAD A,WÄSCHER G. A heuristic,dynamic programming-based approach for a two-dimensional cutting problem with defects[J]. OR Spectrum,2014,36(4):971-999.

Memo

Memo:
-
Last Update: 2023-06-15