论文研究-管道工具喷粉线生产调度建模与算法.pdf

所需积分/C币:10 2019-09-20 16:49:59 546KB .PDF
收藏 收藏
举报

论文研究-管道工具喷粉线生产调度建模与算法.pdf,  针对不同品种、不同材质和不同颜色管道工具喷粉生产调度问题, 以生产成本最小化为优化目标, 研究其优化调度方法. 首先, 建立这个问题的混合整数非线性规划模型(MINLP); 其次, 针对该问题设计出相应的贪婪随机自适应搜索算法(GRASP)和遗传算法(GA); 在此基础上, 提出两种算法相集成的GRASP GA算法. 应用生产实例数据分
2350 系统工程理论与实践 第31卷 QR+Qo之内; 3)L:整条链的长度,分成P-P-P3-P4-B-P6-P-P-P1八段,见图1; 4)S∷零件i的特征参数包括零件编号(S1),零件材料(S2),零件颜色(S),对应的链速(S2),相邻零 件的间距(S5); 5)p:零件i的加工时间,即零件讠移动一个零件间距所需时间, ∈ (1) 6)d;:从零件讠到零件j的转换时间,由材料转换时间(d1x)和颜色转换时间(d2)两部分构成;两种 转换时间有可能有部分重合,所以转换时间(d2)的计算如下: 否则, 其中d1和2分别是通过下式计算得到C(S,S3)即从颜色S到S3的喷粉室准备时间 0 d LP-P 否则 P (S,S)+-2,否则 i,j∈N 7)ddz;零件i的交付时间; 8)r;零件i到达喷粉车间的时间 312整数变量 1)V:所有零件计划生产天数集合,假设计划需要m天生产,包括{1,2,…,m}个元素,其中元素i表 示第i天 2)xk和k是0-1整数变量,每天都以虚拟零件0开始加工 1,如果第k天j直接在之后加工 k 0,则 i,∈N,k∈V ,如果讠被分配到第k天加工 yik ∈N,b∈V 0,否则 313连续变量 1)Oks:第k天的实际加班时间 Ok-max(0,qk-Qn),k∈W 其中¢k表示第k天实际生产时间,Bk表示第k天的空走时间,i表示第k天第一个加工的零件 =∑P*3+∑*山+B,B k 1k,k∈V i∈N\{0} N\{0} 否 i∈N\{0} 2)C:零件i的加工完成时间, ∫(K-1)*QR+B C L∈ (6) dn;+p;,否则, 其中K表示被分配在第K天加工,表示零件i的上一个零件,Cn和dn2分别表示零件的上一个零 件的完成时间和零件i的上一个零件到零件i的转换时间:K=∑k*y,n=∑?来xv,i∈N ∈N\{0} 3)D3:零件i的延迟时间, max Cz-dd2),i∈N 4)l;零件讠的库存时间, Ii= max(0, Ci-pi-Ti), iEN 第12期 胡章勇,等:管道工具喷粉线生产调度建模与算法 2351 32喷粉线的数学模型 为了表示每种时间成本,这里使用四个成本参数A,i∈{1,2,3,4},分别表示生产时间成本参数,加班时 间成本参数,延迟时间成本参数和库存时间成本参数.使用上文中所述参数和变量,建立喷粉线调度问题混 合整数非线性规划模型如下: G=M(∑∑∑电,+∑+>)+M∑O+A∑D+A∑ z(9) i∈N ∑ yk=1,i∈N\{0} k∈v ∑=,V∈N\{0},k (11) i∈N h=1.Vk∈V (12) i∈N\{0} qk<Q,Vk∈ (9)式中每个部分代表一种时间成本,而目标方程对应的是总成本第一项代表的是生产时间成本,其中 包括三个子项,转换时问成本,空走时问成本和加工时问成本;其余的三项分别是加班时问成本,延迟时问成 本和库存时间成本.(10)式表示每一个零件只能被分配到某一天生产一次;(11)式表示生产的连续性;(12) 式表示每天生产由虚拟零件开始;(13)式表示每一个的零件实际生产时间都在每天计划工作时间内 本文的喷粉线生产调度问题实质上是以总生产时间、加班时间、延迟时间和库存时间所导致的总成本最 小化为目标的单机序列相关的调度问题46,文献⑨已经证明单机调度问题等价于旅行商问题(TSP)是 NP难问题,所以本文中的喷粉线生产调度问题也是NP难问题.关于单机序列相关准备时间的调度算法的 研究已经很多Ⅳ-6,然而由于喷粉线生产调度问题的生产环境的特殊性,这些算法都不能直接运用,需要针 对研究问题的特点设计更加适用的算法 4算法设计 这里研究并比较了三种算法:1) Gupta和 Smith[提出的贪婪随机自适应搜索算法( greedy randomize adaptive search procedure, GRASP);2) Rubin和 ragatz提出的遗传算法(GA;3)将 GRASP中的贪婪 随机自适应机制引入GA算法中,提出了两者相集成的 GRASP+GA算法 4.Ⅰ贪婪随机自适应搜索算法( GRASP) GRASP是一个应用于组合优化问题求解的启发式算法,分为构造阶段和改进阶段首先,利用贪婪和随 机的方法构造出一个解;然后通过搜索这个解的一些合适的邻域,改进这个解直到得到局部最优解.这个过 程将被重复特定次数,选取当中目标函数值最低的解为最终的解. 41.1构造阶段 利用贪婪随机方法,在保证可行性的情况下,通过每次加入一个零件j到序列S当中,来构造初始解.首 先,利用(9)式,计算未被加入到序列中的零件集合(U)中的所有零件,加入后形成的部分序列S′的优化目 标函数值,C表示零件加入到序列后的部分序列S的优化目标函数值, CTmin和 CTmab分别表示每个 零件加入序列后的优化目标函数值的最小值和最大值;然后,只要符合 n;≤a( CTmin-Cr)+ CTmin,c∈0,1 的所有零件都包含在限制候选集合(RCD)中;最后,随机从BCL中选择一个零件j加入到序列S中,同时 将零件j从U中删除,返回第一步开始下一个零件的选择直到U为空,序列S构造完成.具体步骤如下 Step1计算U中所有零件的优化目标函数值Cr; step2构造一个限制候选集合(RCL); Step3从RCL随机选择出一个零件j加入到当前序列S中,同时将j从U中删除; Step4如果一个解还没构造完成(U非空),返回Step1;否则转到Step5 step5返回构造的解.停止 2352 系统工程理论与实践 第31卷 4.12改进阶段 局部搜索的效率主要依赖于搜索的郐域的结构及产生的机制、初始解和邻域解的评价计算等.这里 根据变邻域搜索(VNS)8,定义了四种适合喷粉线生产调度叫题的邻域空间:1)天内互换搜索,任意交换同 一天的两个零件的位置进行搜索;2)天内插入搜索,将同一天的任意零件插入到任意位置进行搜索;3)跨天 交换搜索任意交换不在同一天的两个零件进行搜索;4)跨天插入搜索,将一天的任意零件插入到其他所有 不同的天当中进行搜索.具体步骤如下 Step1将从构造阶段得到的解作为当前解 step2设 CrEst等于当前解的优化目标函数值;执行天内交换搜索直到得到一个局部最优解,并将局 部最优解设为当前解 Sυ3执行天内插入搜索直到得到一个局部最优解,并将局部最优解设为当前解. Sep4执行跨天交换搜索直到得到一个局部最优解,并将局部最优解设为当前解. Sυ5执行跨天插入搜索直到得到一个局部最优解,并将局部最优解设为当前解. step6如果当前解的优化日标函数值小于 CrEst,返回Step2;否则,停止搜素 4,2遗传算法(GA) 42.1种群规模 种群规模NP=100.通过反复实验,综合计算效果和计算效率,确定最合适的种群规模为100 422编码 用零件编号{0,1,2,…,m}组成的序列代表一个调度方案(染色体x) 423选择 在设计适应于喷粉线生产调度问题的遗传算法时利用排序选择的方法啊选择进入交叉变异的父代所 有的群休按总成本从大到小排序,也就是所有的群休从差到好排列,然后每个群休被选择的概率也就可以按 照群体的排序来计算了.利用排序选择的方法可以通过调节参数来防止遗传算法过快收敛,过早失去进化能 力 424交叉 这里参考Gupa和Sni1为单机序列相关准备时间问题提出的贵传算法中的交叉操作首先,将所 有的零件分为两个子集, Group1和 Group2:然后将两个父代 Mother和 Father,分别按原相对顺序分解为 两个子集M1和M2,F1和F2;最后组合两个父代分解得到的四个子集,共有四种组合方式(MF1,MF2 M2F1,M2F2),再将每种组合方式分别按照两个父代中子集的位置顺序进行排列.这样就得到了8个子代, 其中有两个是父代,6个是新染色体.为了防止近亲繁殖,从8个子代中随机选取2个子代进入下代.通过实 验分析,父叉的概率P=80%时所得的结果最好. 4.25变异 变异操作将染色体看作一个整体所以变异的概率即每个染色体是否发生变异操作的概率.这里参照G- pta和 Smith遗传算法中的变异操作,将变异过程定义为:可换任意一对会改进目标函数值的零件,直到 得到一个局部最优解.试验表明本研究中变异比率定为Pn=1%结果最好. 426新的染色体的引入 通过将随机产生的新的染色体引入到每个新的一代,有利于保持群体的多样性.当每代引入Ⅰ-10%比 例的新的染色体时,最终得到的结果会明显比没有引入的情况要好 427精英保存 在遗传算法中,加入了精英保存原则,即将当前最优解总是保存在遗传种群中 428惟一性 在每一代中,有可能会出现重复的染色体,删除重复染色体,保持种群的惟一性,有利于提高种群的多样 性和进化能力 4.3贪婪随机自适应搜索算法与遗传算法相集成 GRASP+GA算法 由于贪梦随机自适应搜索算法( GRASP)和遗传算法(GA)各有优缺点: GRASP贪婪随机自适应构造 过程,与GA的初始种群随机产生的方式相比考虑了问题本身的特征,而且 GRASP的搜索阶段所采用的变 邻域搜索(VNS)比GA的交叉和变异的搜索强度更高;但是 GRASP的每次迭代都是没有记忆性的,而GA 第12期 胡章勇,等:管道工具喷粉线生产调度建模与算法 2353 的每一代都是在不断进化的,不断得到更好的解.所以,本文应用GA的框架,引入 GRASP的思想,提出 GRASP和GA相集成的 GRASP+GA算法,具体步骤如下 step1算法初始化:设定最大代数Na,种群规模Nn=100,交叉概P=80%,变异概率Pn=0.5%, 每代引入新的随机染色体的比率7=10% Step2利用 GRASP中贪婪随机构造解的方法,构造含Np个染色体的初始种群P,并计算每个染色 体x的适应值 Step3重复下面的过程有到达到代数上限 Step3.1初始化下一代种群为一个空集(P1-o),然后将当前最优解加入到P1中 Step32重复下面的过程,直到下一代种群的数目达到Np(|P1|=Np) step3.2.1利用排序选择的方法随机选择两个父代x,y∈P0 Stcp322以Pe的概率,对x和y进行交叉操作,产生8个新的染色体,随机从中选择两个染色体替 代 Step323以Pm的概率分别对x,y进行变异操作,利用 GRASP改进阶段的变邻域搜索的方法,搜 索染色体的天内互换邻域、天内插入邻域、跨天互换邻域和跨天插入邻域直到得到一个局部最优解 Step32.4将和y加入到P,删除P1中重复的染色体 Step325如果P1中染色体数目大于Np(P1>Np),则从最近加入的两个染色体中随机选择一个染 色体删除 Step33检查P中有没有优于当前最优解的染色体,并相应更新当前最优解. Step34计算P1中每个染色体的适应度 Step35利用 GRASP的贪婪随机构造方法构造Ⅰ*NP个新的染色体,替代相应数量的P1中适应度 最差的染色体,并计算这些新的染色体的适应度 Step3.6用P来替代P1. step4返回当前最优解及其优化目标函数值,结束 5实证分析 实证分析利用上文提到的某管道工具公司的实际生产数据,来验证 MINLP模型的有效性,并比较人工 调度方法(Man),贪婪随机自适应搜索算法( GRASP),遗传算法(GA)和 GRASP+GA集成算法的计算效 果.实证数据共有8周数据,每周为一个实例,每个实例包含50到200个零件 该公司原有的人工调度方法是以周计划为基础,按照不同产品或订单时间上的紧迫性和同类型零件合并 生产的原则,来规划零件生产顺序.该方法的调度结果来自企业,在表1中表示为Man 表1Man, GRASP,GA和 GRASP+GA算法的比较 计算结果 计算时间(s) 实例 Man Grasp ga GG g&p2 g&a Grasp ga GG g&p2 g&a3 2868595305 55605326 0.4%4.2% 91050271022.0%-41.4.% 7887681611517204145199.9.%15.6 27981200142449.1%-18.7% 2345678 17445 4102 425740451.4% 5.0% 431 16325840.1% 58.3% 257363162 0231001.9%6.1% 30643421.5%-41.8% 180955556459245534 % 6% 41046944.1% 14.4% 423354847499748150.7%3.6% 700 42233851.7%19.9% 5583 2366 259323660.0%88% 33 13013412.5% 3.1% 7027 2834 304727981.3%8.2% 18620428.4%9.7% 平均1693395537586053134.0%9.3% 841 11549641.2%19.6% 1.GG: GRASP+GA算法:2.G&P: GRASP+GA算法和 GRASP的比较; 3.G&A: GRASP+GA算法和GA的比较 GRASP,GA和 GRASP-GA算法都是在Ⅴ isual studio2008平台上利用C#语言编程实现,在P42.8 GHZ和1GRAM的计算机上运行的,计算结果和计算时间如表1.“计算结果”表示不同算法计算得到优 2354 系统工程理论与实践 第31卷 化目标函数值及 GRASP+GA算法相对其他两种算法的改进比率;“计算时间表示不同算法的计算时间及 GRASP+GA算法相对其他两种算法计算时间缩短的比率,单位为秒;这里正值表示 GRASP+GA优于其他 算法的比率,负值表示 GRASP+GA劣于其他算法的比率从表1数据可知 1)所有的实例中, GRASP,GA和 GRASP-GA的计算结果都远好于人工调度方法(Man),这说明通过 建模和算法求解的必要性和优越性 2)绝大部分实例中, GRASP+GA算法的计算结果优于 GRASP,只有实例1中比 GRASP差0.4%以 及实例7两者计算结果中一样;所有实例中, GRASP+GA算法的计算时问都比 GRASP短很多 3)所有实例中, GRASP+CA算法的计算结果都优于GA;绝大部分实例中, GRASP+GA算法的计算 时间都比GA长只有实例6中比GA时间短19.9% 4)总的来说,(RASP+GA算法的计算结果平均分别比 GRASP和GA好40%和9.3%,但是 GRASP+ GA算法的计算时间平均比GA长19.6%,比 GRASP短412%.所以综合来说 GRASP+GA算法要优于 GRASP和GA 6结论 研究了管道工具生产中喷粉线生产调度问题.结合现实生产约束,建立了这个问题混合整数非线性规划 模型.由于此问题是一个\P难问题,为了得到一个满意的解,本文分别设计了相应的贪婪随机自适应搜索算 法( GRASP)和遗传算法(GA),并将 GRASP的贪婪随机自适应的构造过程和变邻域搜索思想引入到GA 算法中,提岀两者相集成的 GRASP+GA算法.通过生产实际数据分析计算的结果和比较,证明∫所建立的 模型的正确性和 GRASP+GA算法的有效性 参考文献 1 Tang L X, Wang X P. A predictive reactive scheduling method for color-coating production in steel industry J International Journal of Advanced Manufacturing Technology, 2008, 35: 633-645 2 Tang L X, Wang X P, Liu J Y. Color-coating production scheduling for coils in inventory in steel industry[J IEEE Transaction on Automation Scicncc and Enginccring, 2008(5 ): 544-549 3 Tang L X, Wang X P Simultaneously scheduling multiple turns for steel color-coating production[J. European Journal of Operational research, 2009, 198: 715-725 Tan K C, Narasimhan R, Rubin P A, et al. A comparison of four methods for minimizing total tardiness on a single processor with sequence dependent setup times[]. The International Journal of Management Science, 2000,28:313-325. 5 Gupta s R, Smith J s. An algorithms for single machine total tardiness scheduling with sequence dependent setups[J. Europcan Journal of Operational Rescarch, 2006, 175: 722-739 6 Rubin P A, Ragatz G L Scheduling in a sequence dependent setup environment with genetic search J. Computers and Operations Research, 1995, 22: 85-99 7 Resende M G, Ribeiro CC. Handbook of Meta-heuristics, International Series in Operations Research and Management Science[M. New York: Kluwer Academic Publishers, 2003: 219-249 8 Mladenovic N, Hansen P Variable neighborhood search[J. Computers and Operations Research, 1997, 24: 1097 1100 9 Du J, Leung J Y T. Minimizing total tardiness on one machine is NP-hardJ. Mathematics of Operations Research,1990,15:483-495

...展开详情
试读 7P 论文研究-管道工具喷粉线生产调度建模与算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744207 如果觉得有用,不妨留言支持一下
2019-09-20
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-管道工具喷粉线生产调度建模与算法.pdf 10积分/C币 立即下载
1/7
论文研究-管道工具喷粉线生产调度建模与算法.pdf第1页
论文研究-管道工具喷粉线生产调度建模与算法.pdf第2页

试读结束, 可继续读1页

10积分/C币 立即下载 >