下料是生产物流中流水线作业承上启下的重要环节,该环节最为关键的工作则为排样方案的制定。本文研究矩形件排样问题,矩形件排样问题是指将矩形件按照一定的工艺约束排放于原材料上,使得原材料的利用率达到最高的过程。排样问题不仅受到众多学者的关注,更是企业提升资源利用率的重要课题,矩形件排样的合理性将不仅直接影响到原材料的利用率,而且能够减少物料的搬运、提高加工效率、降低生产成本等,因此亟需解决。考虑到下料过程中板材的纤维方向、“一刀切”和刀缝等约束条件,建立了以原材料平均利用率最高为目标的数学模型。排样问题在求解过程中具有高时间复杂度的特性,属于NP问题。使用运筹学中的枚举法、背包算法、线性规划法只有在问题规模较小的时候有效,为了求解方法的普适性,选择启发式的排样算法对问题进行求解。文中分别介绍了 4种常用的排样算法,分别是BL算法、下台阶算法、最低水平线算法、填充算法,通过对比算法特性,最终选择能够同时满足“一刀切”约束、刀缝和纤维方向限制的填充算法作为本文的求解工具。虽然该算法能够满足上述约束条件,但是该算法存在试排范围小、排列方式单一的问题,间接的造成了排样利用率低的现象。本文在考虑上述不足的前提下提出了一种改进填充算法,增加了矩形件的排列方式,不仅对矩形件进行纵向试排,而且还要对矩形件进行横向试排;扩大了矩形件试排范围,通过将未试排矩形件在所有余料上试排的方式,实现了排样的多样性。此外,无论是填充算法还是改进填充算法均只为定序排样,仅仅依靠排样规则依旧无法获得高质量的排样方案,所以针对单一的排样顺序做出优化,通过在填充算法的基础上增加横向试排方式并上引入了遗传算子,利用遗传算法全局搜索能力强的特性,对矩形件排样顺序寻优。充分发挥了混合算法中填充算法对排样效果的局部寻优能力和遗传算法对矩形件排列顺序的全局搜索能力的特点。最后,采用不同规模的算例验证了改进后的算法能够有效提高板材的利用率,可为实际下料作业提供技术支持。综上所述,本文创新点主要体现在三个方面。首先,对填充算法提出了改进方案,优化了排样规则,证明了改进后算法的有效性;其次,同时考虑“一刀切”约束条件和刀缝的影响,在实际下料作业中更为适用;最后,针对复杂的排样问题,提出了遗传算法与改进填充算法相结合的混合算法,实现了在复杂排样中板材效率的进一步提高。