文摘
全面分析柔性工作车间调度问题的特点(FJSSP),需要等实际调度过程中的动态因素的到来和离开工作,机器的故障和恢复同时考虑进去,并建立一个新的动态多目标数学模型。松鼠搜索算法(SSA)为核心的发展战略,并结合多目标框架和动态处理技术解决建立数学模型。实验结果表明,本文提出的数学模型可以有效地解决柔性作业车间调度问题。与其他数学模型相比,本文建立的数学模型能保持更好的平衡之间的效率和稳定性。
<年代pan class="end-abs">1。介绍柔性工作车间调度问题
柔性工作车间调度问题的目的(FJSSP)是合理分配机器到达工厂的所有流程处理,以实现一个或多个目标有关运行效率和系统的稳定性1]。FJSSP是一个复杂的组合优化问题。增加的计算量成倍增加机器的数量和工作。智能进化算法不限制搜索空间的约束,不依赖于其他辅助知识,他们只需要确定优化目标和相应的适应度函数的搜索方向,适合求解大规模优化问题,如极化估计,估计,合作定位(2- - - - - -6]。许多学者已经使用群集智能进化算法,包括传统的智能优化算法,如遗传算法(7),新的智能进化算法,如重组青蛙跳算法,蜂群蜘蛛优化算法,等等,来解决FJSSP大规模组合优化问题。调度计划的完成时间最小,FJSSP的初始优化目标,这是最常见的优化目标8- - - - - -10];然而,实际的工作环境往往是动态的,也就是说。,new events may occur at any time, such as the arrival of new jobs, the departure of completed jobs, and the sudden breakdown of machines. Obviously, the best scheduling scheme matching the original system state is unsuitable for the new working environment. Rescheduling the jobs in the new environment is necessary. For the scheduling scheme in the new environment, if the highest efficiency is the goal, the machine with the highest efficiency for the process to be chosen may cause the load imbalance of the system, and the new scheduling scheme may have a great difference from the historical scheduling scheme, which will affect the system stability. If the system stability is the optimization objective, the gap between new and old scheduling schemes can be reduced, but the processes needed may not be performed by the most efficient machines corresponding to them, resulting in low operation efficiency. In summary, flexible job shop scheduling should consider the efficiency and stability of the system at the same time to ensure the scheduling efficiency after changing the working environment, and a mutual exclusion relationship exists between the two. Scholars have proposed new flexible job shop scheduling methods after environmental change.
例如,Lei,詹森,分别针对完成最短的时间和最好的鲁棒性,和解决机器故障的任务调度问题11,12]。Chryssolouris和张完成时间和延迟时间的加权和作为生产调度方案的优化目标(13,14),虽然运行效率和系统的稳定性被认为是在优化过程;解决问题时,多个目标可以转化为单一目标通过使用加权求和方法,和合理的体重值不能设置依照实际情况的环境;因此,最合适的调度方案很难生成,普遍性是弱。黄Zhiqing等人FJSSP问题建立一个能源消耗模型和改进遗传算法与粒子群优化和模拟退火算法。完成时间和能源消耗是作为优化目标,同时优化和效率和稳定性。然而,该模型忽略了区别新旧调度方案之前和之后的机器故障,在故障时系统的稳定性是可怜的(15]。FJSSP史等人解决问题通过使用离散multi-population入侵杂草优化算法、自适应变异和域搜索策略以提高算法的搜索能力和使用滚动窗口的概念来安排系统运行在特定的时间。从本质上讲,静态FJSSP问题分为几个时期,并不适用于动态情况的任务序列随时离开16]。陈et al .,延迟和偏差作为效率指标和稳定性指标,分别。他们用NSGA-II同时优化两个目标。偏差度的评估是重新安排计划的时候失败。系统的稳定性在一定程度上改善了之前和之后的机器故障,但它并不适用于动态环境中操作到达任何时间(17]。
总之,首先,FJSSP自然动力学。当建立柔性工作车间调度模型,工作效率通常是衡量处理任务的完成时间,以及系统的稳定性是衡量机器车间的负荷状态。尽管现有的数学模型可以应付一些工作环境的变化,他们仍然不能处理任务序列的随机到达,完成任务的离开,突然机器故障和修复失败的机器在同一时间。其次,灵活的车间的效率和稳定系统是互相排斥的;因此,在数学的本质,FJSSP是一个动态的多目标优化问题(18]。相比之下的方法将多目标转化为单目标通过加权求和,多目标进化算法可以同时考虑效率和稳定性,这是解决柔性作业车间调度的主要方法。因此,多目标算法的性能也是解决DJSSP的关键。为了得到一个调度方案的效率和稳定在动态环境下,有必要建立一个数学模型符合DFJSSP的动态特性和动态多目标进化算法具有优良的性能。
基于上述分析,本文提出了一种基于动态多目标柔性车间调度方法松鼠算法。的主要创新如下:首先,在考虑一个实际的车间环境的变化,包括任务序列的随机到达、出发完成任务,突然机器故障,和失败的修复机,提出了一种新的动态多目标柔性车间调度模型,完成时间,负载平衡(磅),和故障延期偏差为目标函数,以解决工作效率和系统的稳定性。第二,为了有效地解决上述建立的数学模型,一种改进的动态多目标松鼠搜索算法提出了基于分解。采用操作和机器编码个体编码和提高个人进化策略的SSA根据FJSSP的特点。此外,一个新的动态处理技术包括建立和更新外部人口和人口的初始化的时候重新安排,提出了再生可以快速响应变化的初始种群在重新安排时间。
其余部分安排如下:部分2介绍了数学模型的建立过程的动态多目标柔性车间调度问题;第三部分介绍了柔性车间调度方法的原理基于动态多目标松鼠搜索算法;第四部分给出了实验结果和分析;第五部分总结了整个论文。
2。建立一个数学模型对动态多目标柔性作业车间调度问题
2.1。柔性工作车间调度问题的描述
柔性工作车间调度问题可以描述为:<我>n我>工作<我>J我>={<我>J我><年代ub>1年代ub>,<我>J我><年代ub>2年代ub>,…我>,<我>J我><年代ub>n我>年代ub>},每个操作<我>J我><年代ub>我我>年代ub>是由<我>n我><年代ub>我我>年代ub>流程和多目标的数量每操作步骤<我>n我><年代ub>我我>年代ub>。的处理时间<我>t我><年代ub>ij我>年代ub>每个进程有一定的分布。FJSSP的目的是为每个进程分配操作机器,所以到达车间的过程在一定的顺序加工,加工完成后,操作机器离开车间。一个新的数学模型建立了柔性工作车间调度问题,实现柔性工作车间动态调度。首先,介绍了变量参与柔性工作车间调度问题如下:<年代pan class="list">t我><年代ub>1年代ub>:延期偿还周期时间<我>t我>=<我>nt我><年代ub>l我>年代ub>(<我>n我>是一个正整数),更新车间的状态,包括新任务,机器空闲时间等。年代pan>t我><年代ub>b我>年代ub>:机器坏了的时候。年代pan>t我><年代ub>r我>年代ub>:从机械故障中恢复的时间。年代pan>平均故障间隔我>:平均故障时间。年代pan>Mttr我>:平均恢复时间。年代pan>J我><年代ub>我我>年代ub>:任务<我>我我>到达工厂。年代pan>N我><年代ub>l我>年代ub>:数量的任务的时间之前到达工厂<我>nt我><年代ub>l年代ub>。年代pan>n我><年代ub>我年代ub>:数量的过程。年代pan>O (i, j)我>:<我>j我>任务的过程<我>J我><年代ub>我我>年代ub>。我>年代pan>米我>:在车间机器的总数。年代pan>米我>:在车间的机器,<我>米我>={<我>米我><年代ub>1年代ub>,<我>米我><年代ub>2年代ub>、…<我>米我><年代ub>米年代ub>}。年代pan>M (i, j)我>:一组机器可以处理<我>O(我,j)。我>年代pan>F (i, j)我>:机器替代机组中包含的数量<我>米(我,j)我>的<我>O(我,j)我>、灵活程度。年代pan>t (i, j, k)我>的处理时间<我>O(我,j)我>在机<我>米我><年代ub>k年代ub>。年代pan>年代我><年代ub>我我>年代ub>:工作的开始时间<我>我我>。年代pan>C我><年代ub>我我>年代ub>:工作的完成时间<我>我我>。<我>年代(我,j)我>:开始时间的过程<我>O(我,j)我>。年代pan>C (i, j)我>:过程的完成时间<我>O(我,j)我>。年代pan>C我><年代ub>k_last年代ub>:<我>O(我,j)我>处理<我>米我><年代ub>k年代ub>最后的完成时间过程的<我>米我><年代ub>k年代ub>前处理<我>O(我,j)我>就开始了。年代pan>S (i, j)我><年代pan class="nowrap"> :年代pan>的开始时间<我>O我><年代ub>ij我>年代ub>在重新安排流程。年代pan>C (i, j)我><年代pan class="nowrap"> :年代pan>的完成时间<我>O我><年代ub>ij我>年代ub>在重新安排流程。年代pan>我我><年代ub>k我>年代ub>:最早的机器可用时间<我>米我><年代ub>k我>年代ub>;年代pan>l我><年代ub>k我>年代ub>:机器的总工作时间<我>米我><年代ub>k我>年代ub>;年代pan>
柔性工作车间任务调度要求:<年代pan class="list">(1)年代pan>在最初的时候,所有的机器都是可用的,例如,<我>t我>=0,<我>我我><年代ub>k年代ub>= 0。年代pan>(2)年代pan>这一过程只能由一台机器处理,也就是说,<我>O(我,j)我>只能处理一台机器<我>米(我,j)我>在一个时间。年代pan>(3)年代pan>一台机器一次只能处理一个进程。年代pan>(4)年代pan>之间不存在优先约束不同的任务。年代pan>(5)年代pan>流程在同一任务没有优先级,也就是说,<我>O(我,j- 1)我>只能处理<我>O(我,j)我>后加工。年代pan>(6)年代pan>所有进程没有优先考虑同一台机器上,也就是说,这台机器之前必须处理当前进程可以处理下一个过程。年代pan>(7)年代pan>机器没有故障时,操作系统将在一个固定的周期根据操作的完成和到达。当机器坏了,无论执行过程的故障机还是要执行的过程很快,在重新安排计划,所有剩下的过程对应于故障机由nonfault安排执行机器。修理机器故障后是固定的,可以继续执行作业调度。年代pan>
nt的周期重新安排时间<年代ub>l我>年代ub>重新安排时间<我>t我><年代ub>b我>年代ub>和要处理的任务延期的恢复时间<我>t我><年代ub>r我>年代ub>,如果程序<我>O(我,j)我>是上处理机器<我>米我><年代ub>k我>年代ub>,然后开始时间<我>年代(我,j)我>和结束时间<我>C(我,j)我>的<我>O(我,j)我>分别是公式所示(1)和(2)。如果一开始时间和结束时间<我>C我><年代ub>我我>年代ub>的<我>J我><年代ub>我我>年代ub>所示公式(3)和(4),分别。<年代pan class="equation_break" id="EEq1">
其中包括:<年代pan class="inline_break"> ,年代pan>
调度的例子(19]说明有一个增强的柔性工作车间调度规则的理解。如表所示1,“/”意味着这个过程不能在相应的机器上执行。图1是一个甘特图对应于一个特定的调度计划数据表1。
如图1,当<我>t我>=0,<我>O我><年代ub>31日年代ub>,<我>O我><年代ub>41年代ub>,<我>O我><年代ub>21年代ub>被使用<我>米我><年代ub>1年代ub>,<我>米我><年代ub>3年代ub>,<我>米我><年代ub>5年代ub>,分别。考虑到<我>O我><年代ub>31日年代ub>,<我>O我><年代ub>41年代ub>,<我>O我><年代ub>21年代ub>第一个过程吗<我>J我><年代ub>3年代ub>,<我>J我><年代ub>4年代ub>,<我>J我><年代ub>2年代ub>分别所有的机器都空闲时<我>t我>=0;因此,<我>年代我><年代ub>31日年代ub>=<我>年代我><年代ub>41年代ub>=<我>年代我><年代ub>21年代ub>= 0。<我>O我><年代ub>11年代ub>选择治疗使用吗<我>米我><年代ub>1年代ub>。虽然<我>O我><年代ub>11年代ub>的第一步吗<我>J我><年代ub>1年代ub>,没有优先级约束在不同的任务中,<我>米我><年代ub>1年代ub>已经开始加工<我>O我><年代ub>31日年代ub>当<我>t我>=0。<我>O我><年代ub>11年代ub>后就可以开始<我>O我><年代ub>31日年代ub>结束;因此,<我>年代我><年代ub>11年代ub>=<我>我我><年代ub>1年代ub>=<我>C我><年代ub>31日年代ub>=<我>年代我><年代ub>31日年代ub>+<我>t我><年代ub>311年年代ub>= 5。<我>O我><年代ub>12年代ub>处理使用<我>米我><年代ub>4年代ub>。考虑到流程在同一任务没有优先级,<我>O我><年代ub>12年代ub>只能开始后<我>O我><年代ub>11年代ub>结束,<我>O我><年代ub>11年代ub>结束<我>t我>=<我>C我><年代ub>11年代ub>=<我>年代我><年代ub>11年代ub>+<我>t我><年代ub>111年年代ub>= 7。然而,当<我>t我>=7,<我>米我><年代ub>4年代ub>处理<我>O我><年代ub>32年代ub>,<我>米我><年代ub>4年代ub>后闲置<我>O我><年代ub>32年代ub>完成后,即<我>我我><年代ub>4年代ub>=<我>C我><年代ub>32年代ub>=<我>年代我><年代ub>32年代ub>+<我>t我><年代ub>324年年代ub>= 8;因此,<我>年代我><年代ub>12年代ub>=<我>我我><年代ub>4年代ub>= 8。<我>O我><年代ub>13年代ub>处理使用<我>米我><年代ub>2年代ub>。虽然<我>米我><年代ub>2年代ub>一直在空闲<我>t我>=5时<我>O我><年代ub>22年代ub>结束后,<我>O我><年代ub>12年代ub>还没有开始的时候吗<我>t我>=5,流程在同一任务没有优先级。因此,<我>年代我><年代ub>13年代ub>=<我>C我><年代ub>12年代ub>=<我>年代我><年代ub>12年代ub>+<我>t我><年代ub>124年年代ub>= 10。
2.2。FJSSP特点分析
柔性工作车间调度问题的,甚至完全相同的调度任务,往往存在多个调度方案。图2甘特图对应表吗1和另一个调度方案不同于图1。
对于FJSSP,通常被认为是效率和系统的稳定性。在此基础上,比较和分析数据的调度方案1和2从这两个观点。在表的任务1,最后两个调度方案的完成时间是17日,表明两个调度方案的效率是等价的。然而,在相对应的调度方案图1、所有机器参与调度过程和机器的负载平衡。调度方案图2,<我>米我><年代ub>6年代ub>没有参与调度过程。完成所有进程使用<我>米我><年代ub>1年代ub>- - - - - -<我>米我><年代ub>5年代ub>和机器的磅差。机器在车间的不平衡负荷可能导致一些机器闲置和其他人在工作状态很长时间了。机器的工作状态很长一段时间很容易失败,从而影响系统的稳定性。因此,相比之下,在图的调度方案2,调度方案图1同时确保效率和考虑系统稳定性要好。
上面提到的机器故障的重要因素之一,影响系统稳定性,并具体分析如下。当机器在车间分解,过程在同一任务没有优先级,除了过程实施失败的机器上或尚未实现。<我>O我>(<我>我我>,<我>j我>)只能加工后<我>O我>(<我>我我>,<我>j我>1)处理,流程安排在无过错机在原始的调度计划也将受到影响。图2被认为是一个例子,即。,如果<我>米我><年代ub>4年代ub>分解在<我>t我>=9。过程<我>O我>(1、2)处理<我>米我><年代ub>4和过程<我>O我>(4,2)尚未处理<我>米我><年代ub>4我>年代ub>需要重新安排。<我>O我>(1、3)<我>O我>(4,3)无法按照原来的调度计划执行的变化造成的<我>O我>(1、2)<我>O我>(4,2),虽然<我>O我>(2、3)原调度方案是失败的影响机器,机器故障系统状态变化,调度<我>O我>(2,3)也将有一个新的对系统状态的影响。尽管如此,车间仍然保持一个高效稳定运行时失败。除了流程已经开始无过错机的过程已经完成故障机器上的,所有其他进程需要改期。复苏的时候,所有剩余的未经处理的流程需要改期,除了已经完成,开始的过程。重新安排计划之间的偏差越小原调度方案,系统变化越小,稳定性越好。相反,新老之间的差异越大调度方案,系统的稳定性将会越糟糕。
总之,如果我们想要确保运行效率,最有效的机器在所有进程可能导致一些机器被闲置了很长一段时间,虽然一些机器的工作很长一段时间,导致不平衡负载。如果我们想确保机器的磅,有些工作可能不是最有效的处理机器,导致低效率。有些流程不匹配最有效的机器,和机器的效率仍有可能减少。如果要保证工作效率,新的调度方案可能比历史上的调度方案,但系统的稳定性将会更糟。
2.3。FJSSP的动态多目标数学模型
分段2。2表明,运行效率和系统的稳定性是矛盾的。考虑车间的效率和稳定的同时,本文把完成时间,磅,和重新安排偏差为目标函数,建立了多目标优化数学模型。完成时间是用来评估车间效率,而磅和故障延期偏差用于测量系统的稳定性。细节如下:
2.3.1。工作效率
完成时间短,意味着工作效率较高。确保车间工作效率,本文把完成时间最短为优化目标,以及目标函数公式所示(5)。<年代pan class="equation_break" id="EEq5">
2.3.2。系统的稳定性
本研究系统稳定性的措施两个方面:机器磅和延期偏差。磅是使用机器利用率的方差公式所示(6);方差越小,越平衡机负载和系统的稳定性就越好。当机器分解或恢复,新老之间的平均偏差(广告)调度方案所示公式(8)表明延期偏差。小广告显示重新安排之间的细微差别和原始的调度计划,稳定和改善。<年代pan class="equation_break" id="EEq6">
在(6),<年代pan class="equation_break" id="EEq7">
磅是越小,系统将更加平衡。<年代pan class="equation_break" id="EEq8">
在(8),<我>n我><年代ub>res年代ub>操作的总数是改期;的操作,已经开始或完成的工作机器,<年代pan class="inline_break"> 和<年代pan class="inline_break"> 。年代pan>
总之,考虑系统的效率和稳定性,建立了FJSSP动态多目标数学模型:<年代pan class="equation_break" id="EEq9">
在上面的数学模型中,第一个目标函数保证所有任务的完成时间最短到达时间<我>nt我><年代ub>l年代ub>;第二目标函数保证所有机器都将尽可能均匀,直到加载<我>nt我><年代ub>l年代ub>;第三个目标函数确保机器分解或回去工作时,重新安排计划之间的偏差和原调度方案是最小的。当没有机器分解或一台机器不是恢复,只有1和2被认为是目标函数,以供应点和数学模型是优化问题。如果一台机器坏了或者有缺陷的机器恢复,这三个目标都需要优化,并被视为three-objective优化问题的数学模型。
与现有FJSSP的数学模型相比,本文建立的数学模型考虑完成任务的动态特性出发,新任务的到来,车间机器的故障,修理机器故障。调整优化数学模型目标自动按照国家机器,这将缩短机器的工作时间和平衡负载时不机分解或机不是恢复。与此同时,建立数学模型,将新老的偏差最小化调度计划当一台机器分解或错误的恢复,使考虑工作效率和系统的稳定性。
3所示。为解决动态多目标SSA FJSSP
解决动态多目标优化问题时,动态环境分为几个瞬态环境;动态处理技术用于处理环境变化,以及多目标算法是用来解决静态瞬态环境中的多目标优化问题。松鼠搜索算法(SSA)是一种新的群集智能进化算法(20.]。与传统的进化算法相比,SSA具有较高的收敛速度和精度。王等人提出一种改进的松鼠全球函数优化搜索算法(ISSA),提高了SSA的收敛。此外,张等人提出MOEA / D,可以解决多目标优化问题在瞬态环境中,具有较高的求解速度和效率21]。因此,为了扩大SSA在工程领域的应用,本文认为伊萨为核心的进化策略,认为MOEA / D的多目标框架,集成了一个动态处理技术来解决FJSSP。图3是解决动态多目标SSA FJSSP的流程图。
图3说明在每个瞬态环境,最终的调度方案在当前环境nondominated解集应该选择,和新环境下的调度是基于所选择的调度方案。在这项研究中,TOPSIS (22)是用来确定最终的调度方案为每个瞬态环境。此外,考虑到FJSSP是一个离散的优化问题,本研究采用个体编码方法(23]。按照FJSSP的特点,动态处理技术与进化策略FJSSP设计如下。
3.1。个体编码方法
个体编码方法包括两个部分:操作和机器代码。确定操作编码使用数量在重新安排时间处理工作。操作<我>O(我,j)我>由其任务是几号<我>J我><年代ub>我我>年代ub>。第一次出现的<我>J我><年代ub>我我>年代ub>对应于操作<我>O(1)我我>,第二次出现<我>J我><年代ub>我我>年代ub>对应于操作<我>O(我,2)我>,等等。的<我>j我>发生的<我>J我><年代ub>我我>年代ub>对应于操作<我>O(我,j)我>;因此,发生的频率<我>J我><年代ub>我我>年代ub>总操作数是一样的<我>J我><年代ub>我我>年代ub>。每个操作代码对应一台机器代码。一组机器从候选人中选择机器的<我>O(我,j)我>随机,所选的机器的数量相对应的机器代码<我>O(我,j)我>。
任务表中的数据1被认为是一个例子。完整的代码对应的调度方案如图1是342133221144/135145264243,即。阿,<年代ub>31日年代ub>⟶米<年代ub>1年代ub>阿,<年代ub>41年代ub>⟶米<年代ub>3年代ub>阿,<年代ub>21年代ub>⟶米<年代ub>5年代ub>阿,<年代ub>11年代ub>⟶米<年代ub>1年代ub>阿,<年代ub>32年代ub>⟶米<年代ub>4年代ub>阿,<年代ub>33年代ub>⟶米<年代ub>5年代ub>阿,<年代ub>22年代ub>⟶米<年代ub>2年代ub>阿,<年代ub>23年代ub>⟶米<年代ub>6年代ub>阿,<年代ub>12年代ub>⟶米<年代ub>4年代ub>阿,<年代ub>13年代ub>⟶米<年代ub>2年代ub>阿,<年代ub>42年代ub>⟶米<年代ub>4年代ub>阿,<年代ub>43年代ub>⟶米<年代ub>3年代ub>。
3.2。动态处理技术
3.2.1之上。建立和更新的外来人口
MOEA / D的解决方案原理表明,当后代个体<年代vg height="14.8655pt" id="M13" style="vertical-align:-3.4294pt" version="1.1" viewbox="-0.0498162 -11.4361 11.4504 14.8655" width="11.4504pt" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
当的规模<我>莎莉我>小于上限吗<我>T我>如果num_alt = 0,相应的<年代vg height="14.8655pt" id="M18" style="vertical-align:-3.4294pt" version="1.1" viewbox="-0.0498162 -11.4361 11.4504 14.8655" width="11.4504pt" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
当的规模<我>莎莉我>到上限吗<我>T我>,如果num_alt<我>=我><我>0我>,人口已经进化到一定程度上,当前个人接近其邻国个人。保持种群的多样性,个人的最小欧氏距离当前的个人<我>莎莉我>被删除,<年代vg height="14.8655pt" id="M20" style="vertical-align:-3.4294pt" version="1.1" viewbox="-0.0498162 -11.4361 11.4504 14.8655" width="11.4504pt" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
3.2.2。代的初始种群在重新安排时间
两种情况需要重新安排任务被认为是。第一个车间工作时间有关,即周期性的重新安排。第二个是有关机器的状态,包括故障和故障恢复重新安排。考虑到上述两种情况中,两个不同的动态处理技术设计,细节如下。
在周期性的重新安排<我>nt我><年代ub>l我>年代ub>,新任务记录,机器状态更新,新时期下的初始种群生成按照分段编码方法3.1。
如果机器坏了或再次运行,也就是说,<我>t我>=<我>t我><年代ub>b我>年代ub>或<我>t我>=<我>t我><年代ub>r我>年代ub>,新的人口<我>t我><年代ub>b我>年代ub>或<我>t我><年代ub>r我>年代ub>生成按照原调度方案的实现。细节如下。如果<我>t我>=<我>t我><年代ub>b我>年代ub>,在目前的调度方案,操作调度包含所有未完成的操作安排在破碎的机器,所有的操作都才开始<我>t我><年代ub>b我>年代ub>。如果<我>t我>=<我>t我><年代ub>r我>年代ub>在当前的调度方案,操作调度包含所有的操作才开始<我>t我><年代ub>r我>年代ub>。所有操作的集合被重新命名<我>O我><年代ub>再保险年代ub>。当<我>t我>=<我>t我><年代ub>b我>年代ub>或<我>t我>=<我>t我><年代ub>r我>年代ub>为每个单独的原始人群,如果<我>莎莉我>=∅,所有操作<我>O我><年代ub>再保险我>年代ub>应该被重新初始化新的个人在新环境中按照上面的编码方法;如果<我>莎莉我>≠∅,对于每个调度计划<我>莎莉我>操作的集合,需要重新记录和命名<我>O我><年代ub>莎莉年代ub>;如果内存和完全相同的个体<我>O我><年代ub>莎莉年代ub>和<我>O我><年代ub>再保险年代ub>存在,一个是随机选择的,所有操作的调度顺序保存在<我>O我><年代ub>莎莉年代ub>,和相应的机器代码是突变,视为初始个体在新环境中。高相似性调度方案在内存中人口和当前执行的调度方案,生成的新个体使用内存的人更适合当前工作状态,有利于系统稳定。
3.3。核心进化策略
每个瞬态环境的调度过程中,核心的进化策略SSA用于更新人口。个体包含操作和机器代码,但机器代码是由操作码。因此,人口的更新策略是只针对操作的代码,而不是机器代码。具体的更新过程描述如下。
3.3.1。相关的变量
F我><年代ub>d我>年代ub>:学习目标按照标准SSA;详细介绍了在文献[20.]。年代pan>n我>_年代ame:当操作的代码<我>F年代我><年代ub>我我>年代ub>和<我>F我><年代ub>d我>年代ub>匹配一个接一个地<我>n我>_年代ame的总数是一样的操作规范。年代pan>n我>_<我>j我><年代ub>l我>年代ub>:新工作的总数<我>t我><年代ub>l我>年代ub>。我>年代pan>Fr我><年代ub>1年代ub>,<我>Fr我><年代ub>2年代ub>:如果<我>莎莉我>=∅,<我>Fr我><年代ub>1年代ub>和<我>Fr我><年代ub>2年代ub>两个人不同的来自哪里<我>F我><年代ub>d我>年代ub>和<我>F年代我><年代ub>我我>年代ub>随机选择在他们的邻居;如果<我>莎莉我>≠∅,<我>Fr我><年代ub>1年代ub>在周边国家的任何个人不同吗<我>F年代我><年代ub>我我>年代ub>,<我>Fr我><年代ub>2年代ub>是随机选择的<我>莎莉。我>年代pan>
和<年代vg height="11.8174pt" id="M22" style="vertical-align:-3.1815pt" version="1.1" viewbox="-0.0498162 -8.6359 21.9089 11.8174" width="21.9089pt" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
FS我><年代ub>我我>年代ub>被认为是死,生成后代使用吗<我>F我><年代ub>r我>1年代ub>和<我>F我><年代ub>r我>2年代ub>按照痘了文献[24]。
FJ年代年代P要求每个维度的价值是工作号码对应操作,和每个作业的总出现时间应该是相同的总操作数。因此,操作码的后代获得使用上述更新策略应该被修改。任务表1被认为是一个例子来介绍修改过程,细节如下。
冗余工作数量确定和记录在向量”。“如果数量<我>我我>的工作<我>J我><年代ub>我我>年代ub>发生<我>n我><年代ub>我我>年代ub>+我><我>c我>次,然后<我>我我>发生在“更多”<我>c我>次了。图4被认为是一个例子。在表的问题1后代的操作码是134312214131,更多= {1 1}。
失踪的就业数据标识和记录在向量”<我>更少。我>“如果数量<我>我我>的工作<我>J我><年代ub>我我>年代ub>发生<我>n我><年代ub>我我>年代ub>- c我>次,然后<我>我我>发生在“少”<我>c我>次了。图4被认为是一个例子。在表的问题1后代的操作码是134312214131,莱斯<我>年代我>={2、4}。
冗余就业数据出现在“更多”的后代选择随机替换丢失的工作数字”更少。“所有元素在“少”是随机分布的,修改完成。图4被认为是一个例子,后代的5日维操作代码更改从1到4,和第十维度从1到2的变化。
随机选择一个操作机器的替代机组操作码后确定每一个后代,和操作代码构成一个完整的后代调度方案。
4所示。实验仿真和结果分析
验证动态多目标的有效性SSA求解FJSSP数学模型建立了本文FJSSP模型和动态多目标SSA应用于解决一个实际的FJSSP。所有的测试在计算机上实现CPU:英特尔(R)的核心(TM) i5 - 7200 u, 4 G内存和2.70 GHz频率。程序中实现MATLAB R2016a。实验包括两个部分:有效性验证和先进的验证。
4.1。有效性验证
本文探讨FJSSP建立数学模型和设计的调度方法的影响,以下FJSSPs测试:机器的数量<我>米我>=6;重新安排周期是<我>t我><年代ub>l我>年代ub>=我>1;两个相邻任务之间的时间间隔到达平均0.5的指数分布;工作/任务的数量<我>n我><年代ub>j我>年代ub>遵循(之间的均匀分布<我>米/我>2,<我>米我>];每个流程的灵活性受到之间均匀分布(<我>米/我>2,<我>米我>];每个流程的处理时间服从指数分布的平均值的1;<我>平均故障间隔我>服从指数分布的意思<我>快艇我>,<我>快艇我>遵循(20、40)之间的均匀分布;<我>米TTR我>服从指数分布的意思<我>地铁我>,<我>地铁我>遵循的均匀分布5,10),随机选择一个故障机器。要处理的任务的初始时间如表所示2。算法参数设置如下:SSA的<我>N我><年代ub>fs我>年代ub>= 2;人口规模<我>N我>=300;人口的上限附近大小和积极的内存大小是20;每个瞬态环境的最大迭代数<年代pan class="inline_break"> ;年代pan>痘十字交叉概率模式<我>p我><年代ub>c我>年代ub>= 1;变异概率<我>p我><年代ub>米我>年代ub>= 1;当<我>N我><年代ub>l我>年代ub>=我>年代ub>100年,调度任务的总数是终止。
表3是nondominated解决方案的一部分获得从断层的空闲时间吗<我>t我>=5,第一次失败的时间<我>t我>=15。7633,第一次故障修复时间<我>t我>=23。7424或重新安排任务的优化。数据5- - - - - -7分别是nondominated图得到的任务处理或重新安排任务优化t = 52.1802失败的时候免费t = 30,第二个失败时间t = 43.6123,第二次故障修理时间。
从上面的图表中,本文提出的数学模型是一个以供应点优化问题当所有失败的机器在车间都是免费的。nondominated的解决方案是分布在同一个平面上。当故障发生或恢复时,数学模型是一个three-objective优化问题,nondominated的解决方案是分散在一个三维空间。
数据8和9的甘特图是车间调度计划在吗<我>t我>=10- 30<我>t我>分别为= -55。<我>J我><年代ub>我我>年代ub>任务数量。紫色,黄色,蓝色,橙色,青色,灰色代表每个任务的1 - 6的流程,分别。红色代表机器后重新安排过程失败,和绿色代表了重排过程机后无法恢复。当机器<我>米我><年代ub>2年代ub>分解在<我>t我>=15。7633- -23.7424,故障机不执行任何操作。当机器<我>米我>分解在<我>t我>=43。6123- -52.1802,故障机不执行任何操作。机分解后,故障机器处于工作状态。
为了进一步验证本文FJSSP数学模型建立和设计调度方法的影响,我们进行以下实验。机器的数量设置为8,重新安排时间<我>t我><年代ub>l我>年代ub>= 15;两个相邻的任务之间的时间间隔服从指数分布与平均为0.625。其他调度环境的参数设置和算法设置符合上面提到的这些。要处理的任务的初始时间如表所示4。数据10和11的甘特图是车间调度计划在吗<我>t我>=15- 25<我>t我>=30- 40,分别。
从数据可以看出10和11,当机<我>米我><年代ub>1我>年代ub>分解在<我>t我>=15。5810-<我>t我>=17。7670,故障机不执行任何操作。当机器<我>米我><年代ub>2我>年代ub>分解在<我>t我>=33。9251-<我>t我>=39。2939,故障机不执行任何操作。机分解后,故障机器处于工作状态。
总之,FJSSP数学模型,本文建立的调度方法可以有效地应对变化的一个实际的车间环境,包括到达或离开的任务在任何时间和故障的发生。这个条件可以有效地解决FJSSP。
4.2。先进的验证
动态多目标SSA用于优化本文建立的数学模型和文献[23)解决FJSSP通过满足下列条件:机器的数量<我>米我>=6;重新安排周期<我>t我><年代ub>l我>年代ub>= 30;之间的时间间隔两个相邻任务到达的意思是3的指数分布;工作/任务的数量<我>n我><年代ub>j我>年代ub>遵循(之间的均匀分布<我>米我>/2,<我>米我>];每个过程遵循的程度的灵活性之间的均匀分布(<我>米我>/2,<我>米我>];每个流程的处理时间服从指数分布的意思是5;<我>平均故障间隔我>服从指数分布的意思<我>快艇我>,<我>快艇我>服从均匀分布(100、200);<我>米TTR我>服从指数分布的意思<我>地铁我>,<我>地铁我>服从均匀分布的(30、60)和随机选择一个故障机器的时候失败。其余的参数设置是与之前的一致。要处理的任务的初始时间如表所示5。
动态调度环境下的调度方案是不同的,和车间状态结束时每个瞬态环境是不同的。研讨会的初始状态,开始下一个新环境是不同的。比较不同数学模型的优化能力FJSSP需要相同的初始车间状态和相同的任务优化。以下部分在本研究中进行了测试。<年代pan class="list">(1)年代pan>数学模型在文献[23)用于动态环境不断优化。车间状态记录每个新的调度周期的开始。几种不同的初始状态和瞬态调度周期。要处理的新任务在每个调度周期记录,本文建立的数学模型是用来优化初始状态对应的车间。完成时间和最大机器负载两个调度指标的文献[23)进行了比较。图12是最大的调度时间的对比图获得优化的两个模型。图13最大的是一个比较图机负载从两个模型获得。年代pan>(2)年代pan>图12显示,当数学模型在文献[23)是用于优化FJSSP不断,完成时间增加而增加的数量要处理的任务。在最初的时候,数学模型在文献[23)达到第四周期调度完成时间短,但最小差异之间存在两个数学模型在第九调度周期。在调度周期的其余部分,本文数学模型实现完成时间短。因此,相比之下,数学模型在文献[23),本文的数学模型是更有效的解决FJSSP。在图13机器负载的增加,最大数量的增加要处理的任务。第一调度周期和第七调度期在文献中最大产量较小的机器负荷。两个数学模型的优化结果在第五调度周期相似。在调度周期的其余部分,本文提出的数学模型实现最大机载荷较小。因此,相比之下,数学模型在文献[23),本文的数学模型解决FJSSP时具有更好的稳定性。年代pan>(3)年代pan>本文建立的数学模型用于上述动态环境不断优化。车间状态记录每个新的调度周期的开始。几种不同的初始状态和瞬态调度周期。要处理的新任务在每个调度周期记录,以及数学模型在文献[23)优化的初始状态对应的车间。完成时间、磅和偏差度的三个调度索引优化本文进行了比较。图14显示了最大的调度时间的比较从两个模型的优化,获得和图15描绘了一个磅所得的比较两个模型的优化。图14显示了两个模型的故障或恢复(<我>米我><年代ub>2年代ub>分解在<我>t我>=85。7705,108.0616;<我>米我><年代ub>5年代ub>分解在<我>t我>=137。4366和复苏<我>t我>=196。8504;<我>米我><年代ub>6年代ub>分解在<我>t我>=253。2210和复苏<我>t我>=261。4715)。图16是最后的甘特图得到的调度方案优化的数学模型建立。年代pan>
(一)年代trong>
(b)年代trong>
(c)年代trong>
图14表明本文建立的数学模型时不断优化FJSSP,完成时间与任务要处理的数量增加。除了在第四调度周期,本文的数学模型实现一个更小的完成时间在调度周期的其余部分。因此,相比之下,数学模型在文献[23),本文的数学模型是更有效的解决FJSSP。在图15调度过程的进度,车间的稳定性增强。除了在第六调度周期,本文的数学模型实现一个小磅的调度周期。因此,相比之下,数学模型在文献[23),目前的模型解决FJSSP达到更好的系统稳定性。图14说明当时的失败和恢复的时间,本文建立的数学模型可以实现更小的新老方案的偏差。因此,本文提出的数学模型可以重新安排过程中保持更好的稳定后,车间机器故障或机器故障恢复。一个全面的观察数据14- - - - - -17表明,机<我>米我><年代ub>5我>年代ub>失败在第四调度周期。虽然最终的调度计划优化的数学模型建立在本文较长,最好保持系统稳定,特别是当机器故障延期实现较小的偏差;<我>米5我>恢复在第六调度周期。虽然最终的调度计划优化的磅用本文建立的数学模型是穷人,完成时间是短的,和一个较小的偏差度达到在机器故障延期。
(一)年代trong>
(b)年代trong>
(c)年代trong>
总之,本文建立的数学模型具有更高的效率和更好的解决FJSSP时系统的稳定性。此外,在车间机器故障或故障恢复,它可以同时关注效率和稳定性。它为FJSSP优化有一定的优势。
5。结论
在这项研究中,FJSSP特点和研究现状的综合分析。一个新的数学模型的基础上建立了三个目标:完成时间,磅,和广告新老之间的调度方案。一个动态的多目标SSA用于建立优化模型。实验结果表明,动态多目标SSA可以用来解决FJSSP。在本文建立的数学模型在解决动态多目标FJSSP提高效率与稳定。尤其是车间机器分解或回到工作,建立模型可以提高效率之间的平衡与稳定。在未来,收敛速度应该改进柔性工作车间调度算法。
数据可用性
使用的数据来支持本研究的发现可以从相应的作者。
的利益冲突
作者宣称没有利益冲突有关的出版。
确认
这项工作的部分支持由吉林在格兰特没有技术创新发展。20210103090。
引用
-
黄z d . Tang和m .戴“Bi客观的工艺规划和车间调度优化模型改进算法的基础上,“<我>南京航空航天大学杂志》上我>卷,47号1,第95 - 85页,2015。
视图: 谷歌学术搜索 -
施施x、y、x元,“离散多物种群优化算法求解柔性工作车间调度问题,“<我>信息和控制我>,44卷,不。2、238 - 243年,2015页。
视图: 谷歌学术搜索 -
杨x”,建立了潮流。遗传算法求解柔性工作车间调度问题,“<我>控制与决策我>,10卷,第1200 - 1197页,2004年。
视图: 谷歌学术搜索 -
c . Zhang y . Rao,刘x”基于POX交叉遗传算法解决作业车间调度问题,“<我>中国机械工程我>,23卷,第87 - 83页,2004年。
视图: 谷歌学术搜索