论文部分内容阅读
布局问题属于高复杂度的典型NP难度问题,对机械、船舶和汽车等制造行业有重要意义。本文研究了二维剪切下料布局问题,优化目标是：寻求一个毛坯布局方案,使板材利用率最高。基于动态规划算法和背包问题精确算法,本文提出了两类基于同形块布局方式的精确布局算法。结合列生成的线性规划求解算法,提出了基于同形块的布局方案精确算法。实验结果比国际上针对同类问题的常用有效算法在时间价值比方面有明显改善,并化简了下料切割工艺。本文的研究内容主要包括：(1)根据实际生产中允许毛坯转向的要求,提出了生成三种新型同形块布局方式的精确算法：同形块两阶段布局方式算法、同形块两段布局方式算法和同形块三阶段布局方式算法。(2)针对某些行业存在毛坯方向固定的要求,本文将同形块转换为一种特殊结构—单毛坯条带,提出了生成三种新型单毛坯条带布局方式的精确算法：单毛坯条带两阶段算法、单毛坯条带两段算法和单毛坯条带三阶段算法。(3)将上述六种布局方式算法与列生成的线性规划方法结合生成解决生产中大规模二维剪切下料布局问题的布局方案精确算法。(4)将本文的新型布局方式与目前常用的布局方式进行分析对比,得出各种布局方式优化效果的大小关系,并分析得出本文布局方式的四个特性：板材利用率高、切割工艺简单、生产周期短和布局方式易扩展性。(5)在以上布局方式算法和布局方案算法的基础上,本文设计了解决大规模二维无约束剪切布局问题和二维剪切下料布局问题的运行环境GCSRE,在GCSRE上运行共120例算例,将本文算法与目前多种常用有效算法进行比较,通过大量的对比实验来验证本文算法的有效性。主要实验结果如下：(1)将本文同形块布局方式算法与三种常用有效算法进行比较。以同形块三阶段算法为例：在61例基准测题中,本文算法在布局价值上高于普通三阶段算法27例,等于34例；高于TSHB算法8例,等于53例；本文算法得到最优布局价值测题数41例,其余很接近于最优布局价值。在平均计算时间上,本文算法短于普通布局算法65.5秒,短于普通三阶段算法16.06秒,与TSHB算法相当(1.27秒)。(2)将本文单毛坯条带布局方式算法与五种常用有效算法进行比较。以单毛坯条带三阶段算法为例：在第一组42例基准测题中,本文算法在布局价值上高于T-Shape算法9例,等于33例；高于普通两段算法8例,等于34例；高于普通三阶段算法7例,等于35例。第二组20例基准测题中,本文算法在布局价值上高于启发式算法TABU500为16例,等于3例。本文算法得到最优布局价值43例,其余测题很接近于最优布局价值。本文算法的平均计算时间为0.85秒。(3)将本文同形块三阶段布局方案算法与T-Shape布局方案算法进行比较,在文献中的7例测题中,本文算法在布局价值上均好于T-Shape布局方案算法,本文算法的平均板材利用率达到99.11%。实验结果表明,与目前多种常用有效算法比较,本文算法可以更有效地解决大规模二维剪切下料布局问题。