Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (2): 392-397.DOI: 10.11772/j.issn.1001-9081.2019081397

• DPCS 2019 • Previous Articles     Next Articles

Design and implementation of parallel genetic algorithm for cutting stock of circular parts

Zhiyang ZENG, Yan CHEN(), Ke WANG   

  1. School of Computer,Electronics and Information,Guangxi University,Nanning Guangxi 530004,China
  • Received:2019-07-31 Revised:2019-09-19 Accepted:2019-09-23 Online:2019-11-04 Published:2020-02-10
  • Contact: Yan CHEN
  • About author:ZENG Zhiyang, born in 1994, M. S. candidate. His research interests include optimization of intelligent algorithm, intelligent system, machine learning.
    WANG Ke, born in 1994, M. S. candidate. His research interests include optimization of intelligent algorithm, intelligent system.
  • Supported by:
    the National Natural Science Foundation of China(71371058)


曾志阳, 陈燕(), 王珂   

  1. 广西大学 计算机与电子信息学院,南宁 530004
  • 通讯作者: 陈燕
  • 作者简介:曾志阳(1994—),男,广西贵港人,硕士研究生,CCF会员,主要研究方向:智能算法优化、智能系统、机器学习
  • 基金资助:


For the cutting stock problem of circular parts which is widely existed in many manufacturing industries, a new parallel genetic algorithm for cutting stock was proposed to maximize the material utilization within a reasonable computing time, namely Parallel Genetic Blanking Algorithm (PGBA). In PGBA, the material utilization rate of cutting plan was used as the optimization objective function, and the multithread was used to perform the genetic manipulation on multiple subpopulations in parallel. Firstly, a specific individual coding method was designed based on the parallel genetic algorithm, and a heuristic method was used to generate the individuals of population to improve the search ability and efficiency of the algorithm and avoid the premature phenomena. Then, an approximate optimal cutting plan was searched out by adaptive genetic operations with better performance. Finally, the effectiveness of the algorithm was verified by various experiments. The results show that compared with the heuristic algorithm proposed in literature, PGBA takes longer computing time, but has the material utilization rate greatly improved, which can effectively improve the economic benefits of enterprises.

Key words: cutting stock of circular parts, genetic algorithm, parallel computing, heuristic method, dynamic programming method



关键词: 圆片下料, 遗传算法, 并行计算, 启发式方法, 动态规划方法

CLC Number: