基于约束满足的板坯设计模型与求解方法1

辽宁工业大学汽车与交通工程学院大学生创新专业论文1基于约束满足的板坯设计模型与求解方法作者：张晶晶，指导教师：金辉(辽宁工业大学汽车与交通工程学院，辽宁锦州121001)摘要：针对客户订单的重量需求为固定值、客户订单分配过程中有最小重量限制的板坯设计问题,建立了以最小化板坯数量为目标的约束满足模型.通过三划分问题的多项式归结,证明了该问题是强NP难的;针对问题的特殊性质,给出了变量选择策略和值选择策略;提出了基于约束满足技术的求解算法,并证明了算法的收敛性;通过数据实验对算法的有效性进行了验证.关键词：热轧;板坯;生产计划;约束满足;变量选择;值选择在强烈市场竞争的压力下，钢铁企业必须制定优质的设计方案，钢铁设计是钢铁企业生产计划管理中的关键环节，在生产计划的制定过程中通常先将客户订单分配到板坯中，建立客户订单与板坯的关系，然后由板坯组成炉次，有炉次组成浇次，最后通过板坯的对应关系协调浇次与轧制单元的衔接，可见板坯设计是整个生产组织过程中的先行环节，是将客户订单与与生产过程连接起来的关键之所在。板坯设计问题就是针对给定的订单需求，在满足工艺限制的前提下生产出成本最低的板坯集合。使企业有最高的生产效益。1问题分析和约束满足模型1.1问题描述钢铁企业的热轧板生产包括炼钢、连铸和热轧三个主要工艺环节，在其生产组织过程中，板坯是衔接这些环节的物流单元，也是将客户需求和工艺要求统一起来的关键所在。在面向订单的生产模式中，一块板坯中可以包括多个订单，一个订单也可以被分配到多块板坯中加工生产。通常板坯设计的目标是用尽可能少的板坯数给定的客户订单，从而达到客户需求余材的最小化，同时也有利于生产计划与调度的优化管理。本文要研究的问题是在板坯量一定，且合同所需的各种钢板重量已知的条件下，求解用哪种板坯生产哪种钢板，用量多少，以降低板坯库存，提高交货水平，以使企业获取最大的生产效益。1.2约束满足模型1.2.1基本假设（1）不同出钢记号、厚度及宽度的板坯看作不同种类的板坯；（2）具有不同宽度范围、厚度范围和钢级的钢板看作不同种类的钢板；（3）用于生产某种产品的每一种板坯又具有不同的成材率；（4）某种板坯在库中存放有一定的费用；（5）计划期内生产的钢板不能完全满足客户的需求；（6）未满足需求有一定的惩罚费用；（7）生产的几种钢板在一台轧机上轧制，生产过程中有一定的调整时间（轧机换辊时间）；（8）用不同的板坯轧制不同的钢板时有一定的调整费用。同一种板坯生产同一种钢板时，每隔一段时间也要进行一次调整。假设调整费用系数及调整时间均与轧制时间成正比。1.2.2目标函数PCYXDSCXIPRYXdPYXjjkjkkjjtotalkkjkjkkjkjkjkjkjjkjkkjkjMaxMax)()(/)])[(..辽宁工业大学汽车与交通工程学院大学生创新专业论文2PCYXDSCXIPRYXdPYXjjkjkkjjtotalkkjkjkkjkjkjkjkjjkjkkjkjMaxMax)()(/)])[(..该式是模型的目标函数，即最大化效益。其中，第一项是产品的生产(销售)收入；第二项为调整费用，调整时的调整费用用一个固定的费用项来表示；第三项为剩余板坯存储费用；最后一项是钢板未满足需求惩罚费用。1.2.3约束条件产品组合约束01,1,1YXYXjkkjkjkkjkjjj=1,2,…,N-1(1)材料的供应限制约束IXkjkjk=1,2,…,M(2)需求约束jkjkkjDYXj=1,2,…,N(3)时间约束TPRYXekjkjkjkjkj/)1((4)非负约束0Xkjk=1,2，…，N(5)式（1）是产品组合约束，即生产的产品必须等于总产品的某个固定比例。式（3）是每一种输入材料的供应限制。式（4）表示轧机产量不一定满足需求。式（5）表明获得产品的时间是有限制的。式（6）是非负约束。1.2.4符号说明Ik——第k种板坯库存总量；SCk——第k种板坯的单位库存保管成本；D——总的钢板需求量；j——第j种钢板需求量占总需求量的比率；Pj——第j种钢板的单位价格；PCj——第j种为满足需求钢板的单位惩罚成本；Ykj——用第k种库存板坯生产第j种钢板的成材率；PRkj——用第k种库存板坯生产第j种钢板的生产速率；Xkj——生产第j种产品所用的第k种库存板坯的数量；T——生产时间总和；Dkj——用第k种板坯生产第j种钢板时轧机的调整费用系数；ekj——用第k种板坯生产第j种钢板时轧机的调整时间系数；2数值算例在实际生产中存在各种可能的输入板坯和输出钢板。在此以五种输入板坯和五种输出钢板为例计算。决策时间长度（计划期）：100天总产品需求（Dtotal）:400吨。产品信息及相关数据见表1-表6。辽宁工业大学汽车与交通工程学院大学生创新专业论文3表1.产品信息表2.输入材料信息表3.成材率(Ykj)产品（j）1234产品组合（j）0.150.270.20.25价格(Pj)2800200022003500过剩惩罚成本（PCj）725620525550板坯（k）12345单位保管成本（j）710720830650600库存量(Pj)13013014010090Ykjj=1j=2j=3j=4K=10.920.900.8K=20.980.930.890K=30.9500.890.97K=400.9200.96K=5000.990.86辽宁工业大学汽车与交通工程学院大学生创新专业论文44.生产速度表（PRkj）表5.调整费用系数(dkj)PRkjj=1j=2j=3j=4K=16062090K=26593780K=34407775K=4070088K=5006363dkjj=1j=2j=3j=4K=1300200300150K=2150200300170K=3350250370240K=4170210240370K=5260300270320辽宁工业大学汽车与交通工程学院大学生创新专业论文5表6.调整时间系数（ekj）目标函数模型是线性规划模型，用LINGO编程求解，结果见表7.表7.求解结果ekjj=1j=2j=3j=4K=12113K=21122K=33211K=41233K=52213Xkjj=1j=2j=3j=4K=1048.93197081.06803K=261.2244968.7755100K=3000140.0000K=4000100.0000K=50080.808089.191919最优值1624068.13辽宁工业大学汽车与交通工程学院大学生创新专业论文6通过模型求解可以得出，在所给的算例中，分别用48.93197、81.06803吨的第一种板坯生产第二、四种钢板；分别用61.22449、68.77551吨的第二种板坯生产第一、二种钢板。分别用140吨的第三种板坯生产第四种钢板。分别用100吨的第四种板坯生产第四种钢板。分别用80.80808、9.191919的第五种板坯生产第四种钢板，可使企业获最大收益1624068.13元.3.结论:在钢铁企业的生产过程中，板坯是衔接各个关键工序的物流单元，也是将客户需求和工艺要求统一起来的关键所在，合理的板坯设计对提高生产效率起着重要的作用．本文建立了以最大化生产效益为目标的约束满足模型;进而，结合问题的特殊性质提出了基于约束满足的求解算法，本文所研究的就是根据最新的销售和订货情况，利用现有库存板坯数量，确定最优的板坯分配模型，以使企业提高生产效率，降低生产成本，改善客户服务，获得最大的收益，从而提高企业核心竞争力。参考文献：[1]夏杰生.注重关键技术开发加速整体工艺优化[N].中国冶金报,2005年6月9日.[2]康永林,傅杰.关于薄板坯连铸连轧产品开发问题的探讨[J].中国冶金,2004年第6期.[3]席阳,李铁克.针对固定重量板坯的板坯设计优化算法[J].北京科技大学学报,2008,30(10):11-79.[4]孙树慧,肖拥军,李铁克.基于约束满足方法求解热轧带钢库存匹配问题[J].北京科技大学学报,2008,30(6):6-80.辽宁工业大学汽车与交通工程学院大学生创新专业论文7