文摘
本文考虑两种类型的随机重入作业车间调度问题(SRJSSP),即,最大的SRJSSP迟到判据和SRJSSP极小化准则。由于RJSSPs非完全多项式复杂性的考虑,一个有效的微分进化算法(DEA)结合两种不确定性处理技术,即DEA_UHT,提出解决这些问题。首先,计算成本,合理控制最优计算预算分配技术(OCBAT)申请分配有限的计算预算,以确保可靠的评估和识别优秀的解决方案或者个人,和假设检验技术(计画)被添加到执行统计相比,减少一些不必要的重复评价。其次,reentrant-largest-order-value规则旨在将DEA的个人(即。,连续向量)(即SRJSSP的解决方案。一个操作排列)。第三,传统的主动的解码方案作业车间调度问题扩展到解码的解决方案获得标准的值。第四,一个插入的开发策略和一个交换的勘探战略设计增强DEA的开发能力和探索能力,分别。最后,测试结果和比较清单DEA_UHT提议的有效性和鲁棒性。
1。介绍
作业车间调度问题(JSSP)是最著名的组合优化问题之一。JSSP的一种变体,可重入JSSP (RJSSP)中可以找到许多现实的生产和制造环境中,比如在半导体制造企业(1,2)和纺织厂(3]。RJSSP的主要特点是,一份工作可能访问一组机器在生产过程中不止一次。自从JSSP具有非完全多项式性质(4),它可以减少RJSSP,后者也非完全多项式。研究RJSSP仍然是有限的。锅和陈5]介绍了两个扩展二进制整数规划RJSSP配方。Topaloglu和Kilincli6)提出了一种修改转移瓶颈启发式RJSSP的标准。陈等人。7)提出了一个混合分布估计算法的RJSSP顺序相依设置*最大完工时间最小化。
我们都知道,不确定性是非常普遍的在许多现实世界的生产场景。目前,一些不确定JSSPs已经进行了研究。它们中的大多数都是JSSP的随机处理时间(8- - - - - -22),其余的JSSP概率机可用性(23),JSSP的模糊处理时间(24),和JSSP模糊机可用性(25]。在这些研究中,进化算法是主要的方法,和考或迟到/早熟是主要的优化准则。JSSP的随机加工时间,如何评估解决方案的预期目标(即价值。合理,则值)是关键环节之一的设计算法。直接的方法是多次样品相应的随机模型获得多个客观值,然后使用这些采样值的平均值作为一个近似估计预期的客观价值。显然,抽样时间越多,更加稳定和可靠的估算值。这种方法是在现有研究中最常用的方法。然而,这样的方法通常有较高的计算成本。因此,一些研究人员采用了三种类型的技术来控制和降低计算成本。第一个是最优计算预算分配技术(OCBAT) [26]。Zhang et al。13和杨et al。16利用它来分配有限的计算预算保证更可靠的评价更好的解决方案。第二个问题是转换技术。沈和朱19)用它来JSSPs的随机模型转化为确定性的,信心或被认为是鲁棒性水平。然后,每个解决方案的客观价值是通过这些确定性模型计算。第三是客观价值预测技术,它主要是由仿真元模型驱动的。Ghasemi et al。22)建造了一个元模型利用遗传编程(GP)直接预测解决方案的客观价值。然而,对于不确定RJSSPs,只有穆罕默迪(27)设计了一个模拟退火算法和遗传算法模糊加工时间的RJSSP最大完工时间最小化,和随机RJSSP直到现在还没有被研究过。
从上面的文献综述,可以知道它是非常必要的随机RJSSP进行研究。因此,RJSSP随机加工时间被认为是在这里。最近,许多有效的进化算法已经成功地用于处理不同的复杂的优化问题28- - - - - -37]。例如,段等。28)开发了一种混合分布估计算法的分布式置换流水车间调度问题(FSSP)与流线的资格。郭et al。31日)提出了一种粒子群优化算法的动态多目标车辆路径问题。唱et al。33)提出了三种入侵杂草分布组装排列FSSP优化算法。郭et al。36)设计了一个新颖的互动个性化多目标进化算法的优化问题螺栓支持网络。Zhang et al。37)设计了一个matrix-cube-based分布估计算法的分布式组装排列FSSP。计算比较表明,这些进化算法可以获得非常满意的解决方案和合理的计算时间。由于随机RJSSP np完全的,一个有效的基于进化算法,即。微分进化算法(DEA)也选择处理这个复杂的问题。DEA是首先提出了解决优化问题在连续域(38,39]。因为它的简单的概念和快速收敛,DEA了许多应用程序在各种各样的领域。然而,由于其连续性质,JSSPs的DEA研究仍非常有限。因此,在本文中,一个增强的DEA与不确定性处理集成技术(DEA_UHT)是专为解决随机RJSSP下最大的迟到和随机RJSSP考下 。
DEA_UHT的主要特色在于两个方面:合理的不确定性处理技术和有效DEA-based搜索。对于不确定性处理技术,不仅是上述OCBAT用于识别(即更好的解决方案。,在dividuals) with high confidence under limited computation cost but also the hypothesis test technique (HTT) is added to avoid the unnecessary repetitive evaluation for the poor solutions. That is, the solutions with high quality can be selected during the DEA’s search process, which is helpful to guide the algorithm search faster to the truly promising regions in the stochastic solution space. As for the DEA-based search, an插入的开发策略和一个交换的勘探战略设计增强DEA的开发能力和探索能力,分别。测试结果和比较验证DEA_UHT提议的有效性和鲁棒性。
本文的其余部分组织如下。介绍了两种随机RJSSPs在下一节。基本的DEA、OCBAT和计画部分的简要描述3。展示解决方案表示后,延长解码方案,修改后的OCBAT,和两个特殊的交叉策略,提出了DEA_UHT通过结合DEA OCBAT和计画4。给出了测试结果和比较和分析部分5。最后,结论和进一步的研究方向进行了总结6。
2。随机RJSSP
考虑到随机RJSSP,由n工作和米机器。每个工作应该在每台机器上处理l(l> 1)倍。每个工作在每台机器上的加工时间是一个随机值在一定的分布。让 表示行动解决方案或序列处理, 和 的工作 , 重复或可重入的时候工作在 , 噪音或不确定因素, 的随机处理时间的工作在机 , 的预计完成时间的工作 , 工作的到期日期 , 除外迟到的工作 , 除外迟到的工作。在这里 应该是受到均匀分布 , ),预计处理时间和吗表示噪声级。
然后,预计最迟到 可以给
下的随机RJSSP最大迟到(SRJSSP -T马克斯)可以作为制定 在哪里代表所有可能的排列。
同样,预期的时间 可以给
下的随机RJSSP考(SRJSSP -C马克斯)可以作为制定 在哪里代表所有可能的排列。
显然,无限的上述问题模型可以使方程的客观价值(1)和(3)稳定,但事实上,它几乎是不可能的。在实际的计算,方程的价值(1)或(3)通常是由有限的抽样值的平均值近似(例如,蒙特卡罗模拟法)[8- - - - - -18]。因此, 可以估计
和 可以估计
3所示。介绍DEA、OCBAT和计画
3.1。DEA
微分进化算法(DEA) (38,39]是一种进化算法求解连续优化问题。基本的DEA旨在找到全局最优的解决方案通过使用当前的个人之间的区别。具体地说,每个人的搜索行为是动态控制通过改变分化的方向和步长。在每一代,突变和交叉运营商应用于当前个体生成候选人群,然后选择运算符是用来确定一个新的下一代人口。如今,有几种变异/ DEA的方案。
3.2。OCBAT
OCBAT计算是一种动态分配技术预算(26,40]。具体地说,它可以优化采样时间为每个候选解决方案,以便真正更好的解决方案可以确定在一个给定的计算成本。表示可能的解决方案的总数,(职责。 )计算成本或采样时间分配给解决方案(职责。当前最佳解决方案)后kth分配,(职责。 )标准差在抽样的客观价值的解决方案(职责。当前最佳解决方案)后kth分配,(职责。 )的平均采样客观价值的解决方案(职责。当前最佳解决方案)后kth分配, 之间的区别和后kth分配,总抽样时间后kth分配,给定的总采样时间。
根据上述定义,标准OCBAT提供的算法如下:步骤0。集 , 和 。步骤1。如果 ,算法应该停止了。步骤2。执行(即样品。,simulation replications) for each solution ,然后设置 。步骤3。计算每个通过使用 和 。步骤4。执行 样品为每个解决方案 。第5步。集 ,并返回步骤1。
基于文献[26),的推荐值范围和是(5,20.]和[ , ),分别。
3.3。计画
计是一种统计推断方法,可以用来判断两个解决方案之间的差异和是由抽样误差引起还是本质区别(41]。让零假设是“ ,”然后备择假设是“ 。“基于统计理论、临界区定义如下: 在哪里是分布和证据水平。当 ,它可以判断,解决方案比解决方案 。
4所示。为随机DEA_UHT RJSSP
4.1。编码方案
自从DEA的个体是一个真正的向量,传统DEA不能直接用来处理离散优化问题。因此,我们利用reentrant-largest-order-value (RLOV)规则来源于现有largest-order-value(值列表)规则42将DEA的我th个人 工作序列 基于RLOV规则中的元素首先按降序排名获得暂时的离散序列 。然后,行动方案可以通过生成 在哪里是一个操作符的一部分(例如, )。表1说明了向量的编码在DEA小RJSSP 。
4.2。解码方案
基于RJSSP的特点,一个最优的解决方案必须积极安排在常规的标准(例如,最大的迟到和考 )(43]。这意味着解决方案的质量可以通过改变半主动改善进度到活跃的一个。因此,当解码解决一个可行的时间表,每个操作应填写第一个空闲时间间隔在当前的甘特图,而不是最后一个空闲的时间间隔。这个活跃的解码方案是利用我们的算法。
让机器的数量j操作处理lth可重入的工作我,的处理时间lth可重入的工作j在机我,的最早可能开始时间的工作 。注意到的价值应符合下列不等式: 在哪里 ,和[t1,t2代表任何空闲时间间隔的机器上。
基于上述定义,解码方案,生成一个活跃的时间表RJSSP的解决方案提供如下:步骤1。集 和 , 。步骤2。如果 和(国防部 ),然后设置 。步骤3。集 。步骤4。计算 ,并设置 。第5步。集 。如果 ,然后返回到步骤2。
4.3。应用轮盘OCBAT掌权
对于随机RJSSPs,之间的区别和( )通常比之间的更大和 。这可能会导致 。基于第4步的标准OCBAT(见部分3.2),重复步骤1 - 5的时候可能会远远低于这一标准算法 。的次数,OCBAT可用于动态地分配计算预算非常有限。因此,可靠的OCBAT评价能力不能充分利用。
在这种情况下,所谓的“最饥饿”规则(40)通常用于处理这个障碍。然而,这种规则集1,需要执行OCBAT的步骤1 - 5次了。这可能增加OCBAT的算法的运行时间。自从OCBAT决定预算分数而不是数字,这里我们利用“轮盘赌”规则来分配 。步骤4,标准的OCBAT应该改为以下两个子步骤:步骤4.1。计算分配概率 对于每一个解决方案在(k +1)分配。步骤4.2。应用“轮盘赌”规则来分配每一个解决方案根据 ,和更新每 。
4.4。特殊的开采和勘探策略
基于引用(44,45],RJSSP的解决方案空间可以被看作是一个“大山谷,”当地的最适条件通常是接近对方,和接近全球最适条件底部的“大山谷”,要么插入的运算符或交换的运营商可以执行更紧凑的搜索。与此同时,DEA已经被证明是一个有效的算法来找到有前途的解决方案或地区在整个山谷42,44]。至于随机RJSSP,形状和底部区域的大山谷总是改变。因此,为了提高我们DEA_UHT的搜索能力,我们设计一个插入的开发策略和一个交换的勘探战略取代DEA的原始突变和交叉,不能获得足够的有前途的解决方案。前战略选择一些可靠的好的个人被OCBAT和计画来取代一些贫穷的人,并执行插入的运营商在这些选定的人。后者策略执行交换的运营商根据DEA的基本方案在所有个人除取代了可怜的人。这些策略的详细程序提供了第五步在下一节。
4.5。DEA_UHT
在DEA_UHT DEA-based搜索是根据DE / rand-to-best / 1 /设计经验策略执行全球搜索或探索,在基矢量是当前最好的个人。因此,最好的个人信息可以被其他个体共享。通过合并OCBAT、计画和两个特殊的开采和勘探到DEA策略,一种混合方法,即随机RJSSP DEA_UHT,提出。
表示一代,人口与大小在一代t,一套档案保存的个人需要采用特殊的插入的交叉,的我th个人与维N( )在 , 一个临时的人口规模在一代t,的我th个人 , 的k变量/组件的个体 , 的kth的变量 , 的kth的变量 , 交叉概率,比例因子, 的序数在按照降序排列(见部分4.1), 的中相应的作业编号排列(见部分4.1),随机值的区间[0,1]。这些定义的基础上,给出DEA_UHT框架如下:步骤1。输入 , , ,让界限 和 , 。步骤2。种群初始化步骤2.1。生成 为 步骤2.2。使用OCBAT算法的部分3.2和4.3分配T抽样预算(即。,evaluation times) for all individuals while estimating the objective values of all individuals and set 集。步骤3。集 并选择一个人从作为与最低客观价值。步骤4。之间的进化阶段(步骤4和9)。 。第5步。突变和交叉阶段。步骤5.1。如果属于 ,然后执行插入的剥削(见部分4.4)。5.1.1步。随机选择一个个体从最好的百分之五的并将它设置为 。5.1.2步。随机生成u和( ),和随机集1或2。5.1.3步。如果 ,然后插入后 。5.1.4步。如果 ,然后插入之前 。一步是5.1.5。集 步骤6。步骤5.2。执行交换的探索(见部分4.4)。集试验向量 , 和 。随机选择 ,在哪里 ,和随机选择 。5.2.1步。集 ,和 。5.2.2步。如果 ,然后找到令人满意的 和交换与 ;其他随机生成( )和交换与 。5.2.3步。集 。5.2.4步。集 国防部和 。5.2.5。如果 和 ,5.2.1然后回到步骤。. 5.2.6步。集 。步骤6。集我=我+ 1。如果 ,然后返回到步骤5。步骤7。使用OCBAT算法的部分3.2和4.3估计所有个人的客观价值 。步骤8。选择阶段。节表现遗传性出血性毛细血管扩张症3.3在与 , 。步骤8.1。如果零假设成立 ,然后设置一个布尔变量b_replace= true;其他设置b_replace= false步骤8.2。如果b_replace= true然后设置 ;其他设置 。步骤8.3。如果b_replace= true和 ,然后设置 。步骤8.4。如果b_replace= false和在最糟糕的20% ,然后添加来 。第9步。集t=t+ 1。如果 (最大代),然后返回到步骤4。第10步。输出( )和它的客观价值。
从上面的过程,它不仅可以知道DEA_UHT利用OCBAT良好的解决方案,确保可靠的评价也采用计画减少重复搜索。此外,DEA-based搜索结合两个特殊的策略设计有效地执行空间勘探和开发解决方案。与此同时,“ 5.2.5”步骤是用来控制的搜索范围交换的探索。此外,值得注意的是,虽然步骤5.1(分别地。步骤5.2)直接执行插入(职责。交换)操作的个体,它相当于执行相同的插入(职责。交换)操作对应的排列的个人(参见RLOV统治的部分4.1)。
5。仿真结果和比较
5.1。实验装置
验证DEA_UHT的表现,十个实例的确定性RJSSP创建通过以下步骤:步骤1。选择一个经典十JSSP的基准(46依次为页(例如,FT06, FT10, FT20, LA01, LA06, LA11, LA16, LA21, LA26, and LA31 [46])。步骤2。设置可重入时间 。步骤3。设置每个和每个相应的数据页。步骤4。集 为 和 。第5步。集 为 。步骤6。集 为 和 。步骤7。集 为 。
使用上面的步骤,可以创建十RJSSP实例。这些实例名为FT06_R2 FT10_R2、FT20_R2 LA01_R2, LA06_R2, LA11_R2, LA16_R2, LA21_R2, LA26_R2和LA31_R2分别。每一个名字都是由相应的名称后添加“_R2 JSSP的基准。显然,这些RJSSP实例通过简单地扩展经典JSSP的实例。因为每一和之间随机生成[1,n分别]和[100],每个RJSSP内部相关的实例可以被忽略。使用上述步骤获得RJSSP的实例只是为方便其他研究人员生成相同的实例。
对于任何创建的实例,每个工作的到期日期可以通过以下步骤:步骤1。随机产生一个排列 为每个RJSSP的实例 。步骤2。计算每个 通过部分解码方案4.2。步骤3。通过指定每个作业的日期 在哪里 是一个随机值之间 。因为地址的能力紧张的截止日期会影响一个企业的能力和严密的到期日期更难解决的问题比在宽松的到期日期,(10)的目的是获得一个严密的到期日期。
接下来,随机RJSSP的实例可以通过改变每一个原始的处理时间 上述RJSSP均匀分布的实例 ,在哪里是预期的处理时间,等于原 和表示噪声级。为了测试算法的性能更全面,两种随机RJSSPs被认为是。第一种是随机RJSSP下 。十个实例 和他们 生成。这些实例由S1_Iname_R2_表示T马克斯,Iname表明S1_Iname_R2_T马克斯来源于Iname确定性的实例。第二种是随机RJSSP下 ,的十个实例 生成。同样,这些实例由S1_Iname_R2_捐赠C马克斯。此外,因为它是一个常见的场景,只有一部分的机器不稳定,一个变体也被认为是第一类的问题。这变种,即S2_Iname_R2_T马克斯,只有设置每个工作机的处理时间和机器三个均匀分布
DEA_UHT提议和其他算法相比在Delphi 2010中实现,实验上执行一个英特尔3.0 GHz PC与8 GB内存。DEA_UHT的主要参数设置如下:人口规模 , = 0.7,= 0.1, , ,和 。每个算法相比的最大代设置为300。每个算法相比30次执行独立在每个实例。
显示DEA_UHT的有效性,比较两个变量。这些变体的缩写给出如下:(我)PDEA: DEA_UHT没有OCBAT,计画插入的开发战略和交换的勘探策略。细节可以描述如下:(1)没有OCBAT DEA_UHT。DEA_UHT步骤2.2和7,OCBAT被替换为20的算法评估时间为每个解决方案的性能评估。(2)DEA_UHT没有计画。在DEA_UHT步骤8,HTT-based选择被替换为正常的选择。(3)DEA_UHT没有插入5.1的开发策略:一步是删除。(4)DEA_UHT没有交换的开发策略:删除步骤5.2.2和5.2.3,“ 5.2.5步中”被替换为“ 。”(2)DEA_UHT_O。DEA_UHT没有计画,插入的开发战略和交换的勘探策略。
5.2。仿真结果和比较
总结了统计结果表2和3,在那里噪声级,的信徒是最好的预期最大迟到或考吗是预计平均最大迟到或考。统计结果清晰,在表2和3最好的和次优值每一行表示使用粗体和斜体字体,分别。最后输出解决方案通过每个在每个运行算法相比,其预期的客观价值 或 计算预期的处理时间(即。,没有噪音)的处理时间。很明显,的信徒和是可以反映出这些算法相比在统计意义上的性能。此外,进一步显示结果的统计分布表1和2小提琴的阴谋,算法对“PDEA vs DEA_UHT”和“DEA_UHT_O vs . DEA_UHT”给出了数据1和2。
(一)
(b)
(一)
(b)
从表2和3同时,很明显的信徒价值和是值通过DEA_UHT PDEA获得的比,验证了通过将OCBAT有效性,计画,插入的开发策略,交换的勘探战略转化为PDEA。这也意味着DEA_UHT能达到一个更好的平衡比PDEA勘探开发和DEA_UHT_O之间。与此同时,大部分的的信徒和所有的值是获得的值通过DEA_UHT_O比PDEA,从中可以得出结论,OCBAT提高优化性能是必要的。值得注意的是,上述结论仍然可以在考虑表的实例1和2,在那里 。此外,从数据1和2可以看出,DEA_UHT更好的统计分布和更好的中间线与PDEA和DEA_UHT_O相比。这些小提琴情节证实DEA_UHT的竞争力。
显示OCBAT的作用,计算OCBAT的预算分配XXX DEA # # # # # # 5 f; UHT为中型实例XXX S1 # # # # # # 5 f; LA11 XXX # # # # # # 5 f; R2 XXX # # # # # # 5 f;提供在图3。此外,来阐释的有效性XXX DEA # # # # # # 5 f; UHT,收敛曲线的算法相比,在相同的实例给出了图4,连接形成的曲线 最好的个人的价值在每一代的相应算法。 这是通过设置计算 (例如, )。计算预算分配和其他实例的收敛曲线类似的数据3和4。
从图3,这是表明OCBAT可以明智地分配更多评价次更好的个人。也就是说,OCBAT可以提高算法的能力找到更可靠的高质量的解决方案或地区在每一代相同的计算预算。从图4可以看出,DEA_UHT的收敛速度明显快于其他算法进行比较。这体现DEA_UHT可以指导整个人口搬到预期的底部(即“大山谷”。,“大山谷”的底部没有噪音)在解空间更快,因此具有更好的搜索性能。此外, DEA_UHT_O的值小于那些三者在大多数情况下,验证OCBAT有助于指导搜索真正有前途的地区在嘈杂的环境中。
6。结论和未来的研究
提出了一种新型DEA_UHT结合DEA解决随机RJSSP OCBAT和计画。这类问题有许多实际应用在现代企业。最好的作者的知识,这是第一次,DEA已经应用到这样一个重要的问题。OCBAT明智地分配有限的帮助下采样预算执行可靠识别优秀或良好的个人,和计画的帮助下储备好高的个人信心,以及插入的和交换的策略来有效地执行增强的开发和探索,DEA_UHT是不同类型的随机RJSSP性能好。在未来,我们的工作是将DEA_UHT扩展到其他类型的随机调度问题。
数据可用性
数据被作者和策划可按照客户要求定制。
的利益冲突
作者宣称没有利益冲突。
确认
这项研究部分由中国国家自然科学基金(61963022和61963022)和基础研究云南省重点项目(202101 as070097)。