Non-guillotine Cutting Algorithm of Rectangular Items Based on Five-Homogeneous-Block Mode

doi:10.12068/j.issn.1005-3026.2018.06.003

Abstract

Abstract: A type of non-guillotine cutting problem of rectangular items was studied based on the use of five-homogeneous-block mode. According to the idea of dynamic programming and implicit enumeration， a five-homogeneous-block cutting algorithm for an unconstrained non-guillotine cutting problem was designed. The comparative experiments with existing non-guillotine cutting algorithms indicated that optimal solutions of the problem could be quickly given by this algorithm， and both the difficulty of plate cutting process and the sorting cost of rectangular items could be reduced. Furthermore， comparisons with another experiment with two guillotine cutting algorithms show the benefits of “non-guillotine”.

Key words: non-guillotine cutting problem, five-block mode, dynamic programming algorithm, implicit enumeration

CLC Number:

TP391

ZHANG Rui-you， PAN Wei-ping， LIU Shi-xin. Non-guillotine Cutting Algorithm of Rectangular Items Based on Five-Homogeneous-Block Mode[J]. Journal of Northeastern University Natural Science, 2018, 39(6): 771-775.

References

[1]Wscher G，Hauner H，Schumann H.An improved typology of cutting and packing problems［J］.European Journal of Operational Research，2007，183(3):1109-1130.
[2]Cintra G F，Miyazawa F K，Wakabayashi Y，et al.Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation［J］.European Journal of Operational Research，2008，191(1):61-85.
[3]Cui Y P，Cui Y，Tang T.Sequential heuristic for the two-dimensional bin-packing problem［J］.European Journal of Operational Research，2015，240(1):43-53.
[4]Lodi A，Monaci M，Pietrobuoni E.Partial enumeration algorithms for two-dimensional bin packing problem with guillotine constraints［J］.Discrete Applied Mathematics，2017，217:40-47.
[5]Beasley J E.Algorithms for unconstrained two-dimensional guillotine cutting［J］.Journal of the Operational Research Society，1985，36(4):297-306.
[6]Cui Y，He D，Song X.Generating optimal two-section cutting patterns for rectangular blanks［J］.Computers & Operations Research，2006，33(6):1505-1520.
[7]杨传民，王树人，王心宇.基于4块结构的斩断切割布局启发性算法［J］.机械设计，2007，24(2):25-26.(Yang Chuan-min，Wang Shu-ren，Wang Xin-yu.Heuristic algorithm on layout of chopped cutting based on 4 pieces of structure［J］.Journal of Machine Design，2007，24(2):25-26.)
[8]潘卫平，陈秋莲，崔耀东，等.基于匀质条带的矩形件最优三块布局算法［J］.图学学报，2015，36(1):7-11.(Pan Wei-ping，Chen Qiu-lian，Cui Yao-dong，et al.An algorithm for generating optimal homogeneous strips three block patterns of rectangular blanks ［J］.Journal of Graphics，2015，36(1):7-11.)
[9]Fekete S P，Schepers J，Van der Veen J C.An exact algorithm for higher-dimensional orthogonal packing［J］.Operations Research，2007，55(3):569-587.
[10]Egeblad J，Pisinger D.Heuristic approaches for the two-and three-dimensional knapsack packing problem［J］.Computers & Operations Research，2009，36(4):1026-1049.
[11]Birgin E G，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.
[12]易向阳，潘卫平，张俊晖.基于五块模式的单一矩形件排样算法［J］.图学学报，2015，36(4):521-525.(Yi Xiang-yang，Pan Wei-ping，Zhang Jun-hui.Algorithm for generating five block mode cutting patterns of single rectangular items［J］.Journal of Graphics，2015，36(4):521-525.)

[1]	PANG Yan-wei， SU Chang， LONG Tao. Adaptive Multi-scale Cost Volume Construction and Aggregation for Stereo Matching [J]. Journal of Northeastern University(Natural Science), 2023, 44(4): 457-468.
[2]	DING Qi-chuan， WANG Li， LIU Cheng. Classification of Pulmonary Nodule by Combining Long-Distance Channel Attention and Pathological Feature [J]. Journal of Northeastern University(Natural Science), 2023, 44(4): 476-485.
[3]	LI Hai-yan， XIONG Li-chang， GUO Lei， LI Hai-jiang. Two-Stage Inpainting Algorithm Based on U-net Edge Generation and Hypergraphs Convolution [J]. Journal of Northeastern University(Natural Science), 2023, 44(3): 331-339.
[4]	YANG Dan， LIU Guo-ru， REN Meng-cheng， PEI Hong-yang. Retinal Blood Vessel Segmentation Method Based on Multi-scale Convolution Kernel U-Net Model [J]. Journal of Northeastern University(Natural Science), 2021, 42(1): 7-14.
[5]	HAN Dong-hong， ZHANG Hong-liang， ZHU Shuai-wei， QI Xiao-long. Sentiment Community Detection Algorithm for Sina Weibo [J]. Journal of Northeastern University(Natural Science), 2021, 42(1): 21-31.
[6]	YUAN Pei-xin， CHEN Ding-fu. Compression Algorithm of Dual X-ray Security Inspection Images with High Dynamic Range [J]. Journal of Northeastern University(Natural Science), 2021, 42(1): 96-101.
[7]	WEI Ying, XU Chu-qiao, DIAO Zhao-fu, LI Bo-qun. A Multi-target Pedestrian Tracking Algorithm Based on Generated Adversarial Network [J]. Journal of Northeastern University(Natural Science), 2020, 41(12): 1673-1680.
[8]	LI Ji， XU An-jun. Simulation-based Solution for Multi-crane Dynamic Scheduling in Steelmaking Shop [J]. Journal of Northeastern University Natural Science, 2020, 41(12): 1699-1707.
[9]	LI Zhan-shan， LYU Ai-na. A Feature Selection Method Based on New Redundancy Measurement [J]. Journal of Northeastern University Natural Science, 2020, 41(11): 1550-1556.
[10]	WANG Xin， WANG Cui-rong， WANG Cong， YUAN Ying. Dual-channel Multi-perception Convolutional Network for Image Super-Resolution [J]. Journal of Northeastern University Natural Science, 2020, 41(11): 1564-1570.
[11]	ZHANG Chun-lei， DAI Li， LIU Yu， LI He. Patient Registration for Surgical Navigation System Based on Three-Point Method and ICP Algorithm [J]. Journal of Northeastern University Natural Science, 2020, 41(11): 1584-1590.
[12]	CHEN Jian， HE Tao， WEN Ying-you， MA Lin-tao. Entity Recognition Method for Judicial Documents Based on BERT Model [J]. Journal of Northeastern University Natural Science, 2020, 41(10): 1382-1387.
[13]	ZHANG Tian， TIAN Yong， WANG Zi， WANG Zhao-dong. Adaptive Threshold Image Segmentation Based on Definition Evaluation [J]. Journal of Northeastern University Natural Science, 2020, 41(9): 1231-1238.
[14]	ZHANG Li-jie， LIU Jian-chang， TAN Shu-bin. Multi-objective Planning of Personnel Evacuation Route in Complex Building Fire [J]. Journal of Northeastern University Natural Science, 2020, 41(6): 761-766.
[15]	ZHAO Hai， ZHOU Bing-ling， ZHU Hong-bo， DOU Sheng-chang. Fast Segmentation Algorithm of 3D Lung Parenchyma Based on Continuous Max-Flow [J]. Journal of Northeastern University Natural Science, 2020, 41(4): 470-474.