文摘

本文地址序列不相关的平行机调度问题和机器相关的设置时间。它的目标是最小化最大完工时间的。问题是解决组合弯管机分解。这种方法可以缓慢收敛。因此,三个程序介绍了加速收敛。第一个过程是一个新的方法,包括终止主问题的执行重复的最优解时发现。第二个过程是基于multicut技术。第三个过程是基于热启动。改进的弯管机分解方案相比,弯管机分解的数学公式和一个标准的实现算法。在实验中,使用两个测试集文学,240年和600年60工作和5机器实例。 For the first set the proposed method performs 21.85% on average faster than the standard implementation of the Benders algorithm. For the second set the proposed method failed to find an optimal solution in only 31 in 600 instances, obtained an average gap of 0.07%, and took an average computational time of 377.86 s, while the best results of the other methods were 57, 0.17%, and 573.89 s, respectively.

1。介绍

本文地址序列不相关的平行机调度问题和机器相关的设置* (UPMSP-SMDST)。并行机器调度问题都进行了广泛的研究和应用在很多制造系统(1]。因为原材料的成本上涨,劳动力、能源、运输、调度的作用是目前重要的规划公司(2]。了解更多关于这些问题,调查由Mokotoff [3可以咨询)。大部分的文学在这些问题上忽略了建立时间之间的工作。然而,Allahverdi和Soroush [4)公布了一份研究报告显示的重要性,考虑到设置时间,从而获得更为真实和有效的规划。

UPMSP-SMDST是一个np难问题,因为这个问题的一个特例,一台机器相当于旅行推销员问题,这是np困难(5]。一些研究中使用的方法来解决这个问题,罗查et al。6)是值得注意的,因为它提出了一个最大完工时间和最小化方法和加权之和迟到的工作。德波拉et al。7)提出了一个nondelayed relax-and-cut算法基于拉格朗日松弛time-indexed配方的最小化加权总迟到。Tran和贝克8)提出了一个算法基于一种基于逻辑的弯管机分解最大完工时间最小化。最后,Avalos-Rosales et al。1]探索许多新的线性化的数学公式来计算时间。

大多数研究使用启发式和metaheuristics解决UPMSP-SMDST。在这些论文中,德波拉et al。9]提出的方法基于可变邻域搜索最大完工时间最小化和加权之和迟到的工作。林等。10)提出了一种迭代贪婪启发式最小化总迟到。Vallada和鲁伊斯11)使用两个版本的最大完工时间最小化的遗传算法。应等。12)提出了一个模拟退火算法来最小化最大完工时间的限制,和李et al。13)评估基于禁忌搜索算法以最小化总迟到。Arnaout et al。14)提出了一种蚁群算法与最大完工时间最小化两个阶段。最后,Avalos-Rosales et al。1)提出了三个版本的方法基于multistart和盾算法来最小化最大完工时间的。

选择组合弯管机分解解决UPMSP-SMDST在这项研究中,因为它已经成功地应用于几个调度问题([8,15- - - - - -19])。弯管机分解方法在于将最初的问题划分为一个主问题和一个更简单的子问题。在一个最小化问题,主问题解决方案提供了一个下界(磅)和子问题的解决方案提供了一个上界(乌兰巴托)最初的问题。子问题是用来评估的可行性解决方案提供的主问题,如果有必要,产生组合的不平等,叫做削减弯管机,它被添加到主问题迭代,直到获得原问题的最优解(20.]。削减的弯管机,乌兰巴托和磅之间的差异减少,当 ,在那里是一些宽容,优化解决方案被发现。这种方法也被称为基于逻辑的弯管机分解。组合宗分解是一个泛化的经典宗分解,因为子问题可以是任何组合问题,不一定是一个线性或非线性规划问题(21]。

的建议是本文的贡献三个过程来加速收敛的组合弯管机分解应用于UPMSP-SMDST。第一个过程是首次提出,由主问题的终止执行重复的找到最优解。第二个过程是基于multicut技术并生成几个弯管机削减在每个迭代中基于质量解决方案的执行中发现主人的问题。第三个过程是基于热启动技术,由执行限制主问题,从而更快更容易解决问题比原来的主人,更快地削减产生弯管机。此外,与特定的适应性,这些程序可能会被应用到其他问题。

剩下的纸是组织如下。部分2介绍了UPMSP-SMDST的定义和一个实际的数学公式。部分3提出了弯管机的定义分解和评论论文该方法收敛加速技术。还描述了该过程和他们的组合创建方法,即改进的组合弯管机分解(ICBD)。部分4提出了计算实验的结果,比较最好的数学公式,弯管机的标准实现分解,ICBD。节5,并给出了结论。

2。问题公式化

在UPMSP-SMDST,一组组的工作计划的机器。每一份工作需要处理时间在机。系统机器无关,这意味着工作可以有一个处理时间长于工作吗在一个特定的机器,虽然同样不能对另一台机器。有一个准备时间,,对应于所需的时间之间的工作和工作的开始在机。在这个模型中,有必要使用一个虚拟工作0,所有参数等于零。此外,它的第一个和最后一个岗位序列,在哪里是一组的工作+虚拟工作0。问题的目标是确定一个时间表的工作分配的机器最大完工时间最小化。使用格雷厄姆的三元素符号等。22),这个问题可以分为。

目前,最好的数学模型提出了UPMSP-SMDST Avalos-Rosales et al。(1]。在这个模型中,1如果工作处理机器(和0,否则),是1,如果工作吗处理后的工作吗在机器(和0,否则),表示工作的完成时间,的极小化的解决方案。模型本身如下: 目标(1)解决方案的最大完工时间最小化。约束(2)确保每个工作是处理只有一台机器。约束(3)和(4)确保每个工作只有一个前任的继任者,分别。约束(5)确保最大的一项工作安排在每台机器上的第一份工作。约束(6)是一种新的线性化计算无关的极小化,这是一个很高的值不变。然而,值得注意的是,Tran和贝克8)是第一个提出这个约束加强主问题。约束(7)确保使用正确的就业和消除子循环的形成;也就是说,如果 工作的完成时间应大于或等于工作的完成时间吗,如果 ,这些约束成为多余的。约束(8)也定义解决方案的时间。约束(9)分配0到虚拟工作的完成时间。约束(10)(12)定义变量的nonnegativity和完整性。最后,约束(6)负责这个模型的效率相对于其他模型应用到这个问题。

3所示。组合弯管机分解

组合弯管机分解可以用来分解UPMSP-SMDST进入机器和主工作分配上的问题在单个机器上调度子问题。子问题是用来评估的可行性解决方案发现主问题和削减产生弯管机。标准实现该方法的UPMSP-SMDST首次提出了Tran和贝克8]。然而,直接应用该方法的收敛缓慢。因此,本文提出了三个程序加速收敛。

与这相关的主要问题收敛缓慢的运行时间(i)主问题和子问题和削减(2)产生的质量(23]。许多研究已经进行了开发技术来加速收敛的弯管机分解。他们可以分为两种主要的方法。第一个使用策略来减少计算工作解决主问题,和削减第二生成更有效的消除不可行或次优的解决方案(24]。因为产生的弯管机削减任何主问题的解决方案是有效的,这使得创建许多类型的削减([23- - - - - -29日])。麦克丹尼尔和迪瓦恩30.建议热启动技术,生成削减使用主问题的解决方案通过放松整数变量。惠特利et al。31日)开发了一个名为restrict-and-decompose的方案,包括放松整数变量的原始主问题和执行它。当这个问题不产生更多的削减,方法返回原主人的问题。Geoffrion和坟墓32)提出了一个计划,削减弯管机每次生成一个新的可行的解决方案,比现任的解决方案。这种策略避免了不得不解决主问题到最后为了产生弯管机削减。它还可以节约计算时间。象牙海岸和劳顿33)演示了使用启发式的好处到主问题找到好的解决方案。同样,Rei et al。26体能训练时)使用的本地分支策略Fischetti这样,洛迪(34]探索每种解决方案的社区获得的主问题检测重复的最优解。Poojari和比斯利35)利用遗传算法和启发式找到主问题的可行的解决方案。Lunday Sherali和这样[24)提出了生成一组初始削减主问题。黄和郑36]提出一种可行性降低某些特色反复删除不可行的解决方案。另一个策略是主问题提出并引入有效的不平等开始前的方法以消除不可行的解决方案([27,37,38])。产生一个以上的优质弯管机削减在每个迭代中被称为multicut技术(39]。马尼安蒂和黄40)定义了概念的帕累托最优削减退化弯管机子问题和应用multicut技术。

提出加速程序旨在减少主问题的执行时间和multicut生成。方法改进的质量和数量削减生成像帕累托最优削减40),覆盖包(27),最大可行的子系统(23,最大化密度减少(28引用)等方法,是不习惯,因为他们依赖于一个线性子问题,问题正在研究子问题是整数。有效的文献中发现的不平等也不习惯,因为他们是特定于问题解决;从深度分析我们没有确定任何特定的或通用的有效不等式的研究问题。此外,我们测试了两个加速度方法引用:首先从Geoffrion和坟墓32),其次是体能训练时当地的分支策略Fischetti这样和洛迪(34]。但是,他们没能有一个更好的性能比我们建议的程序。提出了加速收敛过程如下。

3.1。主问题的终止执行

在标准的弯管机分解有时主问题的最优解(磅)等于上一次迭代的最优解;也就是说,不同的解决方案相同的值。因此,我们提出一个程序终止执行时主问题早发现重复的最优解。因此,当这一切发生的时候,主问题不需要跑到最后,节省计算时间。

命题1。主问题执行期间,如果找到新的解决方案等于当前磅,掌握问题的执行终止,磅保持相同的值。

证明。主问题的最优解的值不能低于最优解的值在前面的迭代中找到。也就是说,考虑到下界迭代 根据定义,下界的顺序获得的主问题 。否则,前面的解决方案不是最佳。这是因为可以有多个相同的值的最优解。因此,在这种情况下,磅是相同的。

3.2。Multicuts

减少组合弯管机(CBC)生成不可行的子问题时确定。问题在这项研究中,当主问题发现机器的工作顺序次循环。例如,考虑六个工作1到6的标签。两次循环将是0-1-3-4-0和0-1-3-4-0。Tran和贝克8)提出了如下所示的削减。 在哪里的完成时间与机器相关的子问题的工作吗在迭代,是一组的工作分配给机器吗在迭代,是一个上限的影响工作吗在完成时间分配给机器在迭代,计算 , , 。也就是说,当工作不再是解决方案的一部分,磅可以减少的价值。

通过分析提出削减Tran和回8)有一个失败。考虑到假想的工作顺序 如果这份工作删除,只影响磅的设置次吗 ,如果 ,削减仍然有效;否则它不是。因此,我们使用一个“无用的”减少,只有消除已发现的不可行解。根据一些作者,这种类型的减少可以很弱41),但因为没有使用特殊结构发现可以建立更强的削减,削减,消除其他不可行或次优的解决方案。唯一的变化有关(13)来代替通过一个很高的值不变。测试的版本Tran和贝克的弯管机算法使用切割类型没有显示出不同性能和解决方案。我们在削减,因为这种变化之前削减并不像声称,减少分离但只有无用的削减。

实验进行的标准实现弯管机分解表明,主问题生成许多质量解决方案除了最优解决方案。通过质量解决方案,我们的意思是那些有一个值, 。下一个迭代的最优解可能在这些解决方案中,如果方法没有被终止。因此,这些解决方案,包括最优解,池存储在一组被称为解决方案。每个解决方案的池是解决的子问题,不仅仅是最优解,这就是为什么multicut过程。当一份工作序列的机器解决方案池是发现不可行,生成CBC(如上所述)。这迫使主问题生成解决方案以外池在下一次迭代的解决方案。因此,multicut策略降低了该方法的收敛所需的迭代次数,从而减少计算运行时。

3.3。热启动

热启动过程的组合弯管机分解,提出了基于解决限制主问题的想法。其目的是生产优质cbc更快。许多作者表明,强劲的下界发现time-indexed配方的线性松弛的机器调度问题提供有用的信息指导原始启发式叫list-scheduling算法([42- - - - - -44])。在这个意义上,弯管机分解主问题的线性松弛还提供了一个强有力的下界。测试进行的这项研究表明,线性松弛之间的差距和整数最优解主问题是平均的7%。此外,Fanjul-Peyro和鲁伊斯(45)表明,对并行机器调度问题没有设置时间,粉碎启发式生产优质解决方案与计算量小。这些启发式使用一些聪明的标准来减少变量在运行期间可用的数学模型。我们加入这两个想法提出限制主问题。

限制主问题是通过设置一组变量的主问题为零,如下所示。首先,执行主人的线性松弛问题。也就是说,变量的所有工作获得一个非零值插入到机器可用的工作,这是表示。此外,剩下的工作是插入的工作不能用于机器我,用。因此,限制主执行问题的变量的工作设置为0;也就是说,他们无法选择,而变量的工作可以取0或1的值。增加可用的数量在每台机器上工作,从而提高解决方案的质量,使用以下破碎启发式。我们先评估每个工作然后选一个最可能产生最小的影响完成时间的机器(),然后插入。这种效果,计算参数计算出每一工作吗 。这个参数是工作的处理时间的总和在机,最低设置时间工作后续的工作,最低设置时间工作之前的工作,在那里 ;也就是说, 。这份工作的最低插入且远离。这个过程会一直重复,直到达到理想的大小。

提出了热启动过程由一个弯管机分解使用上述限制主问题而不是主问题所有可用的工作(原主人问题)。主问题是因此更快地解决,从而生成CBC也更快。热启动过程分两个阶段执行不同百分比的工作因为他们经验显示,更好的性能。每个阶段结束后固定数量的迭代或者限制主问题的最优解等于乌兰巴托。我们观察到的最优解限制主问题不是一个磅的原始问题。

3.4。ICBD

主提出的问题是一个放松的整数配方Avalos-Rosales et al。1UPMSP-SMDST]。这个放松消除了消除子循环的约束,也就是说,约束(7),因此约束(8)和(10)。出于这个原因,主问题可能会发现工作与子循环序列,这是不可行的解决方案。然而,这种放松提供了一个严格磅和明显比完整的容易解决的问题。因此,这放松UPMSP-SMDST分解到主人的工作分配和问题在单个机器上调度子问题,用来评估子循环的存在。

主问题给出一个解决方案,工作的完成时间序列的机器吗在主的问题,下一步是确定在每台机器上任何子循环的存在通过子问题。由此产生的子问题相当于导演弧的旅行商问题,也称为非对称旅行商问题。在此表示,乔布斯的节点和节点之间的距离之间的设置时间的工作。的完成时间序列之间的距离之和的处理时间节点和工作。为每个迭代的算法和机器,一子问题生成及其完成时间是发现。当 有次循环序列,所以生成CBC和添加到主问题。最大的是迭代的考。如果小于乌兰巴托,然后它就变成了新的乌兰巴托。这个过程被称为子问题评估,其算法伪代码所示1。

拟议中的ICBD方法包括解决主问题(MP)使用过程和提出的三个子问题,直到终止条件是正确的。在每个迭代中ICBD,主池的大小问题生成一个解决方案根据multicut过程中概述部分3.2。算法1评估每一个解决方案。ICBD算法的算法2。

算法2用于限制和原主人的问题。因此,这个算法是按顺序执行两次:一次在热启动过程限制主问题,一旦与原主人的问题。热启动程序终止时在两个阶段的结论或执行时间达到允许的最长时间。原来的主人问题最优性条件时终止 或全部允许运行时。重要的是要注意,在热启动的过程中,主问题的最优解并不是一个有效的问题,因为它没有磅所有可用的变量。

4所示。计算实验

为了测试的数学公式和弯管机分解方法,他们使用API实现c++和音乐会技术解决了使用IBM ILOG最大化策略12.5。测试进行戴尔Inspiron笔记本,配有英特尔酷睿i5 - 2430 m 2.40 GHz处理器和4 GB的内存和Windows 7操作系统。任何情况下允许的最大运行时是3600年代。如果解算器无法找到最优的解决方案,最好的整数解获得报告。

计算实验是使用两个不同的执行实例集:首先使用的实例Tran和贝克8从Vallada和Ruiz[]和下一个实例11)使用Avalos-Rosales et al。1]。测试实例获得Tran和贝克8)以下配置,工作岗位的数量 和机器的数量 。设置时间间隔均匀分布:25 - 50。处理时间是5 - 200之间均匀分布。有10个数量为每个可能的组合形式复制的工作,机器,共有240个实例。测试实例从Vallada和鲁伊斯(2011) 和 。设置时间均匀分布在三个间隔:1-49,1 - 99和1 - 124。处理时间是1到99之间的均匀分布。有10个复制的每个可能的组合工作和机器,和设置时间,共有600个实例。最后的实例可用http://soa.iti.es。

实例被就业人数和机器分组。因此,每个表行代表10到30实例测试的平均结果Tran和贝克8)或Vallada鲁伊斯(11),分别。表1比较的结果Tran的弯管机分解方法和贝克8](t细胞和b),提出从Tran ICBD方法使用实例和贝克8]。列1和2是指工作和机器的数量,分别。其余的表分为三组。第一组是指平均比例差距议员的第一次迭代磅(磅₁)和最优解(选择)计算 。第二和第三组t细胞和b和ICBD方法的结果。每组的列是指数量的迭代(iter),削减削减(#),运行时间(时间)。

所有实例从Tran和贝克(8)是由两种方法来解决最优在不到3600年代。从表1有人指出t细胞和b方法的平均迭代次数为1.69。一个更详细的分析显示,44.2%的实例解决迭代(即只有一个。,the first solution of MP is equal to optimal solution) and 45.8% of instances are solved in two iterations. However 90% of instances are solved within two iterations, and the maximum number of iterations was 5 which occurred once. Therefore, with this instance set the ICBD method was performed using only the multicut procedure because other procedures only consume computational time and not bring any advantage. In the combinations 10 × 2, 10 × 3, 10 × 4, and 20 × 4 the ICBD method does not reduce the number of iterations or increase the number of cuts generated. In other combinations there were improvements, but as the number of iterations is small the improvements are also small. The biggest differences in runtimes were in the instances with five machines, usually more difficult. Moreover, the final reduction in runtime using the ICBD method compared to T&B method was 21.85%.

表2显示结果的平均百分比差距使用MP第一个解决方案和最优解(或最佳解决方案)的实例从Vallada和鲁伊斯(11]。第一列代表的工作;其余的表分为五组,第一个四组显示机器的四个数字的结果为每个就业人数和平均结果显示在第五小组。有人指出差距大于那些获得使用Tran的实例和贝克8),整体的平均差距分别为1.54%和0.16%。缺口增加机器的数量也增加,但相反的发生在增加就业的数量。

所使用的参数值ICBD方法下所示。工作集的百分比在热启动程序设置为50%和75%,分别为第一和第二阶段。每个热启动阶段的最大迭代数是8。这些参数的校准是未遂,尽管,在组合测试,没有优越的统计性能,所以这些测试不了。允许的最大时间执行的两个热启动阶段是1800年代。原来的主问题的最大执行时间是3600年代-热启动过程的总执行时间。

表3比较了混合整数规划模型的结果(MIP) Avalos-Rosales et al。1),t细胞和b方法,ICBD(三个提出过程)方法使用实例从Vallada Ruiz [11]。列1和2是指工作和机器的数量,分别。其余的表分为三组。第一组是指尚未解决的实例的数量,直到最优(#”)。第二组显示的平均百分比差距差距(%),计算 。第三组显示秒的平均CPU时间(时间)当解决实例。每组有三个列和一个为每个方法评估。值在斜体显示最好的结果为特定的工作和机器的结合。

比较三种方法,ICBD获得最好的结果三个性能标准为每一个分析。它未能解决只有31实例,MIP未能解决57实例,t细胞和b有63未解决的实例。ICBD获得最低的总体平均差距为0.07%,而t细胞和b和MIP方法获得的0.17%和0.28%,分别。在所有实例组,ICBD获得平均差距低于或等于其他方法。实例与60工作和5机器获得最高的差距:MIP, t细胞和b,和ICBD方法获得的3.18%,1.08%,和0.68%,分别。ICBD的平均执行时间是377.86秒,而t细胞和b和MIP方法的573.89和706.28年代,分别。ICBD方法少用了51.88%的运行时间比t细胞和b方法,更高的价值比获得Tran使用实例和贝克(8从Vallada和Ruiz[],因为实例11)需要更多的迭代来解决;然后提出改进方法获得更好的结果。在t细胞和b方法中,7.67%和15.17%的实例是解决了一个和两个迭代,分别从Tran比例远低于使用实例和贝克8]。结果表明,Vallada和Ruiz实例获得最优解更困难。因此,证明三个改进程序的使用。

平均迭代次数使用原来的主问题1.87 ICBD和8.90 t细胞和b,这种差异是由于平均迭代次数由热启动执行程序,也就是6.63。加在一起的数量两个迭代,ICBD方法使用平均8.5迭代。虽然两种方法几乎相同数量的迭代,迭代在热启动过程消耗更少的计算时间比原主人的问题,因为有更多的ICBD,这使得这种方法更快。的数量产生的cbc ICBD在热启动过程(56.76)高于生成执行期间原主人问题(10.07)。ICBD产生平均66.83 cbc在这两个阶段,远远超过t细胞和b方法产生的平均32.40 cbc。这是由于multicut程序。主问题的提前终止发生在所有实例平均1.89倍;然而,随着就业人数的增加,执行这个程序的次数也增加了。例如,在60工作和3机器的实例,它发生在平均4.60倍。ICBD,热启动过程的平均运行时间是193.18秒,这是大于原主人的平均运行时间的问题,这是184.68秒。 The sum of these two run times is 377.86 s, which is less than the average run time of the T&B method (573.89 s). These results are shown in Table4,列1和2是指工作和机器的数量,分别。的平均数字迭代(# iter)和削减削减(#)执行期间原主人问题测定t细胞和b和ICBD方法。此外,掌握问题的平均数字终端(# ta),热启动迭代(# ws iter)和热启动过程中产生cbc (# ws削减)测量ICBD。平均ICBD热启动过程的执行时间(ws)和原始主问题(原始时间)也被测量。

5。结论

弯管机的主问题分解提供了一个紧磅,作为第一次迭代后的最优差距最多5%的乌兰巴托。因此,该方法的困难是,可能会有许多解决方案的主问题小于原问题的最优解。直到所有这些解决方案被发现和评估子问题,该方法不能终止的差距为0%。因此,挑战在于找到这些解决方案尽快。有鉴于此,该程序寻求快速找到他们。这些程序由一个主问题的提前终止执行重复磅时发现,multicut过程评估多个解决方案,最后,热启动过程中,发现质量解决方案更快。没有程序开发加速子问题的解决方案,因为他们消耗更少的计算时间比主问题。

之前提出的加速过程没有被应用于UPMSP-SMDST。此外,他们可以使用与任何其他组合弯管机分解问题。此外,结果表明,该程序提高Tran的弯管机分解方案的性能和贝克8]。此外,该方法还表现得比整数制定Avalos-Rosales et al。1]相对于三个性能标准进行了分析。

Geoffrion所使用的方法和坟墓32解决主问题的只有一次,生成一个弯管机每次找到更好的现任解决方案测试和使用更多的计算时间比传统的方法。为什么会这样的一个假设是,要实现这个过程,有必要使用的回调函数最大化策略禁用动态搜索用于提高最大化策略的性能。体能训练时的本地分支策略Fischetti这样,洛迪(34)还测试了,但它消耗更多的计算时间找到重复的解决方案建议的程序。

未来工作的建议之一是开发一个强有力的削减,消除了更多解决方案不可行解决方案的毫无用处的人。另一个建议是开发一个启发式创建质量削减被插入到主问题开始前弯管机分解过程本身,Lunday Sherali和这样[24]。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

作者要感谢托尼·t·Tran博士提供的实例用于Tran和贝克(8),还有CNPq(国家科学和技术发展委员会),斗篷(人员改善高等教育的协调),和FAPEMIG(基础研究支持米纳斯吉拉斯州)的金融支持。