带交货期窗口的单机排序多目标变邻域搜索算法

可在www.sciencedirect.com在线获取理论计算机科学电子笔记281（2011）5-19www.elsevier.com/locate/entcs带不同交货期窗口单机排序问题的多目标变邻域搜索算法José Elias Claudio Arroyo1，2 Rafael dos Santos Colononi3Alcione de Paiva Oliveira2Departamento de InformáticaUniversidade Federal de ViçosaViçosa-MG-巴西摘要在本文中，我们比较了三个多目标算法的基础上可变邻域搜索（VNS）启发式。并将该算法应用于求解具有不同交货期窗口的单机排序问题。在这个问题中，我们考虑最小化总的加权提前/拖期和总的排队时间标准。我们引入了两个强化程序，以提高多目标VNS（MOVNS）算法在文献中提出。 算法的性能在一组中等和较大的问题实例上进行测试。计算结果表明，所提出的算法优于原来的MOVNS算法的解的质量。进行统计分析，以分析所提出的方法的性能关键词：多目标优化，局部搜索算法，作业调度。1引言单机调度问题（SMSP）在过去的几十年中得到了广泛的研究[16][27][4][15]。大多数的贡献考虑一个单一的优化标准，虽然在实践中，决策者往往面临几个（通常是冲突）的标准。要考虑的主要标准是最大完工时间（即最大完工时间）的最小化，总生产时间或排产时间的最小化和总延误的最小化。这些目标的使用在实践中是合理的，因为完工时间最小化意味着1本研究由国家科学和技术发展委员会（CNPq）和米纳斯吉拉斯州保护宪法权利基金会（FAPEMIG）资助。2电 子邮件：{jarroyo，alcione}@dpi.ufv.br3 电子邮件：voviz. gmail.com1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.11.0226J.E. C Arroyo et al. /Electronic Notes in Theoretical Computer Science 281（2011）5最大化的吞吐量和资源利用率，而最小化的流水时间是有关的平均周期时间最小化和低的在制品。总拖期标准与作业的交货期有关，它在制造系统中非常重要，因为当一个作业在其交货期前没有完成时，会产生一定的成本和惩罚大多数关于工件调度问题的研究都假设准备时间与工件的顺序无关[1]。然而，在生产系统中，当机器从处理一个作业切换到另一个作业时，会产生序列相关的设置时间。准备时间的大小往往取决于两个连续工件的工艺技术要求的相似性。通常情况下，如果两个连续作业在处理要求方面存在显著差异或使用不同的处理技术，则会出现较大的准备时间。在具有序列相关设置时间的SMSP中最小化单个准则是NP难问题[6] [16]，因此不太可能开发出有效的算法来精确求解它。在这项工作中，我们解决了SMSP提前和迟到的惩罚。这个问题的一般情况下，允许插入空闲时间连同不同的到期日的工作。没有插入空闲时间的假设与提前/迟到标准不一致，因为提前是一种不规则的性能度量[3]。这个调度问题是一个非常重要和常见的工业问题，是常见的大多数准时制（JIT）生产环境。JIT包括在正确的时间交付产品和服务以供立即使用，其主要目标是不断寻求生产过程的改进，这是通过减少库存来实现和发展的[20][28]。JIT调度问题在工业中非常普遍。在JIT调度环境中，作业应尽可能接近到期日完成。 早日 作业完成导致库存持有成本，例如存储和保险成本。另一方面，延迟完成工作会导致惩罚，例如损失客户的善意和声誉受损。在文献中，不同的作者从单目标的角度研究了提前和拖期惩罚的SMSP。大多数作品考虑不同或共同的截止日期。Lee和Choi [17]研究了考虑不同到期日的问题。他们提出了一个最优算法，多项式复杂性，以确定最佳的完成时间为每个工作在遗传算法（GA）确定的时间表使用这种最优算法是因为可能是有趣的预期工作，甚至支付罚款，如果罚款短于迟到产生的罚款[24]。在[21]中，还考虑了不同的交货期，并使用了结合局部搜索算法和GA的混合启发式在[11]，[20]和[29]中，研究了考虑共同交货期的问题提出了禁忌搜索、遗传算法、变邻域搜索（VNS）和恢复波束搜索等算法.Wang和Yen [28]提出了SMSP的数学公式，考虑了不同的到期窗口而不是不同的到期日，具有提前和迟到惩罚他们不考虑设置时间。Wang和Yen [28]将Lee和Choi [17]的最优定时算法扩展到具有不同到期窗口和J.E. C Arroyo et al. /Electronic Notes in Theoretical Computer Science 281（2011）57提出了禁忌搜索算法来生成近似调度。在[23]和[24]自适应遗传算法被提出来解决具有不同到期窗口和序列相关设置时间的问题在本文中，我们处理这最后一个问题，提前和tardi- ness罚款，考虑不同的由于窗口和序列相关的设置时间的SMSP。该问题的目标是确定可行的工件调度计划，以最小化总的加工时间服从最小的加权提前/拖期总惩罚。其目标是为决策者提供一组有效的时间表（帕累托最优解），使他/她可以选择最合适的解决多目标组合优化问题最常用的方法是元算法[13] [8]。元启发式方法最初被认为是用于单目标优化的，并且在其应用于非常大量的问题中取得的成功刺激了研究人员将其扩展到多目标组合优化问题。VNS元启发式多目标优化的应用是稀缺的。据我们所知，Geiger [9]提出了第一个多目标VNS（MOVNS）算法。在文献[9]中，MOVNS被应用于求解最小化不同准则组合的置换流水车间调度问题。Geiger的MOVNS在[18]和[19]中被用于解决其他多目标问题我们提出了两个算法的基础上VNS元启发式求解双目标SMSP。VNS是一种随机局部搜索方法，它基于搜索过程中邻域的系统变化。所提出的算法基于Geiger [9]开发的算法。我们包括一个基于构造非支配的解决方案，根据非支配的部分解决方案的信息，而不是评估完整的解决方案，在现有的解决方案的邻域仿真结果和比较证明了所提算法的有效性、快速性和鲁棒性本文的其余部分组织如下。 多目标问题定义见第2节。第3节提供了MOVNS算法的详细描述。计算实验的结果，以评估所提出的算法的性能报告在第4节。最后，科5是结论。2问题陈述本文研究的多目标SMSP如下。在一台连续可用的单机上有一组n个工件要处理。这台机器一次只能处理一件工作 每个工件j在时间0可用于处理，具有已知的处理时间pj，到期日w[dej，dtj]以及提前（α j）和拖期（βj）特性（dej是最早的到期日，dt j是最晚的到期日）。在两个连续作业i和j的处理之间被认为是序列相关的设置时间sij。 在这个问题中，作业j应该优选地在其到期时间w[d ej ，dtj]内完成。如果作业j的完成时间Cj在8J.E. C Arroyo et al. /Electronic Notes in Theoretical Computer Science 281（2011）5Σ∈Σ图1.一、a）有机器空闲时间的计划;（b）没有机器空闲时间的计划dueewind ow，即，ifC j[dej，dtj]，则工件j没有拖期（Tj=0）和提前期（E j=0）。否则，它会导致提前（α j E j）或延迟（β j T j）的概率。 提前和延迟分别计算为Ej=max{0，dej−C j}和T j= max{0，C j− dt j}。该问题的目标是确定可行的时间表，使最小的总加权提前/拖期惩罚的工件（ f1）和最 小的总排 队时间（ f2）。对于 作业序 列（n 个作 业的排 列） s=（i1，...，ij，.，i n），则准则f1和f2被计算为：nf1（s）=（αj Ej+βj Tj）（1）j=1Nf2（s）= Cj（2）j=1在所解决的问题中，允许机器空闲时间的发生。这可能需要在其到期窗口内完成工作，避免过早。为了计算给定时间表s的f1（s）和f2（s），首先计算s这些时间是通过使用Wang和Yen [28]提出的最佳定时算法计算的给定一个工件序列，最优定时算法根据每个工件对应的交货期窗口确定最优完工时间。该优化算法的目标是最小化每个序列的提前/拖期惩罚。在这项工作中，第一个目标（f1）被认为比第二个目标（f2）更重要。在计算作业的最优完成时间之后计算f2。下面我们给出一个例子，其中使用Wang和Yen[28]的最优定时算法例2.1让我们考虑表1中的5-job实例。为了简化示例，我们不考虑设置时间。图1（a）和（b）分别示出了作业序列（1，5，3，4，2）和（5，4，1，2，3）的调度。第一个序列的目标值为f1= 0和f2= 360。对于第二个序列，它们是f1= 580和f2=138。注意，在第一个调度表中有机器空闲时间，作业j的完成时间是相 应的duewindows[dej，dtj]的时间。一般来说，这些目标是有冲突的，这意味着改善一个目标函数的解决方案将恶化另一个目标函数。多目标优化考虑向量f（s）=（f1（s），.，f r（s））的最佳性标准。解s（在决策空间中）的图像是J.E. C Arroyo et al. /Electronic Notes in Theoretical Computer Science 281（2011）59表1包含5个作业的作业参数工作1作业2工作3job 4工作5压缩时间（pj）9158125最早到期日（dej）151502214021最迟到期日（dtj）251703018022提前惩罚（αj）32415迟到惩罚（βj）768410目标空间中的点z = f（s）。 由于相关的最优性准则往往具有冲突性，通常不存在一个单一的解决方案s同时优化f（s）的所有分量。因此，多目标优化问题中的最优性被理解为帕累托最优性的意义，并且多目标优化问题的解决方案在于识别属于帕累托或有效集合的所有元素，该集合包含不被任何其他备选方案sJ支配的所有备选方案S。为了正确地比较多目标优化问题中的两个解决方案，需要一些定义 不失一般性，我们假设最优性准则f i，i=1，.， R.定义2.2如果z=f（s）优于zJ=f（sJ），则解s优于sJ，即对于所有i，fi（s）≤fi（sJ），并且对于至少一个i，fi（s）>|RefD1|和 |RefD3|>>|RefD2| ） . 对 于 所 有 实 例 组 ， 算 法 M O VNS2 优 于 M OVNS1（|RefD2|>>|RefD1|）.在表3中，通过使用距离度量和超体积指示符来比较由三种算法获得的结果。对于每个实例组和每个算法，给出了dav、dmax和H的平均值。我们可以看到，对于所有实例组，除了n=20的实例组之外，MOVNS 3算法在三个度量方面的表现也优于其他算法。对于n=20的实例，算法MOVNS 2的性能优于MOVNS 1和MOVNS 3。对于所有的实例组，算法MOVNS 2比MOVNS 1好得多。从计算测试中，我们可以看到，最好的结果是由建议的MOVNS算法，特别是MOVNS 3版本提供。18J.E. C Arroyo et al. /Electronic Notes in Theoretical Computer Science 281（2011）5(a) dav性能度量（b）H（超卷）性能度量见图4。 间隔图为了验证结果，应用方差分析（ANOVA），以检查观察到的差异是否具有统计学显著性。采用dav和H测量作为响应变量进行了ANOVA。所有测试均以95%的置信水平（α=0. 05）的情况。 关于dav和H，ANOVA分析表明，三种算法的这些测量值具有统计学差异（p值= 0.00）。从单个95%置信区间中，我们观察到算法的区间不重叠。这意味着所考虑的措施在统计上是不同的。我们还对Tukey进行了多重比较检验，以验证结果是否具有统计学意义。图4a和图4b分别描述了ANOVA检验的Tukey置信区间均值图（置信水平为95%），并报告了响应变量dav和H我们可以清楚地看到，在算法之间的dav和H值之间存在统计上的显著差异。我们可以观察到，算法MOVNS 3表现出最好的性能。5结论本文应用Geiger [9]的MOVNS算法求解具有不同交货期窗口的单机排序问题。两个标准同时最小化，总提前/拖期惩罚和总排队时间。我们提出了两个新版本的MOVNS 算 法 ， 命 名 为 MOVNS 2 和 MOVNS 3 。 我 们 的 算 法 使 用 基 于 部 分enumeration启发式的强化过程。应注意的是，通过使用强化程序，溶液质量显著提高。通过计算实验和统计分析，我们可以得出结论，所提出的算法（MOVNS 2和MOVNS 3）显示出优于原始MOVNS的优异性能。为进一步研究，本文的工作将扩展到将MOVNS强化应用于解决其他调度问题。J.E. C Arroyo et al. /Electronic Notes in Theoretical Computer Science 281（2011）519引用[1] Allahverdi，A.，C.T. Ng，T.C.E. Cheng和M.Y. Kovalyov，具有安装时间或成本的，Eur。Jour. ofOperational Research，187，（2008），985-1032.[2] 阿罗约，J.E.C.，P.S.维埃拉和D.S. Vianna，A GRASP algorithm for the multi-criteria minimumspanning tree problem，Annals of Operations Research，159，（2008），125-133.[3] Baker，K.R.和G.D.施明德，早迟惩罚排序，运筹学，第38期，（1990），第22 -36页.[4] 陈威J.，最小化周期维修单机排序问题的总加工时间，Jour。of the Operational Research Society，57，（2005），410-415.[5] Czyzak，P.和A. 杨文，多目标优化的一种新方法--帕累托模拟退火算法，北京大学出版社，1998年，第7期，第34-47页。[6] 杜，J.，还有J.Y.T. Leung，Minimizing total tardency on one machine is NP-hard，Mathematics of Operations Research，15，（1990），483-495.[7] Framinan，J.M.和R. Leisten，一个多目标迭代贪婪搜索的最大完工时间和最短工期标准的车间调度，ORSpectrum，30（2008），787 -804。[8] 冈迪布勒角和M. Ehrgott，1984-2004，多目标元分析学20年，计算机科学讲义，3410，（2005），33-46。[9] Geiger，M.J.，随机变量邻域搜索多目标优化，第四届欧盟/ME：先进的混合元启发式设计和评估，（2004），34-42。[10] Hansen，P. and N.陈文辉，变邻域搜索，“元搜索方法”，李文辉。Eds. Kluwer Academic，（2003），145-184.[11] 日野，C.M.，D.P. Ronconi和A.B.最小化提前和拖期惩罚在一个单一的机器问题与一个共同的交货期，欧洲。Jour. 运筹学，160，（2005），190-201。[12] Ishibuchi，H.，T. Yoshida和T.李明，多目标置换遗传算法的遗传局部搜索与多目标置换遗传算法的比较，北京：计算机科学出版社，2003年，第7期，第204-223页。[13] 琼斯，D.F.，S.K. Mirrazavi和M. Tamiz，多目标元分析：当前最新技术的概述，Eur。Jour. 《运筹学》，137，（2002），1-19。[14] 诺 尔 斯 ， J.D. ， 和 D.W.Corne ， On metrics for comparing non-dominated sets ， in ： Proc. ofCongress on Evolutionary Computation，Hawaii，（2002），711-716。[15] Kuo，W-H. D-L。杨，基于时间学习的单机最大完工时间调度问题，信息处理快报，97，（2006），64-67。[16] Lenstra，J.K.，AHGR Kan和P. Brucker，机器调度问题的复杂性，离散数学年鉴（1977），343-362。[17] Lee，C.Y.蔡 玉 杰 ， 一 种 求 解 具 有 不 同 交 货 期 和 一 般 迟 到 惩 罚 权 重 的 ， 计 算 机 运 筹 学 ， 22（ 8） ，（1995），857-869。[18] Liang，Y-C.，H-L. A. Chen和C-Y.田，多目标并行机调度问题的变邻域搜索，第八届信息与管理科学国际会议论文集（IMS 2009），中国，（2009），519-522。[19] Liang，Y-C和M-H。Lo，使用可变邻域搜索算法的多目标冗余分配优化，Jour. of Heuristics，16，（2010），511-535.[20] Liao，C-J.和C-Cg.程，基于变邻域搜索的单机加权提前和拖期问题，计算机工程，52，（2007），404-413.[21] M'Hallah河，Minimizing total earliness and tardiness on a single machine using a hybrid heuristic，Computers Operations Research，34，（2007），3126-3142.[22] Mladenovic，N.和p.汉森，可变邻域搜索，计算机和运筹学，24，（1997），1097-1100.20J.E. C Arroyo et al. /Electronic Notes in Theoretical Computer Science 281（2011）5[23] 里贝罗，F.F.，Souza，S.R.和Souza，M.J.F.，一个自适应遗传算法求解单机调度问题的提前和拖期惩罚，在：IEEE国际会议上系统，人，和控制论。San Antonio，USA，（2009），698-703.[24] 里贝罗，F.F.，S.R. Souza，M.J.F. Souza和R.M. Gomes，一种求解具有提前和拖期的单机