混合GRASP启发式算法解决带提前和拖期惩罚的并行机排序问题

可在www.sciencedirect.com在线获取理论计算机科学电子笔记302（2014）53-72www.elsevier.com/locate/entcs混合GRASP启发式算法求解带提前和拖期惩罚João Paulo de C.M. Nogueira2 José Elias C. 阿罗约1，3哈莱姆毛里西奥M. Villadiego 4Luciana B.贡萨尔维斯5巴西维索萨联邦大学计算机科学系摘要研究了一类以最小化总提前和拖期惩罚为目标的不相关并行机排序问题。机器和作业序列相关的设置时间和空闲时间被认为是。由于所研究的问题是NP-Hard的，我们测试的贪婪随机自适应搜索过程（GRASP）元启发式算法的基础上，以确定近最优的解决方案的适用性。我们提出了三种不同的方法。第一个是一个简单的GRASP启发式，第二个启发式包括一个基于路径重链接技术的强化过程，第三个启发式在GRASP算法的局部搜索阶段使用迭代局部搜索（ILS）启发式。使用一组小型，中型和大型的实例进行了比较，得到的结果的分析。为了比较算法的性能，进行了全面的计算和统计分析关键词：平行机排程、提早与拖期惩罚、组合最佳化、启发式演算法、局部搜寻、元分析法。1引言生产调度是生产作业层的重要决策，在制造业和服务业中起着至关重要的作用。调度问题处理在给定时间段内将可用资源分配给作业，目标是优化一个或多个目标（或标准）[38]。这些问题在文献中得到了广泛的研究[9]。主要表现在两个方面：1本研究由国家科学和技术发展委员会（CNPq）和米纳斯吉拉斯州保护宪法权利基金会（FAPEMIG）资助。2电子邮件：jpcmnogueira@gmail.com3电子邮件：jarroyo@dpi.ufv.br4 电子邮件：ufv.br5 电子邮件地址：lbrugiolo@ufv.brhttp://dx.doi.org/10.1016/j.entcs.2014.01.0201571-0661 © 2014 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。54J.P. de C.M. Nogueira et al. /Electronic Notes in Theoretical Computer Science 302（2014）53/第一个是它们的实际重要性，在几个工业中有各种应用，如化学、生物和纺织工业。第二个方面是关于这门课大多数问题解决的困难在众多的生产调度问题中，并行机调度是一个具有广泛实际意义的典型调度问题。Cheng和Sin [11]对PMS问题进行了调查研究PMS问题可以定义为一组n个作业，这些作业需要由一组m个并行机器处理。目标是调度作业（每个作业分配给m台机器中的一台），使得一个或多个标准被最小化。当m台机器上每件工件的加工时间都相同时，称该问题为相同PMS问题。在PMS问题中，研究最多的优化准则是最小化最大完工时间，这一准则被称为完工时间。Garey和Johnson [17]证明了在m= 2台相同机器上最小化最大完工时间是一个NP困难问题。PMS中还有两种类型的问题：统一的和不相关的PMS。不相关的并行机可以被描述为执行相同功能但具有不同能力或容量的机器作业的处理时间不相关平行机是最现实的情况，也是均匀同机情况的推广。在文献[33]中，对不相关并行机调度（UPMS）问题的研究要少得多。Van deVelde [48]和Martello等人已经提出了最小化完工时间的精确算法和近似算法[34].局部搜索和启发式方法也被用于最大完工时间最小化[18]，[37]，[13]，[30]。最近，在UPMS问题中考虑了其他性能标准。Lin等人[30]和Rodriguez等人[41]最小化了总加权完工时间，Liaw等人考虑了总加权延误最小化。[28]和Lin et al.[30 ]第30段。针对机器和工件顺序相关的UPMS问题，提出了一些求解方法在这种情况下，每对工件和每台机器的准备时间是不同的。也就是说，机器具有不同的设置时间，并且机器k上的作业i和j之间的设置时间不同于同一机器上的作业j和i之间的设置时间（si，j，k=sj，i，k）。具有序列相关设置时间的UPMS问题研究较少，可以在文献中找到一些论文[3]。解决这个问题最常用的方法是元分析法。为了最小化最大完工时间，Franca et al.[16]提出了一种禁忌搜索算法，Vallada和Ruiz [47]提出了一种遗传算法，Changand和Chen [10]通过将优势特性与遗传算法相结合开发了一种元启发式算法。在Kim等人[24]和Kim和Shin [23]中，分别提出了以最小化总延迟和最大延迟为目标的模拟退火和禁忌搜索算法。Logendran等人提出了一种禁忌搜索算法，以获得最小加权延误的解决方案[31 ]第30段。De Paula等人[12]Rocha et al.[40]建议，重新-J.P. de C.M. Nogueira et al. /Electronic Notes in Theoretical Computer Science 302（2014）5355最小化加权总延误时间和最大完工时间的搜索算法在[40]中，也开发了一个分支定界算法，用于相同的问题。对于最小化总延误，一个简单的迭代贪婪启发式林等。[29].在本文中，我们专注于UPMS问题的机器和作业序列依赖的设置时间，使总的提前和拖期（E/T）的罚款最小化。我们处理一个一般情况下，这个问题中的工作有不同的到期日和机器空闲时间是允许的。没有插入空闲时间的假设与提前/迟到标准不一致，因为提前是一种不规则的性能度量[6]。与E/T相关的标准在JIT生产环境中非常重要。在JIT生产中，工作应该在尽可能接近到期日的时间内完成：无论是提前还是迟到都应该被劝阻。这是由于一个事实，即早期的工作可能会导致库存持有成本，如机会成本的钱投资于库存，储存和保险费用和恶化。实际上，一个迟到的工作可能会导致客户不满，合同处罚，销售损失和声誉损失因此，涉及E/T成本的标准最近受到了极大的关注[27]。许多研究同时考虑了E/T惩罚，处理单机问题[6]，[25]，[45]，[49]，[5]。只有少数作品研究了par-pronounced机器的问题Biskup和Cheng [8]解决了相同的PMS问题，目标是最小化提前，迟到和完成时间惩罚。他们证明了这个问题是NP难的，并提出了一个有效的启发式算法。Sivrikaya和Ulusoy [44]开发了两种遗传算法来解决带有E/T惩罚的PMS问题，其中作业具有不同的到期日。这些作者考虑序列依赖的设置。Bank和Werner [7]考虑了UPMS关于重新租赁日期以及共同到期日的问题。他们提出了建设性的和局部搜索算法，以最小化E/T惩罚的加权和后来，Kedad-Sidhoum等人。[22]提出了具有不同到期日和E/T成本的相同PMS问题的有效下限。他们还提出了一个简单的局部搜索算法，以获得上限。 他们开发了一个混合整数模型，并提出了基于遗传算法和模拟退火的混合遗传算法，以最小化总加权E/T。Vallada和Ruiz [46]研究了具有机器和作业序列相关准备时间的UPMS问题，目标是最小化总加权E/T。他们的研究允许有空闲时间。Kayvanfa等人。[21]研究了具有序列相关设置时间的UPMS问题，目标是最小化总加权E/T，完工时间以及工作成本压缩和扩展取决于压缩/扩展量。他们还假设工作的到期日是不同的，机器空闲时间是不允许的。为了解决中型到大型的实例，他们采用了启发式和元启发式方法。在本文中，我们开发了三种基于GRASP方法学的方法学[14]。第一个启发式算法是一个基本的GRASP算法，它包括两个阶段：56J.P. de C.M. Nogueira et al. /Electronic Notes in Theoretical Computer Science 302（2014）53Σ----{−}{− }解决方案构造阶段，其随机构造贪婪解决方案;以及改进阶段，其使用该解决方案作为初始起点。第二个启发式算法是GRASP与路径重链接的混合[19]。在第三个启发式中，我们使用ILS启发式[32]作为GRASP的改进过程GRASP和ILS是元启发式算法，已被应用于解决各种组合优化问题[15]，[32]。路径重新链接是一种搜索强化过程，它在邻域解空间中探索连接两个高质量解的路径PR和GRASP的杂交增加了GRASP的记忆机制本文的其余部分组织如下。在第2节中给出了所述UPMS问题的定义和混合规划模型公式我们在第一节中详细描述了所提出的化学方法3.第4节讨论了计算结果。最后，第五部分总结了本文，并为未来的研究提供了一些有益的方向2问题陈述与数学模型本文研究的UPMS问题如下所述。有一个集合J=1，…，n中的n个必须在集合M= 1，...，m台并行机。每台机器都是连续可用的，一次最多只能处理一个作业不允许作业抢占 每个工件j在时间0变为可用，在机器k上有一个加工时间p j，k，一个交货期dj，以及提前（α j）和拖期（βj）概率。在机器k上加工两个连续工件i和j时，可考虑与顺序有关的准备时间si，j，k。在机器上处理第一个作业之前，我们不考虑设置时间。在这个问题中，允许出现机器空闲时间机器上的空闲时间可能需要在其到期日完成作业，以避免过早。该问题的目标是确定一个可行的时间表，使总的提前和拖期惩罚的工件是最小的。对于时间表s，最小化准则计算为：nf（s）=（αj Ej+βj Tj）（1）j=1其中，Ej=max0，djCj是工件j的提前量，Tj=max0，Cjdj是工件j的拖期，Cj是工件j的完成时间。注意，当作业j在其到期日之前完成时，它是早的（C jdj）时，i具有拖期。 对早熟和迟熟的惩罚分别由α jEj和β jTj决定。根据Graham et al. [20]中，我们所研究的问题可以表示为R/sijk/（α iEi +βiTi），其中R是不相关的并行机环境，sijk是机器和工件序列相关的准备时间，（αiEi +β iTi）是目标函数。我们提供了一个混合规划（MIP）模型的UPMS问题与序列相关的设置时间。该模型是基于MIP模型的预处理，J.P. de C.M. Nogueira et al. /Electronic Notes in Theoretical Computer Science 302（2014）5357⎨ΣΣΣΣ作者：Morabito et al.[4]求总提前和拖期最小化。该模型使用虚拟作业0来标记每台机器上作业序列的开始和结束。该模型涉及以下决策变量：Ci，k=工件i在机器k上的完成时间E i=工件iTi=作业i的延误xi，j，k=101，如果在机器k作业i在作业j000，否则。nmin（αi Ei+βi Ti）（2）i=1M nx i，j，k= 1，j = 1，.， n（3）k=1i=0i/=jnx0，j，k≤ 1，k=1，...， 中文（简体）j=1n nx i，h，k−n，k = 1，...，中文（简体）i=0i/=hj=0j/=hC0，k= 0，k = 1，...，中文（简体）Cj，k≥C i，k−M+（p j，k+s i，j，k+M）x i，j，k，i= 0，.，n，j = 1，...，n，k = 1，...， 中文（简体）E i≥d i− C i，k，i = 1，.，n，k = 1，...， 中文（简体）T i≥C i，k− d i，i = 1，.，n，k = 1，...， 中文（简体）T i≥ 0，E i≥ 0， i = 1，.，n（10）x i，j，k∈ {0，1}，i，j = 0，...，n，k = 1，...，M.（十一）目标函数（2）是最小化总的加权提前/迟到惩罚。 约束集（3）确保每个作业j都被分配只有一台机器，只有一个前任。约束条件（4）将虚拟作业0的后继作业的数量限制为在每台机器上最多一个K. 约束（5）确保每个作业h都有一个后继者，除了在机器上建立作业顺序的开始和结束的一种虚拟作业数学模型为：58J.P. de C.M. Nogueira et al. /Electronic Notes in Theoretical Computer Science 302（2014）53K.对于作业0，约束（6）规定该作业在每台机器上的完成时间等于零。约束集（7）是控制机器上工件的完成时间如果作业j在作业i之后被分配给机器k（即，xi，j，k=1），其完成时间Cj，k必须大于i，Ci，k的完成时间，加上J.P. de C.M. Nogueira et al. /Electronic Notes in Theoretical Computer Science 302（2014）5359i和j之间的建立时间以及j的处理时间。如果xi，j，k=0，那么大常数M使约束变得多余。约束（8）和（9）分别定义了每个作业的提前和拖后最后，约束集（10）确定非负性条件，约束集（11）定义二元变量。3提出的启发式算法为了获得R/sijk/（αiEi+βiTi）问题的近似最优解，我们在贪婪随机自适应搜索过程（GRASP）元启发式的基础上开发了树启发式算法. GRASP最初由Feo和Rescue[14]提出，是一种多起点（迭代）两阶段方法，基本上由解构造阶段和改进阶段组成。构造阶段随机地逐步构建贪婪解，向部分解添加元素当一个可行的解决方案已经建立，它的邻居是探索在一个局部搜索阶段，直到找到一个局部最优。在给定的预先指定的迭代次数（或终止标准）之后产生的最佳解决方案作为输出返回GRASP算法适应性强，已成功应用于多个NP难组合优化问题[15]。 在这项工作中，我们首先开发了一个适应的基本GRASP算法的sijk/（α i E i+ β i T i）的问题。然后，我们使用路径重链接（PR）技术，以提高GRASP的性能。这种技术被用作一种强化策略，以组合在迭代过程中获得的最佳 我们还提出了一种混合启发式算法，该算法将GRASP算法与迭代局部搜索（ILS）元启发式算法相结合[32]。ILS被用作GRASP算法中的标准局部搜索的替代。ILS是一种迭代算法，它在每次迭代时将扰动应用于局部最优解，然后将所得的扰动解提交给局部搜索。这三种方法分别称为基本GRASP、GRASP+PR和GRASP+ILS+PR。在接下来的小节中，首先，我们描述可行解的表示和评估。然后，我们描述了GRASP算法的各个阶段（建设和改进），PR技术和ILS局部搜索算法。3.1解决方案的表示和评价R/sijk/n（αi Ei+βi Ti）问题的解由m个作业链表（每台机器一个）表示。 每个列表表示分配给机器的作业的处理顺序。例如，对于n= 6个作业和m= 2台机器的实例，解决方案表示为s =[s1，s2]=[[1，4，6]，[2，3，5]]，其中s1=[1，4，6]和s2=[2，3，5]分别表示分配给机器1和2的 作 业 的 处 理 顺 序。为了计算给定解s的目标函数f（s），首先计算作业的最佳开始时间 在计算这些时间时，可以允许出现机器空闲时间。也就是说，机器可以空闲，直到下一个作业的处理开始。[45]第四十五话60J.P. de C.M. Nogueira et al. /Electronic Notes in Theoretical Computer Science 302（2014）53∅ ∀Wang和Yen [49]提出了计算单机排序问题工件最优开始时间的最优定时算法在这项工作中，我们适应这些算法的并行机的情况下。该算法根据每个工件对应的交货期来确定最优的开工时间和完工时间最优算法的目标是使先前确定的解的总提前和拖期惩罚最小化为了更好地理解机器空闲时间插入，我们使用了一个例子问题，有六个工件和两台机器（ n=6，m=2）。假设作业1， ... ， 6个为 d1=7， d2=10， d3=18，d4=20，d5=27d6=3.0。 设s=[[1，4，6]，[2，3，5]]为该实例的解。一最佳时间表如图1所示。在这个时间表中，第一台机器（M1）上的作业序列是[1，4，6]，第二台机器（M2）上的作业序列是[2，3，5]。不是这样的，所有的工作都在到期日结束。很容易看出，所有的机器都有空闲时间。例如，有3倍的空闲时间在作业2的完成时间（在设置时间s2，3，2之后）和作业3的开始之间，机器M2上的单元在该示例中，作业1，.，6分别为3、4、15、14、22和25。我们可以注意到，机器空闲时间是必要的，以避免工作提前。 对于同一个实例，图2显示了一个不允许空闲时间的调度。在这个进度表中，由于所有作业都在其到期日之前完成，因此会产生Fig. 1.双机调度：允许空闲时间图二、双机调度：不允许有空闲时间3.2解决方案构建阶段在GRASP算法的构造阶段，解s=[s1，...，s m]是迭代生成的，其中s k是机器k上的作业序列。 首先是空解（s k=，k=1，...，m），在每次迭代中，从限制候选列表RC中随机均匀地选择作业j j，并将其添加到恰好一个机器kJ（或序列sJk）。列表RC形成如下。首先，每个未调度的工件j被临时分配给机器k，机器k产生目标函数的最低值（已经调度的工件的工件的总提前和拖期惩罚）。然后，根据生产值排列作业，形成未调度作业的候选列表C。受限制的候选人J.P. de C.M. Nogueira et al. /Electronic Notes in Theoretical Computer Science 302（2014）5361∅∅ ∀联系我们∈×||∈||| |||联系我们- -公司简介10：选择作业j从RC中随机抽取;列表RC由具有最佳值的C的作业形成。RC的大小为r=max（1，αC），其中α[0，1]是控制数量的参数贪婪和随机性的问题。在每次构造迭代中，从C中删除选定的作业jJ，并重新排序未调度作业的列表。构造贪婪随机解的算法在所有作业都分配给机器时结束，即当C=。此时，将返回完整的解决方案。构造过程的完整伪代码可以在算法1中找到。注意，α= 0（RC=1）对应于一个贪婪构造，其中C的第一个作业总是被选择。α= 1（RC=C）产生一个随机结构，其中一个作业是从C中随机选择的。Ruiz和Andrés [42]提出的构造性启发式DJASA（Dynamic Job Assignment withSetups Resource Assignment）中也使用了未调度作业的排序方式DJASA是一种确定性贪婪启发式算法，其中总是选择有序列表的第一个作业，即提供目标函数值最小增量的作业。算法1GreedyRandomizedConstruction（α）1：设s k=，k=1，...， m;2：将所有作业添加到未调度作业的列表C（候选列表）;3：当C=do时4：for对于每个待处理的作业jCdo5：将作业j临时分配给产生目标函数的最低值的机器k（作业j的对应机器是k）;6：令g（j）为所获得的部分解的目标函数值; 7：结束，8：按照函数g的递增顺序排列C中的作业;9：设RC为由第一个max（1，α × |C|C的工作;11：将作业j′分配给相应的机器k′（sk′=sk′j′）;12：从C删除作业j′13：结束时14：返回得到的解s;3.3改进阶段在建设性阶段构建的每个解决方案都是局部搜索过程的起点，我们试图改进解决方案。在这项工作中实现的LocalSearch此方法通过在当前解决方案中进行作业插入来生成新解决方案（相邻解决方案）。插入移动通过将工件从其原始位置u移除并将其插入相同或不同机器的位置v来生成新的解决方案。邻域包含通过在当前解中进行的单次移动而到达的所有解在该邻域中，选择比当前解更好的解。所选择的解决方案成为新的解决方案（或当前解决方案），并且该过程继续，直到达到局部最小值局部搜索过程的伪代码可以在算法2中看到。解 s 的 插 入 邻 域 ， 其 中 sk= ， k=1 ， . ， 如 果 m 是 偶 数 ， 则 具 有 大 小（n2n+m），如果m是奇数，则具有大小（n2m）。考虑下面的例子，有四个作业和两台机器。解s=[[2，1]，[3，4]]的邻域为62J.P. de C.M. Nogueira et al. /Electronic Notes in Theoretical Computer Science 302（2014）53←/∈由14个解组成：s1=[[1，2]，[3，4]]，s2=[[1]，[2，3，4]]，s3=[[1]，[3，2，4]]，s4=[[1]，[3，4，2]]，s5=[[2]，[1，3，4]]，s6=[[2]，[3，1，4]]，s7=[[2]，[3，4，1]]，s8=[[3，2，1]，[4]]，s9=[[2，3，1]，[4]]，s10=[[2，1，3]，[4]]，s11=[[2，1]，[4，3]]，s12=[[4，2，1]，[3]]，s13=[[2，4，1]，[3]]，s14=[[2，1，4]，[3]]。算法2LocalSearch（s）1：确定解s，N（s）的插入邻域：2：设s′为N（s）中的较优解;3：如果f（s′）

下载后可阅读完整内容，剩余1页未读，立即下载