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

制造业每年要消耗大量金属线材(型材、管材、棒材等)，用于制造各种产品。研究-维下料问题(1DCSP：1D cutting stock problem)的解法 ，对于促进材料节约具有重要意义。国内外对 1DCSP进行 了大量研究，采用的方法包括整数规划 、线性规划 、顺序法Ⅲ、进化算法 、禁忌算法 引、模拟退火算法 等。

整数规划算法是精确解法，可以获得问题的最优解，但对于较大规模的例题，计算时间长得不可忍受。线性规划算法速度快，适合于大规模问题的求解，但因需要对最优解中的决策变量值取整，会带来-定误差，特别是每种毛坯的平均需求量较小时。顺序法有利于考虑实际约束和多优化目标，但当毛坯的平均需求量较大时，其解可能比线性规划解差～线性规划和顺序法结合，用线性规划解去满足大部分需求，用顺序法满足剩余需求 ，是-种值得探讨的方法 。

本文采用 LPESHP框架，将线性规划(LP：linear programming)与增强顺序法(ESHP：enhanced se-quential heuristic procedure)相结合，求解多线材-维下料问题。首先用LP法满足大部分毛坯的需求，然后用ESHP法满足剩余毛坯的需求。在LP法中，采用动态规划技术-次生成多个排样方式，通过比值法选择材料利用价值最大的排样方式。

1 多线材-维下料问题的数学模型及解法在 1DCSP中，使用库存 种线材切割 种毛坯，第 i种毛坯的长度和需求量分别为z 和d ，第 k种线材的长度和单价(每根价值)分别为 厶 和C ，i-1，，m，忌-1，，M。1DCSP的解是-个排样方案，其中含 N个排样方式(A ， Ⅳ)。设排样方式 A 含第i种毛坯‰个，使用次数为 z 为A 使用的线材单价 。1DCSP的 LP模型如下 ：N Nmin z-≥ c ；>：a1.x ≥ ，i-1，， ； ≥0， -1，，N。

1 - 1其中优化目标为线材成本最小，约束条件为各种毛坯的需求都必须满足，决策变量是各种排样方式的使用次数。令 A-Ea ] ，C-[f ，CN]， - ”，z ] ，D- ”，d ] 。注意A的每-列代表-个排样方式。LP法的求解步骤如下：收稿 日期 ：2012-04-11基金项目：国家自然科学基金资助项目(61063031)通信联系人：崔耀东(1957-)，男，河南林州人，广西大学教授，博导。E-mailydcui###263.net15O 广西师范大学学报：自然科学版 第 3o卷步骤 1：确定初始解。令 -N，令 A为单位矩阵，初始解XA DD。排样方案含 个排样方式。

排样方式 只含第，z种毛坯-个，不含其他毛坯，1"-1，，m。

步骤 2：令毛坯单价向量V-CA [ ”， ]，即当前解的信息(毛坯单价撒于当前解矩阵A)将被用来在步骤 3中生成-个新的排样方式。

步骤 3：求解如下背包问题，确定新排样方式l，-[ -， 二r， 为第i种毛坯的个数：m min z - ： ； ：liy ≤L ；Y ∈N， -1，， ；屉∈1，，M， (1)- 1 - i其中N为自然数的集合。如果存在-个 k使置换条件 z >c 成立，用 y取代 A的第K列(K值按单纯形法规则确定)，令 cKC 并转步骤 2；否则，X-A D为最优解，结束。

- 般解法顺序考察各种线材，求解问题(1)，直到满足置换条件为止。每次循环中求解问题(1)的次数在 1～M。本文取 L -max(L -，LM，采用具有全容量性质的动态规划算法E川，只需求解 1次，就可以获得 z -， M。然后采用比值法，选择 k使Zk/c ：max /c ”，zM/CM，并选取对应的排样方式作为新排样方式 y；如果本文解法中按 z ：raini 1Zi>c ，1≤ ≤M)选择 k，称为顺序法。下节实验计算中，将对-般解法、顺序法和比值法进行比较。

求出LP的解后，对z ( -1，， )进行下取整，得到 LP排样方案，可以满足大部分需求。对于短缺的毛坯(设第 i种毛坯短缺r 个)，采用ESHP法，得到ESHP排样方案～这 2个排样方案组合，就得到多线材-维下料问题的解。文献[3]中报道的ESHP法，可以求解单线材-维下料问题。它考虑多组参数值，对于每组参数按下述步骤生成-个排样方案，然后选取线材成本最低的方案作为最终排样方案(详细描述请参见文献[3])：步骤 1：令剩余毛坯个数 - i-1，， 。令 -0。

步骤 2：令 - 1。确定候选毛坯个数b ，玩≤乱 ，i-1，， 。

步骤 3：使用候选毛坯生成第 个排样方式y-[ -， r，其使用次数为grainL / j IY >0。

本文ESHP法仅对步骤 3加以修正，求解下述问题生成排样方式 y，以适合多线材的情况：rain - ：viyf； ：li，y ≤厶； ∈N且yi≤6 ，i1，，m；k∈1，， )，- 1 - 1其中 为第i种毛坯的单价，按文献[3]中所述方法确定。采用具有全容量特性的动态规划算法[7]，对于 L- L 求解上述问题-欠，就获得所有 M种线材 的解。然后按前述比值法，选择第k种线材对应的排样方式作为 y。

2 实验计算首先说明在求解 LP排样方案时，应用比值法可大幅度缩短计算时间。按均匀分布随机生成 4个例题：毛坯长度 区间E25o，2 5ool，需求量 d 区间[1，3o]，4个例题的毛坯种数 分别为 50、100、200和300。线材种数M-16，长度从 3 000 mm到 6 000 mm，间隔2O0 iTlm递增。表 1所示为各题的材料利用数表 1 各例题的材料利用数据Tab.1 M aterial utilization for each instance第 3期 崔耀东等：多线材-维下料问题的求解策略据。表 2所示为各种方法的计算时间，其中ti.p为LP排样方案的计算时间，t为总的计算时间〖察 4个例题的 值知，比值法计算时间分别为-般法计算时间的 5.6 、6.5 、6.3 9/6和 8.9 ，比值法要比-般法快得多，也比顺序法快得多。

表 2 各种方法的计算时间Tab.2 Computation time for each m ethod其次说明本文算法和商业(-维下料)CAD系统相比，计算时间短，材料利用率相同。表 3所示为计算结果。其中A、B和c分别表示商业CAD系统CutLogic 1D v4.4(htp：//)、1D Cut-ting Optimizer v1.2(http f w.optimumcut.com/)讯 Pipe Cutting Suite v5.29(http f .opti-mizecutter.corn/)；U为材料利用率；f为计算时间；L为所耗线材总长度。对于系统c，只列出第 1题结果，因为其他题在允许的最长计算时间(5 h)内没有得出结果。系统 C材料利用率较差，其他 3种系统的材料利用率基本相同，所耗线材总长度差别在 0.4 m以内。本文系统的运算时间最短。

表 3 各种 CAD系统的计算结果Tab.3 Results for each CAD system暂 ±u/% L/m t/s舁 俪 题 1 例题 2 例题 3 例题 4 例题 1 例题 2 例题 3 例题 4 例题 1 例题 2 例题 3 例题 4A 99.95 99.98 99.99 99.99 942.6 1 839.4 4 024.6 5 987.2 1O0 350 1 200 2 200B 99.95 99.99 99.99 100.00 942.6 1 839.2 4 024.6 5 987.0 4 24 75 146C 98.18 959.6 480本 文 99.97 99.98 99.99 99.99 942.4 1 839.4 4 024.8 5 987.4 2 6 37 124最后说明本文算法能够改善文献中报道的例题的解。表 4列出文献[4-6]中使用的10个例题的计算结果，其中文献中算法结果引自文献[6]中表 7。对于 1～7题，本文算法解和已知的最好解相同(按消耗线材根数计)。对于8-1O题，本文算法解优于已知的最好解，并且都是最优解，因为再将线材根数减少-根时，线材总长度将小于所需毛坯总长度，无可行解存在。对于第8题，每根线材长度为 120 mm，表 5所示为毛坯需求数据，表 6所示为本文算法给出的排样方案。不难验证该排样方案可满足全部毛坯的需求。该排样方案也是最优的，因为毛坯总长度为 17 068 mm，相当于 142.2根线材的长度，因此使用线材的总根数(整数)，不可能小于 143。

表 4 文献 中 10个例题 的计算结 果Tab.4 Results for the 10 instances in the literature表 5 第 8题的毛坯需求数据 (毛坯总长度 17 068 mm)Tab.5 Items data of instance 8(total length of items 1 7 068 mm)第 3期 崔耀东等：多线材-维下料问题的求解策略 l53Strategies for Solving the 1D Cutting Stock Problem of M ultipleStock LengthsCUI Yao-dong，ZHOU M i，YANG Liu(School of Comp6ter，Electronics and Information，Guangxi University，Nanning Guangxi 530004，China)Abstract：The linear programming approach and the enhanced sequential heuristic procedure are com-bined to solve the 1D cutting stock problem of multiple stock lengths.A procedure of the all capacityproperty is used to generate multiple patterns，from which the new pattern is selected using a ratiomethod.The experimental result indicates that the algorithm can improve the solutions to some bench-mark instances and give solutions of the same material cost as that of some commercial packages，usingmuch shorter computation time。

Key words：1D cutting stock；lengthwise cutting stock；cutting stock problems(责任编辑 黄 勇)崔耀东，男，1957年生，汉族，河南林州人，博士，教授，博士生导师。1982、1985、2002年分别于南京航空航天大学航空宇航制造工程专业本科、硕士研究生和博士研究生毕业，获工学学士、硕士和博士学位。2001年至2009年在广西师范大学工作，任计算机科 学与技术学科教授、计算机应 用教研室主任、计算机科 学与信息工程学院学术委 员会主任 ；连续多年工作考核为优秀，2次被评为广西师范大学优 秀教师；曾任桂林 市政协委 员和中国农工民主党桂林 市委常委。崔耀东教授现在广西大学计算机与电子信息学院工作，院学术委 员会委员，计算机科学与技术学科硕士生导师，兼职华南理工大学工业工程与管理工程学科博士生导师(2011年实际招生)。

崔耀东教授的研究兴趣 为优化计算技术 ，重点研 究切割与填充(Cuting＆.Pack-ing)问题 ，提出多种有影响的优化排样方法。围绕该问题，崔耀东教授 2002年 以来在 19种 SCI检 索的国际 英文期刊上发表第-作者论文 48篇；根据 2010年的分 区数据 ，这些期刊中包括 2种国际顶级(top)期刊、1种 SCI-区期刊、5种 SCI二 区期刊、5种 SCI三 区期刊和 8种 SCI四区期刊。论文被 SCI他引 40多次。先后主持国家自然科学基金项目二项和广西科学基金项目2项，出版专著 1部。

崔耀东教授从 2008年起担任 SCI检 索国际期刊Computers＆Operations Research》编委(SCI三 区期 刊，2O10年影响 因子 1.769)。先后担任《Computer-Aided Design》、《Computational Optimization andApplicati-ons》、European Journa1 of Operational Research》、《INFORMS Journal on Computing》、《In-ternational Journal of Production Research》、(Journal of Combinatorial Optimization》、Journal of Paral-le1 and Distributed Computing》等 10多种 SCI检索期刊的论文评审专家。