联系我们

Contact

安徽智浩钢结构工程有限公司
电话:15209809766 
联系人:卢经理
地址:安徽省六安市裕安区城南镇汪家行村
网址:laxygs.com
当前位置:首页> 行业资讯

求解有限等待时间的两阶段流水车间调度问题的启发式算法

* 来源: * 作者: * 发表时间: 2019-06-25 0:47:48 * 浏览: 9
(1。北京科技大学东陵经济管理学院,北京100083; 2.教育部钢铁制造执行系统技术工程研究中心,北京100083)本文分析了这个问题与一般两阶段流水车间调度和两阶段流水车间调度无需等待的关系。给出了两类特殊问题的多项式求解方法,并讨论了工件序列的最优序列。在此基础上,设计了一种基于置换排序的启发式算法。该算法使用Gilmore~Gomory启发式生成初始序列,构建一组备选调度解决方案以实现迭代优化,并使用工件序列特征调整工件的顺序以优化当前调度。 。通过理论上分析算法的求解性能,即S是F2ICmax问题的任何可行解,那么在F2 || Cmax中必须存在与S具有相同工件序列的解S',并且存在C-腿(3)Cmax(S')。可以看出,Cmax(OPT)表示F2IWi矣al问题的最佳值,并且Cmax(trd)表示相应的F2 || Cmax问题的最佳值,并且两者都满足Cmax(OPT)Cmax(trd)。 ICmax调度解决方案对应图上述分析表明,F2ICmax的最优值不小于Cmax(trd),ICmax问题是通过1954年提出的内部计算得到的。任意排列的排序解是最优调度,并且是最优的。值为:证明:7表示当满足条件0a ICmax的排序解时,有两种情况如图所示。如果A,第一台机器M1没有空转时间,两级之间任何工件的等待时间为零,那么M1上的所有工件和M2 J1上的最后一个完工件= a(。= 1,... ,n-1),因此C1矣2,即M2将不会产生空闲。此时,M1上工件J和M2上的所有工件构成了调度的关键路径。 (1)你的2启发式算法IWi矣alCmax有一个多项式解。特殊情况,但其标准问题是强NP很难,基于置换排序的启发式方法是一种有效的解决方案。因此,本文对问题的解决方案空间进行了分类,该解决方案空间基于可更换的集合。 RSS(基于ReplaceableSet的basedScheduling)算法的基本思想是:(1)尽可能好地生成一系列初始伪像,(2)构造一组可替换的当前调度解,并在集合中找到更好的解。 2.1当初始序列Wi矣alCmax的等待时间的上限为零时,它是两阶段流水车间调度F2InwtlCmax。显然,F2InwtlCmax问题的最优解是相应问题F2IWialCmax的可行解。因此,令Cmax(Ni t)表示F2InwtICmax问题的最佳值,然后在F2I和相应的无等待调度问题之间满足CmaJOPT)矣Cmax(nwt),如图所示。 IWi矣aICmax问题的最佳值始终不小于F2InWtICmax的最佳值,即Cmax。因此,当CmJtrd)时,必须有= CmaXUWt)= Cmax(trd),也就是说,在这种情况下,F2InWtlCmax问题的最佳Makespan值和最佳工件序列是F2IW矣aICmra的最佳值。问题,分别。最佳序列。例如,F2 = Cmax(trd)的条件,其最佳工件序列无需等待也是原始问题的最佳序列。 InWtICmax的最优调度对于解决F2ICmra问题具有重要的参考价值,而F2I-tGomory算法在O(nlgn)时间内获得3。因此,RSS算法使用Gilmore~Gomoiy算法生成初始工件序列。 2.2 Cmax问题的多项式最优算法可以用集合代替,而无需等待的约束是等待时间有限的极端情况。因此,在等待时间的约束紧张的情况下,初始解决方案接近最优解决方案。然而,当放宽等待时间的上限时,初始解和最优解之间的偏差增加,这需要进一步优化初始解。为此,RSS算法构造了一个alt针对特定工件的外部调度集,定义如下:定义1:与调度解决方案S中的位置不同的所有调度解决方案集,以及其他工件的顺序相同对于S的备选-1调度解决方案丨,可以通过以下方法确定:= SXJJ,k = 1,k。是S,k的位置,意思是插入S-On的第k个位置,得到新的调度解= k + 1,如果k矣n,则转到步骤(2),否则输出fiep = / S. J1的替代调度集是:RSS算法的搜索过程依赖性在工件序​​列的初始解中,具体策略是:在每次迭代中,根据工件序列S =从初始解得到的/ 1,...,/ H,确定当前最佳调度解Si可以相对于8替换。在集合中,搜索目标值优于Si的调度解,其中i是当前迭代次数(i在搜索过程中计算给定工件序列的目标值Cmax时,为了满足等待时间限制的约束,当等待时间超过上限时,它可以在工件中,延迟通过延迟M1的开始时间来解决。基于此思想,为了进一步指导算法的优化过程,本文讨论了F2I矣alCmax最佳工件序列的工件优先级关系(DR)。定理3:对于F2I矣aICmra问题,如果两个相邻的工件Ji,J的处理时间处于非递增或非递减序列,即,如果满足7矣矣2或Pi2p2,则存在最佳调度,其中相邻工件Ji和J在两台机器上的处理顺序相同和先于J. Proof:Ji,J被称为相邻工件,有两种情况,其中Ji和J在两台机器上的订单相同且订单相同。对于这两种情况,如果存在最多的最佳调度,则调整原始调度中的相邻工件Ji和J,使得两台机器上的处理顺序相同,并且在J之前处理Ji。如果此调整不增加目标函数的值,定理证明(1)情况1:在最优调度中,Si,Ji和Jj是相邻的工件,但两台机器的加工顺序不同。进一步分为以下两种情况:Jj,M2按相反顺序排列。类情况,由7确定可以知道当矣,+,交换时,M2上的位置不会延迟后续工件的开始时间。 M1上的Ji和J的处理顺序是Jj-Ji,M2上的顺序是相反的。在这种情况下,7的定理6表明当+ 2时,Ji被交换,并且M1上的位置不延迟后续工件的开始时间。 P2可以满足上述条件。换句话说,对于情况1,如果矣P1矣矣p2或Pi1P1Pi2p2,则原始时间表中的相邻工件Ji和J.在两台机器上以相同的顺序处理,并且在J.之前处理Ji,并且目标价值没有增加。情况2:最优秀的调度S:中等Ji和J.是相邻的工件,两台机器的处理顺序相同,并且J.在Ji之前处理。在不失一般性的情况下,假设在M1和M2上的J.和M2之前的工件分别是人和Jh。下面将说明Ji和J的顺序不会增加目标值。根据5中给出的完成时间的计算方法,对于J.,存在:Ji和J的交换的处理顺序获得新的时间表S3。设J.在S3中的完成时间与CyC类似:显然,如果满足C Ci Ci1和C'.2矣Ci2,则两个工件的交换不会延迟后续工件的开始时间。为了便于描述,在下文中,使用表1左侧给出的符号代替Ci1,Ci2,C'.1,C'.2,即Ci1(t),Ci2(t) C'.1(t),C'.2(t)分别表示与完成时间对应的第t项,并得出以下结论。表1符号对应表当1矣P1矣凡2矣P2时,有:1交换S2 Ji和J.处理顺序不增加目标值。综上所述,如果两个相邻的工件姬,。处理时间根据1,1,2递增或递减,和P2,即如果满足1矣P1矣凡2矣P2或1P1凡2P2,则存在最佳调度,以便两台机器上的相邻工件Ji处理顺序与J.相同并且处理Ji在J.在ICmax问题得到验证之后,包括排名。可以看出,对于任何分类的分类解决方案,如果两个相邻的工件Ji,J满足定理3的条件并且J.在Ji之前被处理,则交换两个工件的顺序可以优化原始的调度解。基于该属性,可以进一步改进RSS算法的初始解决方案和优化过程:迭代优化后的最终调度解决方案,相邻两个工件J的处理时间关系依次确定,右,1,1 ,1,2,2 Wang递增或递减序列,然后在S,S,Ji的位置交换J,...,/,满足Jk-1和pS'i。 +1位置,生成工件子序列S-一= k。,转到步骤2d,否则,将8插入S-的第k个位置,合并到S'i关于宽可替换集合,表示为fle / S'i,VIII )k,计算工件序列fcy(S'i,/ B)k的完成时间和目标值k矣n,并转移Step3调整S *的相邻工件的顺序,计算S * C的目标值:ax,转P,2'父改变S,k-1中7 * J的位置,转到Step3b,否则,返回调用语句。从算法步骤可以看出,Step1a的计算时间为O(nlgn),Step1b调用Step3调整相邻工件的顺序的复杂度为O(n),Step1c的复杂度为: Step1为n-1,每次迭代使用O(n),因此内循环时间为O(n2),因为外循环执行n次,循环体复杂度为O(n3),Step2f进一步调用Step3调整工件顺序,并计算完成时间。 (n),因此Step2的复杂度为O(n3)。总之,RSS算法的时间复杂度取决于步骤2的计算时间,即O(n3)。 2.5算法性能分析ICmax问题,设置集P = = 1,... = 1,并按p的顺序排序。令pk表示集合P中的第k个元素(1首先给出下界误差率的定义。差异比率是调度解决方案S的目标值。显然,D(S)的值较小,表示调度。解决方案S越接近最优解,解决方案的质量越好。对于本文提出的RSS算法,根据定理4,下界误差率可以测量调度解的质量,但它不能反映算法解决方案质量的稳定性,即算法。在大多数情况下,我们可以得到满意的解决方案。为此,本文提出了另一个指标,即上限覆盖概率。定义3:为了求解F2Iw,aICmax问题的近似算法A是由它获得的调度解的目标。值落在CmaxUwt内的概率称为算法A的上界覆盖概率,表示为P(A):1。显然,P(A)的值越大,算法得到的概率越大。接近最优解或甚至最优解。解决方案越大,算法解决方案的质量稳定性越强。 3.2实验环境和数据为了进一步检查问题的性质并验证RSS算法的有效性,进行了以下数据实验。在实验中,将RSS算法与以下四种算法进行了比较:约翰逊规则。也就是说,Johnson规则用于生成过程歹丨J,并且计算满足等待时间限制的工件完成时间,并且生成最终调度方案。 Ham,1983年提出,目前是最小化Makespan的一般流水车间调度问题的最佳排序规则。 NEH-1算法通过NEH算法获得工件序列而不考虑等待时间限制,并计算每个工件的完成时间。 NEH-!算法。 NEH-!在工件插入操作中,算法计算满足等待时间约束约束的部分处理持续时间,并选择最佳工件序列以生成调度解算离子。 7. SDD(SmallerDifferenceDegreefirst)算法以连续加工具有相似加工时间的工件的思想为指导。方法如下:首先选择一个工件,然后选择差值最小的工件S = Ip.1-丨作为紧凑加工。工件。通过将每个工件处理为第一工件,在所获得的n个调度解中获得最佳工件。数据实验比较了上述五种算法的下界误差率和上界覆盖概率。同时,为了测试本文提出的上下界的紧密性,实验还测试了PCPentium4 /CPU3.0GHz / RAM1.0G中上限和下限n:C语言的比例。编程实现5种算法。考虑到影响算法的主要因素是问题的规模,等待时间约束的紧密程度以及处理时间的分布,实验参数设置如下:(1)工件数n = 20, 30,40,50,60,70,80,(2)等待时间的上限为10,20,40,(3)处理时间为P.e30,0,根据统一随机生成分配。根据工件数和等待时间的上限,使用不同的值将实验分成7×5 = 35组,每组随机生成50个实例进行实验。实验结果显示为= 1,因此该项目未在表格中列出。 3.3实验结果分析(1)对于算法的质量,从表2可以看出,RSS算法的两个指标明显优于其他算法,下界误差率达到0几次,表明此时获得RSS算法。解决问题的最佳方案。另外,随着等待时间的上限增加,NEH-!该算法的解决方案效果得到显着改善。两表2实验结果注:CPU是指RSS算法的计算时间。该指标与RSS算法基本相同。约翰逊规则是最糟糕的。当工件数量超过40时,解决方案大于问题的上限。 (2)当问题大小n相同时,随着等待时间的上限a增加,五种算法的下限误差率减小,并且上限覆盖概率增加。这表明等待时间上限的放宽将失去对越来越多的调度解决方案的约束力,因此RSS算法的下限误差与NEH4算法的比率将看起来为零。这也从侧面解释了本文的下限很紧张。 (3)当等待时间上限a相同时,约翰逊规则的下限误差与NEH4算法的比率随着工件数n的增加而显着增加。这是因为算法的工件布置针对的是一般两级流水车间调度问题的特征,这显然受到问题规模的影响。实际上,工件数量的增加有助于减少有限延迟的约束,这可以从n的变化中看出。如果能够有效利用等待时间有限的约束特性,问题量表的增加将对解决方案产生有益的影响。这也是其他三种算法的下界误差率随着问题规模的增加而减小的原因。从表2的n列可以看出,上限和下限之间的偏差程度平均为约0.004。在随机生成的实验示例中,有20.3%的示例的上限和下限比为1,即上限和下限是问题的最佳值。可以看出,本文给出的上下界是紧的,构造的两个评价指标可以有效地衡量算法的性能。 RSS算法具有良好的计算效率。当工件数为80时,可以在0.10s内给出调度解决方案,完全满足调度要求。 4结论流水车间等待时间有限是常见的过程工业中的生产环境类型。即使只有两台机器的调度问题也是强NP难的,并且在多项式时间内无法获得最优解。当前算法要么是划分这种分支的算法,要么只是扩展经典启发式算法,并且不深入研究问题的基本特征以形成有效的调度算法。本文分析了问题与相应问题之间的关系,以及等待时间有限的两阶段流水车间调度问题无等待问题。给出了两种具有特殊处理时间的调度问题的最优解和最优值。最佳工件序列的工件优先级关系。为了解决这个问题,设计了一种基于可替换集的RSS算法,并分析了算法的性能。数据实验表明,该算法能够有效地解决等待时间有限的两阶段流水车间调度问题。本文给出的上下界很紧,相关的评价指标可以有效地衡量算法的性能。