第36卷第1期 北京科技大学学报 Vol.36 No.1 2014年1月 Journal of University of Science and Technology Beijing Jan.2014 基于聚类一约束满足算法的钢管入库优化决策模型 董广静2区，施灿涛12)，李铁克12，王柏琳12 1)北京科技大学东凌经济管理学院，北京1000832)钢铁生产制造执行系统技术教有部工程研究中心，北京100083 ☒通信作者，Emai:dongguangjing_2011@126.com 摘要针对钢管入库优化决策问题，建立了问题的约束满足优化模型，并通过对垛高和钢管堆放规则的分析，提出了基于 聚类和约束满足技术的两阶段求解算法.算法在第一阶段采用聚类的方式对待入库的钢管按照多重属性进行分组：在第二阶 段利用约束满足技术对于每组钢管分别指派垛位及其在垛位上的具体位置，并通过约束传播动态缩减问题的搜索空间.最后 将算法与经典的BFD(best fit deceasing)算法进行实验结果对比.实验结果表明，算法能够在保证倒垛次数最小的前提下，有 效减少垛位数并具有良好的垛位利用率，模型及算法可行、有效 关键词钢管：堆垛：聚类算法：约束满足问题：决策 分类号TP29 Optimization model of steel tube location decision based on clustering and constraint satisfaction algorithm DONG Guang jing,SHI Can-tao LI Tie-ke),WANG Bai-lin 1)Dongling School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China 2)Engineering Research Center of MES Technology for Iron Steel Production,Ministry of Education,Beijing 100083,China Corresponding author,E-mail:dongguangjing_2011@126.com ABSTRACT A constraint satisfaction optimization model was presented to deal with the optimization decision problem about the steel tube location.Through the analysis of stack height and the piling rules of steel tubes,a two-stage algorithm was given based on cluste- ring and constraint satisfaction technology.In the first stage,steel tubes to be put into storage are grouped by clustering-based approach according to their multiple attributes.In the second stage,by using constraint satisfaction technology,the specific location of steel tubes in each group is assigned,and the search space of the problem is dynamically shrunk through constraint propagation.Finally, this algorithm was compared with the classical BFD (best fit deceasing)algorithm through experiments.Experimental results demon- strate that,in the premise of minimizing stacking operations,the algorithm can effectively reduce the quantity of stacks and achieve a well-performed utilization rate of stacks.And thus the results verify the feasibility and effectiveness of the model and algorithm. KEY WORDS steel tubes:stacking:clustering algorithms:constraint satisfaction problems:decision making 随着钢铁企业计算机集成制造理论与技术的发 用，对钢管库作业优化问题的研究具有重要的理论 展，炼钢一连铸一热轧一体化生产计划与调度问题得 意义和实用价值. 到了广泛的关注和研究习.钢管库在生产流程中 目前国内外钢管生产企业大都是按照订单组织 起着承前启后的作用：一方面要接收热轧阶段送来 生产的，但是依照钢管的品种和规格为原则进行入 的钢管，另一方面要为客户配送发运产品.因此，钢 库堆垛的，而钢管出入库时存在着大量复杂约束，导 管库在热轧工序和成品发运出库作业的能力协调以 致堆放无序而产生大量倒垛，严重影响了钢管库作 及对整个生产过程的物流平衡方面均具有重要作 业效率，造成库存和倒运成本的大幅上升.钢管库 收稿日期：2012-12-22 基金项目：教有部博士学科点专项科研基金资助项目(201000061100O6):中央高校基本科研业务费专项资金资助项目(FRF-SD-12011B) DOI:10.13374/j.issn1001-053x.2014.01.019;http://jourals.ustb.edu.cn
第 36 卷 第 1 期 2014 年 1 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 1 Jan． 2014 基于聚类--约束满足算法的钢管入库优化决策模型 董广静1，2) ，施灿涛1，2) ，李铁克1，2) ，王柏琳1，2) 1) 北京科技大学东凌经济管理学院，北京 100083 2) 钢铁生产制造执行系统技术教育部工程研究中心，北京 100083 通信作者，E-mail: dongguangjing_2011@ 126． com 摘 要 针对钢管入库优化决策问题，建立了问题的约束满足优化模型，并通过对垛高和钢管堆放规则的分析，提出了基于 聚类和约束满足技术的两阶段求解算法． 算法在第一阶段采用聚类的方式对待入库的钢管按照多重属性进行分组; 在第二阶 段利用约束满足技术对于每组钢管分别指派垛位及其在垛位上的具体位置，并通过约束传播动态缩减问题的搜索空间． 最后 将算法与经典的 BFD ( best fit deceasing) 算法进行实验结果对比． 实验结果表明，算法能够在保证倒垛次数最小的前提下，有 效减少垛位数并具有良好的垛位利用率，模型及算法可行、有效． 关键词 钢管; 堆垛; 聚类算法; 约束满足问题; 决策 分类号 TP29 Optimization model of steel tube location decision based on clustering and constraint satisfaction algorithm DONG Guang-jing1，2) ，SHI Can-tao 1，2) ，LI Tie-ke 1，2) ，WANG Bai-lin1，2) 1) Dongling School of Economics and Management，University of Science and Technology Beijing，Beijing 100083，China 2) Engineering Ｒesearch Center of MES Technology for Iron ＆ Steel Production，Ministry of Education，Beijing 100083，China Corresponding author，E-mail: dongguangjing_2011@ 126． com ABSTＲACT A constraint satisfaction optimization model was presented to deal with the optimization decision problem about the steel tube location． Through the analysis of stack height and the piling rules of steel tubes，a two-stage algorithm was given based on clustering and constraint satisfaction technology． In the first stage，steel tubes to be put into storage are grouped by clustering-based approach according to their multiple attributes． In the second stage，by using constraint satisfaction technology，the specific location of steel tubes in each group is assigned，and the search space of the problem is dynamically shrunk through constraint propagation． Finally， this algorithm was compared with the classical BFD ( best fit deceasing) algorithm through experiments． Experimental results demonstrate that，in the premise of minimizing stacking operations，the algorithm can effectively reduce the quantity of stacks and achieve a well-performed utilization rate of stacks． And thus the results verify the feasibility and effectiveness of the model and algorithm． KEY WOＲDS steel tubes; stacking; clustering algorithms; constraint satisfaction problems; decision making 收稿日期: 2012--12--22 基金项目: 教育部博士学科点专项科研基金资助项目( 20100006110006) ; 中央高校基本科研业务费专项资金资助项目( FＲF--SD--12--011B) DOI: 10． 13374 /j． issn1001--053x． 2014． 01． 019; http: / /journals． ustb． edu． cn 随着钢铁企业计算机集成制造理论与技术的发 展，炼钢--连铸--热轧一体化生产计划与调度问题得 到了广泛的关注和研究［1--2］． 钢管库在生产流程中 起着承前启后的作用: 一方面要接收热轧阶段送来 的钢管，另一方面要为客户配送发运产品． 因此，钢 管库在热轧工序和成品发运出库作业的能力协调以 及对整个生产过程的物流平衡方面均具有重要作 用，对钢管库作业优化问题的研究具有重要的理论 意义和实用价值． 目前国内外钢管生产企业大都是按照订单组织 生产的，但是依照钢管的品种和规格为原则进行入 库堆垛的，而钢管出入库时存在着大量复杂约束，导 致堆放无序而产生大量倒垛，严重影响了钢管库作 业效率，造成库存和倒运成本的大幅上升． 钢管库
·124 北京科技大学学报 第36卷 的入库优化决策问题就是为即将入库的每一根钢管 实践中为了在合理的时间内找到近优解都采用启发 选择合适的垛位，以便于钢管库的管理，同时减少钢 式方法进行求解，因为传统的搜索技术求解此类问 管库的倒垛作业；其中，存在这样一类入库问题：在 题，会产生“组合爆炸现象”，很难在有效的时间内 钢管库入库管理及钢管的装载运输过程中，为了避 获得最优解.当前对钢铁企业产品入库问题的研究 免滚落和摆放不协调，往往是将半径较大的钢管置 中大部分是针对板坯入库问题的约束满足模型，而 于半径较小的下方，将较长的钢管置于较短钢管的 针对钢管入库决策问题的约束满足模型还尚未见， 下方)，且同一层的半径和长度不能相差太大：同 因此本文针对钢管入库优化决策问题建立了约束满 时为了优化后续的出库作业，要求钢管入库时考虑 足模型在求解算法上，针对入库钢管具有多种规格 交货期的松紧，即具有较紧交货期的钢管应尽可能 的特征，提出一种基于聚类的约束满足算法，并通过 的置于垛位上方，以便于出库.文献4]针对大规模 数据实验验证了算法的有效性 板坯倒垛问题建立了一种基于启发式的阶段动态规 1问题建模 划模型，并设计了对应启发式算法，该算法在实际生 产中可减少10.76%的倒垛量；文献5]提出一种箱 1.1问题描述 子高度可变的三维装箱问题，并设计了针对此类问 一般钢铁企业钢管的存放方式与钢管的半径有 题的一种改进的遗传算法，算法结果明显优于传统 很大关系，半径比较小的多以捆的形式存放，随着钢 装箱算法；文献6]将一种带交货期约束的板坯堆 铁企业的飞速发展，钢铁企业订单多以小批量、多客 垛问题归结为约束满足问题，并设计了一种混合约 户进行生产，钢管的存放方式也发生了一些改变 束满足算法，算法结果优于经典的BFD(best fit de-- 目前有很多钢铁企业钢管的存放多以“A”字型、多 ceasing)算法：文献7]针对板坯入库优化决策问 层多列堆放，这种堆放方式一般适应于半径较大、客 题，采用模糊数学的研究方法将板坯各规格属性模 户交货期松紧度相近的钢管产品，所以对于钢管的 糊化，设计了一种混合离散粒子群算法，相比传统的 入库堆放问题即垛位优化问题的研究对钢管库的管 遗传算法减少了16%的倒垛量；文献8]针对钢铁 理起着至关重要的作用. 企业供应链上的线圈作业调度优化问题设计了一种 对于钢管入库优化决策问题，由于入库钢管的 基于启发式规则的算法，并在实际生产中有了很好 订单交期已经确定，因此钢管在堆垛时主要参照订 的应用；文献⑨]针对库区吊机能力实际限制下的 单交货期执行，将钢管交货期靠前的尽可能摆在上 板坯倒垛问题建立了非线性规划模型，并对问题特 方，以减少出库时的倒垛次数.钢管库中通常存在 征进行分析，针对轧制项目间是否存在共同可选板 若干垛位，为节省空间需要多层多列叠放，因而为了 坯的两种情况，将模型转化为线性整数规划模型，利 保证垛位的稳定性，在进行钢管堆垛时考虑以下几 用问题的性质降低了模型的求解复杂性.以上研究 方面要求：(1)上层钢管的长度与下层相邻钢管的 成果对本文的研究具有一定的参考价值. 长度差的绝对值不超过某一给定上限值；(2)上层 以往研究中多以板坯特性的货物作为研究对 钢管的半径与下层相邻钢管的半径差的绝对值不超 象，一般是多层堆放，一层只允许堆放一个货物，在 过某一给定上限值：(3)同层任意两根钢管的半径 堆放时主要综合考虑货物的厚度、宽度、重量和交货 差值的绝对值不能超过某一给定上限值：(4)同层 期等因素，而对具有钢管特性的货物的研究较少，仅 任意两根钢管的长度差值的绝对值不能超过某一给 有几篇研究的是钢卷的入库优化问题，也是类似于 定上限值：(5)受地面承重能力、安全原因和起重设 板坯的存放方式.对于钢管多层多列的堆放方式研 备所能达到的高度所限，每个垛位上钢管的总高度 究还尚未见.本文以钢管成品库优化管理中的入库 不超过某一给定上限值 优化决策问题作为研究对象，因钢管入库时存在交 根据钢管成批生产且同批钢管钢种相同或相近 货期的松紧约束，故将其归结为带顺序约束的三维 的特征，本文假设每一批的待入库钢管具有相同的 ASBP(a-shape bin packing)问题，并映射为约束满 钢种，则钢管入库优化决策问题即是根据待入库的 足问题o(constraint satisfaction problem,CSP).三 钢管半径、长度等属性的不同，在不违背垛高限制的 维ASBP问题是一个具有复杂约束条件的组合优化 情况下为其指派垛位，使得在满足出库零倒垛的前 问题，具有典型的NP难特性，它在实际中有许多约 提下，占用的垛位数最少 束条件需要考虑，如空间约束、载重约束、货物摆向 1.2符号定义 约束、稳定性约束和货物装卸顺序约束四，一般在 为了便于建立问题的模型，定义以下符号
北 京 科 技 大 学 学 报 第 36 卷 的入库优化决策问题就是为即将入库的每一根钢管 选择合适的垛位，以便于钢管库的管理，同时减少钢 管库的倒垛作业; 其中，存在这样一类入库问题: 在 钢管库入库管理及钢管的装载运输过程中，为了避 免滚落和摆放不协调，往往是将半径较大的钢管置 于半径较小的下方，将较长的钢管置于较短钢管的 下方［3］，且同一层的半径和长度不能相差太大; 同 时为了优化后续的出库作业，要求钢管入库时考虑 交货期的松紧，即具有较紧交货期的钢管应尽可能 的置于垛位上方，以便于出库． 文献［4］针对大规模 板坯倒垛问题建立了一种基于启发式的阶段动态规 划模型，并设计了对应启发式算法，该算法在实际生 产中可减少 10. 76% 的倒垛量; 文献［5］提出一种箱 子高度可变的三维装箱问题，并设计了针对此类问 题的一种改进的遗传算法，算法结果明显优于传统 装箱算法; 文献［6］将一种带交货期约束的板坯堆 垛问题归结为约束满足问题，并设计了一种混合约 束满足算法，算法结果优于经典的 BFD ( best fit deceasing) 算法; 文献［7］针对板坯入库优化决策问 题，采用模糊数学的研究方法将板坯各规格属性模 糊化，设计了一种混合离散粒子群算法，相比传统的 遗传算法减少了 16% 的倒垛量; 文献［8］针对钢铁 企业供应链上的线圈作业调度优化问题设计了一种 基于启发式规则的算法，并在实际生产中有了很好 的应用; 文献［9］针对库区吊机能力实际限制下的 板坯倒垛问题建立了非线性规划模型，并对问题特 征进行分析，针对轧制项目间是否存在共同可选板 坯的两种情况，将模型转化为线性整数规划模型，利 用问题的性质降低了模型的求解复杂性． 以上研究 成果对本文的研究具有一定的参考价值． 以往研究中多以板坯特性的货物作为研究对 象，一般是多层堆放，一层只允许堆放一个货物，在 堆放时主要综合考虑货物的厚度、宽度、重量和交货 期等因素，而对具有钢管特性的货物的研究较少，仅 有几篇研究的是钢卷的入库优化问题，也是类似于 板坯的存放方式． 对于钢管多层多列的堆放方式研 究还尚未见． 本文以钢管成品库优化管理中的入库 优化决策问题作为研究对象，因钢管入库时存在交 货期的松紧约束，故将其归结为带顺序约束的三维 ASBP ( a-shape bin packing) 问题，并映射为约束满 足问题［10］( constraint satisfaction problem，CSP) ． 三 维 ASBP 问题是一个具有复杂约束条件的组合优化 问题，具有典型的 NP 难特性，它在实际中有许多约 束条件需要考虑，如空间约束、载重约束、货物摆向 约束、稳定性约束和货物装卸顺序约束［11］，一般在 实践中为了在合理的时间内找到近优解都采用启发 式方法进行求解，因为传统的搜索技术求解此类问 题，会产生“组合爆炸现象”，很难在有效的时间内 获得最优解． 当前对钢铁企业产品入库问题的研究 中大部分是针对板坯入库问题的约束满足模型，而 针对钢管入库决策问题的约束满足模型还尚未见， 因此本文针对钢管入库优化决策问题建立了约束满 足模型; 在求解算法上，针对入库钢管具有多种规格 的特征，提出一种基于聚类的约束满足算法，并通过 数据实验验证了算法的有效性． 1 问题建模 1. 1 问题描述 一般钢铁企业钢管的存放方式与钢管的半径有 很大关系，半径比较小的多以捆的形式存放，随着钢 铁企业的飞速发展，钢铁企业订单多以小批量、多客 户进行生产，钢管的存放方式也发生了一些改变． 目前有很多钢铁企业钢管的存放多以“A”字型、多 层多列堆放，这种堆放方式一般适应于半径较大、客 户交货期松紧度相近的钢管产品，所以对于钢管的 入库堆放问题即垛位优化问题的研究对钢管库的管 理起着至关重要的作用． 对于钢管入库优化决策问题，由于入库钢管的 订单交期已经确定，因此钢管在堆垛时主要参照订 单交货期执行，将钢管交货期靠前的尽可能摆在上 方，以减少出库时的倒垛次数． 钢管库中通常存在 若干垛位，为节省空间需要多层多列叠放，因而为了 保证垛位的稳定性，在进行钢管堆垛时考虑以下几 方面要求: ( 1) 上层钢管的长度与下层相邻钢管的 长度差的绝对值不超过某一给定上限值; ( 2) 上层 钢管的半径与下层相邻钢管的半径差的绝对值不超 过某一给定上限值; ( 3) 同层任意两根钢管的半径 差值的绝对值不能超过某一给定上限值; ( 4) 同层 任意两根钢管的长度差值的绝对值不能超过某一给 定上限值; ( 5) 受地面承重能力、安全原因和起重设 备所能达到的高度所限，每个垛位上钢管的总高度 不超过某一给定上限值． 根据钢管成批生产且同批钢管钢种相同或相近 的特征，本文假设每一批的待入库钢管具有相同的 钢种，则钢管入库优化决策问题即是根据待入库的 钢管半径、长度等属性的不同，在不违背垛高限制的 情况下为其指派垛位，使得在满足出库零倒垛的前 提下，占用的垛位数最少． 1. 2 符号定义 为了便于建立问题的模型，定义以下符号． ·124·
第1期 董广静等：基于聚类一约束满足算法的钢管入库优化决策模型 ·125· (1)集合和索引. Cn+r为+ i:钢管编号； :垛位编号： :钢管集合，1={1,2，…，i,…,n}: hi: (2) J:垛位集合，J={1,2,…j,…,m}. C2:h≤H,jeJ: (3) (2)参数. Cmax{lr-T,lr1-r}≤D, L(2):初始垛位中空垛位集合； VaeZi (4) H:垛位允许的最大高度，只考虑初始状态为空 C4:lr,-r,≤a,Ha,a2∈Zt; (5) 垛的情况： Csimax D:任一钢管与上层相邻两钢管的半径差额上 Hz1∈Zt; (6) 限值： α：相邻两层半径的差额上限值： C6:l-l≤B,z∈Z: (7) L:任一钢管与上层相邻两钢管的长度差额上 C,:mio04n}≥0ua,a1∈乙：(8） (9) 限值； Cslo%-0≤Y,Ha1eZ: B:同层长度的差额上限值： Cim-ma YjeJ: (10) y:同层交货期的差额上限值； T:钢管i的半径： Comt+)+1≤m,j∈J: (11) l:钢管i的长度； C:0Q0{x}=0: (12) 0:钢管i的交货期. Cn:0)=1; (13) (3)变量. C13:m≥0，mt≥0，x法≥0. (14) h,:垛位j的高度： 目标函数式(1)表示最小化钢管占用垛位数； G:垛位j上的层数： 式(2)表示层数与垛位高度及各层钢管半径的直接 Z:垛位j上第k层的位置编号集合； 关系；式(3)表示垛位的高度不能超过一定限制；式 m:垛位j上的钢管总数： (4)表示第i+1层钢管与第i层相邻两钢管的半径 m:垛位j上第k层上的钢管总数： 差值不超过某一给定值：式(5)表示同一层钢管的 x:为第j个垛位上第k层自左起第z个钢管 半径差值不超过某一给定值：式(6)表示第i+1层 的编号，x1表示垛位j上最底层最左边的钢管编号， 钢管与第i层相邻两钢管的长度差值不超过某一给 随着同一层钢管逐次自左向右堆放，z值逐渐增大： 定值，主要是为了垛位稳定协调作的限制；式(7)表 随钢管的逐层堆放，k值逐渐增大 示同一层钢管的长度值不超过某一给定值：式(8) 1.3约束满足模型 表示第i+1层钢管不大于第i层相邻两钢管的交货 上述钢管入库优化决策问题实质上是一类多层 期，主要考虑到出库时的优化：式(9)表示同层钢管 多列带顺序的三维装箱问题，可以将此问题映射成 的交货期不能超过某一给定值，主要是为了保证出 约束满足问题.约束满足问题(constraint satisfaction 库的协调：式(10)表示垛位j上钢管总数与各层上 problem,CSP)是人工智能的一个重要研究领域，在 钢管的数量之间的关系；式(11)表示相邻两层之间钢 工业工程中的很多实际问题都有着广泛的应用，比 管的数量关系：式(12)要求每根钢管必须只能匹配一 如批量计划☒、作业调度圆、资源分配和产品配 个垛位：式(13)和式(14)定义了变量的取值范围. 置，其建模方法能够以更加接近于现实世界的方式 2钢管入库垛位优化决策问题的定性分析 描述问题及其复杂的约束的.对于钢管入库堆垛 问题，可用一个四元组所表示的约束 2.1垛高的计算策略 满足问题来描述.其中，V={V,V2,,Vn}为变量 一般情况下，在钢管堆放时会出现如下堆放情 集；D={D1,D2,,Dn}为值域集，D:为V:的值域： 况，如下图1. C={C,C2,…,C}为约束关系集；F为优化目标数 对于图1的垛高计算公式如下：设11和r2分别 集.模型如下 为当前层半径及其上一层两相邻钢管的平均半径 min m; (1) 如图1，由三圆圆心组成的等腰三角形的高为h,= Subject to: √(m+r2)2-=√+2r1T2:截止到现在层的垛
第 1 期 董广静等: 基于聚类--约束满足算法的钢管入库优化决策模型 ( 1) 集合和索引． i: 钢管编号; j: 垛位编号; I: 钢管集合，I = { 1，2，…，i，…，n} ; J: 垛位集合，J = { 1，2，…，j，…，m} ． ( 2) 参数． L( Ω) : 初始垛位中空垛位集合; H: 垛位允许的最大高度，只考虑初始状态为空 垛的情况; D: 任一钢管与上层相邻两钢管的半径差额上 限值; α: 相邻两层半径的差额上限值; L: 任一钢管与上层相邻两钢管的长度差额上 限值; β: 同层长度的差额上限值; γ: 同层交货期的差额上限值; ri : 钢管 i 的半径; li : 钢管 i 的长度; oi : 钢管 i 的交货期． ( 3) 变量． hj : 垛位 j 的高度; cj : 垛位 j 上的层数; Zjk : 垛位 j 上第 k 层的位置编号集合; mj : 垛位 j 上的钢管总数; mjk : 垛位 j 上第 k 层上的钢管总数; xjkz: 为第 j 个垛位上第 k 层自左起第 z 个钢管 的编号，xj11表示垛位 j 上最底层最左边的钢管编号， 随着同一层钢管逐次自左向右堆放，z 值逐渐增大; 随钢管的逐层堆放，k 值逐渐增大． 1. 3 约束满足模型 上述钢管入库优化决策问题实质上是一类多层 多列带顺序的三维装箱问题，可以将此问题映射成 约束满足问题． 约束满足问题( constraint satisfaction problem，CSP) 是人工智能的一个重要研究领域，在 工业工程中的很多实际问题都有着广泛的应用，比 如批量计划［12］、作业调度［13］、资源分配和产品配 置，其建模方法能够以更加接近于现实世界的方式 描述问题及其复杂的约束［14］． 对于钢管入库堆垛 问题，可用一个四元组 ＜ V，D，C，F ＞ 所表示的约束 满足问题来描述． 其中，V = { V1，V2，…，Vn } 为变量 集; D = { D1，D2，…，Dn } 为值域集，Di 为 Vi 的值域; C = { C1，C2，…，Cn } 为约束关系集; F 为优化目标数 集． 模型如下． min m; ( 1) Subject to: C1 : rxj1 + rxjcj ( + 2∑ cj k =1 rxjk － cj rxj1 － rxjc ) ( j 2∑ cj k =2 rxjk + cj rxj1 － rx 槡 jc )j = hj ; ( 2) C2 : hj≤H，j∈J; ( 3) C3 : max{ |rxjkz1 － rxj( k + 1) z1 |，|rxjk( z1 + 1) － rxj( k + 1) z1 |} ≤D， z1∈Zjk ; ( 4) C4 : |rjkz1 － rjkz2 |≤α，z1，z2∈Zjk ; ( 5) C5 : max{ | lxjkz1 － lxj( k + 1) z1 |，| lxjk( z1 + 1) － lxj( k + 1) z1 |} ≤L， z1∈Zjk ; ( 6) C6 : | lxjkz1 － lxjkz2 |≤β，z1，z2∈Zjk ; ( 7) C7 : min{ oxjkz1 ，oxjk( z1 + 1) } ≥oxj( k + 1) z1 ，z1∈Zjk ; ( 8) C8 : | oxjkz1 － oxjkz2 |≤γ，z1，z2∈Z; ( 9) C9 : mj = ∑ cj k = 1 mjk，j∈J; ( 10) C10 : mj( k + 1) + 1≤mjk，j∈J; ( 11) C11 : ∩ j ∩k ∩z { xjkz} = ; ( 12) C12 : ∪ j ∪k ∪z { xjkz} = I; ( 13) C13 : mj≥0，mjk≥0，xjkz≥0． ( 14) 目标函数式( 1) 表示最小化钢管占用垛位数; 式( 2) 表示层数与垛位高度及各层钢管半径的直接 关系; 式( 3) 表示垛位的高度不能超过一定限制; 式 ( 4) 表示第 i + 1 层钢管与第 i 层相邻两钢管的半径 差值不超过某一给定值; 式( 5) 表示同一层钢管的 半径差值不超过某一给定值; 式( 6) 表示第 i + 1 层 钢管与第 i 层相邻两钢管的长度差值不超过某一给 定值，主要是为了垛位稳定协调作的限制; 式( 7) 表 示同一层钢管的长度值不超过某一给定值; 式( 8) 表示第 i + 1 层钢管不大于第 i 层相邻两钢管的交货 期，主要考虑到出库时的优化; 式( 9) 表示同层钢管 的交货期不能超过某一给定值，主要是为了保证出 库的协调; 式( 10) 表示垛位 j 上钢管总数与各层上 钢管的数量之间的关系; 式( 11) 表示相邻两层之间钢 管的数量关系; 式( 12) 要求每根钢管必须只能匹配一 个垛位; 式( 13) 和式( 14) 定义了变量的取值范围． 2 钢管入库垛位优化决策问题的定性分析 2. 1 垛高的计算策略 一般情况下，在钢管堆放时会出现如下堆放情 况，如下图 1． 对于图 1 的垛高计算公式如下: 设 r1 和 r2 分别 为当前层半径及其上一层两相邻钢管的平均半径． 如图 1，由三圆圆心组成的等腰三角形的高为 h1 = ( r1 + r2 ) 2 槡 － r 2 2 = r 2 1 + 2r 槡 1 ·r2 ． 截止到现在层的垛 ·125·
·126· 北京科技大学学报 第36卷 类的约束满足算法(constraint satisfaction algorithm based on clustering,CSC).算法由两阶段构成：第一 阶段将入库钢管按照半径、交货期和长度三个属性 进行加权聚类，并将各组按照平均半径非增排序，组 作前垛位高度私 内部按照交货期非增排序：第二阶段对于形成的每 一组采用约束满足算法为各类中钢管指派垛位.算 图1垛高分析示意图 Fig.1 Schematic diagram of analysis for stack high 法的主要流程如图2所示 高为h2=h+△h=h+r1-r2+h,:为了保证垛高增 算法开始 量△h>0,需要满足的半径约束为r1>r2/4. 初始化 显然，这种计算方法得到的堆垛高度必定不小 于实际垛高，换言之，只要此垛高不超过垛高的上限 聚类算法 要求，那么实际的垛高一定不会超过设定的上限值 初始约束 2.2钢管堆放规则 搜常算法 亨 约束传播 钢管的堆放对长度、半径和交货期等属性具有 局部解 严格要求，比一般的板坯堆垛问题要复杂。本文在 新约束 新约束 1.1节给出的五条堆垛要求的基础上定义了以下三 (传插) (决策值) 种规则，以指导钢管的堆放： 最终行效解 规则1]若垛位为空垛，则从垛位的第一层 (即最底层)自左向右依次按交货期非增堆放，交货 图2基于聚类的约束满足算法流程图 Fig.2 Flow chart of the clustering-based CSC algorithm 期相同的，则按长度非增堆放； 规则2]堆放钢管时按照“A”字型堆放，即 为了便于问题的进一步讨论，给出下列定义 第i层的钢管数必须严格大于第i+1层的钢管数， 定义1（适应值）设和”为垛位j上第k层 堆放高度一般不能超过最大高度H,且只有堆满上 两个相邻钢管的编号，i为该垛位上第k+1层与i、 一层才能继续堆放下一层； ”相邻的钢管编号，则定义钢管i与i'、”之间的适应 规则3]同层任意两个钢管的交货期的差值 值Pie为： 不大于给定值，且相邻两层钢管的交货期需满足第 t01+2 i+1层任一钢管的交货期不大于第i层相邻两钢管 √0(0+0-20，)2+w2(0,+l2-2,)2+01+2 的交货期的要求. (15) 其中，01和U2分别为钢管的交货期和长度的权重. 3求解算法 定义2（可排位置）若垛位j的第k个位置为 钢管入库优化决策问题实质上是对经典BP 空，且钢管放置在该位置不违背长度和交货期的 (bin packing)问题在三维上的一种扩展，通常考虑 约束，则称位置(，k)为钢管i的可排位置 将经典的BP启发式算法修改后直接推广使用.就 定义3（能排位置）在不考虑长度和交货期约 钢管入库垛位优化决策问题而言，考虑到降低同垛 束的情况下，若将钢管i堆放在垛位j的第k个位置 内不同层数上钢管之间半径、长度等属性的堆放要 上不会违背其他约束，则称位置(，k)为钢管i的能 求，降序最佳适应算法(best fit decreasing,BFD)具 排位置. 有相对良好的效果.然而考虑交货期的入库垛位优 3.1基于K-Means聚类算法的分组策略 化决策问题更为复杂，约束众多且彼此关联，因而不 将每个钢管的各个属性看作g维向量，记作 能直接采用.约束满足技术—作为求解大规模组 x:=(x1i,x2x,…,x）,（i=1,2,…,n),x表示钢管编 合优化问题的一种有效智能方法，能够针对约束满 号为i的第k个属性量.本文采用欧式加权距离来 足模型，在已知变量和约束的前提下，通过寻求变量 定义钢管之间的距离。则对多属性多约束的钢管进 的合理取值，以满足问题的所有约束，同时优化某个 行分组的K-Means聚类算法(K-Means clustering al-- 性能属性. gorithm of steel tube,KCAST)的具体步骤如下. 针对钢管的多维属性特征，本文设计了基于聚 Step1设钢管集为Q=(x1,x2,…,xn-1xn）
北 京 科 技 大 学 学 报 第 36 卷 图 1 垛高分析示意图 Fig． 1 Schematic diagram of analysis for stack high 高为 h2 = h + Δh = h + r1 － r2 + h1 ; 为了保证垛高增 量 Δh ＞ 0，需要满足的半径约束为 r1 ＞ r2 /4． 显然，这种计算方法得到的堆垛高度必定不小 于实际垛高，换言之，只要此垛高不超过垛高的上限 要求，那么实际的垛高一定不会超过设定的上限值． 2. 2 钢管堆放规则 钢管的堆放对长度、半径和交货期等属性具有 严格要求，比一般的板坯堆垛问题要复杂． 本文在 1. 1 节给出的五条堆垛要求的基础上定义了以下三 种规则，以指导钢管的堆放: ［规则 1］ 若垛位为空垛，则从垛位的第一层 ( 即最底层) 自左向右依次按交货期非增堆放，交货 期相同的，则按长度非增堆放; ［规则 2］ 堆放钢管时按照“A”字型堆放，即 第 i 层的钢管数必须严格大于第 i + 1 层的钢管数， 堆放高度一般不能超过最大高度 H，且只有堆满上 一层才能继续堆放下一层; ［规则 3］ 同层任意两个钢管的交货期的差值 不大于给定值，且相邻两层钢管的交货期需满足第 i + 1 层任一钢管的交货期不大于第 i 层相邻两钢管 的交货期的要求． 3 求解算法 钢管入库优化决策问题实质上是对经典 BP ( bin packing) 问题在三维上的一种扩展，通常考虑 将经典的 BP 启发式算法修改后直接推广使用． 就 钢管入库垛位优化决策问题而言，考虑到降低同垛 内不同层数上钢管之间半径、长度等属性的堆放要 求，降序最佳适应算法( best fit decreasing，BFD) 具 有相对良好的效果． 然而考虑交货期的入库垛位优 化决策问题更为复杂，约束众多且彼此关联，因而不 能直接采用． 约束满足技术———作为求解大规模组 合优化问题的一种有效智能方法，能够针对约束满 足模型，在已知变量和约束的前提下，通过寻求变量 的合理取值，以满足问题的所有约束，同时优化某个 性能属性． 针对钢管的多维属性特征，本文设计了基于聚 类的约束满足算法( constraint satisfaction algorithm based on clustering，CSC) ． 算法由两阶段构成: 第一 阶段将入库钢管按照半径、交货期和长度三个属性 进行加权聚类，并将各组按照平均半径非增排序，组 内部按照交货期非增排序; 第二阶段对于形成的每 一组采用约束满足算法为各类中钢管指派垛位． 算 法的主要流程如图 2 所示． 图 2 基于聚类的约束满足算法流程图 Fig． 2 Flow chart of the clustering-based CSC algorithm 为了便于问题的进一步讨论，给出下列定义． 定义 1( 适应值) 设 i'和 i″为垛位 j 上第 k 层 两个相邻钢管的编号，i 为该垛位上第 k + 1 层与 i'、 i″相邻的钢管编号，则定义钢管 i 与 i'、i″之间的适应 值 Pii'i″为: Pii'i″ = w1 + w2 w1 ( oi' + oi″ － 2oi ) 2 + w2 ( li' + li″ － 2li 槡 ) 2 + w1 + w2 ． ( 15) 其中，w1 和 w2 分别为钢管的交货期和长度的权重． 定义 2( 可排位置) 若垛位 j 的第 k 个位置为 空，且钢管 i 放置在该位置不违背长度和交货期的 约束，则称位置( j，k) 为钢管 i 的可排位置． 定义 3( 能排位置) 在不考虑长度和交货期约 束的情况下，若将钢管 i 堆放在垛位 j 的第 k 个位置 上不会违背其他约束，则称位置( j，k) 为钢管 i 的能 排位置． 3. 1 基于 K-Means 聚类算法的分组策略 将每个钢管的各个属性看作 q 维向量，记作 xi = ( x1i，x2i，…，xqi ) ，( i = 1，2，…，n) ，xki表示钢管编 号为 i 的第 k 个属性量． 本文采用欧式加权距离来 定义钢管之间的距离． 则对多属性多约束的钢管进 行分组的 K-Means 聚类算法( K-Means clustering algorithm of steel tube，KCAST) 的具体步骤如下． Step 1 设钢管集为 Q = ( x1，x2，…，xn － 1，xn ) ， ·126·
第1期 董广静等：基于聚类一约束满足算法的钢管入库优化决策模型 ·127· x:=(x,x2,,x）,标准半径的种类数记为p,其 间实现减少计算量的目的.通过对入库堆垛问题使 中，与标准半径相差（给定值）可视为标准半径，因 用约束传播技术，能够约减部分变量（即钢管）的值 此将聚类组数设为p; 域，去掉一些无效的垛位取值，具体方法为：在完成 Step2随机选取每个类里的一个粒子作为初 对当前钢管i垛位匹配的同时，通过约束C3~C4可 始聚类中心c1,c2,…,Cp: 以过滤掉变量中有上下两层相邻钢管半径和同层半 Step3根据下式将钢管集Q中的对象x:(i= 径都有冲突的变量：通过约束C5~C。可以过滤掉变 1,2,…,n)依次按欧式平均距离分配给距离最近的 量中有上下两层相邻长度和同层长度都有冲突的变 中心c=1,2,…,p), 量；通过约束C,~Cg可以过滤掉变量中有上下两层 相邻交货期和同层交货期都有冲突的变量：通过约 lx:-c‖=min ,(1≤≤p), 束C,可以减少值域的搜索范围，加快搜索速度. (16) 通过上述操作，可以有效地降低问题的规模，降 式中，q为粒子的属性组成的维数，4为各属性的 低搜索空间，提高求解效率，从而简化了问题使其易 权值； 于求解. Step 4 按下式计算p个聚类的中心c)=1, 3.3算法步骤 2,…,p）, CSC算法的具体步骤如下. Step1(初始化) S=∑j=1,2,…p (17) 初始化入库钢管编号i,半径r、长度l:和订单 其中，N为第j个聚类S中所包含的粒子个数； 交货期·：及垛位信息及对应垛位上钢管信息 Step5如果各个聚类中心c,(=1,2,…,p)不 Step2(入库钢管的聚类分组) 再变化，转至Step6,否则返回Step3; 执行KCAST算法，将一批入库的钢管按照半 Step6分别对p个聚类结果中的钢管按照钢 径、长度和交货期的一定权重聚类，并在各类内按交 管的交货期非增，交货期相同的按长度非增排序 货期非增排序，类与类之间按平均半径非增排序 算法结束] Step3(变量选择) 3.2约束满足算法 遍历每个类里面的钢管，选定订单的交货期对 (1)变量选择.首先选择安排起来比较困难的 变量进行降序排序.令min(topLength())、min(to- 变量，即半径较大的钢管i,以尽可能避免形成不可 pOrder())和totalHeigtht()分别表示垛位j中能堆 行的部分解.结合BP的特点，对求解装箱问题的降 放钢管的位置上同层相邻钢管的最小长度、订单的 序最佳适应规则进行推广，得到以下两种变量排序 最小交货期以及该垛位钢管的水平高度 规则： Step4(值选择) 规则4]变量按交货期非增顺序排序； (a)依次为变量赋值，即对当前变量值域进行 规则5]变量按长度非增顺序排序，若存在 值排序，选取值域中的第一个垛位作为当前变量的 长度相同的多个变量，则按交货期降序排列. 当前取值： (2)值选择.首先依据所选变量的交货期约束 (b)设当前变量为i,当前取值为j,则通过搜索 对值域（可排位置）进行约简，即去除不满足当前钢 钢管所能堆放的位置确定是否将j赋值给变量： 管交货期约束的垛位然后采用值选择规则从值 若可堆放位置同层己有其他钢管，且满足！，≤ 域中选择垛位指派给当前钢管.为了使堆垛问题的 min(topLength())、o:≤min(topOrder()),则将垛 目标值尽可能最小化，采用BFD作为值选择规则： 位j赋值给钢管i,同时更新该垛位的min(topLength 规则6]值域按照垛位的剩余能排位置数的 ())、min(topOrder(i))取值； 非增排序，若能排位置数相同，则选择可排层数较高 若可堆放位置的同层没有其他钢管，且满足 的垛位； l,≤min(topLength(i)）、o,≤min(topOrder())和to- 规则7]若所有非空垛位都不能放置该钢管 talHeight()+V3r,≤H,则将垛位j赋值给钢管i,同 时，则为其申请一个新垛位 时更新该垛位的min(topLength(j))、min(topOrder 由于变量值域的大小在搜索过程中是动态变化 (i))和totalHeight()取值： 的，所以上述变量选择和值选择的顺序也是动态的 若取值j均不满足上述情况，则从值域中选取 (3)约束传播.约束传播技术通过缩小搜索空 下一个取值作为变量i的当前取值，重复Step4
第 1 期 董广静等: 基于聚类--约束满足算法的钢管入库优化决策模型 xi = ( x1i，x2i，…，xpi ) ，标准半径的种类数记为 p，其 中，与标准半径相差 θ( 给定值) 可视为标准半径，因 此将聚类组数设为 p; Step 2 随机选取每个类里的一个粒子作为初 始聚类中心 c1，c2，…，cp ; Step 3 根据下式将钢管集 Q 中的对象 xi ( i = 1，2，…，n) 依次按欧式平均距离分配给距离最近的 中心 cj ( j = 1，2，…，p) ， ‖xi － cj‖ = m ( in ∑ q k =1 ωk ( xki － ckj ) 槡 ) 2 ，( 1≤j≤p) ， ( 16) 式中，q 为粒子的属性组成的维数，ωk 为各属性的 权值; Step 4 按下式计算 p 个聚类的中心 cj ( j = 1， 2，…，p) ， cj = 1 Nj ∑i∈Sj xi，j = 1，2，…，p， ( 17) 其中，Nj 为第 j 个聚类 Sj 中所包含的粒子个数; Step 5 如果各个聚类中心 cj ( j = 1，2，…，p) 不 再变化，转至 Step 6，否则返回 Step 3; Step 6 分别对 p 个聚类结果中的钢管按照钢 管的交货期非增，交货期相同的按长度非增排序． ［算法结束］ 3. 2 约束满足算法 ( 1) 变量选择． 首先选择安排起来比较困难的 变量，即半径较大的钢管 i，以尽可能避免形成不可 行的部分解． 结合 BP 的特点，对求解装箱问题的降 序最佳适应规则进行推广，得到以下两种变量排序 规则: ［规则 4］ 变量按交货期非增顺序排序; ［规则 5］ 变量按长度非增顺序排序，若存在 长度相同的多个变量，则按交货期降序排列． ( 2) 值选择． 首先依据所选变量的交货期约束 对值域( 可排位置) 进行约简，即去除不满足当前钢 管交货期约束的垛位 j． 然后采用值选择规则从值 域中选择垛位指派给当前钢管． 为了使堆垛问题的 目标值尽可能最小化，采用 BFD 作为值选择规则: ［规则 6］ 值域按照垛位的剩余能排位置数的 非增排序，若能排位置数相同，则选择可排层数较高 的垛位; ［规则 7］ 若所有非空垛位都不能放置该钢管 时，则为其申请一个新垛位． 由于变量值域的大小在搜索过程中是动态变化 的，所以上述变量选择和值选择的顺序也是动态的． ( 3) 约束传播． 约束传播技术通过缩小搜索空 间实现减少计算量的目的． 通过对入库堆垛问题使 用约束传播技术，能够约减部分变量( 即钢管) 的值 域，去掉一些无效的垛位取值，具体方法为: 在完成 对当前钢管 i 垛位匹配的同时，通过约束 C3 ～ C4 可 以过滤掉变量中有上下两层相邻钢管半径和同层半 径都有冲突的变量; 通过约束 C5 ～ C6 可以过滤掉变 量中有上下两层相邻长度和同层长度都有冲突的变 量; 通过约束 C7 ～ C8 可以过滤掉变量中有上下两层 相邻交货期和同层交货期都有冲突的变量; 通过约 束 C2 可以减少值域的搜索范围，加快搜索速度． 通过上述操作，可以有效地降低问题的规模，降 低搜索空间，提高求解效率，从而简化了问题使其易 于求解． 3. 3 算法步骤 CSC 算法的具体步骤如下． Step 1 ( 初始化) 初始化入库钢管编号 i，半径 ri、长度 li 和订单 交货期 oi 及垛位信息及对应垛位上钢管信息． Step 2 ( 入库钢管的聚类分组) 执行 KCAST 算法，将一批入库的钢管按照半 径、长度和交货期的一定权重聚类，并在各类内按交 货期非增排序，类与类之间按平均半径非增排序． Step 3 ( 变量选择) 遍历每个类里面的钢管，选定订单的交货期对 变量进行降序排序． 令 min( topLength( j) ) 、min( topOrder( j) ) 和 totalHeigtht( j) 分别表示垛位 j 中能堆 放钢管的位置上同层相邻钢管的最小长度、订单的 最小交货期以及该垛位钢管的水平高度． Step 4 ( 值选择) ( a) 依次为变量赋值，即对当前变量值域进行 值排序，选取值域中的第一个垛位作为当前变量的 当前取值; ( b) 设当前变量为 i，当前取值为 j，则通过搜索 钢管所能堆放的位置确定是否将 j 赋值给变量 i; 若可堆放位置同层已有其他钢管，且满足 li≤ min( topLength( j) ) 、oi≤min( topOrder( j) ) ，则将垛 位 j 赋值给钢管 i，同时更新该垛位的 min( topLength ( j) ) 、min( topOrder( j) ) 取值; 若可堆放位置的同层没有其他钢管，且满足 li≤min( topLength( j) ) 、oi≤min( topOrder( j) ) 和 totalHeight( j) + 槡3ri≤H，则将垛位 j 赋值给钢管 i，同 时更新该垛位的 min( topLength( j) ) 、min( topOrder ( j) ) 和 totalHeight( j) 取值; 若取值 j 均不满足上述情况，则从值域中选取 下一个取值作为变量 i 的 当 前 取 值，重 复 Step 4 ·127·
·128 北京科技大学学报 第36卷 (b). Step1初始化钢管各指标数据及垛位参数； Step5(计算可排位置适应值) Step2对所有钢管按优先半径r:非增排序， 根据式(15)计算各个钢管在其可排位置的适 其次按长度非增排序： 应值，选择适应值最大的值j赋给变量i,其中将任 Step3选择当前半径最大的钢管，搜索其非空 意钢管在第一层空位置的适应值记为l,转Step6; 垛位上的适应位置，选择最适合的适应位置，转Step Step6(约束传播) 3:若不存在该适应位置且L(2)≠O,转Step4;否 根据当前变量i的赋值，对值域中包含j的剩余 则若L(2)=O,转Step5; 变量进行约束传播： Step4开辟一个新垛位，并将该钢管分配到新 规则8]根据约束C2,对于满足≥H- 开启非空垛位中： totalHeight()]/W5的变量，从值域中剔除j: Step5选择能排位置中最适合的位置； 规则9]根据约束C5~C6,对于满足Il- Step6重复Step3到Step5直到分配完所有 min(topLength()I>L的变量，从值域中剔除j: 钢管 规则10]根据约束C,~Cg,对于满足min [算法结束] (topOrder())<o的变量，从值域中剔除j: 4.3实验结果与分析 若存在未堆放钢管，转Step3,否则转Step7. 本文算法采用Microsoft Visual Studio C#编程 Step7算法结束 实现了CSC算法的入库优化决策问题测试.测试环 CSC算法在有限步骤内收敛，因为对于给定的 境为Pentium4/1GHz/512MB/Windows XP Profes- 钢管集合I,其垛位的适应位置为固定值.在CSC算 sional. 法的每一次循环中，钢管的未分配垛位量以离散值 根据上述规则，在600个数据中分别随机抽取 的形式单调递减.因此，由CSC算法一定在有限步 150、200、250、300、350、400、450、500、550和600根 骤内收敛 的钢管对以上设计的算法进行验证，共计10组实验 4仿真实验 数据，每组实验单独运行40次.将基于聚类的约束 满足算法与改进的经典的BFD算法就占用平均垛 4.1实验参数设置 位数、垛位平均利用率进行了比较，实验结果见表 为了验证模型及算法的正确性及可行性，根据 1:同时就入库钢管数不同时所占用的新增垛位数进 某钢厂钢管入库的实际数据，按如下方式设计钢管 行模拟实验40次，计算两算法的平均垛位增加数 堆垛算例：初始垛位有四个非空垛位和若干空垛位， 实验结果如图3. 其中已存放钢管的各个属性已知：已匹配订单的待 14 入库钢管600根，编号为i的钢管具有一组属性数 13 (算法 据[or,l,],且订单号o:∈1,9]，4，∈100,109]， 12 +一BD算法 T:∈50,59]，垛高上限为800，垛宽为1200.模型中 11 权重系数的选取直接关系到库位和垛位的选择是否 94 合理，其值应根据专家知识获得，此外规格品种相近 8 的钢管在生产计划中具有连续分布的特点 4.2参照算法 由于目前还未能找到针对钢管入库优化决策问 150200250300350400450500550600 题的相关文献与算法，因此为了评价CSC算法，本 人库钢管数 文给出了以下改进的参照算法 图3CSC算法与BD算法性能比较 Fig.3 Comparison of the performance of CSC algorithm and BFD al- 入库优化决策问题可以归结装箱问题，而钢管 gorithm 入库问题是一种带顺序的A型装箱(a-shape bin packing,ASBP)问题，都是力求用最少的箱子（垛 随机抽取600个数据对本文设计的算法进行验 位)装箱所有的物品（入库钢管），可以借鉴装箱问 证40次，其中垛位编号为1,2,3,4的前四个垛位为 题行之有效的经典算法BFD构造钢管入库优化决 初始化后的四个非空垛位，其余垛位都是钢管入库 策问题的类似求解算法BFD如下. 后新增的垛位.实验结果见图4.采用CSC算法，计 BFD算法] 算得出只需平均新增10个垛位，垛位利用率为
北 京 科 技 大 学 学 报 第 36 卷 ( b) ． Step 5 ( 计算可排位置适应值) 根据式( 15) 计算各个钢管在其可排位置的适 应值，选择适应值最大的值 j 赋给变量 i，其中将任 意钢管在第一层空位置的适应值记为 1，转 Step 6; Step 6 ( 约束传播) 根据当前变量 i 的赋值，对值域中包含 j 的剩余 变量进行约束传播: ［规则 8］ 根据约束 C2，对于满足 ri' ≥［H － totalHeight( j) ］/槡3的变量，从值域中剔除 j; ［规则 9］ 根据约束 C5 ～ C6，对于满足 | li' － min( topLength( j) ) | ＞ L 的变量，从值域中剔除 j; ［规则 10］ 根据约束 C7 ～ C8，对于满足 min ( topOrder( j) ) ＜ oi'的变量，从值域中剔除 j; 若存在未堆放钢管，转 Step 3，否则转 Step 7． Step 7 算法结束． CSC 算法在有限步骤内收敛，因为对于给定的 钢管集合 I，其垛位的适应位置为固定值． 在 CSC 算 法的每一次循环中，钢管的未分配垛位量以离散值 的形式单调递减． 因此，由 CSC 算法一定在有限步 骤内收敛． 4 仿真实验 4. 1 实验参数设置 为了验证模型及算法的正确性及可行性，根据 某钢厂钢管入库的实际数据，按如下方式设计钢管 堆垛算例: 初始垛位有四个非空垛位和若干空垛位， 其中已存放钢管的各个属性已知; 已匹配订单的待 入库钢管 600 根，编号为 i 的钢管具有一组属性数 据［oi，ri，li］，且订单号 oi∈［1，9］，li∈［100，109］， ri∈［50，59］，垛高上限为 800，垛宽为 1200． 模型中 权重系数的选取直接关系到库位和垛位的选择是否 合理，其值应根据专家知识获得，此外规格品种相近 的钢管在生产计划中具有连续分布的特点． 4. 2 参照算法 由于目前还未能找到针对钢管入库优化决策问 题的相关文献与算法，因此为了评价 CSC 算法，本 文给出了以下改进的参照算法． 入库优化决策问题可以归结装箱问题，而钢管 入库问题是一种带顺序的 A 型装箱( a-shape bin packing，ASBP) 问题，都是力求用最少的箱子( 垛 位) 装箱所有的物品( 入库钢管) ，可以借鉴装箱问 题行之有效的经典算法 BFD 构造钢管入库优化决 策问题的类似求解算法 BFD 如下． ［BFD 算法］ Step 1 初始化钢管各指标数据及垛位参数; Step 2 对所有钢管按优先半径 ri 非增排序， 其次按长度非增排序; Step 3 选择当前半径最大的钢管，搜索其非空 垛位上的适应位置，选择最适合的适应位置，转 Step 3; 若不存在该适应位置且 L( Ω) ≠，转 Step 4; 否 则若 L( Ω) = ，转 Step 5; Step 4 开辟一个新垛位，并将该钢管分配到新 开启非空垛位中; Step 5 选择能排位置中最适合的位置; Step 6 重复 Step 3 到 Step 5 直到分配完所有 钢管． ［算法结束］ 4. 3 实验结果与分析 本文算法采用 Microsoft Visual Studio C# 编程 实现了 CSC 算法的入库优化决策问题测试． 测试环 境为 Pentium4 /1 GHz/512 MB /Windows XP Professional． 根据上述规则，在 600 个数据中分别随机抽取 150、200、250、300、350、400、450、500、550 和 600 根 的钢管对以上设计的算法进行验证，共计 10 组实验 数据，每组实验单独运行 40 次． 将基于聚类的约束 满足算法与改进的经典的 BFD 算法就占用平均垛 位数、垛位平均利用率进行了比较，实验结果见表 1; 同时就入库钢管数不同时所占用的新增垛位数进 行模拟实验 40 次，计算两算法的平均垛位增加数． 实验结果如图 3． 图 3 CSC 算法与 BFD 算法性能比较 Fig． 3 Comparison of the performance of CSC algorithm and BFD algorithm 随机抽取 600 个数据对本文设计的算法进行验 证 40 次，其中垛位编号为 1，2，3，4 的前四个垛位为 初始化后的四个非空垛位，其余垛位都是钢管入库 后新增的垛位． 实验结果见图 4． 采用 CSC 算法，计 算得出只需平均新增 10 个 垛 位，垛 位 利 用 率 为 ·128·
第1期 董广静等：基于聚类一约束满足算法的钢管入库优化决策模型 ·129· 71.43%;而采用BFD算法，则需要平均新增12个 足算法多2个垛位，这在实际库存管理中具有很重 垛位，垛位利用率为68.75%，比基于聚类的约束满 要的实际应用价值. 表1入库钢管数不同的算法比较 Table 1 Comparison of different algorithms for diverse number of steel tubes CSC算法 BFD算法 钢管数 平均垛位数 垛位平均利用率/% 运行时间/s 平均垛位数 垛位平均利用率/% 运行时间/s 150 8.67 3.36 1.570 10.17 2.97 0.0200 200 8.83 33.37 2.340 9.67 28.67 0.0190 250 9.83 40.01 2.985 11.60 36.95 0.0320 300 9.63 50.23 3.407 11.17 45.47 0.0400 350 10.40 49.49 4.740 12.00 47.97 0.0450 400 11.00 57.54 4.986 12.03 48.07 0.0600 450 12.03 60.91 5.367 13.85 54.30 0.0730 500 12.90 68.95 5.803 14.07 58.15 0.0814 550 14.42 70.47 7.940 16.35 61.46 0.1020 600 15.69 78.67 8.002 17.78 65.29 0.2100 及半径、长度属性的松弛约束，而且在扩大各个松弛 50 约束的松弛范围的情况下可以适当地减少垛位堆垛 数、增加垛位的利用率.此外，虽然有个别垛位钢管 40 比较少，但在一般情况下，生产入库和销售是连续进 30 ◆一（算法 行的，这种情况的出现会减弱，不会出现钢管的入库 20 ◆一BFD算法 堆垛停滞问题. (4)在已知入库钢管的各个属性的前提下，CSC 4 6810 1 算法能够准确输出每根钢管具体垛位安排，即钢管 探位编号 的具体垛位编号、层编号和左起编号等信息，这在实 图4CSC算法与BFD算法垛位分布比较 际钢管库存管理中具有很重要的指导意义. Fig.4 Comparison of stack position distribution based on CSC algo- (5)随着问题规模的增大CSC算法的求解时间 rithm and BFD algorithm 相对BFD算法虽然略有增长，但是即使在钢管数目 由以上实验结果可以得到以下结论： 达到600根时，其运算也能在10s之内完成，而且 (1)针对钢管入库优化决策问题设计的CSC算 钢管入库是一种半离线状态下的入库，CSC算法的 法求的垛位数少于BFD算法（表I),而且随着入库 求解时间完全可以满足实际生产的需求. 钢管数的增加，CSC算法占用垛位数的增加量少于 5结论 BFD算法（图3），也就是说，该算法在保证出库效率 的前提下（即零倒垛），实现了垛位的有效利用，CSC 研究了钢管入库优化决策问题，将其归结为一 算法性能优于BFD算法. 类三维装箱的组合优化问题，并将其映射为约束满 (2)随着入库钢管数的增加，CSC算法的垛位 足问题，建立了问题的约束满足模型.针对问题特 平均利用率随之增大：但采用BFD算法得出的垛位 征，给出了垛高的计算策略和钢管堆放规则，并在此 平均利用率递增的速度相比较慢，在数据量比较大 基础上设计了基于聚类的约束满足算法，即CSC算 时（一般认为在一批入库钢管数不小于150根）， 法.算法采用两阶段实现问题求解：在第一阶段通 CSC算法的垛位利用率明显优于BFD算法的垛位 过聚类对入库钢管进行分组：在第二阶段采用约束 利用率，说明该算法在保证垛位上各属性约束的前 满足技术为钢管指派垛位。数据实验结果表明，本 提下，能够增大垛位空间的有效利用. 文提出的CSC算法能够有效减少垛位数，并提高垛 (3)由(1)和(2)可知，CSC算法进行堆垛的结 位利用率及垛位空间利用率，在解决钢管入库优化 果能够很好地满足模型中设置的交货期的紧约束以 决策问题上是可行且有效的，能够满足实际应用的
第 1 期 董广静等: 基于聚类--约束满足算法的钢管入库优化决策模型 71. 43% ; 而采用 BFD 算法，则需要平均新增 12 个 垛位，垛位利用率为 68. 75% ，比基于聚类的约束满 足算法多 2 个垛位，这在实际库存管理中具有很重 要的实际应用价值． 表 1 入库钢管数不同的算法比较 Table 1 Comparison of different algorithms for diverse number of steel tubes 钢管数 CSC 算法 BFD 算法 平均垛位数 垛位平均利用率/% 运行时间/s 平均垛位数 垛位平均利用率/% 运行时间/s 150 8. 67 3. 36 1. 570 10. 17 2. 97 0. 0200 200 8. 83 33. 37 2. 340 9. 67 28. 67 0. 0190 250 9. 83 40. 01 2. 985 11. 60 36. 95 0. 0320 300 9. 63 50. 23 3. 407 11. 17 45. 47 0. 0400 350 10. 40 49. 49 4. 740 12. 00 47. 97 0. 0450 400 11. 00 57. 54 4. 986 12. 03 48. 07 0. 0600 450 12. 03 60. 91 5. 367 13. 85 54. 30 0. 0730 500 12. 90 68. 95 5. 803 14. 07 58. 15 0. 0814 550 14. 42 70. 47 7. 940 16. 35 61. 46 0. 1020 600 15. 69 78. 67 8. 002 17. 78 65. 29 0. 2100 图 4 CSC 算法与 BFD 算法垛位分布比较 Fig． 4 Comparison of stack position distribution based on CSC algorithm and BFD algorithm 由以上实验结果可以得到以下结论: ( 1) 针对钢管入库优化决策问题设计的 CSC 算 法求的垛位数少于 BFD 算法( 表 1) ，而且随着入库 钢管数的增加，CSC 算法占用垛位数的增加量少于 BFD 算法( 图 3) ，也就是说，该算法在保证出库效率 的前提下( 即零倒垛) ，实现了垛位的有效利用，CSC 算法性能优于 BFD 算法． ( 2) 随着入库钢管数的增加，CSC 算法的垛位 平均利用率随之增大; 但采用 BFD 算法得出的垛位 平均利用率递增的速度相比较慢，在数据量比较大 时( 一般认为在一批入库钢管数不小于 150 根) ， CSC 算法的垛位利用率明显优于 BFD 算法的垛位 利用率，说明该算法在保证垛位上各属性约束的前 提下，能够增大垛位空间的有效利用． ( 3) 由( 1) 和( 2) 可知，CSC 算法进行堆垛的结 果能够很好地满足模型中设置的交货期的紧约束以 及半径、长度属性的松弛约束，而且在扩大各个松弛 约束的松弛范围的情况下可以适当地减少垛位堆垛 数、增加垛位的利用率． 此外，虽然有个别垛位钢管 比较少，但在一般情况下，生产入库和销售是连续进 行的，这种情况的出现会减弱，不会出现钢管的入库 堆垛停滞问题． ( 4) 在已知入库钢管的各个属性的前提下，CSC 算法能够准确输出每根钢管具体垛位安排，即钢管 的具体垛位编号、层编号和左起编号等信息，这在实 际钢管库存管理中具有很重要的指导意义． ( 5) 随着问题规模的增大 CSC 算法的求解时间 相对 BFD 算法虽然略有增长，但是即使在钢管数目 达到 600 根时，其运算也能在 10 s 之内完成，而且 钢管入库是一种半离线状态下的入库，CSC 算法的 求解时间完全可以满足实际生产的需求． 5 结论 研究了钢管入库优化决策问题，将其归结为一 类三维装箱的组合优化问题，并将其映射为约束满 足问题，建立了问题的约束满足模型． 针对问题特 征，给出了垛高的计算策略和钢管堆放规则，并在此 基础上设计了基于聚类的约束满足算法，即 CSC 算 法． 算法采用两阶段实现问题求解: 在第一阶段通 过聚类对入库钢管进行分组; 在第二阶段采用约束 满足技术为钢管指派垛位． 数据实验结果表明，本 文提出的 CSC 算法能够有效减少垛位数，并提高垛 位利用率及垛位空间利用率，在解决钢管入库优化 决策问题上是可行且有效的，能够满足实际应用的 ·129·
·130· 北京科技大学学报 第36卷 计算效率.这些内容和成果不但具有实际应用价 [8]Zapfel C,Wasner M.Warchouse sequencing in the steel supply 值，而且为进一步的研究提供了理论基础. chain as a generalized job shop model.Int Prod Econ,2006, 104(2):482 [9]Ren HZ,Tang L X.Study on modelling and optimization method 参考文献 for the slab stack shuffling problem considering area crane capaci- [Atighehchian A,Bijari M,Tarkesh H.A novel hybrid algorithm ty.Acta Autom Sin,2010,36(4)586 for scheduling steel-making continuous casting production.Comput (任会之，唐立新.考虑库区吊机能力的板坯倒垛问题的建模 0 per Res,2009,36(8):2450 与优化方法研究.自动化学报，2010,36(4)：586) 2]Liu S X,Tang J F,Song J H.Orderplanning model and algo- [10]Cheng C C.Smith S F.Applying constraint satisfaction tech- rithm for manufacturing steel sheets.Int J Prod Econ,2006,100 niques to job shop scheduling.Ann Oper Res,1997,70:327 (1):30 01] Zhai Y,Sun X M.A heuristic algorithm for three-dimensional B]Manyem P.Bin packing and covering with longest items at the bot- container loading problem with non-identical items.Shanghai tom:online version.ANZIAM J,2002,43(E):E186 Jiaotong Unin,2007,41 (8):1244 4]Tang L X,Ren H Z.Modelling and a segmented dynamic pro- (翟钰，孙小明.多种物品三维装箱问题的一种启发式算法 gramming-based heuristic approach for the slab stack shuffling 上海交通大学学报，2007,41(8)：1244) problem.Comput Oper Res,2010,37 (2):386 [12]Tang L X,Huang L.Optimal and near-optimal algorithms to roll- [5]Wu Y,Li W,Goh M,et al.Three-timensional bin packing prob- ing batch scheduling for seamless steel tube production.Int lem with variable bin height.Eur JOper Res,2010,202(2):347 Prod Econ,2007,105(2）:357 Hou D L,Chen F R.Constraint satisfaction technology for stac- 13] Cui JS,Li TK.Zhang WX.Hybrid flowshop scheduling model king problem with ordered constraints.Procedia Eng,2012,29: and its genetic algorithm.J Univ Sci Technol Beijing,2005,27 3317 (5):623 Tu X P,Shi C T,Li T K.Model and algorithm for the slab loca- (崔建双，李铁克，张文新.混合流水车间调度模型及其遗 tion optimization decision problem based on fuzzy matching.Unir 传算法.北京科技大学学报，2005,27(5)：623) Sci Technol Beijing,2011,33(3):376 [14]Bartak R,Salido M A,Rossi F.Constraint satisfaction tech- (涂雪平，施灿涛，李铁克.基于模糊匹配的板坯入库优化决 niques in planning and scheduling.J Intell Manuf,2010,21 策问题模型及求解.北京科技大学学报，2011,33(3)：376) (1):5
北 京 科 技 大 学 学 报 第 36 卷 计算效率． 这些内容和成果不但具有实际应用价 值，而且为进一步的研究提供了理论基础． 参 考 文 献 ［1］ Atighehchian A，Bijari M，Tarkesh H． A novel hybrid algorithm for scheduling steel-making continuous casting production． Comput Oper Ｒes，2009，36( 8) : 2450 ［2］ Liu S X，Tang J F，Song J H． Order-planning model and algorithm for manufacturing steel sheets． Int J Prod Econ，2006，100 ( 1) : 30 ［3］ Manyem P． Bin packing and covering with longest items at the bottom: online version． ANZIAM J，2002，43( E) : E186 ［4］ Tang L X，Ｒen H Z． Modelling and a segmented dynamic programming-based heuristic approach for the slab stack shuffling problem． Comput Oper Ｒes，2010，37( 2) : 386 ［5］ Wu Y，Li W，Goh M，et al． Three-dimensional bin packing problem with variable bin height． Eur J Oper Ｒes，2010，202( 2) : 347 ［6］ Hou D L，Chen F Ｒ． Constraint satisfaction technology for stacking problem with ordered constraints． Procedia Eng，2012，29: 3317 ［7］ Tu X P，Shi C T，Li T K． Model and algorithm for the slab location optimization decision problem based on fuzzy matching． J Univ Sci Technol Beijing，2011，33( 3) : 376 ( 涂雪平，施灿涛，李铁克． 基于模糊匹配的板坯入库优化决 策问题模型及求解． 北京科技大学学报，2011，33( 3) : 376) ［8］ Zpfel G，Wasner M． Warehouse sequencing in the steel supply chain as a generalized job shop model． Int J Prod Econ，2006， 104( 2) : 482 ［9］ Ｒen H Z，Tang L X． Study on modelling and optimization method for the slab stack shuffling problem considering area crane capacity． Acta Autom Sin，2010，36( 4) : 586 ( 任会之，唐立新． 考虑库区吊机能力的板坯倒垛问题的建模 与优化方法研究． 自动化学报，2010，36( 4) : 586) ［10］ Cheng C C，Smith S F． Applying constraint satisfaction techniques to job shop scheduling． Ann Oper Ｒes，1997，70: 327 ［11］ Zhai Y，Sun X M． A heuristic algorithm for three-dimensional container loading problem with non-identical items． J Shanghai Jiaotong Univ，2007，41( 8) : 1244 ( 翟钰，孙小明． 多种物品三维装箱问题的一种启发式算法． 上海交通大学学报，2007，41( 8) : 1244) ［12］ Tang L X，Huang L． Optimal and near-optimal algorithms to rolling batch scheduling for seamless steel tube production． Int J Prod Econ，2007，105( 2) : 357 ［13］ Cui J S，Li T K，Zhang W X． Hybrid flowshop scheduling model and its genetic algorithm． J Univ Sci Technol Beijing，2005，27 ( 5) : 623 ( 崔建双，李铁克，张文新． 混合流水车间调度模型及其遗 传算法． 北京科技大学学报，2005，27( 5) : 623) ［14］ Barták Ｒ，Salido M A，Ｒossi F． Constraint satisfaction techniques in planning and scheduling． J Intell Manuf，2010，21 ( 1) : 5 ·130·