文摘
摘要排列flowshop调度问题没有中间缓冲区和提出了一种基于分散搜索的混合算法和变量附近搜索。混合算法,解决方案具有良好的质量和多样性是由一组引用的分散搜索,搜索,每一代开始从参考集生成一个解决方案,以提高搜索的多样性,同时保证质量的初步解决方案。此外,附近一个变量基于job-block开发的概念,和附近的大小可以自适应地改变根据job-block的建设。这样一个动态的战略可以帮助获得搜索深度和多样性之间的平衡。广泛的基准问题进行实验,结果表明,该混合算法是强大的和竞争与其他强大的算法在文献中。
1。介绍
传统的置换流水车间调度问题(PFSP)的重点研究领域的生产调度由于其强大的工业背景(1]。这个问题通常被认为有无限的能力在相邻的机器之间的一个中间缓冲区存储工作。然而,在许多实际的行业,由于需要连续生产,生产线通常相邻机器之间没有中间缓冲区(2]。例如,在热轧过程中沉重的钢铁行业板块,厚板将不断由一系列连续的处理阶段,也就是说,重新加热、热轧、冷却、切割、淬火,没有中间缓冲区之间的任何两个阶段。在这种情况下,处理完成后机器,一份工作这台机器上必须等待直到下一个机器吗可用(例如,下一个机器空闲时)。这种现象的工作和机器被称为阻塞,这样一种PFSP然后被称为PFSP阻塞。当目标是最小化考(),这个问题可以表示为/屏蔽/,吸引了大量的注意力从许多研究人员最近。
大厅和Sriskandarajah3)的调查/屏蔽/并介绍了这个问题在实际产业的一些实例。因为这个问题已经被证明是np完全问题,具体的算法和基于只能解决非常小型的问题。对于大型问题,启发式算法或metaheuristics变成唯一的候选人。
麦考密克et al。4称为PF)提出了一个启发式算法,在每个迭代中会插入这个工作职位目前获得的部分序列,这样导致新的序列至少增加机器的空闲时间和截止时间。纳瓦兹提出的基于NEH启发式算法et al。5)和PF启发式,Ronconi和Armentano6)设计了一种混合算法与PF NEH和所取得的良好效果。Caraffa et al。7)提出了一种改进的遗传算法(GA)的最小化来解决这个问题,实验结果表明,该算法是有效的,其性能优于启发式提出Abadi et al。8]。格拉博夫斯基,Pempera2]提出了禁忌搜索(TS + M)这个问题,和基于基准问题的计算结果表明,TS + M算法优于以前的算法在文献中。Jarboui et al。9)设计了一个混合分布估计算法(H-EDA)问题,和测试结果表明,该算法优于算法提出了(2,7]。梁等。10)提出了一种多群粒子群优化,结果表明,该算法问题是比TS + M算法(2]。小王和唐11)提出了一种离散粒子群算法的变邻域搜索算法作为局部搜索和计算结果表明,该算法优于TS算法+ M。
可变邻域搜索(VNS)是一个简单但有效的智能优化算法(12]。有别于传统的本地搜索算法,搜索附近,手脚的想法是使用两个或两个以上的社区在搜索过程中,在搜索过程中,该算法将执行另一个搜索根据给定的规则。因为社区结构不同,一个局部最优解在一个社区不一定是当地最优解在其他社区。因此替代搜索沿着不同的社区可以帮助改善迷走神经刺激法的搜索多样性。迷走神经刺激法算法已被广泛用于解决各种各样的组合优化问题,并取得了许多可喜的成果通过迷走神经刺激法(13]。分散搜索(SS)是一种以人群为基础的方法(14),其主要思想是选择解决方案的质量和多样性人口构造参考集,然后使用参考集生产下一代的人口。该算法已经成功地应用于许多组合优化问题,如车辆调度问题(15)和生产调度问题(16]。
因此,在本文中,我们杂交SS与迷走神经刺激法,提出一种混合算法/屏蔽/问题,结合SS的全局搜索能力和局部搜索能力的手脚。通过他们的组合,可以实现全局搜索和局部搜索的平衡。在附近的结构中,我们开发一个基于job-block社区,提高迷走神经刺激法的搜索效率。本文的主要贡献如下。(1)不同于之前的研究,包含了VNS SS作为本地搜索,本文结合SS为迷走神经刺激法来存储解决方案具有良好的质量和多样性和发展一种新的混合算法。(2)混合媒母算法,提出了一种自适应选择策略选择适当解决方案VNS基于前面的选择时间和搜索结果从它。(3)job-block社区结构设计,可以动态地调整它的大小,实现搜索深度和多样性之间的平衡。
本文的其余部分组织如下。的/屏蔽/问题是部分中描述2。提出的迷因算法的描述部分3节中,4我们进行大量的实验来测试我们的算法的性能和比较文学中的其他强大的算法。最后,本文的结论部分5。
2。的/屏蔽/问题
的/屏蔽/问题考虑本文可以描述如下。有一组工作到达时间为零和一组加工机器。每一份工作必须处理这些吗机器在同一顺序从第一个到最后一个,也就是说,。工作的处理时间在机是,这是一个固定的和非负价值。假设每个工作的处理不能中断一旦处理开始。在任何时候,每个作业最多可以处理在一个机器,每台机器最多只能处理一个工作。没有中间缓冲区之间的任何两个连续的机器,因此,一份工作,完成了加工机器,应该保持机器直到下一个机器就变为空闲的,并可用。也就是说,工作和机器是阻塞如果下一个机器不是空闲的。调度的任务是确定这些工作序列工作上的机器以最小化最大完工时间(例如,考)。
让的排列工作中,表示索引的工作分配th的位置。出发的时间工作在机(表示为)可以计算如下: 的极小化的解决方案可以计算为。
3所示。混合算法
3.1。该算法的主要过程
混合算法的参考引入VNS帮助算法摆脱局部最优的得到更多的权力。在该算法中,用于存储解决方案具有良好的质量和多样性。该算法的主要过程中给出的算法1,其中一个解决方案是由所有工作的处理顺序,和每个过程的细节在下面几节中提出的。
|
||||||||||||||||||||||||||||||||||
在混合算法,我们更换摇晃过程在传统迷走神经刺激法生成一个新的解决方案基于解决方案的选择这样新的解决方案可以有良好的初始质量和多样性,这反过来可以帮助算法避免陷入局部最优。此外,提出了传统VNS PFSP普遍采用插入移动(删除作业从作业序列,然后插入到另一个位置),交换移动(交换两个岗位的工作序列)。Bozejko et al。17)指出,化合物(即移动。,multiple insertions or swaps) generally have better performance than simple insertion or swap for the scheduling problems in which a solution is represented as a job sequence. The reason is that the compound move can have a larger solution space. Therefore, in this paper we develop a job-block neighborhood whose size can be dynamically adjusted according to the size of job blocks. In the hybrid algorithm, the neighborhood size changes in an ascending order so as to guarantee a balance between search depth and diversity.
3.2。代的初始解
因为PFSP NEH方法可以获得良好的解决方案,我们也采用这个方法来生成一个初始解,然后应用本地搜索去改善它。过程可以描述如下。步骤1。根据nonascending序列的所有工作的总处理时间顺序在所有阶段,每个作业序列,获得一份工作。步骤2。确定最优序列序列中的前两个工作的部分解决方案,然后删除这两个职位和从序列。步骤3。从第一份工作中剩下的序列,插入到最佳位置的部分解决方案(即。增加目标函数值最小),将其移出序列。插入重复这个过程直到所有工作已经插入,随后一个初始解。步骤4。与插入附近执行本地搜索,提高最初的解决方案,以改进的解决方案为真正的初始解。
3.3。更新的参考组
为了确保解决方案的参考()可以有良好的质量和多样性,使用下面的更新策略。如果,然后改进的解决方案可以添加到直接;否则,改进的解决方案可以添加到如果它能满足在哪里表示最糟糕的解决方案和是一个阈值。插入后,最差的,解决方案的多样性将被删除。一个解决方案的多样性来标示如下:两个方案之间的距离和被定义为,在这如果和其他方面。如果两个解决方案相同的坏的多样性,质量较差的解决方案将被删除。
3.4。代的新解决方案
最初,每一个解决方案有相同的选择概率。如果一个解决方案已被选为本地搜索和由此产生的改进解决方案未能进入参考集吗,然后我们组(选择时间的解决方案吗);否则,保持不变。根据,选择一个解决方案可以被定义为的概率
3.5。本地搜索基于Job-Block附近
如前所述,基于job-block社区是一种compound-move社区。对于一个给定的解决方案,让job-block的大小和相应的社区来标示;然后本地搜索过程可以描述如下:步骤1。设置迭代索引最好的解决方案。步骤2。随机删除相邻的工作并表示这job-block和左边的部分解决方案。步骤3。集。步骤4。插入最好的位置。第5步。集。如果,转到步骤4;否则,获得一个新的解决方案。步骤6。如果,然后设置。步骤7。集。如果(最大迭代),转到步骤2;否则,终止和输出。
在上面的本地搜索,很明显,不进行本地搜索整个社区但只有一些随机搜索。这种策略可以帮助节省计算时间,同时保持质量的解决方案。此外,社区是一个升序排序的搜索深度,以获得一个搜索深度和多样性之间的平衡。后的值和与相比要小得多(的工作),这种本地搜索的复杂性不会超过的本地搜索的基础上插入社区或交换社区,其复杂性。所以可以保证搜索效率的局部搜索算法。
4所示。计算实验和结果
在实验中,我们测试了算法的基准问题PFSP提出Taillard [18相比),它与其他强大的算法在文献中。总共有12组基准问题的西装,每组有10个实例。工作岗位的数量从20到500年变化和机器的数量从5到20。
c++语言实现的混合算法和测试与英特尔酷睿i3个人电脑(2.8 GHz) CPU和4 GB内存。停止准则的最大计算时间秒。混合算法的参数设置如下:的大小等于10,job-block的最大大小设置为5,和本地搜索的最大迭代设置为10的实例和20的其他实例。
比较的统计性能,10为每个实例和独立运行进行的最小百分比相对偏差(minPRD)和平均相对偏差百分比(APRD)收集。民主的定义是相对差异,在那里和罗恩,分别代表解决方案通过一个算法,给出的解决方案19]。
4.1。效率分析,结合参考集
测试和分析的性能将参考组SS纳入迷走神经刺激法,在本节中我们比较我们的混合算法(表示SSVNS)和另一个版本不包括参考集(VNS)表示。请注意,手脚也同样的停止准则用于我们的SSVNS。比较结果如表所示1,一个更好的结果显示在一个大胆的风格。
从表中所示的结果1,可以发现,可以显著提高了算法的性能将参考集。这一现象背后的主要原因是公司的参考设置可以帮助提供一个初始解决方案具有良好的质量和多样性迷走神经刺激法,进而有助于提高解决方案的质量,同时使算法有很好的能力摆脱局部最优区域。
4.2。比较与其他强大的算法
在上面的部分中,我们展示了将参考设置纳入迷走神经刺激法的效率和分析对算法的影响。进一步说明提出的混合算法的效率,在本节中,我们比较文学中的其他强大的算法,例如,t + M算法(2),H-EDA算法最近提议在9],和DMS-PSO算法[10]。
给出了比较结果表2,TS + M的结果,H-EDA, DMS-PSO报道在相应的引用。从比较结果,看来APRD度量H-EDA获得最佳性能。然而,我们的混合算法可以获得最好的结果比H-EDA多个实例组。此外,很明显,我们的SSVNS算法达到最好的结果为10的12个实例组minPRD度量和这些结果比H-EDA获得的算法。此外,SSVNS比DMS-PSO算法APRD和minPRD指标对所有实例组除了实例组100×20和500×20。因此,可以得出结论,该混合算法具有竞争力或优于文献中一些强大的算法。
5。结论
摘要排列flowshop调度问题,没有中间缓冲了。在这个问题上,一份工作和一台机器可能阻塞由于连续之间没有中间缓冲机器,这样的情况经常发生在实际的行业。虽然有很多文件处理这一问题,本文提出一种新的混合算法,将学生纳入迷走神经刺激法和开发一个基于job-block附近搜索。党卫军的合并迷走神经刺激法可以提供一个初始解决方案具有良好的质量和多样性,从而可以保证高质量的解决方案提高了手脚,同时保持良好的搜索多样性(即。的混合算法可以获得很好的能力的局部最优的搜索空间区域)。自适应选择策略的解决方案参考集能够进一步改善搜索多样性。使用的本地搜索迷走神经刺激法是基于job-block compound-move附近。这种社区可以提供一个更大的搜索空间,从而可以增加的概率更有前途的解决方案。此外,这种本地搜索的变量搜索深度也可以帮助实现搜索强度和多样性之间的平衡。广泛的基准问题进行实验测试混合算法和结果表明,该算法是非常有效的,甚至与或优于其他竞争强大的算法在文献中。
利益冲突
作者宣称没有利益冲突有关的出版。
承认
本研究在一定程度上是由中国国家自然科学基金(批准号51104033),中国国家自然科学基金(批准号61403277),国家自然科学基金(批准号71201105)。