一种流水车间重调度方法

摘要

本发明提供一种流水车间重调度方法，属于车间调度技术领域，包括实时获取当前流水车间的突发事件、重调度工件、机器可用时刻和正加工工序完工时刻；针对不同突发事件对已开工工序和未开工工序进行分组；确定流水车间重调度目标及约束条件；采用迁徙鸟群优化方法生成流水车间重调度方案；将流水车间重调度方案下发到流水车间各工序进行重调度。本发明将迁徙鸟群算法用于流水车间重调度问题，考虑多种突发事件，保证在突发事件之间快速反应；采用插入或交换的邻域搜索机制，有效确保重调度方案在两个突发事件间及时处理；不断传递搜索信息到后续迁徙鸟，不断调换领头鸟，可以确保调度方案的多样性和稳定性。

主权项

一种流水车间重调度方法，其特征在于：包括以下步骤：步骤1：实时获取当前流水车间的突发事件、重调度工件、机器可用时刻和正加工工序完工时刻；所述突发事件包括工件随机到达、工件随机撤销、工件加工时间变化和设备随机故障；所述重调度工件包括待加工工件和新插入工件；所述机器可用时刻为重调度时刻的空闲机器可获得时刻，或者忙碌机器/故障机器正加工工件的完工时刻；所述正加工工序完工时刻为非故障机器的原计划完工时刻或故障机器的重调度时刻；步骤2：针对不同突发事件，对已开工工序和未开工工序进行分组：若突发事件为工件随机到达，则保持已经在第一个机床上开工的工序的原调度顺序，对未开工工序和新加入的工件执行步骤3；若突发事件为工件随机撤销，则保持已经在第一个机床上开工的工序的原调度顺序，在删除该撤销工件后对未开工工序执行步骤3；若突发事件为工件加工时间变化，则计算受突发事件影响的正加工工序的完工时刻，执行步骤3；若突发事件为设备随机故障，则计算受突发事件影响的机床的可用时刻，执行步骤3；步骤3：确定流水车间重调度目标及约束条件：以最小化最大完工时间和最小化开工时间变化的工件数量为目标建立流水车间重调度目标函数，该函数的约束条件包括：工件的完工时间约束：重调度下工件在机床上加工的完工时间不小于重调度下工件在机床上加工的开工时间、重调度下工件在机床上加工的时间及机床故障时间之和；工件的开工时间约束：重调度条件下工件的开工时间不小于其释放时间；机床的加工次序约束：重调度条件下，在同一个机床上加工的紧邻两个工件不能出现重叠加工现象；工件的加工次序约束：重调度条件下，同一个工件在紧邻两个流水线上加工的次序关系，即工件在下一个流水线的开工时间不小于其在上一个流水线的完工时间；流水车间重调度目标函数f如下：f＝w₁*f₁+(1‑w₁)*f₂         (1)$f_1=min\left\{\underset{1\le i\le n}{max}{c}_{i,m}\right\}---\left(2\right)$$f_2=min\left\{\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{m}{\Sigma }}{X}_{ij}\right\}---\left(3\right)$s.t.$\overline{c_{i,j}}\ge \overline{s_{i,j}}+\overline{p_{i,j}}+Y_{ij}(B_e-B_s)---\left(4\right)$$\overline{s_{i,j}}\ge r_{i,j}---\left(5\right)$$\overline{s_{i+1,j}}\ge \overline{s_{i,j}}+\overline{p_{i,j}}---\left(6\right)$$\overline{s_{i+1,j+1}}\ge \overline{c_{i,j}}---\left(7\right)$X_ii＝{0，1}           (8)Y_ij＝{0，1}            (9)0≤w₁≤1           (10)上述函数中，式(1)为目标函数，其包含两个目标f₁和f₂，并对这两个目标进行加权处理；式(2)表示第一个目标f₁，即最小化最大完工时间，式中所有工件在最后一个机床m上的完工时间的最大值，即当前解的最大完工时间；式(3)表示第二个目标f₂，即系统稳定性指标，用所有工件在重调度下的开工时间和原计划下的开工时间的差值的总和表示；式(4)表示重调度条件下，工件的完工时间约束；式(5)表示重调度条件下，工件的开工时间应不小于其释放时间；式(6)表示重调度条件下，在同一个机床上加工的紧邻两个工件不能出现重叠加工现象；式(7)表示重调度条件下，同一个工件在紧邻两个流水线上加工的次序关系，即工件在下一个流水线的开工时间不小于其在上一个流水线的完工时间；式(8‑10)表示重调度条件下，变量的取值范围；目标函数变量如下：步骤4：针对流水车间重调度目标及约束条件，采用迁徙鸟群优化方法生成流水车间重调度方案；步骤4.1：按照原调度计划产生一个迁徙鸟，并加入迁徙鸟群，循环随机若干个初始迁徙鸟加入迁徙鸟群；步骤4.2：对每个迁徙鸟计算目标函数值，选择迁徙鸟群中目标函数值最优的迁徙鸟作为领头迁徙鸟，其余迁徙鸟随机按照V形排列；步骤4.3：设置迁徙鸟群最大迭代次数和每只领头迁徙鸟带领迁徙鸟群的最大迭代次数；步骤4.4：采用插入或交换的邻域搜索机制对领头迁徙鸟进行局部搜索，得到若干随机邻域解，将这些解按照目标函数值进行升序排列，选取目标函数值最优的邻域解更新当前领头迁徙鸟；步骤4.5：对领头迁徙鸟选择若干个未使用的随机邻域解，传递给V形队列左右两边第一个迁徙鸟；步骤4.6：对于迁徙鸟群中非领头迁徙鸟随机产生若干邻域解，并将这些领域解与该迁徙鸟的上层迁徙鸟所传递的领域解按照目标函数值升序排列，选取目标函数值最优的邻域解更新当前迁徙鸟；步骤4.7：对迁徙鸟群中非领头迁徙鸟选择若干个未使用的随机邻域解，传递给V形队列的下一层迁徙鸟；步骤4.8：当达到每只领头迁徙鸟带领迁徙鸟群的最大迭代次数时，更换领头迁徙鸟：调整领头迁徙鸟到V形队列最后位置，将V形队列中第一个迁徙鸟设置为领头迁徙鸟；步骤4.9：判断是否满足迁徙鸟群最大迭代次数，若不满足，则进行下一次迭代；否则，在当前的迁徙鸟群中选取目标函数值最优的迁徙鸟，作为流水车间重调度方案；步骤5：将流水车间重调度方案下发到流水车间各工序进行重调度。