[1]湛维明,王 佳.缺陷板材二维排样的一种随机密钥遗传算法[J].南京师范大学学报(工程技术版),2023,23(02):025-31.[doi:10.3969/j.issn.1672-1292.2023.02.004]
　Zhan Weiming,Wang Jia.A Random Key Genetic Algorithm for Two-Dimensional Layout of Defective Plate[J].Journal of Nanjing Normal University(Engineering and Technology),2023,23(02):025-31.[doi:10.3969/j.issn.1672-1292.2023.02.004]
点击复制

缺陷板材二维排样的一种随机密钥遗传算法
分享到：

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

卷:
23卷
期数:
2023年02期
页码:
025-31
栏目:
计算机科学与技术
出版日期:
2023-06-15

文章信息/Info

Title:
A Random Key Genetic Algorithm for Two-Dimensional Layout of Defective Plate
文章编号:
1672-1292(2023)02-0025-07
作者:
湛维明1; 2; 王 佳1; 2
(1.河北省高校智慧金融应用技术研发中心,河北 保定 071051)
(2.河北金融学院信息工程与计算机学院,河北 保定 071051)
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
分类号:
TP391
DOI:
10.3969/j.issn.1672-1292.2023.02.004
文献标志码:
A
摘要:
讨论缺陷板材二维排样问题,即用一张带缺陷区域的板材切割出若干种矩形件,对每种矩形件允许从板材上切割的数量不做限制,优化目标为板材切割出的矩形件的总价值最大. 将放置规则和随机密钥遗传算法相结合求解排样方式,用放置规则确定当前待排样矩形件在板材上的放置位置,用随机密钥遗传算法确定矩形件的排样序列和排样参数,用极大空闲空间技术处理板材的空闲空间和缺陷区域. 为了提高遗传算法对解空间的搜索范围,放置规则采用最下最左和最左最下两种不同的启发式. 通过数值实验比较所提方法与文献方法,实验结果表明,所提方法计算时间较少、排样价值较高.
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:
收稿日期:2022-06-02.
基金项目:河北省科技计划软科学研究项目(21557690D).
通讯作者:湛维明,博士,讲师,研究方向:算法优化、信息安全、数据分析. E-mail:zwmhb01@163.com
更新日期/Last Update: 2023-06-15