文摘

本文的目的是分析,模型,解决延期问题在动态置换流水车间环境,同时考虑几个标准来优化。搜索多目标优化问题的最优解可能是困难的,因为这些目标是表达不同的概念,不具有直接可比性。因此,它是不可能减少问题简略优化,和一组有效的(nondominated)解决方案,所谓帕累托前沿,必须找到。此外,在生产环境中,破坏性的变化通常出现在调度问题,如机器故障或新的就业机会的到来,导致需要快速适应。本文提出这类问题的数学模型和一个重启迭代帕累托贪婪(RIPG) metaheuristic用来找到最优帕累托。为了演示这种方法的适当性,该算法应用于一个基准专门设计在这项研究中,考虑三个目标函数(考,总加权迟到,和稳定性)和三个类别的中断(新工作,机器故障,和操作时间)的变化。实验研究表明该方法能有效地解决在多目标环境中重新安排任务。

1。介绍

调度生产系统地址排序的问题,制造一系列的工作分配给不同的机器在生产环境中受特定的需求。自1950年代以来,这些复杂的问题(np难)类型如图所示Garey et al。1)已经被科学界研究深度。

流水车间系统寻求最优调度”n”乔布斯{j₁,j₂、…j_n}"米“机器{米₁,米₂、…米_米}。每个工作由“米”任务,我^th正在处理的任务的机器米_我。在每一个特定的时间内,每台机器处理一个任务。因此,完成一个工作的机器上我,这台机器必须是可用的,并且工作机器”米−1”应该被完全处理。

在每台机器作业调度是相同的时,有一个置换流水车间的问题(PFSP),通常假定没有优先级在不同工作任务或中断。PFSP本文解决的问题,因为它有很多实际应用,尽管其他环境可能出现,如阻塞流水车间问题[2)或综合规划和调度生产系统(3,4]。

由于组合的性质问题,阶乘的订单,安排数量的增加n!

多目标优化寻求识别最有利的解决方案,同时分析多个矛盾的目标(例如,成本,质量,或时间)。每一个目标可以测量在不同的单位或者有不同的含义,使其无法比拟的。因此,他们不允许一个可能的所有标准来获得最优解。虽然找到有效的解决方案(称为nondominated),最终的目标是获得nondominated解决方案的集团,也称为帕累托最优的解决方案,使帕累托面前。随后,决策者会选择更好的满足业务需求的解决方案。

多目标优化问题需要使用指标,允许比较的性能效率Pareto-Front得到每一个算法。基于多目标优化的文献,以下指标选择:(我)超体积(5](2)一元ε指标(6- - - - - -8]

用于解决多目标优化问题的方法通常是基于标量(9)或metaheuristic技术(10]。关于标量方法,很多策略可以用来设置目标权重:常规(公告),动态(DWA),随机(风险权重),砰砰的枪声加权聚合(BWA)。他们试图将多目标问题转化为一个,通过修改目标函数的权重在每个流程步骤为了找到Pareto-front解集。其他标量方法epsilon-constraint,目标规划,辞典编纂的秩序。

关于metaheuristic方法,有技术支持的进化算法(11- - - - - -17),粒子群优化系统(18),禁忌搜索(19),模拟退火(20.- - - - - -22,蚁群23,24],贪心算法[25),或局部搜索方法(26]。

这些方法大多数论文研究biobjective问题更容易表示图形,其结果更容易分析。当前算法的限制通常是分析与更多的解决问题的目标函数,随后设计新技术允许有效地解决特定的问题(27,28]。

本文以以下方式结构。首先,重新安排计划研究在文献评论。一旦问题的数学公式定义为一个整数线性规划模型,重新安排架构提出了基于predictive-reactive策略来解决这个问题。接下来,RIPG metaheuristic描述和验证在一个静态Dubois-Lacoste实例,biobjective环境。校准参数后,RIPG metaheuristic应用于专门为本文设计的基准。最后,获得的比较结果,讨论和论文的主要结论。

2。重新安排系统

在经典调度问题,已知一组初始的工作安排必须考虑系统中可用的机器和现有技术限制。这种静态(也所谓的离线)方法假定就业测序和事先已知系统的配置和持续时间。在实际生产环境中,可能会有新工作移民,以及某些事件,事先不知道,诱发的变化需要一个新的计划,如在机械故障或预防性维护活动或工作的优先级的变化。这些条件使得有必要把活力在调度系统中,通过重组工作,静态方法不是最优的了。重新安排是实现当前调度的过程中适应可能出现的中断。这一过程的基本阶段如下:(我)延期策略,必要时需要定义一个新的生产计划(2)指定的重组政策,指定的时间和方式进行重排过程(3)设计技术更新原来的时间表

主要有三个延期策略文献中描述:predictive-reactive,主动(或健壮的)和动态(29日- - - - - -32),其中predictive-reactive一个被选中。此外,三个政策通常是用来完成重新安排的工作在这个方法:事件驱动、周期性和混合(33),其中第二个选择。也有三个主要的过程可以实现non-feasible时间表将在生产系统中断的发生:右移位延期(34,35),部分再生(34),并完成再生(36,37),最后被使用。

指标通常用于评估重组性能可以基于效率(例如,考、平均流动时间或总加权迟到)或鲁棒性(例如,系统的稳定,平均为普费弗等人提出的。33])。

在文献中,有几乎没有任何论文封面重新安排在动态,与置换流水车间环境和多目标函数。Itayef et al。38)和Liefooghe et al。39)开发了算法集中在寻找nondominated解决方案与proactive-reactive PFSP环境策略不使用目标函数加权法。Itayef et al。38)使用多目标模拟退火算法(MOSA)而Liefooghe et al。39]提出了基于超体积metaheuristics,称为指标进化算法(IBEA)。刘等人。40)提出了一种改进的迭代贪婪算法(eIG_Rep),引入一个有效的逃避机制从局部最优,需要考虑PFSP新订单的到来。

同样,文学不富于当延期分析扩展到环境不同于PFSP环境。熊等。41适应NSGA-II, Nondominated排序遗传算法(12),随机柔性工作车间问题(FJSP)。[[42)开发了一种多目标遗传算法来最小化调度总迟到和稳定的环境中并行机器和工作交付日期的变化。Zhang et al。43]提出了基于分解的多目标进化算法的应用(MOEA / D)来解决混合流水车间延期问题2目标(时间与稳定:工作岗位数量分配到不同的机器和原计划)和随机机器故障。他等。44)实现NSGA-III算法(27)解决冲订单的延期问题的混合流水车间系统考虑三个目标:考,总运输时间和序列的稳定性。在审查延期技术由维埃拉et al。(45)和Ouelhadj罗维奇(46),predictive-reactive策略被确定为最常用。

3所示。建议的解决方案

首先,没有发现参考文献中,一个数学公式来解决这种类型的问题,提出了整数线性规划模型。模型试图优化三个目标函数极小化,总加权迟到(行),为了提高生产力和稳定性(1)生产环境中(通过减少考),(2)客户服务(通过最小化行波管),和(3)进度延期的稳定过程当面对不同的突然中断。

随后,提出重新安排系统的体系结构,描述了它的实现,应用RIPG方法。RIPG non-population-based算法最近由Ciavotta et al。25),应用于biobjective PFSP环境。本文使用的算法在不同的上下文中,已经适应了动态重新安排架构开发和优化使用三个目标函数定义:极小化加权总迟到,稳定。

3.1。数学模型

之前制定的数学模型,科学文献处理不确定性和多目标优化方法将简要讨论。Razmi et al。47)提出了一个数学模型,包括通过模糊加工时间的不确定性,也就是说,一个随机模型,处理时间不输入数据模型,但与一个已知的概率分布的随机变量。对于多目标环境,Itayef et al。38制定一个biobjective数学模型来解决新就业机会的到来,从而最小化最大完工时间的任务,提高计划的稳定性。在这种模型中,两个独立的工作被认为是:新移民系统,和工作在之前已经安排重新安排时间。

Fattahi和Fallahi48制定一个动态FJSP考虑延期时间的起始时间和延期时间(RT),试图优化两个目标:考和稳定性。为了模型FJSP系统,限制操作优先级包括(这种类型的约束不存在PFSP问题)。

Ramezanian et al。49)提出了一个数学模型来制定biobjective PFSP,目的是减少股票的线性组合工作成本和后期发布成本,包括机器的工作的起始时间(发布时间)。写的论文Thornblad [50]在FJSP解释数学公式分析目标函数的重要性在发展中解决问题的方法。这一分析,提出了不同的配方,在这所谓的time-indexed模型,基于调度的时间离散化时期,突出。不同配方进行评估时考虑的目标考迟到和完整性之间的平均时间工作,观察性能的差异,这取决于目标达到。

叶尼塞和Yagmahan51)被认为是静态的,多目标PFSP配方包括三个时间的分析类型:等待时间(工作机)、预处理时间工作(工作前处理系统就绪时间),和处理时间。李等人。52)提出了一个数学公式PFSP延期问题,包括破机器的恢复时间目标是最小化bi-criteria函数而比重极小化和系统稳定性(计算工作的数量有一个不同于释放时间计划释放时间计算在之前延期点)。最后,元阴(53当地搜索)开发了一种模糊多目标分解(FMOLSD)算法来解决biobjective问题时间和总流程时间,同时考虑模糊加工时间的工作安排在一个置换流水车间的问题。

解决问题的数学公式是详细的在下面。这个配方是基于前面提到的方法和具有新的特点。因为这是一个PFSP,每个工作必须访问每台机器遵循同样的处理顺序,也就是说,从第一个到最后一个机器。的问题,以下因素被认为是:(1)重叠是不允许相同的工作在连续操作;即新操作的工作不能开始,直到前面的工作是完成的操作。(2)工作优先购买权是不允许的;也就是说,每个工作必须等到前面的工作已经完成了为了在同一台机器上进行处理。(3)有无限的缓冲区(中间存储区域)在两台机器之间。(4)所有的工作已经开始处理系统必须保持在任何类型的中断时调度顺序。(5)所有工作中断由于中断必须保持在他们指定的机器,必要时悬而未决的工作被推迟。工作不受中断影响,所以不推迟,将继续正常的过程。(6)重新安排定期进行;因此,两种类型的工作系统中存在:那些已经正在处理的安排顺序不能改变,和那些可以改变(新工作岗位和工作尚未开始处理)。重要的是要考虑就业,正在处理,因为根据出现的中断(例如,机器故障),将建立一个特定的最低起始时间为下一个传入的工作系统中(为了处理第一个机器)。(7)机器故障可能出现在任何时间,而不是只有当机器很忙。(8)如果出现机器故障处理工作时,将重启处理工作在中断发生的地方。(9)当工作出现的处理时间的变化,新处理时间是固定的,直到下一个处理时间变化发生在同样的工作。

因为它是predictive-reactive重新安排过程中,混合整数线性规划(MILP)模型可以在每个延期点运行,这意味着过去中断(新工作、处理时间的变化和机器故障)收到每延期期间发生在模型中作为输入。这些中断影响接下来的日程安排。因此,没有预测破坏被认为是在这个配方。

问题是由三个有限集:(我)J:新工作的集合计划从1,…,n(2)米:机器的设置从1…米(3)O:每个工作的组操作在每台机器从1,…,米在这里,J_我是工作我^th排列的位置。

模型中使用的参数如下:(我)p_ij:处理时间的工作J_我€J在机j。(2)d_我:工作的交付日期J_我€J。(3) :工作的优先级(重量)我关于剩下的工作。(iv)rl_我(发布时间):一旦新工作已经到达系统,发布时间是工作所需的时间我可用来再加工的生产环境。(v)rt_j(准备时间):时间机器j准备过程的新工作。这个输入数据向量代表了最初状态的机器在进行新的调度。它计算基于当前时间,出现的中断和调度方案在前面的延期点计算。这是一个重要的因素,因为它不能认为所有的机器最初是可用的。(vi)RT:当前时间。这代表了当前在生产环境中重新安排。(七)考虑到进度稳定性判据,未经加工的工作基地计划的数量(n_{没有加工过的})需要定义,包括新移民系统,其起始时间的工作安排在每台机器的基地 ,当前延期即时(RT)、规模和比例常数(按照使用的价值= 10 Pfeiffer et al。33),用于二次处罚方法适用于起始时间变化基本计划对RT)。(八) :机器的故障即时j。(第九) :复苏即时故障的机器j。(x)大米:大型常数(大米⟶∞)。

决策变量而言,以下被认为是:(我)二进制变量代表的位置中的每个工作计划安排: (2)C_我工作职位:完成时间我。(3)C_我,j工作职位:完成时间我,在机j。(iv)年代_我,j:工作的起始时间我,在机j。(v)二进制变量表明在何种情况下发生机器故障(三个情况是模仿):(一) :1如果操作价值故障发生之前完成;也就是说,时间操作完成小于机器的故障的起点。(b) :1如果操作价值还没有完成的时候发生故障;也就是说,时间操作完成与机器的故障重叠的起点。(c) :1如果操作价值后一个起始时间的时候机器坏了。(vi)C_马克斯行波管,机顶盒:这些变量对应的最大完成时间的任务,总加权迟到,分别和时间表稳定。

数学模型的MILP配方置换流水车间重新安排问题是基于以下方程。

问题的目标是最小化最大完工时间的,总加权迟到(行)和进度计划的稳定性(机顶盒),获得最优帕累托前沿(PF):

考是计算最大完工时间的所有的工作,它对应于最后的完成时间安排工作,也就是说,当最后一个任务在过去的机器完成:

总完工时间为每一个工作,C_我定义由以下方程,根据完成时间在过去的机器米: 在哪里米是系统的机器。

更具体地说,每项工作的完成时间我在每台机器上j考虑以下组件:(我)的时间工作我可以开始处理机器吗j。这个时间取决于以下:(一)工作的完成时间我前面的机器上 。(b)前一份工作的完成时间,位于位置(我−1),对当前机器j 。(c)这些条款将即时的最大的时间工作我可以开始处理机器吗j 。(2)工作的处理时间我在机j 。(3)时间机器的故障j当工作我在处理 。

在计算完成时间和机器故障,以下方程建模,考虑了三种可能的故障情况:

如果出现故障前的操作完成,

如果出现故障,而操作正在处理,有必要工作等到机器准备好了再来继续处理:

最后,如果操作工作尚未开始,必须等到机器故障已经完成:

尽管上述方程包含max函数(即不是线性),它们可以使用大,线性化的方式表达米加上二进制变量表示,被大多数的商业解决方案和自动转换尊重MILP问题的配方。

如果机器出现故障,只有这三种情形之一出现;这可以确保包括以下方程:

每个工作的起始时间我在每台机器上j取决于以下方程:

为了定义开始次MILP模型,使用下面的方程。

操作不能开始,直到前面的操作工作在同一台机器上完成: 和操作不能开始,直到前面的操作同样的工作已经完成:

工作的起始时间我在第一台机器必须大于整体释放时间,因为这是当该工作准备开始处理:

因为并不是所有的机器都是最初,为了能够处理接下来的工作,重要的是要考虑到工作的起始时间不能开始,直到机器可用;也就是说,

如果有延误,当工作完成时间大于其交付——总加权迟到(行)计算加权和总完工时间为每个任务之间的差异和它的交货日期,根据他们的分配优先级权重( ):

用于建模的MILP问题,下列方程包括:

第三个目标函数考虑问题是稳定(机顶盒),对基本安排在前面的计算周期(基线)。稳定表示为的平均值的绝对差异未加工的工作开始时间,添加一个点球,取决于基本计划的起始时间的变化对当前RT,未处理的任务被定义为那些以前的工作被安排在之前点的重新安排和尚未开始处理系统在当前RT:

绝对值函数用于计算稳定性的目标是nondifferentiable除了是非线性的。不过,它可以表示一个整数线性方式,如下:

两个新的二进制变量d_1j和d_2j介绍,以及一个大型恒大米MILP配方,下列方程:

如果d₁在开始时间= 1,然后δ值 ;否则,如果d₂= 1,需要值 。

最后,模型可以确保工作必须在一个位置,只有一个工作可以在任何位置存在的时间表。这是通过以下方程:

3.2。重新安排架构

延期策略是基于使用predictive-reactive方法;因此,基线计划首先是生成的,然后根据中断,出现在系统更新。定期重新安排政策通过时间窗。最后,重新安排方法包括一个完整的重新安排基于启发式/ metaheuristic算法(重排方法我们提出RIPG算法,在下一节中详细描述)。RIPG被选中,因为它有效的行为在静态多目标置换流水车间问题[25)是一种很有前途的技术,动态环境下学习。提出延期架构如图1。

最初,基线计划是根据生成流水车间相关制度和工作计划。然后,每天同步控制T单位时间的顺序进行重排过程系统中出现中断时,获得的Pareto-front输出解决方案中每个执行延期间隔。指定一个适当的时期是很重要的,基于问题的维度,对于每个重排过程。在这篇文章中,这一时期被计算为工作的最大完成时间(C_马克斯)除以总数量的延期点系统上执行(我们认为5延期点,因为它是一个适当的数量来评估架构适应能力,不过分增加系统中执行的数量)。

同样,在每个角度重新安排,有必要选择一个代表计算帕累托前沿解决方案。所选择的解决方案将被用作一个基线计划为每一个新的延期使用。这个基地计划的根本重要性在于它使用在评估目标函数的稳定。计算帕累托的代表解决方案方面,膝盖点方法(54- - - - - -56]。详细描述曲线拐点的方法用来计算这最有代表性的解决方案可以在Valledor et al。57]。

3.3。重新启动迭代贪婪算法

发达RIPG算法的实现是基于提出的设计Ciavotta et al。25]。他们的应用程序的技术解释使用biobjective PFSP, Taillard实例及其结果,17比较RIPG技术和算法,包括MOSA和多目标禁忌搜索(著)。Ciavotta et al。25)描述了RIPG作为最先进的方法,因为它出色的结果与最好的方法相比以前的文学。RIPG算法是一个搞笑的延伸(迭代贪婪)技术提出的鲁伊兹和Stutzle58]。这些技术属于随机局部搜索(SLS)类别。RIPG技术包括5个阶段,如图2:第一阶段。首先,确定一个初始解集(ISS)基于不同的简单的启发式方法的执行。更具体地说,NEH启发式(59,60),每一个被应用与不同的目标函数获得可接受的解决方案。的两个解决方案获得通过启发式贪婪的阶段(阶段3)下面描述,生成一组初始的nondominated解决方案(工作集)。第二阶段。第二,优化循环开始选择一个解决方案的过程中通过修改后的拥挤距离任务(MCDA)方法,为了提高工作集在贪婪的阶段。MCDA过程接收工作集作为输入参数,并计算每一个解决方案的距离。选择的解决方案是最大的一个修改拥挤距离(MCD)值,恰逢解决方案在人烟稀少的搜索空间。主要区别MCDA和拥挤距离分配(CDA),提出了最初的NSGA-II [12),第一个方法考虑的次数,一个解决方案被选中时,使它不被选择的机会。第三阶段。下一步,贪婪的执行阶段。选择的解决方案是修改通过应用一个破坏操作来消除sub-schedule工作的解决方案,一个贪婪的过程,称为施工操作,插入每个消除工作的一个可能的安排职位。通过这种方式,一个解决方案创建池。第四阶段。接下来,再一次被MCDA方法,选择一个解决方案从溶液池生成在贪婪的阶段,和一个改进的局部搜索方法。作为本地搜索,我们应用提出的经典方法一样Ciavotta et al。25),n_选取工作是随机选择;然后,他们每个人将被淘汰的时间表和重新插入n_马嘶声连续位置,其中一半在初始位置的选定工作,另一半跟随它。一旦所有的动作进行选择的工作,随后生成解决方案评估,主导解决方案消除了。nondominated解决方案添加到工作集。阶段5。最后,重启机制实现的解决方案只能防止算法达到局部最优解,导致停滞效应。机制是简单和可靠的;它由存储组nondominated解决方案在一个外部文件工作集,随后,随机重新启动工作集。这个重启过程启动如果工作集的大小,也就是说,nondominated解决发现的数量,直到那个时候,没有一个预设的迭代次数不同。

RIPG算法需要的配置5输入参数:设置的大小的解决方案(工作集),k(连续的元素在贪婪的破坏操作阶段消除),n_选取(随机选择的元素数量在本地搜索阶段),n_马嘶声(连续工作的职位的数量重新插入本地搜索阶段),并重新启动阈值(允许的最大迭代次数,无需修改nondominated解集的大小;一旦超过了这个极限,工作集自动重启)。

4所示。结果与讨论

4.1。实验设计

缺乏一个共同计划评估PFSP导致延期问题的生成数据库,允许在生产环境中使用不同的中断(新工作,机器故障,等等)和评估一个多目标优化问题。主数据库评估PFSPs建立了Taillard [61年]最初生成的实例应用到简略环境,最小化完工时间的工作。随后,这些实例修改将每个作业的截止日期,类似于Minella et al。62年]和Hasija Rajendran [63年),允许延期系统评估不同目标函数下,如总加权迟到(行)或最大延迟的工作(64年]。

在提出延期系统中,原计划生效后,随着时间的推移可能出现不同的中断。NEH启发式(使用59,65年)达到原定计划以优化时间。Minella et al。62年也使用它有一个可行的原定计划。此外,在我们的基准生成,破坏被认为是定义和他们的方式发生。尽管大多数重新安排系统专注于一个类型的中断,在这篇文章中,我们使用三:机器故障,新工作移民,变量处理时间。

机器故障定义通过指数分布定义为故障系统达到的水平,平均修复时间(MTTR)和平均故障间隔时间(MTBF)。故障级别(Ag)、机器故障时间的百分比,估计通过以下表达式:

我们跟随着机器故障参数化提出的阿迪比et al。66年和梅森et al。67年]。关于新工作的移民,还收养了一个指数分布与到达率之间基于商系统的使用程度和平均运行时间68年]。关于工作的偏差处理时间,他们随机生成(1%概率)的变异系数为30%,符合参数建立了Swaminathan et al。69年对称三角形分布]。

从120年Taillard实例,另一个120延期实例被创建,从他们的一个子集选择50与RIPG评估算法。没有评估所有120个实例的原因是高所需的执行时间。因此,对于每一种情况下,延期5点被处死,在系统更新根据流水车间环境的事件,和,因此,该技术被处决5乘以每个实例。50实例使用从一组随机选择120 Taillard实例,排除那些更大的规模(500人),因为它不是通常使用如此高的工作环境与多个目标函数。网站实例&解决方案,包含以下文件:(我)训练实例使用Irace包(2)评价实例(3)从RIPG Pareto-front解决方案为每一个为每个评估实例的10个重复进行

4.2。验证Dubois-Lacoste RIPG算法的实例在静态,Biobjective环境

因为我们还没有找到一个基准动态three-objective问题在文献中,我们适应一个静态的算法,biobjective Dubois-Lacoste提出的方法,利用多目标性能指标等。26)来验证算法的正确行为。Dubois-Lacoste等人的目的是最小化最大完工时间的任务和加权总迟到。的原因选择这个环境是能够应用算法的比较结果最好的结果在文献中通过一个两阶段本地搜索+帕累托本地搜索(TP +请)混合算法。

在我们的实验中,RIPG metaheuristic使用经典的参数化提出了文献[25(见表)和推荐biobjective环境1)。

每个实验重复5次(独立),以评估超体积的多目标指标和一元ε指标( )在每个Dubois-Lacoste等人的实例(26]。根据初步统计研究随着Wilcoxon试验,RIPG算法都是被推断出来的行为类似于TP +请算法在静态,biobjective环境,可以看到在图的箱线图3。类似的结果得到的一元乘法ε指示器,可以看到在图4。

在图5帕累托,一个比较方面RIPG算法获得的和最好的结果发现在文献中显示(26]的一些Taillard实例。

RIPG算法方法最好的帕累托方面获得了文学,遵循同样的趋势没有过分偏离参考nondominated解决方案。新的nondominated解决方案甚至被发现在某些情况下,我们可以看到在实例ta018和ta024。

4.3。参数标定

作为经典参数静态环境中无法正确调整动态场景,我们运行参数校准的RIPG延期多目标环境。实验的硬件环境由一台机器与四核Intel Xeon X5675处理器,3.07 GHz和16 GB的RAM内存。所使用的操作系统是Windows 7企业版,64位架构。软件是在。net平台上开发和使用微软的c#编程语言Visual Studio 2010开发框架。

为了定义停止准则,我们分析了不同方法的文献[58,70年- - - - - -74年]。大多数使用最大执行时间,计算根据问题的大小定义的工作岗位的数量和机器可用的系统,作为停止准则。在这项研究中,计算的期限与以下方程: ,在哪里t时间以毫秒为单位,n工作岗位的数量,米是机器的数量。上面的表达式是用来计算执行时间因为工作的数量和机器的数量影响的困难要解决的问题。此外,它允许使用更多的计算时间与更复杂的问题。

同样,RIPG定义的参数的自动配置算法,提出了基于迭代F-Race方法的延伸和实现在Irace工具(75年]。为此,超体积被定义为一个指标来评估配置计划,因为这是最常见的标准多目标问题。选择训练实例,使用取决于复杂性分析结果提供了文献中关于Taillard实例(26]。

代表性实例,总共有6个问题选择(ta02、ta031 ta047, ta061, ta080,和ta024),两个低复杂性、两个介质的复杂性,和两个高复杂性的解决困难。选择评估标准是基于实例的复杂性之间的权衡的数量nondominated biobjective解决方案发现文献中,静态问题(时间和总加权迟到),结合考虑单目标问题中的相对误差极小化准则。校准阶段中使用的实例没有随后用于算法的评估,以避免过度拟合。

分析Irace结果后,RIPG算法参数的配置没有大影响结果;因此,这个算法是稳健的参数变化。在表2,最优的结果显示RIPG Irace自动配置算法。

4.4。RIPG算法在多目标动态环境下的性能

目的是验证的性能RIPG metaheuristic, 50是执行基准问题,专门在这项研究中开发的流水车间重新安排环境。RIPG算法被处决的10倍(独立)的每个实验为了执行一个可靠的统计分析。因为它是不可能比较RIPG算法与其他metaheuristics在拟议的环境中,模拟的结果在4选择实例介绍如下。在数据6- - - - - -9帕累托方面获得的4所示选择实例。5帕累托方面从每个实例所示,对应5生成的每一点的重新安排。我们可以看到许多nondominated的解决方案如何发现下降随着问题规模的增加。

所有的帕累托方面获得RIPG算法可以在实例和解决方案。https://www.dropbox.com/s/l4mqu5p17wov5s6/Multiobjective Rescheduling-Instances % 26 solutions.zip ? dl = 0。

最后,目标是当中断出现查看重新安排流程,一个小实例被选中(TA_20_5_3)来显示制造业的发展计划。应该注意的是,这是一个小实例,机器没有发生故障;然而,其余的中断并出现(见表3)。在图10的安排不同的点的工作重新安排。J16是第一个工作安排在最初的基础。NJX识别新的就业机会。基本安排提出了(t= 0)以及5延期运行(有时t= 232,t= 464,t= 696,t= 928,t= 1160)。由于新的就业机会的出现和变化工作处理时间,安排修改。图11显示了每个RIPG帕累托前沿TA_20_5_3延期点实例。

5。结论和未来的研究

本研究提出了相应的贡献。首先,一个新的MILP数学公式提出了代表动态,triobjective延期需要解决的问题。同样,一系列的问题(基准实例)被定义模型动态重新安排环境,包括规范不同的中断,可以在生产环境中出现。此外,延期的架构设计和实现,基于predictive-reactive策略与周期性的重新安排。此外,RIPG metaheuristic已经应用及其在动态重新安排正确操作系统验证。

验证该方法并没有发现引用文献中,基于静态biobjective基准环境使用。重要的是要注意,RIPG算法方法最好的获得帕累托前沿文献,遵循同样的趋势没有过分偏离参考nondominated设置在静态biobjective环境解决方案。新的nondominated解决方案甚至被发现在某些情况下,我们可以看到在实例ta018和ta024。同样,RIPG非常健壮,因为算法产生相似的结果的任何参数化的中间值。因为它已经不可能比较RIPG算法与其他metaheuristics在拟议的环境中,由于缺少技术应用于此类问题,帕累托前沿获得几个大小不一的问题已经被证明的实例。nondominated解决发现的数量下降随着问题规模的增加。

为未来的研究,它可能是有用的影响深入了解分析基本时间表(基线)用来评估稳定目标函数算法的结果。此外,尽管本文分析了所有的实验使用5延期点,动态系统可以评估数量可变的延期点0到1000之间,Sabuncuoglu和Karabuk [76年考虑他们的工作。同样,RIPG metaheuristic可以称为种动态调整的问题许多客观优化中,目标函数的数量大于3。最后,另一个现有的metaheuristic可以适应解决这个问题,那么结果可能会与那些通过RIPG相比。

数据可用性

本文实例和解决方案的数据集称为可以访问https://doi.org//10.17632/4p4jcwdwpt.2(Mendeley网站)。

的利益冲突

作者宣称没有利益冲突。