本发明公开了一种基于多目标进化算法的动态柔性作业车间调度方法,主要解决现有方法对动态变化的环境自适应能力差且搜索效率低的问题。其实现步骤是：（1）初始化。读取作业和机器属性等信息，定义优化目标,设定约束条件；（2）在初始时刻，基于静态多目标进化算法，同时优化完工时间、拖期和最大机器负载；（3）在车间生产过程中，采用由紧急动态事件驱动的重调度方式，基于动态多目标进化算法在新环境中快速产生一个新的调度方案，以同时优化待调度工件的完工时间、拖期、最大机器负载和稳定性。与传统调度方法相比，本发明能够及时响应紧急动态事件的发生，根据动态环境自适应地调整搜索策略，生成的调度方案具有效率高、稳定性优的特点。
基于多目标进化算法的动态柔性作业车间调度方法
技术领域
[0001] 本发明涉及柔性作业车间调度控制领域，可用于在动态不确定的柔性作业车间生产环境中，实现对各作业工序的机器分配以及加工顺序的调度。
背景技术
[0002] 柔性作业车间调度问题是指建立柔性作业车间调度的模型，通过某种算法为每项作业的每道工序分配适当的机器，并确定各机器上工序的加工顺序，以在满足各种约束条件的前提下，实现作业的完工时间最短、拖期最小、各机器的负载均衡等优化目标。
[0003] 实际柔性作业车间的生产环境是动态不确定的，存在着“新的作业下达”、“机器发生故障”、“故障机器修复”等多种动态因素。当面临这些扰动时，根据初始数据产生的最优调度方案的性能可能大大降低，因此亟需研究一种能够处理动态不确定因素的新型柔性作业车间调度方法。柔性作业车间的动态调度技术对实际生产系统的成功实施具有重要意义。
[0004] 进化算法是模拟生物在自然环境中的进化过程而形成的一类自适应全局优化概率搜索算法。进化算法可以处理传统优化方法难以解决的复杂优化问题，例如非连续、多模态等问题，它对整个群体实施选择、交叉、变异等操作，可以在算法的一次运行中并行搜索到多个解，加之其具有较强的环境自适应能力，因此，进化算法特别适用于求解柔性作业车间调度这类同时存在多个Pareto非支配解的动态多目标优化问题。
[0005] 目前已有的柔性作业车间调度方法存在以下不足：
[0006] 1)大多仅考虑了静态的生产环境，它们假设柔性作业车间中的所有信息都是预先可知且确定不变的，显然，当实际生产环境发生动态变化或存在不确定因素时，依据静态方法产生的调度方案不再适用。
[0007] 2)尽管目前已经出现了一些动态调度方法，但它们大多仅考虑了动态事件对车间生产效率(如完工时间)的影响。这种方法可能会产生一个与原方案截然不同的新调度方案，某些未加工工序的开始时间将会被提前或推迟，从而对依据原方案规划的其它生产活动产生严重影响，并导致作业车间系统不稳定，使生产过程缺乏连续性。因此，动态调度方法应当同时优化柔性作业车间的生产效率和稳定性。
[0008] 3)对多个优化目标的处理方式比较单一。大多已有方法采用加权求和法将多个目标转换为一个目标，这种方法将会引入较多的参数，并且需要事先对各个目标进行归一化处理。由于柔性作业车间调度问题的多个目标之间往往是相互矛盾的，因此更好的方式是采用多目标进化算法对多个目标并行处理，从而为生产管理者提供一组反映目标间不同折中程度的调度方案，为其做出最终的决策提供参考。
发明内容
[0009] 本发明的目的在于克服上述现有技术的不足，提出一种基于多目标进化算法的动态柔性作业车间调度方法，以在现实世界动态不确定的车间生产环境中，及时响应随机事件的发生，实现机器的有效分配和工序加工顺序的调度，从而提高车间的生产效率，并维护生产系统的稳定性。
[0010] 为实现上述目的，本发明的实现步骤包括如下：
[0011] (1)初始化：读取初始时刻的输入信息，包括每项作业的工序数、加工期限、权重，每道工序可分配的机器集合、各工序在相应机器上的加工时间、正常工作的机器数目；给出优化目标的定义；将初始时刻视为初始调度点t0，将紧急动态事件，包括“新的紧急作业下达”、“机器发生故障”、“故障机器修复”的发生时刻视为重调度点tl(l＝1,2,…)；在tl(l＝0,1,2,…)时刻所处的生产环境下，“完工时间”定义为从开始加工到完成当前所有可调度的工序所花费的时间开销；“拖期”定义为对作业在加工期限上的延误值进行惩罚；“机器的最大负载”定义为各台机器加工时间的最大值；“稳定性”仅在tl(l＝1,2,…)有定义，将其定义为各工序在新旧方案中开始加工时间和完成时间的差别；所设定的约束条件包括加工时间约束、工序优先级约束、禁止抢先占有的约束；
[0012] (2)在初始时刻t0，根据车间内机器和作业的属性，基于静态多目标进化算法，同时最小化以下目标：完工时间、拖期以及机器的最大负载，预先产生一组Pareto非支配解，Pareto非支配解是指提高该解在任何一个目标上的性能，都必然会导致它在剩余的至少一个目标上的性能降低；将Pareto非支配解提供给生产管理者进行参考，并由他从中挑选出一个符合生产要求的满意解作为调度方案；
[0013] (3)在车间生产过程的每个重调度点tl(l＝1,2,…)时刻，采用由紧急动态事件驱动的基于动态多目标进化算法的反应式重调度方式：依据机器和作业的当前属性，包括当前可以正常工作的机器，每项作业剩余未加工的工序，当前每台机器上正在加工的工序，从上一个重调度点tl-1时刻开始至tl时刻新下达的作业，每道工序当前可分配的机器集合，在多目标进化算法的群体初始化中引入启发式动态优化策略，使得算法快速地适应动态变化的环境，产生一组能够优化车间的完工时间、拖期、机器的最大负载及稳定性的新的Pareto非支配解，提供给生产管理者,并由他从中挑选出一个符合生产要求的满意解作为调度方案；该方案在车间中一直执行，直到下一个紧急动态事件发生，重新启动动态多目标进化算法进行调度。
[0014] 本发明的进一步设计在于：
[0015] 其中，步骤(1)所述的tl(l＝0,1,2,…)时刻的完工时间定义为：
[0016]
[0017] 其中，n(tl)表示到tl时刻为止，已下达到柔性作业车间中的作业总数；标记第i项作业Ji在tl时刻是否需要调度，即它是否包含可调度的工序， 表示
作业Ji在tl时刻需要调度， 表示Ji在tl时刻不需要调度；在tl时刻的调度方案
中，Ci(tl)表示完成Ji当前所有可调度工序的时间；Si(tl)表示Ji中第一个可调度工序的开始时间；
[0018] 步骤(1)所述的tl(l＝0,1,2,…)时刻的拖期定义为：
[0019]
[0020] 其中，ωi表示作业Ji的权重；DDi(tl)表示在tl时刻，Ji中所有可调度工序的加工期限；
[0021] 步骤(1)所述的tl(l＝0,1,2,…)时刻机器的最大负载指标定义为：
[0022]
[0023] 其中，m是柔性作业车间内机器的总台数； 标记第k台机器Mk在tl时刻是否能够正常工作， 表示Mk可正常工作， 表示Mk发生故障；
kr k
是根据tl时刻的调度方案，在Mk上第r个进行加工的工序O (tl)的加工时间；q (tl)是tl时刻分配到Mk上的工序个数；
[0024] 步骤(1)所述的tl(l＝1,2,…)时刻的稳定性定义为：
[0025]
[0026] 其中，sij(tl)、cij(tl)分别表示在tl时刻的调度方案中，第i项作业的第j道工序Oij(tl)的开始和完成加工时间；rush starting表示新方案比原方案提前开始的工序集合；delay starting表示新方案比原方案推迟开始的工序集合；delay delivery表示新方案比原方案推迟完成的工序集合；惩罚因子γ＝1.5；稳定性的公式只针对在tl和tl-1时刻均需调度的工序进行计算；
[0027] 步骤(1)所述的加工时间约束是指每道工序在可对其进行加工的每台机器上的加工时间是事先确定的；
[0028] 步骤(1)所述的工序优先级约束是指每项作业的各道工序是按事先确定的顺序进行加工的；在柔性作业车间问题中，每道工序可以在它机器集合中的任一台上进行加工；
[0029] 步骤(1)所述的禁止抢先占有的约束包括：(i)每道工序的加工，只能在同一作业中排在它之前的所有工序都完成之后才能开始进行；(ii)如果将一道工序分配给了某台机器，只有在这台机器完成之前调度的所有工序之后，才能开始该道工序的加工。
[0030] 其中，步骤(2)所述的在初始时刻t0，基于静态多目标进化算法的调度方法的具体步骤如下：
[0031] a)群体初始化：根据t0时刻车间的当前状态，随机生成初始群体P(t0)，初始群体P(t0)中的每个初始个体包括工序序列向量和机器分配向量；计算初始群体中每个个体的多目标值，即目标f1(tl)、f2(tl)、f3(tl)；从初始群体中确定出所有的Pareto非支配解构成外部存储器群体Arc(t0)；设置目标评价次数计数变量ct＝sizepop，sizepop为群体规模；
[0032] b)群体选择：采用二进制联赛选择法从群体P(t0)中选择一个个体sp；对于个体a和b，如果个体a在所有待优化的多个目标，即f1(tl)、f2(tl)、f3(tl)上均优于或等于个体b，且至少在其中一个目标上优于个体b，则称个体a支配b；从群体P(t0)中随机挑选两个个体，然后判断两个体间的相互支配关系；如果一个个体支配另一个，则选择该个体作为sp；否则，从两个个体中随机选择一个作为sp；
[0033] c)外部存储器选择：从外部存储器群体Arc(t0)中随机选择一个个体e；
[0034] d)个体繁殖：采用针对动态柔性作业车间调度问题设计的，基于工序序列向量和基于机器分配向量的交叉和变异算子，由父代个体sp和e生成子代个体sc1和sc2；
[0035] e)解码和目标评价：计算子代个体sc1和sc2的多目标值，即目标f1(tl)、f2(tl)、f3(tl)；
[0036] f)群体更新：判断子代个体sc1是否支配群体P(t0)中的某些个体，如果支配，则从这些受支配个体中随机挑选一个，并用sc1取代它；如果sc1受P(t0)中的某个体支配，则sc1不能加入群体；如果上述两种情况均不成立，则sc1随机取代P(t0)中的某一个体；对子代个体sc2采取与上述同样的群体更新方法；
[0037] g)外部存储器更新：判断子代个体sc1是否支配外部存储器Arc(t0)中的某些个体，如果支配，则将所有受支配个体从Arc(t0)中删除，并将sc1加入Arc(t0)；如果sc1受Arc(t0)中的某个体支配，则sc1不能加入Arc(t0)；如果上述两种情况均不成立，则将sc1加入Arc(t0)；对子代个体sc2采取与上述同样的外部存储器更新方法；如果Arc(t0)中解的个数超过了其最大容量M，则移除那些排挤距离较小的个体；
[0038] h)终止准则判断：如果目标评价次数计数变量ct＜最大目标评价次数，则令ct＝ct+2，转至第b)步；否则，算法终止，把当前外部存储器Arc(t0)作为在初始时刻t0预先产生的Pareto非支配解集输出，供生产管理者进行参考。
[0039] 其中，步骤(3)所述的在重调度点tl(l＝1,2,…)时刻，基于动态多目标进化算法的反应式重调度方式的具体步骤如下：
[0040] I)群体初始化：根据tl(l＝1,2,…)时刻车间的当前状态，采用启发式策略构造初始群体P(tl)，初始群体P(tl)中的每个初始个体包括工序序列向量和机器分配向量；计算初始群体中每个个体的多目标值，即目标f1(tl)、f2(tl)、f3(tl)、f4(tl)；从初始群体中确定出所有的Pareto非支配解构成外部存储器群体Arc(tl)；设置目标评价次数计数变量ct＝sizepop，sizepop为群体规模；
[0041] II)群体选择：用二进制联赛选择法从群体P(tl)中选择一个个体sp；对于个体a和b，如果个体a在所有待优化的多个目标，即f1(tl)、f2(tl)、f3(tl)、f4(tl)上均优于或等于个体b，且至少在其中一个目标上优于个体b，则称个体a支配b；先从P(tl)中随机挑选两个个体，然后判断两个体间的相互支配关系；如果一个个体支配另一个，则选择该个体作为sp；否则，从两个个体中随机选择一个作为sp；
[0042] III)外部存储器选择：从外部存储器群体Arc(tl)中随机选择一个个体e；
[0043] IV)个体繁殖：采用针对动态柔性作业车间调度问题设计的，基于工序序列向量和基于机器分配向量的交叉和变异算子，由父代个体sp和e生成子代个体sc1和sc2；
[0044] V)解码和目标评价：计算子代个体sc1和sc2的多目标值，即目标f1(tl)、f2(tl)、f3(tl)、f4(tl)；
[0045] VI)群体更新：判断子代个体sc1是否支配群体P(tl)中的某些个体，如果支配，则从这些受支配个体中随机挑选一个，并用sc1取代它；如果sc1受P(tl)中的某个体支配，则sc1不能加入群体；如果上述两种情况均不成立，则sc1随机取代P(tl)中的某一个体；对子代个体sc2采取与上述同样的群体更新方法；
[0046] VII)外部存储器更新：判断子代个体sc1是否支配外部存储器Arc(tl)中的某些个体，如果支配，则将所有受支配个体从Arc(tl)中删除，并将sc1加入Arc(tl)；如果sc1受Arc(tl)中的某个体支配，则sc1不能加入Arc(tl)；如果上述两种情况均不成立，则将sc1加入Arc(tl)；对子代个体sc2采取与上述同样的外部存储器更新方法；如果Arc(tl)中解的个数超过了其最大容量M，则移除那些排挤距离较小的个体；
[0047] VIII)终止准则判断：如果目标评价次数计数变量ct＜最大目标评价次数，则令ct＝ct+2，转至第II)步；否则，算法终止，把当前外部集合Arc(tl)作为Pareto非支配解集输出。
[0048] 其中，第I)步所述的根据启发式策略构造的初始群体由下述三部分组成：
[0049] 第一部分，利用历史信息构造“历史解”：在tl时刻，确定当前所有的未加工工序和可以正常工作的机器；提取他们在tl-1时刻调度方案中的工序序列向量和机器分配向量构成“历史解”；对于需要在tl时刻调度，但未出现在tl-1时刻调度方案中的工序，将它们随机插入到“历史解”的工序序列向量中，并将它们分别随机分配到一个可加工的机器上；20％的初始群体由“历史解”及对“历史解”实施变异操作后生成的变异个体组成；
[0050] 第二部分，构造“调度方案修补解”：针对“机器发生故障”这一紧急动态事件，对于所有未受该事件影响的工序，保持分配给它的机器和开始加工时间不变；对于直接受该事件影响的工序，即tl时刻，正在发生故障的机器等待队列中等待加工的工序，如果在它可分配的机器集合中有其余机器可正常工作，则将它转移到该机器上；对于间接受该事件影响的工序，保持它分配的机器不变；只有受影响的工序需要重新调度；针对“故障机器修复”这一紧急动态事件，将部分工序迁移到修复的机器上进行加工，这些工序应满足它们能够被该修复的机器加工，并且对它们的迁移不会影响剩余工序的开始加工时间；针对“新的紧急作业下达”这一紧急动态事件，保持原有作业的调度方案不变，而对于新作业中的每道工序，一旦有可对它加工的机器空闲，则将它安排在该机器上加工；30％的初始群体由“调度方案修补解”及对“调度方案修补解”实施变异操作后生成的变异个体组成；
[0051] 第三部分，为了增加群体的多样性，在初始群体中引入随机个体：工序序列向量通过将tl时刻所有可调度工序对应的作业号随机排列后生成；对于初始群体中的一半个体，它们的机器通过启发式机器分配规则进行分配，而另一半个体的机器则在每道工序的机器集合中随机选取；50％的初始群体由随机个体组成。
[0052] 本发明与现有技术相比存在以下优点：
[0053] 1)本发明能够及时响应实际生产环境中发生的紧急动态事件，并能在动态变化的环境中，自适应地对原有调度方案做出适当的调整；它能够同时处理工序排序和机器分配这两种调度策略，因此，与现有技术相比，本发明更适合处理现实世界中的动态柔性作业车间调度问题。
[0054] 2)本发明同时优化了柔性作业车间的效率指标(完工时间、拖期、机器的最大负载)和稳定性，并采用多目标进化算法对多个目标并行处理，从而能够为生产管理者提供一组反映目标间不同折中程度的调度方案，为其做出最终的决策提供有力的参考。
[0055] 3)本发明通过捕捉柔性作业车间中不同类型紧急动态事件的特征，并利用已有的历史调度方案信息和启发式机器分配规则，在多目标进化算法中引入了启发式的动态优化策略，提高了本发明的搜索效率，使得本发明能够快速地适应动态变化的环境，产生一组在多个优化目标间折中的新的调度方案。
附图说明
[0056] 图1为本发明提出的基于多目标进化算法的动态柔性作业车间调度方法的主体流程图；
[0057] 图2为在初始时刻t0，采用的基于静态多目标进化算法的调度方式的流程图；
[0058] 图3为在初始时刻t0采用的静态多目标进化算法中，个体的表示方法示例图；
[0059] 图4为对图3表示的个体进行解码后得到的甘特图；
[0060] 图5为针对个体中工序序列向量设计的交叉算子示例图；
[0061] 图6为排挤距离估计法示意图；
[0062] 图7为在重调度点时刻tl(l＝1,2,…)，采用的基于动态多目标进化算法的反应式重调度方式的流程图；
[0063] 图8为在重调度点时刻tl(l＝1,2,…)采用的动态多目标进化算法中，个体的表示方法示例图；
[0064] 图9为对图8表示的个体进行解码后得到的甘特图；
[0065] 图10为本发明与仅优化生产效率指标的多目标进化算法分别求解实施例时，得到的在每个重调度点上的非支配解集的平均性能指标比较图。其中10(a)为平均完工时间；10(b)为平均拖期；10(c)为平均机器最大负载；10(d)为平均稳定性。
具体实施方式
[0066] 为了更好地理解本发明的技术方案，下面结合附图和具体的实施例作进一步的描述。
[0067] 一个柔性作业车间中，初始时刻t0＝0，有10台机器，10项待加工的作业。10项作业的加工期限、权重以及包含的工序个数如表1所示，加工时间如表2所示。柔性作业车间开始工作后，“新作业下达”、“机器发生故障”、“故障机器修复”这三种类型的动态事件陆续发生。每台机器发生故障的时间间隔如表3所示；每台机器每次发生故障后需要的修复时间如表4所示；新作业下达之间的时间间隔如表5所示；新下达作业的加工期限、权重以及包含的工序个数如表6所示，加工时间如表7所示。新下达的作业中，20％的任务权重为1(不重要)，60％的权重为2(一般重要)，剩余20％的权重为4(很重要)。认为权重为4的新作业为紧急新作业，其余的新作业为常规新作业。本发明中，将“紧急新作业下达”、“机器发生故障”、“故障机器修复”视作紧急动态事件，一旦紧急动态事件发生，将启动基于动态多目标进化算法的反应式重调度方式。本实例中，当柔性作业车间内的作业数目达到1240项时，停止新作业的下达，当1240项作业全部加工完毕后，整个车间的生产停止。
[0068] 表1
[0069]作业编号 J1 J2 J3 J4 J5 J6 J7 J8 J9 J10
加工期限(分钟) 11.3868 2.5035 2.2035 3.2497 4.8579 8.8373 3.3804 10.7493 0.6042 4.0552权重 2 2 2 1 1 2 2 2 2 4
工序个数 6 9 1 4 5 5 5 9 1 5
[0070] 表2
[0071]
[0072]
[0073] *∞表示该工序不能被相应的机器加工
[0074] 表3
[0075]
[0076]
[0077] *本表仅给出了前10次故障发生的时间间隔
[0078] 表4
[0079]
[0080] *本表仅给出了前10次故障修复所需的时间
[0081] 表5
[0082]
[0083] *本表仅给出了前10项新作业下达的时间间隔
[0084] 表6
[0085]作业编号 J11 J12 J13 J14 J15 J16 J17 J18 J19 J20 …
加工期限(分钟) 20.2707 4.0544 4.4483 13.1379 19.3717 10.4268 7.6107 19.8581 7.5316 18.0237 …权重 2 1 2 2 1 2 2 2 2 4 …
工序个数 9 3 1 6 7 4 3 10 1 5 …
[0086] *本表仅给出了前10个新作业的加工期限、权重和包含的工序个数
[0087] 表7
[0088]
[0089]
[0090] *本表仅给出了前3个新作业的加工时间；∞表示该工序不能被相应的机器加工[0091] 使用本发明提出的基于多目标进化算法的动态柔性作业车间调度方法求解该实施例的动态调度方案，主体流程图如图1所示，具体步骤如下：
[0092] (1)初始化。读取初始时刻的输入信息，包括每项作业的工序数、加工期限、权重，每道工序可分配的机器集合、各工序在相应机器上的加工时间、正常工作的机器数目；给出优化目标的定义；由于生产环境是动态变化的，将初始时刻视为初始调度点t0，将紧急动态事件(对生产的进行产生重要影响或需要立刻处理的事件，本实例中的紧急动态事件为“新的紧急作业下达”，“机器发生故障”、“故障机器修复”)的发生时刻视为重调度点tl(l＝1,2,…)。
[0093] 在tl(l＝0,1,2,…)时刻所处的生产环境下，“完工时间”定义为从tl时刻起，完成当前所有可调度的工序所花费的时间开销(某道工序在tl时刻可调度指该工序满足以下3个条件：(i)该工序未被加工；(ii)该工序机器集合中至少有一台机器处于正常工作状态；(iii)同一作业中，排在该工序之前的所有未加工工序满足上述条件(ii))，按下式计算：
[0094]
[0095] 其中，n(tl)表示到tl时刻为止，已下达到柔性作业车间中的作业总数；标记第i项作业Ji在tl时刻是否需要调度，即它是否包含可调度的工序， 表示
作业Ji在tl时刻需要调度， 表示Ji在tl时刻不需要调度；在tl时刻的调度方案
中，Ci(tl)表示完成Ji当前所有可调度工序的时间；Si(tl)表示Ji中第一个可调度工序的开始时间。
[0096] 在tl(l＝0,1,2,…)时刻所处的生产环境下，“拖期”对作业在加工期限上的延误值进行惩罚，按下式计算：
[0097]
[0098] 其中，ωi表示作业Ji的权重；DDi(tl)表示在tl时刻，作业Ji中所有可调度工序的加工期限；本发明将DDi(tl)取为作业Ji的下达时间与Ji的第一道工序到最后一道在tl时刻可调度工序的平均加工时间之和，通过下式生成：
[0099]
[0100] 其中，ai为作业Ji下达到柔性作业车间中的时间；Ki为延迟因子本发明中，Ki服从均值1.5，方差为0.5的正态分布；Average_pij为工序Oij(tl)在正常工作机器上的平均加工时间；Ii(tl)为在tl时刻，作业Ji中第一道可调度工序的序号；n′i(tl)为作业Ji在tl时刻可调度的工序数目。
[0101] 在tl(l＝0,1,2,…)时刻所处的生产环境下，“机器的最大负载”定义为各台机器加工时间的最大值,以防止将过多的工序分配到同一台机器上，按下式计算：
[0102]
[0103] 其中，m是柔性作业车间内机器的总台数； 标记第k台机器Mk在tl时刻是否能够正常工作， 表示Mk可正常工作， 表示Mk发生故障；
是根据tl时刻的调度方案，在Mk上第r个进行加工的工序Okr(tl)的加工时间；qk(tl)是tl时刻分配到Mk上的工序个数。
[0104] 稳定性仅在tl(l＝1,2,…)有定义，本发明将其定义为各工序在新旧方案中开始加工时间和完成时间的差别，按下式计算：
[0105]
[0106] 其中，sij(tl)、cij(tl)分别表示在tl时刻的调度方案中，第i项作业的第j道工序Oij(tl)的开始和完成加工时间；rush starting表示新方案比原方案提前开始的工序集合；delay starting表示新方案比原方案推迟开始的工序集合；delay delivery表示新方案比原方案推迟完成的工序集。如果新方案将某些工序的开始时间提前(即工序Oij(tl)∈rush starting)，它将使得依据原调度方案规划的材料交付期提前，从而导致较高的紧急订单成本，因此本发明对此情况比推迟开始时间(Oij(tl)∈delay starting)和推迟完成时间(Oij(tl)∈delay delivery)的情况施加更大的惩罚(令γ＝1.5)。稳定性的公式只针对在tl和tl-1时刻均需调度的工序进行计算，它的目的是防止同一工序在新旧方案中的开始和完成时间差别过大。
[0107] 上述四个目标f1(tl)、f2(tl)、f3(tl)、f4(tl)的取值均大于或等于0，取值越小越好。
[0108] 本发明设定的约束条件包括加工时间约束、工序优先级约束、以及禁止抢先占有的约束。加工时间约束是指每道工序在可对其进行加工的每台机器上的加工时间是事先确定的。工序优先级约束是指每项作业的各道工序是按事先确定的顺序进行加工的。在柔性作业车间问题中，每道工序可以在它的机器集合中任一台上进行加工。禁止抢先占有的约束包括：(i)每道工序的加工，只能在同一作业中排在它之前的所有工序都完成之后才能开始进行；(ii)如果将一道工序分配给了某台机器，只有在这台机器完成之前调度的所有工序之后，才能开始该道工序的加工。
[0109] (2)在初始时刻t0＝0，根据车间内机器和作业的属性，基于静态多目标进化算法，同时最小化以下目标：完工时间、拖期以及机器的最大负载，预先产生一组Pareto非支配解，Pareto非支配解是指提高该解在任何一个目标上的性能，都必然会导致它在其它至少一个目标上的性能降低；将Pareto非支配解提供给生产管理者进行参考，并由他从中挑选出一个符合生产要求的满意解作为调度方案；本步骤中基于静态多目标进化算法的调度方式的流程图如图2所示，其具体实现步骤如下：
[0110] a)群体初始化。根据t0时刻车间的当前状态，随机生成初始群体P(t0)。计算初始群体中每个个体的多目标值，即工时间f1(tl)、拖期f2(tl)、机器的最大负载f3(tl)。从初始群体中确定出所有的Pareto非支配解构成外部存储器群体Arc(t0)。设置目标评价次数计数变量ct＝sizepop，sizepop为群体规模。
[0111] 初始群体P(t0)由sizepop个随机生成的个体组成，每个个体表示初始时刻t0＝0时问题的一个候选解，即一个候选调度方案。本发明中，一个个体包括两个向量：(i)工序序列向量；(ii)机器分配向量。图3给出了个体表示方法的示例。对于工序序列向量，采用基于作业的表示方法，同一作业的工序均用该作业号表示。例如，图3中，工序O21、O22、O23、O24均用作业号2表示。每道工序依据它在工序序列向量中出现的顺序进行转换。例如，工序序列向量中第一个出现的数字2代表工序O21,第二个出现的2代表O22，依此类推。因此，可将图3中的工序序列向量解释为：
[0112] O21＞O31＞O91＞O11＞O22＞O71＞O23＞O41＞O61＞O51＞O62＞O42＞O101＞O24＞O81＞O82＞O102＞O43＞O83＞O12
[0113] 其中，a＞b表示将工序a首先加入为它分配的机器等待队列中，然后再调度工序b。
[0114] 机器分配向量表示给每道工序分配的机器。它的分配顺序是：从当前序号最小作业的第一道可调度工序到序号最大作业的最后一道可调度工序。例如，在图3中，设当前可正常工作的机器为M1-M10。在机器分配向量中，第一个元素3表示将当前序号最小的作业J1的第一道可调度工序O11分配给机器M3；第二个元素8表示将作业J1的第二道可调度工序O12分配给机器M8；第三个元素6表示将当前序号第二小的作业J2的第一道可调度工序O21分配给机器M6；依此类推。因此，可将机器分配矩阵解释为：
[0115] O11→M3,O12→M8,O21→M6,O22→M7,O23→M1,O24→M1,O31→M2,O41→M7,O42→M9,O43→M4,
[0116] O51→M10,O61→M8,O62→M6,O71→M2,O81→M9,O82→M5,O83→M9,O91→M9,O101→M6,O102→M5
[0117] 其中，→表示将工序分配给相应的机器。
[0118] 在计算每个个体的目标值时，首先需将个体解码为甘特图。图4给出了图3中个体对应的甘特图。表8列出了每道工序在分配给它的机器上的加工时间。创建图4所示甘特图的基本规则是按照工序序列向量的顺序依次安排各工序，具体过程如下：首先，考虑工序序列中的第一道工序O21，由于初始时刻所有机器均空闲，因此直接将它安排在机器M6上，并从t0＝0开始加工；同理，将排在工序序列第二、三、四位的工序O31、O91、O11分别安排在相应的机器M2、M9、M3上，并从t0＝0开始加工；对于排在工序序列第五位的工序O22，它所分配的机器M7空闲，但由于受到禁止抢先占优的约束，它只能在同一作业中的前一道工序(O21)完成后才能开始加工，因此O22在M7上的开始加工时间为t＝0.09分钟；按照上述相同的方法，将工序序列中的后续工序依次安排在相应的机器上。
[0119] 表8
[0120]工序 O21 O31 O91 O11 O22 O71 O23 O41 O61 O51
分配的机器 6 2 9 3 7 2 1 7 8 10
加工时间(分钟) 0.09 1.01 0.13 0.47 0.45 0.10 0.82 0.14 1.06 0.97
工序 O62 O42 O101 O24 O81 O82 O102 O43 O83 O12
分配的机器 6 9 6 1 9 5 5 4 9 8
加工时间(分钟) 0.10 0.32 0.15 0.55 0.58 0.22 2.43 0.14 0.52 0.07
[0121] b)群体选择。采用二进制联赛选择法从群体P(t0)中选择一个个体sp；对于个体a和b，如果个体a在所有待优化的多个目标，即f1(tl)、f2(tl)、f3(tl)上均优于或等于个体b，且至少在其中一个目标上优于个体b，则称个体a支配b；从群体P(t0)中随机挑选两个个体，然后判断两个体间的相互支配关系；如果一个个体支配另一个，则选择该个体作为sp；否则，从两个个体中随机选择一个作为sp。
[0122] c)外部存储器选择。从外部存储器群体Arc(t0)中随机选择一个个体e。
[0123] d)个体繁殖。采用针对动态柔性作业车间调度问题设计的，基于工序序列向量和基于机器分配向量的繁殖算子，由父代个体sp和e生成子代个体sc1和sc2。
[0124] 基于工序序列向量的繁殖算子包括基于工序序列向量的交叉算子和变异算子两类。
[0125] 假设待交叉的两个父代个体为Parent1和Parent2，它们的工序序列向量分别为：[7 8 6 8 9 7 9 8 9 8]和[8 6 7 9 8 9 7 8 8 9]，图5给出了本发明采用的基于工序序列向量的交叉算子示例图，它的实施步骤是：
[0126] 第一步：在重调度点tl时刻，将当前所有可调度的作业随机分成两组：G1和G2。如图5所示，假设当前可调度的作业号为6、7、8、9，将它们随机分成两组：G1：6、9；G2：7、8。
[0127] 第二步：对于来自第一组G1的作业号，它的工序从父代个体Parent1中选取，并按照它们在Parent1中的原始位置将其记录在一个新的数组R1中，如图5中，R1为××6×9×9×92
×，其中，×表示相应的位置没有元素；对于来自第一组G 的作业号，它的工序从父代个体Parent2中选取，并按照它们在Parent2中的原始位置将其记录在一个新的数组R2中，如图5中，R2为8×7×8×788×；
[0128] 第三步：将R1和R2中记录的工序按照它们的原始顺序进行合并，以产生一个子代个体。当合并时，如果两道工序在各自的父代个体中具有相同的位置，例如图5中，作业号6和7均位于相应父代个体的第三个位置，则它们在子代个体中的顺序随机产生。图5中，产生的第一个子代个体为：[8 7 6 9 8 7 9 8 8 9 ]。
[0129] 依据上述方法，生成另一个子代个体。不同点是，G1中作业号对应的工序取自Parent2，G2中作业号对应的工序取自Parent1。图5中，产生的第二个子代个体为：[7 6 8 8 9 7 9 8 8 9]。
[0130] 本发明采用交换和插入算子对工序序列向量进行变异。交换算子随机选取工序序列向量中的两道作业号不同的工序，并交换它们的位置。插入算子随机选取工序序列向量中的两道工序，将其中一道工序插入另一道之前的位置。当对一个个体进行变异操作时，以0.5的概率随机选择交换或插入算子作为变异算子。
[0131] 当对个体的工序序列向量执行繁殖算子操作时，相应的机器分配向量保持不变。
[0132] 基于机器分配向量的繁殖算子包括基于机器分配向量的交叉算子和变异算子两类。
[0133] 根据本发明采用的个体机器分配向量的特点，在两个父代个体机器分配向量中，相同位置上的机器对应于同一道工序，因此，本发明对机器分配向量采用常规的单点交叉算子：在机器分配向量中，随机选取一个元素(第一个和最后一个元素除外)作为交叉点，交换两个父代机器分配向量在该点之后的所有元素，即生成两个子代个体。
[0134] 本发明采用的基于机器分配向量的变异算子按如下方法进行操作：随机选取向量中的一个元素，从对应工序的机器集合中随机选取另一台正常工作的机器替换该机器。
[0135] 当对个体的机器分配向量执行繁殖算子操作时，相应的工序序列向量保持不变。
[0136] e)解码和目标评价。计算子代个体sc1和sc2的多目标值，即完工时间f1(tl)、拖期f2(tl)、机器的最大负载f3(tl)。
[0137] f)群体更新。判断子代个体sc1是否支配群体P(t0)中的某些个体，如果支配，则从这些受支配个体中随机挑选一个，并用sc1取代它；如果sc1受P(t0)中的某个体支配，则sc1不能加入群体；如果上述两种情况均不成立，则sc1随机取代P(t0)中的某一个体；对子代个体sc2采取与上述同样的群体更新方法；
[0138] g)外部存储器更新。判断子代个体sc1是否支配外部存储器Arc(t0)中的某些个体，如果支配，则将所有受支配个体从Arc(t0)中删除，并将sc1加入Arc(t0)；如果sc1受Arc(t0)中的某个体支配，则sc1不能加入Arc(t0)；如果上述两种情况均不成立，则将sc1加入Arc(t0)。对子代个体sc2采取与上述同样的外部存储器更新方法。如果Arc(t0)中解的个数超过了其最大容量M，则移除那些排挤距离较小的个体；
[0139] 本发明采用排挤距离估计个体邻域的密度。将当前群体中的所有个体分别依据各个目标函数进行排序，则个体xi的排挤距离定义为在各个经归一化后的目标函数上，排列在xi的左侧和右侧的两个体的距离的平均值。如图6所示，虚线所围成的四边形的平均边长即为个体xi的排挤距离。某个体的排挤距离越小，则说明该个体周围的密度越大。边界点xk的排挤距离取为无穷大，以保证边界点不会被移除。
[0140] h)终止准则判断。如果目标评价次数计数变量ct＜最大目标评价次数，则令ct＝ct+2，转至第b)步；否则，算法终止，把当前外部存储器Arc(t0)作为在初始时刻t0预先产生的Pareto非支配解集输出，供生产管理者进行参考。
[0141] (3)在车间生产过程的每个重调度点tl(l＝1,2,…)时刻，采用由紧急动态事件驱动的基于动态多目标进化算法的反应式重调度方式；依据机器和作业的当前属性，包括当前可以正常工作的机器，每项作业剩余未加工的工序，当前每台机器上正在加工的工序，从上一个重调度点tl-1时刻开始至tl时刻新下达的作业，每道工序当前可分配的机器集合，在多目标进化算法的群体初始化中引入与问题知识相关的启发式动态优化策略，使得算法快速地适应动态变化的环境，产生一组能够优化车间的完工时间、拖期、机器的最大负载及稳定性的新的Pareto非支配解，提供给生产管理者,并由他从中挑选出一个符合生产要求的满意解作为调度方案；该方案在车间中一直执行，直到下一个紧急动态事件发生，重新启动动态多目标进化算法进行调度。本步骤中基于动态多目标进化算法的反应式重调度方式的流程图如图7所示，其具体实现步骤如下：
[0142] I)群体初始化：根据tl(l＝1,2,…)时刻车间的当前状态，采用启发式策略构造初始群体P(tl)，初始群体P(tl)中的每个初始个体包括工序序列向量和机器分配向量；计算初始群体中每个个体的多目标值，即完工时间f1(tl)、拖期f2(tl)、机器的最大负载f3(tl)、稳定性f4(tl)；从初始群体中确定出所有的Pareto非支配解构成外部存储器群体Arc(tl)；设置目标评价次数计数变量ct＝sizepop，sizepop为群体规模。
[0143] 在tl时刻，根据启发式策略构造的初始群体P(tl)由下述三部分组成：
[0144] 第一部分，利用历史信息构造“历史解”：在tl时刻，确定当前所有的未加工工序和可以正常工作的机器。提取他们在tl-1时刻调度方案中的工序序列向量和机器分配向量构成“历史解”。对于需要在tl时刻调度，但未出现在tl-1时刻调度方案中的工序，将它们随机插入到“历史解”的工序序列向量中，并将它们分别随机分配到一个可加工的机器上。20％的初始群体由“历史解”及对“历史解”实施变异操作后生成的变异个体组成。
[0145] 第二部分，构造“调度方案修补解”：针对“机器发生故障”这一紧急动态事件，对于所有未受该事件影响的工序，保持分配给它的机器和开始加工时间不变；对于直接受该事件影响的工序，即tl时刻，正在发生故障的机器等待队列中等待加工的工序，如果在它可分配的机器集合中有其余机器可正常工作，则将其转移到该机器上；对于间接受该事件影响的工序，保持其分配的机器不变；只有受影响的工序需要重新调度。针对“故障机器修复”这一紧急动态事件，将部分工序迁移到修复的机器上进行加工，这些工序应满足它们能够被该修复的机器加工，并且对它们的迁移不会影响其它工序的开始加工时间。针对“新的紧急作业下达”这一紧急动态事件，保持原有作业的调度方案不变，而对于新作业中的每道工序，一旦有可对它加工的机器空闲，则将它安排在该机器上加工。30％的初始群体由“调度方案修补解”及对“调度方案修补解”实施变异操作后生成的变异个体组成。
[0146] 第三部分，为了增加群体的多样性，在初始群体中引入随机个体：工序序列向量通过将tl时刻所有可调度工序对应的作业号随机排列后生成；对于初始群体中的一半个体，它们的机器通过启发式机器分配规则进行分配，而另一半个体的机器则在其相应的机器集合中随机选取。50％的初始群体由随机个体组成。
[0147] 本发明中的启发式机器分配规则有两条：(i)将各工序在各机器上的加工时间构成加工时间表，如表9所示。搜索加工时间表内的全局最小值，例如，表9中初始全局最小值为工序O24在机器M4上的加工时间1分钟；将全局最小值对应的机器分配给相应的工序，例如，表9中，将机器M4分配给工序O24；然后固定此分配，并更新该机器上的负载，即将该全局最小值加到其它工序在此机器上的加工时间里，例如，表9中，将1分别加到M4所在列的其它元素上；其后，针对尚未分配机器的其它工序，重复此过程。(ii)首先将加工时间表内的作业随机排序，如表10中，经随机排序后，依次为作业J3、J2、J4；然后依次对每道工序，找出具有最小加工时间的机器进行分配，如表10中，工序O35的最小加工时间为在机器M4上的3分钟；固定该分配，并更新该机器上的负载，即将该最小值加到其它工序在此机器上的加工时间里，如表10中，将3加到M4所在列的其它元素上；其后，依次针对尚未分配机器的其它工序，重复此过程。
[0148] 表9
[0149]
[0150] 表10
[0151]
[0152] 群体中的每个个体表示tl时刻问题的一个候选解，个体采用与t0时刻相同的表示方法。在计算每个个体的目标值时，首先需将个体解码为甘特图。图8给出了tl时刻某一个体表示的示例图。假设重调度时刻为tl＝10，当前可调度的工序为O69、O76、O77、O81、O82、O83、O84、O91、O92、O93，在tl时刻，有两道工序O68和O75正分别在机器M6、M5上加工。如图8所示，经过对它的转换，其对应的工序加工序列可表示为：O76(6)＞O81(3)＞O69(3)＞O82(2)＞O91(9)＞O77(5)＞O92(10)＞O83(2)＞O93(5)＞O84(6),其中括号内的数字表示给每道工序分配的机器，图9给出了图8中个体对应的甘特图。表11列出了每道工序在分配给它的机器上的加工时间。创建图9所示甘特图的过程如下：首先，考虑工序序列中的第一道工序O76。由于将它分配给了机器M6，根据禁止抢先占有的约束,它只能在O75(作业J7中排在O76之前的一道工序)和O68(机器M6上当前正在加工的工序)均加工完毕后才能开始加工；其次，考虑排在工序序列第二位的工序O81，由于O81是作业J8的第一道工序，并且分配给它的机器M3当前空闲，因此O81在tl＝10时即可在M3上开始加工，加工时间为0.5分钟；排在第3位的工序O69在机器M3上的开始加工时间为：工序O68和O81完工时间中的较大值；按照上述相同的方法，将工序序列中的后续工序依次安排在相应的机器上。
[0153] 表11
[0154]工序 O76 O81 O69 O82 O91 O77 O92 O83 O93 O84
分配的机器 6 3 3 2 9 5 10 2 5 6
加工时间(分钟) 1.3 0.5 1.8 0.7 0.3 1 0.9 1.3 0.4 0.4
[0155] 在解码过程中，本发明还使用了“空闲时间间隔插入”的方法。例如，依据工序序列，在机器M5上，工序O93应当在O77之后加工。但由图9可见，在机器M5上O92的完工时间(11.2)和O77的开始加工时间(11.8)之间有空闲时间间隔，而O93的加工时间(0.4分钟)小于该时间间隔的长度(11.8-11.2＝0.6分钟)，因此，将O93插入该间隔内，并当它的前一道工序O92完工时(11.2)开始加工。
[0156] II)群体选择。采用二进制联赛选择法从群体P(tl)中选择一个个体sp；对于个体a和b，如果个体a在所有待优化的多个目标，即f1(tl)、f2(tl)、f3(tl)、f4(tl)上均优于或等于个体b，且至少在其中一个目标上优于个体b，则称个体a支配b；先从P(tl)中随机挑选两个个体，然后判断两个体间的相互支配关系；如果一个个体支配另一个，则选择该个体作为sp；否则，从两个个体中随机选择一个作为sp。
[0157] III)外部存储器选择。从外部存储器群体Arc(tl)中随机选择一个个体e。
[0158] IV)个体繁殖。采用针对动态柔性作业车间调度问题设计的，基于工序序列向量和基于机器分配向量的繁殖算子(与t0时刻相同)，由父代个体sp和e生成子代个体sc1和sc2。
[0159] V)解码和目标评价。计算子代个体sc1和sc2的多目标值，即完工时间f1(tl)、拖期f2(tl)、机器的最大负载f3(tl)、稳定性f4(tl)。
[0160] VI)群体更新。判断子代个体sc1是否支配群体P(tl)中的某些个体，如果支配，则从这些受支配个体中随机挑选一个，并用sc1取代它；如果sc1受P(tl)中的某个体支配，则sc1不能加入群体；如果上述两种情况均不成立，则sc1随机取代P(tl)中的某一个体。对子代个体sc2采取与上述同样的群体更新方法。
[0161] VII)外部存储器更新。判断子代个体sc1是否支配外部存储器Arc(tl)中的某些个体，如果支配，则将所有受支配个体从Arc(tl)中删除，并将sc1加入Arc(tl)；如果sc1受Arc(tl)中的某个体支配，则sc1不能加入Arc(tl)；如果上述两种情况均不成立，则将sc1加入Arc(tl)。对子代个体sc2采取与上述同样的外部存储器更新方法。如果Arc(tl)中解的个数超过了其最大容量M，则移除那些排挤距离较小的个体。
[0162] VIII)终止准则判断。如果目标评价次数计数变量ct＜最大目标评价次数，则令ct＝ct+2，转至第II)步；否则，算法终止，把当前外部集合Arc(tl)作为tl时刻的Pareto非支配解集输出。该解集即为在重调度点tl时刻产生的一组在多个目标间折中的重调度方案，供生产管理者进行参考。
[0163] 在本发明的实施例中，多目标进化算法的参数设置如下：群体规模为100；基于工序序列向量和基于机器分配向量的交叉概率分别取0.45；基于工序序列向量和基于机器分配向量的变异概率分别取0.1；最大目标评价次数取为20000。
[0164] 本发明的效果可以通过以下仿真实验进一步说明：
[0165] 1.实验条件：
[0166] 在CPU为Intel core i5 3.2GHz、内存4GB、WINDOWS XP系统上使用Matlab 2010进行仿真。
[0167] 2.实验内容：
[0168] 本发明针对上述具有10台机器、10项初始作业的柔性作业车间实施例求解动态调度方案。本实施例中，有“新作业下达”、“机器发生故障”、“故障机器修复”三类动态事件随机发生。本发明将“紧急新作业下达”、“机器发生故障”、“故障机器修复”视作紧急动态事件，一旦紧急动态事件发生，将启动基于动态多目标进化算法的反应式重调度方式。本实例中，当柔性作业车间内的作业数目达到1240项时，停止新作业的下达，当1240项作业全部加工完毕后，整个车间的生产停止。
[0169] 3.实验结果
[0170] 采用本发明与现有技术中的完全反应式调度方法分别对动态柔性作业车间调度问题进行求解。完全反应式调度方法指依据特定的机器分配规则将工序分配到不同的机器上，一旦某台机器空闲并且在它的等待队列中有待加工的工序,它将依据某一启发式优先级分派规则选择优先级最高的工序进行加工。
[0171] 采用四种启发式优先级分派规则(最短加工时间SPT、先进先出FIFO、后进先出LIFO、随机分派规则random dispatching rule)以及三种机器分配规则(第一条规则首先为每道工序找出具有最短加工时间的机器，然后固定该分配并更新相应的机器负载，简称MAR1；第二条规则将每道工序分配给当前具有最小负载的可加工机器，简称MAR2；第三条规则为每道工序随机选择一台可加工工序，简称MAR3)分别进行组合，构成12种完全反应式调度方法，与本发明在“完成所有1240项作业的时间”、“加权平均作业拖期”、“平均机器负载”这3项性能指标上进行比较。每种方法在实施例中分别独立地运行30次，平均运行结果如表12所示。
[0172] 由表12可见，与完全反应式调度方法相比，本发明能够显著地缩短动态柔性作业车间完成所有作业的时间；同时，本发明能够大幅度地降低对作业交付日期的延迟时间。在平均机器负载方面，包含MAR1的完全反应式调度方法的性能优于本发明，原因是MAR1总是将工序分配给具有最短加工时间的机器，因而能够降低机器的整个负载。但另一方面，它可能导致某台机器的等待队列很长，而其它机器则空闲，从而使得所有作业的完工时间变长，延迟时间也增大。总之，与传统的完全反应式调度方法相比，本发明能够很大程度地提高动态柔性作业车间的生产效率。
[0173] 表12
[0174]
[0175]
[0176] *表中的结果为平均值±方差
[0177] 本发明将柔性作业车间的稳定性与生产效率指标，即完工时间、拖期、机器的最大负载同时进行了优化。为了验证该方法的有效性，将本发明与仅优化生产效率指标的多目标进化算法进行比较。在每个重调度点，将本发明独立地运行30次；将每次运行得到的解集合并，并从中确定出该调度点上的非支配解集；将非支配解集在四个目标上分别取平均值，并绘制于图10中。对于仅优化生产效率指标的多目标进化算法，也采用上述方法，不同点是：在多目标进化算法运行过程中的非支配比较里，仅考虑三个生产效率目标；而仅对于算法最终获取的非支配解，计算稳定性目标，以便于与本发明进行比较。
[0178] 由图10可见，与仅优化生产效率指标的多目标进化算法相比，本发明显著地改善了系统的稳定性。本发明在稳定性方面改进的幅度远远高于在生产效率指标上的退化，这表明如果在求解动态柔性作业车间调度问题时，同时考虑稳定性和生产效率指标，将会得到更加稳定的解，并且不会严重地影响生产效率。
[0179] 综上，本发明提出的基于多目标进化算法的动态柔性作业车间调度方法能够及时处理实际车间生产环境中发生的紧急动态事件，并能在动态变化的环境中，快速并自适应地对原有调度方案做出适当的调整；它同时优化了柔性作业车间的生产效率和稳定性指标，使得生成的调度方案在保持较短的作业完工时间和拖期的同时，车间的稳定性也更强。与现有的完全反应式调度方法相比，本发明能够显著降低完成所有作业的时间和平均作业拖期，因此，本发明非常适合处理现实世界中的动态柔性作业车间调度问题。
