论文研究-缓冲区有限的流水车间调度问题的启发式算法.pdf

所需积分/C币:10 2019-09-10 15:06:19 548KB .PDF
10
收藏 收藏
举报

针对缓冲区有限的流水车间调度问题,分析了目标函数的特征,及目标函数与工件空闲时间之间的关系,设计开发了启发式算法。算法将以Makespan为目标函数转化成以最小化机器空闲时间为目标函数,并以此为基础构造初始加工序列,再通过贪婪排序与插入寻优消除缓冲区受限约束并寻找问题的近优解。仿真实验结果表明,算法在求解质量和计算时间方面明显优于其他几种排序规则,并体现了目标函数表达式结构的特性及对解的适应性。
20 2012,48(32) Computer Engineering and Applications计算机工程与应用 图2为更一般的情况,L件从M至Mn加L时3.1构造初始解 的某一加工序列。 从前面的分析可以看出,为使新目标函数 Pn;达到最小,需要两部分均达到最 M234… B 小。首先,通过求∑Pm的最小值以得到工序中的 n=1 B n-In 第一个工件,再以最小化第m阶段空闲时间为日标, 采用从前向后的方式排列其他工件的加工顺序,形 口2B3…=_n 成初始加工序列。 图2m台机器间空闲时间示意图 步骤1计算所有工件从第1阶段到第m阶段的 223目标网数分析 加工时间之和∑P,将此值按照升序排列,若该值 对于Fpm,B≤bC问题,在按照某种排序 规则确定工件加工序列后,由调度结果的甘特图(图2)出现相同情况时,取pa较小的工件排在前列。 可知,对于已经给定的加工序列={ T, Tp 步骤2将步骤1中形成的工件序列作为兀1,取 月标函数Cm可表示为 兀中第1个工件作为种子工序I′中的第一个工件 不考虑缓冲区有限约束,依次取x中的其余工 P,+ max 件分别作为种子工序中的第2个工件a,并计算在 其中,∑4m+表示第m阶段上的相邻两工件,在满第m阶段工件J与2之间的空闲时间d2,取使 d2得最小值的工件作为,x中其余工件的相对 足缓冲区有限约束时产生的空闲时间总和;∑Pmy顺序不变。 表示加工序列Ⅱ中第一个加工工作在各阶段的加工 步骤3考虑缓冲区有限约束,依次计算x屮其 时间之和;∑Pam表示加工序列中除x外其余余工件与J2在第m阶段的空闲时间,取该空闲时间 最小的工件作为其紧后工件加入种子工序Ⅱ, 所有工件在第m阶段的加工时间之和,并且为定值。 n=n+1,循环该过程,直到x1中所有工件都进入种 因此,对问题Fpm.B≤bCm,若以最小化 子工序。 最大完工时间 Makespan为目标函数,则该目标函数 32插入寻优 值与工件加工序列的第一个工件和为满足缓冲区有 限约束而形成的相邻工件之间在第m阶段的空闲时 为了进一步优化目标函数值,在得到初始调度 间相关,即 之后,结合问题的特性,采用插入搜索方法对工件序 列进行调整。 Minimize c分 Minimize∑++∑Pn,(2 步骤4不考虑缓冲区有限约束,对种子工序Ⅱ 中的最后两个工件L=-m分别考虑不同加工顺序 换言之, Minimize∑m+n+∑Pm可视为新的目 所对应的目标函数值 Makespan,取使 Makespan为较 标函数,且可以把第一个工件从第一台机器到第m台机小值的排列顺序作为最终加工序列的排列顺序, 器的加时间之和∑Pa1/作为新目标函数的一个下界 并在以后的排序过程中,保持相对位置不变。 步骤5在工件序列Ⅰ中已经排序工件位置相对 固定的前提下,由后向前,依次将种子工序I中的 3求解算法 工件插入到步骤4所得的已排序工件的所有可能位 通过以上分析可以看出,第m阶段各工件间的置,并计算各位置相对应的目标函数值 Makespan,选 空闲时间及工件序列m中第一个工件J在各阶段择使该值最小的工件位置,并加入到工件序列中 的加工时间之和,对目标函数的好坏起着重要作用,形成新的部分排序,循环该过程,直到所有工件均完 如何解决这两点成为关键。本文提出了由构造及插成插入过程,即得到最终工件序列。 入寻优的迭代方法两大部分组成的CI启发式算法。 CI启发式算法的流程图描述如图3。 于艳辉,李铁克,王柏琳:缓冲区有限的流水车间调度问题的启发式算法 2012,48(32) 开始 4数据实验与分析 通过上述分析可知,NEH与PFE分别是一般流 计算每一个工件的∑P值 水车间调度问题与阻塞流水车间调度问题屮非常重 并按升序排列形成加序列兀 要的启发式算法。将这两种启发式算法扩展到 依据工件间空闲时间调整x中 LBFSS问题中,使其具有缓冲区有限约束,并与本文 工件顺序,使空闲时间最小 提出的αI算法进行比较,以此来说明三种算法对解 生产初始调度方案 的不同的适应性,Cl算法对问题特征的休现及具有 的优越性 中工件顺序使其得最小值|调用通入算法” 本文采用 Matlab语言在CPU主频30GHz、内存 20GB环境下的PC机上实现上述启发式算法。分别 是否满足终止条件 在B1={1,3,5,10}的情况下,采用文献[14]中的Car 系列和文献[15]中的Rc系列共20个算例进行仿 输出调度结果 真。实验结果见表1,其中C”为缓冲区无穷情况下 图3CI算法的流程图 表1不同问題规模下三种算法比较的实验结果 NEH PFE CPU/s b RA Cmax R RE 71210017094001703 70380.0 37038070380 70380 70380 70380 0.03 1070380 70380 70380 0.03 180030.1273810.0372900.02 13,47166 0.03 0.172090.017166 0.04 577400.0871660 7166 074050.0371660 000 0.03 7166 81250. 79 0.0878160.0 0.03378360.0777570.0675950.04 0.03576630.0574310.0275030.03 0.031074930.0274310.0273270 90640.1384230.0583290.04 8003 0.04388470.1182330.0381790.02 0.0484110.05810300180590.01 0.05 82030.0280030 80030 0.04 5200.1086560.1280470.04 10,67720 0.03383030.0880040.0477500 0.02 00.0579520.037 0.02 1079230.0377200 77200 0.13 117940.4417130.3716690.34 Rec0120,51247 0.12317670.4216550.3315410.24 0.15 516440.3216070.2913290.07 016090.2915130.21 0.15 0.2114860.3412160.10 0.16 3390.2113790.2411840.07 Rec0320,5 11090. 513030.1712980.17115 0.04 0.1 1012570.1312050.0911240.01 0.16 116520.3315930.2814130.14 Rec0520,51242014315310.2315090.2113960.12 0.13 5 4330.1514530.1713670.10 0.1810136001013910.12 1330 19790.2617850.1417360.11 Re0720,1015660.22318660.19 17330.1117050.09 0.18 7950.1516970.0816800.07 0.20 1017010.0916360.0416210.04 0.22 118540.2118550.2116520.07 0.19 Rec0920,101537 8310.1917910.1716390. 0.20 517520.1417600.1516070.05 0.21 016900.1017090.1115770.03 22 2012,48(32) Computer Engineering and Applications计算机工程与应用 各问题的最优解,RE为与C"的相对误差,计算公式好的效果,实验结果同时也说明了缓冲区上限及问 为RE=(Cmx-C)C×100% 题规模对解的影响。 41仿真结果 不同问题规模下三种算法比较的实验结果如表参考文献: 1所示。 [1] Hall n G, Sriskandarajah C. A survey of machine sched 42实验分析 uling problems with blocking and no wait in process[JI 根据上述实验结果,可以得到以下结论 Operations Research, 1996, 44(3): 510-525 (1)从整体的目标函数值C来看,CI算法及(2] Dutta s K, Cunningham AASequencing two machine flow- shops with finite intermediate storage. Management Sci- PFE算法的指标值优于NEH算法,这说明在算法结 ence.1975,21:989-996 构方面,CI及PE较NEH更具有优势。原因在于(3]1 Papadimitriou C h, Kanellakis P C Flowshop schedulin NEI是以LrT规则获得初始解,而CI算法及PFE算 with limited temporary storage[J]Journal of the Associa- 法是依据问题的特征设计初始加工序列,并采用插 tion Computing Machine, 1980, 27(3): 533-549 入寻优的迭代方式。但(I算法在初始解的构造上就[4] Reddi ssseqμ lencing with finite intermediate storage 考虑了有限缓冲区的约束及目标函数的需求,相比 Management Science, 1976, 23 之下,PFE算法虽然添加了有限缓冲区的约束条件,[5] Nowicki e. The permutation flowshop with buffer:atbu 但仍然更适合阻塞流水车间调度问题。另一方面, search approach j. European Journal of Operational ro 当问题规模较小时,αI算法相对误差值多次达到零, search,1999,116 说明αI算法相对于较小规模问题能获得较好的近优 6 Qian Bin, Wang Ling, Huang Dexian, et aL. An effective hybrid DE-based algorithm for multi-objective flow 解甚至最优解。 shop scheduling with limited buffers [J]. Computer Op (2)在问题规模相同的情况下,随着缓冲区上限 erations Research, 2009.36: 209-233 值b的増加,三种算法的相对误差值均呈下降趋势 [7] Kholsa IThe scheduling problem where multiple machines 求解效果均有所提高。原因是随着b值增加,相邻机 compete for a common local buffer[J]. European Journal 器间可进入缓冲区等待的工件数越多,使得各阶段 of Operational research, 1995,84: 330-342 中工件间的空闲时间变小,从而使C值变小,这也[8] Norman b a. Scheduling flowshops with finite buffers 说明随着缓冲区上限的增加,有限缓冲区限制对问 and sequence-dependent setup times[J]. Computers In- 题的约束作用逐渐消弱。 dustrial Engincering, 1999, 36(1):163-177 (3)在缓冲区上限值相同时,三种算法的C值1 Iu Shiqiang. ozan EScheduling a now shop wI 随工件数的增加而增大,这说明随着问题规模的扩 combined buffer conditions[J]. International Journal of Production Economics. 2009.117: 371-380 大,问题也越复杂,受规模的影响越明显 [10] Graham R L, Lawler E L, Lenstra J K, et al optimization (4)CI算法具有良好的计算效率,从实验数据中 and approximation in deterministic sequencing and sched 可看出,当问题规模较大时,运算时间也均在0.3秒 uling: a survey [J.Annals of Discrete Mathematics, 1979 之内,能够满足实际运算需求。 5:287-326. [11 Ruiz R, Maroto C A comprehensive review and evaluation 5结语 of permutation flow shop heuristics[J]. European Journal of 在流程工业中,缓冲区有限的流水车间是常见 Operational research, 2005, 165: 479-494 的一类调度问题,仅有两台机器的该问题即是强NP[12] McCormick s t, Pinedo m L, Shenker S, et al. Sequencing 难的,因此需要设计出能够有效求解的启发式算 in an assembly line with blocking to minimize cycle 法。本文针对该问题进行详细研究,分析了空闲时 time].Operations Research, 1989, 37 间与目标函数之间的关系,在此基础上,设计了一种13] Ronconid pa note on constructive heuristics for the flowshop problem with blocking[J]. International Journal 从问题下界出发,以最小化第m阶段空闲时问为目 of Production Economics. 2004.87: 39-48 标的启发式算法,并对算法的性能进行了分析。数 [14 Carlier JOrdonnancements a contraintes disjonctivesJ] 据实验表明,本文提出的CI算法在初始加工序列的 Operations Research, 1978, 12(4): 333-351 设计上更加符合问题的特征,插入寻优使得算法在[15] Reeves c r∧ genetic algorithm for flowshop sequencing 获得的解的质量和计算所需要的时间方面均具有较 Computers and Operations Research, 1995, 22(1): 5-13

...展开详情
试读 5P 论文研究-缓冲区有限的流水车间调度问题的启发式算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744270 如果觉得有用,不妨留言支持一下
2019-09-10
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

    成功上传501个资源即可获取
关注 私信
上传资源赚积分or赚钱
    最新推荐
    论文研究-缓冲区有限的流水车间调度问题的启发式算法.pdf 10积分/C币 立即下载
    1/5
    论文研究-缓冲区有限的流水车间调度问题的启发式算法.pdf第1页

    试读结束, 可继续读1页

    10积分/C币 立即下载 >