论文部分内容阅读
下料问题存在于生产的各个领域,如剪切金属板材和带材、锯切木板、切割平板玻璃等。其中二维下料的应用较为广泛,而矩形下料是二维下料的基础。本文研究的是矩形二维板材下料问题:用最小的板材成本,生产出所需要的全部毛坯。下料问题的解是一个排样方案,包括一个或者多个排样方式,解的好坏取决于排样方式生成算法的选择。本文提出的基于同质条带和均匀条带的两阶段排样方式生成算法,切割工艺简单,且毛坯无需修剪,适用于要求快速切割的场合,结合价值修正策略与顺序启发式算法来确定最优下料方案,主要研究工作如下:(1)两阶段排样方式生成算法与顺序价值修正框架相结合:采用两阶段排样方式生成算法和顺序启发式算法来依次生成下料方案中的每一个排样方式(排样图),满足部分毛坯的需求,重复此过程,直至所有的毛坯需求均得到满足;采用价值修正策略,每生成一张排样图,均对该排样图中出现过的毛坯的价值进行修正,经过多次迭代生成多种排样方案,从中选择使用板材张数最少者为最优解,若板材张数相同,选择排样方式数较少的为最优。(2)采用同质两阶段排样方式生成算法,生成的条带均为同质条带,即每根条带上仅放置同方向、同尺寸的毛坯。板材大小固定且允许毛坯转向,递归调用同质两阶段排样方式生成算法,确定不同尺寸的板材上放置不同种类数的毛坯时各同质条带的使用根数,直至板材尺寸和毛坯种类数均达到最大,此时得到的排样方式即当前最好排样方式。通过与商业软件的对比,证明本文算法可有效的节约时间,提高板材利用率。(3)采用均匀两阶段排样方式生成算法,生成的条带均为均匀条带,即每根条带上可放置同高度不同长度的毛坯。板材大小固定且允许毛坯转向,每调用一次均匀两阶段排样方式生成算法,便可以确定该排样图上的一根条带,修正可用毛坯数量,重复此过程,直至生成当前排样图。设置生成当前排样图的最长时间,若达到该限制时间,则选择目前计算出的最好排样图作为当前排样图。通过与商业软件和文献算法的对比,证明本文算法可以有效的节约时间,减少板材消耗量。