多线材一维下料问题的求解策略.pdf

第30卷第3期 广西师范大学学报：自然科学版 V01．30No．3 2012年9月 Normal Science J(?tlrna[of Edition Sept．2012 Guangxi University：Natural 多线材一维下料问题的求解策略 崔耀东，周密，杨柳 (广西大学计算机与电子信息学院，广西南宁530004) 摘要：本文将线性规划与增强顺序法相结合，求解多线材一维下料闯题。采用具有全容量特性的解法，一次 生成多个排样方式，按比值法选择新排样方式。实验结果表明：对于文献中报道的一些例题，运用算法可降低 线材成本；和商业一维下料CAD系统相比，在下料方案的线材成本相同的前提下，本文算法可大幅度缩短计 算时间。 关键词：一维下料；线材下料；排样问题 中图分类号：TP301．6；THl64文献标识码：A 文章编号：1001—6600(2012)03—0149—05 0 引言 制造业每年要消耗大量金属线材(型材、管材、棒材等)，用于制造各种产品。研究一维下料问题 stock (1DCSP：1D cutting 量研究，采用的方法包括整数规划‘“、线性规划‘引、顺序法踟、进化算法Ⅲ、禁忌算法‘引、模拟退火算法：6j等。 整数规划算法是精确解法，可以获得问题的最优解，但对于较大规模的例题，计算时间长得不可忍受。线性 规划算法速度快，适合于大规模问题的求解，但因需要对最优解中的决策变量值取整，会带来一定误差，特 别是每种毛坯的平均需求量较小时。顺序法有利于考虑实际约束和多优化目标，但当毛坯的平均需求量较 大时，其解可能比线性规划解差。将线性规划和顺序法结合，用线性规划解去满足大部分需求，用顺序法满 足剩余需求，是一种值得探讨的方法。 本文采用LPESHP框架，将线性规划(LP：linear se— heuristic quential 后用ESHP法满足剩余毛坯的需求。在LP法中，采用动态规划技术一次生成多个排样方式，通过比值法 选择材料利用价值最大的排样方式。 l 多线材一维下料问题的数学模型及解法 在tDCSP中，使用库存M种线材切割m种毛坯，第i种毛坯的长度和需求量分别为z。和d，，第五种 中含Ⅳ个排样方式(A1J．”，A。)。设排样方式A。含第i种毛坯‰个，使用次数为z。‰为4。使用的线材 单价。1DCSP的LP模型如下： N Ⅳ min z=≥：cnX。；≥：ainz。≥df，i一1，…，m；z。≥0，，2—1，…，Ⅳ。 m=l H=l 其中优化目标为线材成本最小，约束条件为各种毛坯的需求都必须满足，决策变量是各种排样方式的使用 方式。LP法的求解步骤如下： 收稿日期：2012—04—11 基金项目：国家自然科学基金资助项目 通信联系人：崔耀东(1957一)，男，河南林州人，广西大学教授，博导。E—mail：ydcui@263．net 万方数据 150 广西师范大学学报：自然科学版 第30卷 排样方式船只含第行种毛坯一个，不含其他毛坯，以一1，…，研。 被用来在步骤3中生成一个新的排样方式。 步骤3：求解如下背包问题，确定新排样方式y—Eyl’．”，y。]T，Y，