论文研究-基于时间槽的敏捷供应链集成调度模型及优化.pdf

所需积分/C币:10 2019-09-20 16:25:28 604KB .PDF
收藏 收藏
举报

论文研究-基于时间槽的敏捷供应链集成调度模型及优化.pdf,  针对市场需求出现后敏捷供应链需要选择各级部件供应商并安排对应的生产运输调度问题,以准时满足市场需求为基本约束,以供应链库存、生产和运输总成本最小为目标函数,建立了基于供应商可用时段时间槽表示方式下的敏捷供应链集成调度INLP模型;基于该模型具有大量的时间和数量约束,设计了以时间槽实数编码作为基因编码的混合遗传算法,在解码过程中引
第2期 王建华,等:基于时间槽的敏捷供应链集成调度模型及优化 285 定义模型的决策变量如下: 1,企业i的第个时间槽被占用 0,否则 1,企业讠的第j个时间槽生产的部件将供应给企业, 0,否则 2.2敏捷供应链集成调度INLP模型 ASCS问题中的成本函数为所有企业生产、库存和运输的总成本,调度优化问题的目标函数为供应链总 成本最小,如式(1) IK I mIn 1=∑∑∑(∑m)-)+∑∑∑ a ikuKo 1 +∑∑[m02m8(e+9g) K 目标函数中石式第一项为供应链库存成本,其中2;=min;(an/m)为企业i的最早开工时间,并令 a=M,M为足够大的正数,20=T,第二项为供应链作业成本,第三项为供应链运输成本因为在问题中 限定∫每个编号的企业只供应一种部件,令p表示企业供应部件的种类,将目标函数简化为式(2) 构建 ASCIs问题的非线性整数规划( integer non- linear planning,INLP)模型如下 目标涵数 nin=∑∑|(Cakk)(an-)+∑∑aye i=1=11j=1 ∑∑ min[ 1. ijyiji' +∑x9vpC =2v=1 约束条件 ∑∑a;s=Q,vk ∑∑别=∑;y TI J ∑∑∑ Nij iji ∑∑xys/k"k,k v=1z=1y=1 max[max(bi;Viji)+min(1,yiji)tiis min(ai/ Tii), Vi max(b;x1)≤T min(1, ai) y (8) mi(1t)2∑,Y, 约束条件(3)-(5)为ASCS间题中的三类总量约束:单类物料总量约束、上下游企业时间槽匹配总量 约東和上下游物料匹配总量约東.单类物料总量约東指第k种物料占用所有能够生产该物料企业的时间槽 总数量要等于Q,如式(3).上下游企业时间槽匹配总量约束指生产第k种物料的下游企业时间槽被占 用数量同Wk的乘积要等于所有生产第k种物料组装件企业的时间槽中用于供应企业v的时间槽数量,令 286 系统工程理论与实践 第31卷 lk=|Wk|表示第k类物料需要的组装件种类,如式(4).上下游物料匹配总量约束指生产下游产品k的所 有企业时间槽被占用总数量同的乘积要等于所有生产k种商品上游组装件企业时间槽被占用总量,如式(5) 约束条件(6)和(7)为 ASCIS问题中的两类时间约束,式(6)约束生产下游物料的企业只有在全部种类 的上游物料送达后方能开始生产,即下游企业的最早开工时间不能早于上游供应企业物料到达的最迟时间, 式(7)约束最终装配企业生产完工时间要不迟于需求的交付时间. 约束条件(⑧)和(9)为 ASCIS问题中的决策变量、输入参数之间的相关关系约束,式(8)约東了决策 变量之问的相关关系,即当企业讠的某时问槽不安排生产,则该时问槽也就不服务于任意企业,如果企业i 的某一时间槽安排了任务,则必然为其设定了一个下游物料接受企业;式(9)约束了决策变量与输入参数之 间的相关关系,即当企业i和企业之间不存在物料供应关系时,则企业也就不会服务于企业v 3混合遗传算法设计 ASCIS问题不仅要确定部件供应商,还要确定供应商处的生产调度安排;不仅要确定上游部件的供应商 及调度、还要确定上上游部件的供应商及其调度;不仅要保证上游调度数量要满足下游企业的需求,而且要 保证上游将部件适时送达下游个业;不仅要考虑生产能力和成本,还需要考虑运输能力和成本.大量的时间 和数量约束,以及部件、供应商、供应商可用调度时段的数量使得 ASCIS优化为复杂的丶P-hard问题.本 文选用遗传算法对模型进行求解,基于 ASCIS问题的时问槽表述方式及其存在的时问和数量约束,引入贪 婪-序解码方法对染色体进行解码,实现在解码过程中即有效的实现了时间和数量约束,形成混合遗传算法 (HGA),保证算法快速收敛至冋题的 Pareto最优解 31算法设计的基本思路 算法设计的思路是为每个时间槽设计唯一的编码,由这些时间槽编码的乱序形成染色体,然后根据时间 槽编码在染色体中的顺序确定调度决策.基本步骤:1)设置模型各项参数,进化代数计数器初始化:g←0; 2)通过时段编码乱序产生初始种群P(⑨y);3)对P(g)中的个体使用基于贪婪算法的序解码方法进行解码 获得个体对应的调度方案及其适应度值,更新最优调度及适应度值;4)使用线性次序交叉LOX算子和逆序 操作INⅤ算子进行交叉和变异操作获得种群P1(g);5)对P1(g)中的个体使用基于贪婪算法的序解码方法进 行解码.获得个体对应的调度方案及其适应度值;6)根据适应度值,使用精英保留策略从种群Po(⑨)和P(⑨g) 中获得下一代种群Po(g+1);7)判断终止条件,若不满足终止条件,则:g=9+1,转至(3);若满足终止条 件,则输出最优调度及其适应度,算法结束 32基于时间槽的编码设计 De jongl提出了遗传算法编码需要参考的两项基本原则:1)有意义积木块编码原则,即应使用能够 易于产生与所求问题相关的,且具有低阶、短定义长度模式的编码方案;2)最小宇符集编码原则,即应使用 能对问题自然表示或描述的最小编码字符集的编码方案. ASCIs问题的决策变量为0-1整数的x和v;, 直接的编码方案是使用二进制编码,但是二进制编码的整个染色体的长度太长,达到∑:=1(+1)J位,而且 染色体对应于解空间的冗余度较大,在解码过程中需要处理大量的约束,将大大降低求解的效率,因此本文 基于信息编码策略设计了问题的可用时间槽编码作为染色休的基因. 时间槽编码为由三部分信息组成的整数值:时间槽序号+企业代码+生产的部件代码.时间槽编码中 部件代码片用的位数pB计使用式(11)确定 pBit= 10ceil(lg K)+1 (11) 即部件所占位数由部件总种类K的长度决定,当K小于10时,占用1位;当K不小于10且小于100时, 占用2位;…企业代码占用的位数cBit由企业总数I的长度决定,规则同部件代码占用位数规则.时间槽 序号处于编码的最前面,不用强制其占用的位数,直接代入时间槽的序号值即可.例如:当 ASCIS问题涉及 的部件种类为15个涉及的企业数量为21个使用编码10101表示企业1的第一个可用时间槽,且企业1 生产部件1;使用编码130304表示企业3的第13个可用时间槽,且企业3生产部件4.整个染色体包含了 每个企业的所有可调度时间槽,其长度为∑:=1J是二进制编码长度的1/(I+1),大幅度地降低了编码的长 度 第2期 王建华,等:基于时间槽的敏捷供应链集成调度模型及优化 287 33基于贪婪-序的HGA解码过程 331贪婪-序解码GSD方法 针对 ASCIS问题的特点和时间槽编码的方式,本文提出对应的贪婪-序解码( greedy- sequence decoding, GS)方法进行染色体解码.贪婪-序解码方法的基本思想是指在使用时间槽编码的遗传算法解码过程中,首 先根据时间槽编码在染色体中岀现的顺序依次确定任务调度的对象企业讠和所能安排的部件类型k,可以获 得企业讠的可用时间槽完工时间集合B={n1,b2,…},第k种部件的下游企业集合N={m1,m2,…}及其 最早开工时问cs;再从企业集合N中按顺序找出对k种部件需求没满足的下游企业诈然后对于任意j,基 于贪婪思想选择表达式e8-(b;+tm)最小的时间槽γ*安排调度,因而确定了决策变量xxy=1,yyt=1; 如果下游企业需要的部件k没能够得到满足,将对染色体施加一个惩罚系数 解码过程通过对时间槽的贪婪选择可以保证获得的调度方案 Makespan最短、库存成本最低,搜索判断 过程实现了上下游企业件物料时间关系约束,惩罚系数处理了上下游物料供应匹配总量约束和物料总量约 束.整个解码过程计算复杂度为O(m2),其中m为所有可用时间槽的数量,因此该解码过程为多项式时间算 法,适合于求解大规模 ASCIS问题 332 GSD-HGA解码过程 根据GSD方法描述具体说明基于GSD方法的HGA解码过程,染色体进行解码并确定调度方苿的基 本步骤如下 步骤1令部件序号k←1; 步骤2以部件k作为输入部件的企业集合为Uk,初始化Uk=⑧,k≠1,U1={0},根据输入参数初始 化企业2的可用时间槽集合B 步骤3从染色体中按顺序提取出部件代码为k的基因片段G,G的位数为L,令基因位序号l←1; 步骤4根据G和Uk安排部件k的调度方案: 步骤4.1令=Uk(1),即取部件k需求企业集合中的第一个企业,令其对部件k的需求量为D 最早需求时间为T 步骤42提取基因G()的企业代码,获得企业i的可用时间槽集合B 步骤43令时间槽序号索引j←1 步骤44判断条件x≠1与b+tn≤T,如果条件成立,则x;=1,3ni=1,D2=D-1,转 步骤4.6;否则,令j=y+1,转步骤45 步骤4.5如果j≤J,转向步骤44;否则转向步骤46: 步骤4.6当D〃=0时,即企业讠需要的部件k已经获得了满足,将谚移出Uk,转向步骤4.7;当 D>0时,令l=l+1,如果l<L,返回步骤4.2,否则表示当前调度解不能完全满足个业对部件k的需 求量,转向步骤4.8进行累积怎罚量 步骤47当Uk≠时,返回步骤41;当Uk=⑧时,令k=k+1,若k≤K返回步骤3,否则解码 结束 步骤48根据D;累积惩罚量P,令k=k-1,若k≤K返回步骙3,否则解码结束; 通过对染色体解码后可以获得各企业动态调度结果集ⅹ,Y和惩罚值P.以及相关输入值计算对应染色 体的适应度函数,进行LOX交叉、ⅠNV变异和精英选择算子操作10 34LOX交叉和INV变异 以两个父代染色体m1=[1010120101301011020220202302021030220302和p2=[102022020230202 1030210101201013010120302]为例,介绍线性次序交叉LOX算子和逆序变异INV算子的计算过程 341线性次序交叉LOX计算 步骤1随机产生两个交叉点,例如:2和5,交换父代交叉点间的片断,得交叉后的子代片段: +D1=***|302021030210101** p2=(***|301011020220202**米 步骤2从原父代染色体中删除从另一父代交叉过来的基因,得到利余基因片段: P1=2010130101102022020220302 288 系统工程理论与实践 第31卷 p2=3020210302101012010120302 步骤3将剩余基因按顺序添到子代对应位置,得到子代染色体 p1=[2010130101302021030210101102022020220302 p2=3020210302|301011020220202101012010120302 342逆序变异INV计算 随机产生两个操作位,例如:2和6,将变异父代(以p1为例)这两个操作位之间的基因逆序排列,形成 新的子代 p1=[101012010130202202021020230101|1030220302] 4算例仿真 41算例描述 偎设市场对产品P1的需求量Q为8套,以当前时刻为时间0,需求时间点为600(时间单位:小时) 图1为产品P1的供应链结构图.图中圆圈内的符号为鄙件代码,鄙件从左向右形成供应关系,例如:生产 单套部件PI需要部件P2和P3各一套;圆圈上的数字为供应链中提供对应部件的供应商代码,例如:企 业2、3均供应部件P2.部件价值向量V={3001500,50,.50,450,300}(单位:元),企业作业周期向量 C={4,5,6,4,6,5,6.6,8,7},企业间的运输时间为:t2,1=11,t3,1=9,t4,1=10,t5,1=11,t6,2=9, l6.3=11,172=6,3=8,l82=12.83=10,l92=7.tq3=8,10.8=10,l109=13.为了表达的简洁性, 所有企业三种费率设定为相同的,即d=0.000c2=0.01,c3=100,c4=0.5.表1为各企业可用时间槽的 起始时刻,时间槽结末时刻为起始时刻加上其作业周期. ASCIS问题需要解决的是以库存成本、生产成本和 运输成本之和为目标函数,为各套产品选择供应商及其生产时间槽的调度方案,最终以JT方式满足市场需 求 图1算例产品供应结构图 表1节点仝业可用调度时问槽起始时刻表(小时) 时间槽123567 9 101112131415 16 企业1592578564560546542533524520506497483474470456452 企业2480475460450445440425410405400385375370355345330 企业3352341325309303292276260254248237226210194188177 企业4455441437433424420416407403394380371357348339335 企业547646045444843743142040939338237637(0364348342336 企业6347342332317307302287282272257252242227212202192 企业7391385374368352341325309303292276270264258247236 企业8364353342326315299293277261255244233227221215199 企业9292279261248230222209201188180167159151143125117 企业10150137124114107100 6353463623 30 4.2算例优化 根据多次实验,设定求解本算例的GSD-HGA进化参数为种群规模 pop-size=50,交叉概率p。=0.5,变 异概率pm=0.6,精英保留数量设定为8,最大进化代数 max gen=400.表2为使用 GSD-HGA和文献[16 第2期 王建华,等:基于时间槽的敏捷供应链集成调度模型及优化 289 的启发式算法JHA对该算例分别进行10次优化计算的结果对比、从表中可以看出, GSD-HGA结果要明显 优于JHA,只是要消耗较多的计算时间.对应于GSD-HGA最优总成本为7170元的遗传进化曲线如图2所 示,算法在进化初期收敛速度非常快,在进化后期能够保持最优解的平稳性,可以看出GSD-HGA对于求解 ASCIS问题具有很好的收敛性和稳定性 表2GSD-IGA与启发式结果比较表 调度成本(元) 均方差计算时间 总成本生产库存运输 (秒) 平均 GSD-HGA723826872455209689 JHA 10133378833143031 235 5 GSD-HGA7170264924402081 最优解 JHA 9253317531772901 900 进化最优解 当代最优解 300 250 进化代数 图2基于GSD-HGA敏捷供应链调度优化曲线 供应链调度总成本为7170元的 Pareto最优调度方案如表3所示,其中各企业相关时间槽单元格中的 数字为该时间槽生产的部件供应给下游企业的编号(最终市场编号为0),例如企业6的第1个时间槽单元 格为2,表示企业6的第1个时间槽被选用,生产的部件供应给企业2,而企业6的第3个时间槽单元格为 空,则调度方案没有选用该时间槽.从3可以看出在供应链相关资源和时间约束前提下,该市场需求的供应 链最优调度方案中各种部件的生产任务对企业时间槽的占用以及上下游的供应关系;对应于该批次需求的部 件1、2、3、5、6分别由家企业进行生产和供应而部件4由两家企业生产和供应,即由企业6向企业2供 应两套和企业7向企业2供应6套;构成的敏捷供应链包括了7家企业,企业3、5和8没有进入该批产品 的供应链中 表3基于GSD-HGA的敏捷供应链 Pareto最优调度方案 时间槽 企业1 企业2 企业4 企业6 201122 3011 4011 501 6011 企业7 企业9 10112229 企业10 9 9 290 系统工程理论与实践 第31卷 5结论 敏捷供应链是能够对市场需求做出快速响应的动态网络,成员之间的决策行为具有很强的相互影响,进 行合理的生产和运输调度可以在准时满足市场需求的前提下有效降低供应链运作成本.本文研究多级供应 链系统为了以J方式满足市场需求,在各可行供应商空闲调度时间糟、供应商之间运输时间、各供应商生 、库存和运输费率等因素既定基础上,为特定的市场需求选择供应商和求解最优调度方案的问题.基于可 用时间槽建立了敏捷供应链集成调度的INLP模型,设计了以供应衔可用时间槽为基因编码,在解码过程中 引入贪婪-序解码方法的混合遗传算法,最后以仿真算例验证了模型和算法对敏捷供应链响应新生需求或者 插单需求进行供应链集成调度具有很强的实用性和有效性 本文假设供应链上下游成员之问为整批直达运输,供应链成员完全保证产品质量和交付时问,而实际供 应链系统中冇在着对特定区域范围的物料进行分批配载运输,以及各企业的产品合格率不完全匹配和交付时 间不及时的现象.对敏捷供应链调度配载联运规则优化以及模糊调度优化冋题叮以作为进一步的硏究方向 参考文献 [I Christopher M, Towill DR. Supply chain migration from lean and functional to agile and customised Supply Chain Management, 2000, 5(1: 206-213 supply chain[J]. Int J Production Economics, 1999, 62: 107-118 d agile manufacturing paradigms in the total 3 Prince J, Kay J M. Combining lean and agile characteristics: Creation of virtual groups by enhanced production fow analysis[]. Int J Production Economics, 2003, 85: 305-318 [4]王英林,戚克涛,张申生.敏捷供应链的XML/EDI集成框架研究].中国机械工程,2003,14(22):1922-1966. Wang Y L, Qi K T, Zhang S S. XML EDI integration framework for agile supply chainJ. China Mechanical ing,2003,14( 1922-1966 Lee Y H. Integrated process planning and scheduling in a supply chain. Computers Industrial Engineering,2008,54:1048-1061 6 Naso D, Surico M. Genetic algorithms for supply-chain scheduling: A case study in the distribution of ready mixed concrete[J. European Journal of Operational Research, 2007, 177: 2069-2099 [7 De Matta R, Miller T Production and inter-facility transportation scheduling for a process industry J. European Journal of operational Research, 2004, 158: 72-88 [8 Chen P Integrating production and transportation scheduling in a make-to-order environment[D. Cornell Uni- versity, 2000 9 Zbayraka M O, Theopisti C P. A flexible and adapt a ble planning and cont rol system for an MTO supply chain systemJ. Robotics and Computer-Integrated Manufacturing. 2006, 22: 557-565 10 GarciaJ M, Lozano S, Canca D. Coordinated scheduling of production and delivery from multiple plants J Robotics and Computer-Integrated Manufacturing, 2004, 20(3): 191-198 11 Hall G, Potts C n. Supply chain scheduling: Batch and deliveryJ. Operations Research, 2003, 51: 566-584 12 Chandra P, Fisher M L. Coordination of production and distribution planning J. European Journal of Opera tional research. 1994. 72: 503-517 ∏13姚建明,周国华.大规模定制模式下供应链计划调度优化分析[].管理科学学报,2003,6(5):58-64. Yao J M, Zhou G H. Analysis of supply chain optimization planning and scheduling in mass customizationJ Journal of Management Sciences in China, 2003, 6(5 ): 58-64 [4姚建明,刘丽文,蒲云.MC模式下供应链动态调度的蚁群寻优分析,J.管理科学学报,2007,10(3):7-14 Yao J m, liu l W, Pu y. Analysis on ants optimization algorithm for supply chain dynamic scheduling in mass customizationJ| Journal of Management Sciences in China, 2007, 10(3):7-14 15 De Jong K A. An analysis of the behavior of a class of genetic adaptive systems[D. University of Michigan, 1975 16 Asano M, Ohta H. a heuristic for job shop scheduling to minimize total weighted tardiness. Computer Industrial Engineering, 2002, 42: 137 147

...展开详情
试读 8P 论文研究-基于时间槽的敏捷供应链集成调度模型及优化.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38743481 欢迎大家使用并留下宝贵意见
2019-09-20
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-基于时间槽的敏捷供应链集成调度模型及优化.pdf 10积分/C币 立即下载
1/8
论文研究-基于时间槽的敏捷供应链集成调度模型及优化.pdf第1页
论文研究-基于时间槽的敏捷供应链集成调度模型及优化.pdf第2页

试读结束, 可继续读1页

10积分/C币 立即下载 >