1.一种面向中成药生产车间调度问题的求解方法，其特征在于，包括以下步骤，S1、分析在中成药生产制造中混合流水车间调度问题的问题特性，确定以最小化最大完工时间为问题求解目标，并初始化参数，包括对于初始解的破坏大小系数α，破坏重构迭代次数T；

S2、使用改进的启发式算法构造出一个初始解，然后对初始解进行破坏重构，破坏大小为初始解的长度乘以α，达到迭代次数T，选择目标值最小的初始解作为最优初始解；其中，改进的启发式算法生成初始解的实现过程包括，(a)定义以下参数，i代表一个工件，I代表工件的集合，I＝{1,2,…,i,…,c}，c代表工件的数量，n代表工件出现的次数，取值为0或者1，取值为0时代表工件第一次出现，取值为1时代表工件第二次出现，s代表阶段，S代表阶段的集合，r代表可重入阶段，t代表可跳跃阶段，S＝{1,2,…s,…k}，k代表阶段总数，Π代表工件的序列，π代表工件的序列里的一个工件，Ps,i代表工件i在阶段s上的加工时间；

(b)每个工件在初始解中出现了两次，每个工件采用两种计算指标的方式，对于第一次出现的工件，计算第一个阶段到可重入阶段的处理时间之和，对于第二次出现的工件，计算可重入阶段到最后一个阶段的处理时间之和，Ki,n代表计算工件i的指标值，计算公式为，(c)将指标值Ki,n按照由小到大的顺序进行排序，每个指标值对应一个工件，由此得到对应的工件的序列Π＝{π1，π2,…,π2c}；

(d)取出Π中的前两个工件π1，π2，然后从{π1，π2}或{π2，π1}中选择目标值较小的作为当前部分序列Z；

(e)从Π中的第三个工件开始，依次取出Π中的第i个工件，i>3，插入到当前部分序列Z中所有位置，共得到i个部分序列，评价所得到的每一个部分序列，并将最大完工时间最小的部分序列作为Z；

(f)返回步骤(e)，直到Π中的最后一个工件插入完成为止，得到完整的初始解；

对初始解的破坏重构的过程如下，

(1)随机删除个数为初始解的长度乘以α的工件，将删除的工件逐一插入到未删除的工件组成的序列Π’中；

(2)每次插入一个工件后，便对工件序列Π’通过局部搜索方法进行搜索，即依次交换相邻位置的两个工件，得到改进的序列，将最大完工时间最小的改进的序列作为最优部分序列，并在下一个工件插入时使用当前最优部分序列，直到所有被删除的工件全部插入完成，得到最优初始解；

(3)对步骤(1)和步骤(2)进行T轮迭代，输出得到的最优初始解；

S3、基于主动调度策略对当前最优初始解进行调度，生成完整的调度方案；其中，构造出一个完整的调度方案的实现过程包括以下步骤，定义以下参数，flag表示工件在可重入阶段的加工次数，flag＝0表示首次加工，flag＝1表示进行可重入加工；

对于首次加工，即flag＝0，工件按照从第一阶段到可重入阶段的前一个阶段的顺序依次处理，选择一台最早空闲的机器进行加工，工件的开始时间由在上一道工序完成时间加转移时间之和、机器空闲时间中的较大值确定，工件的结束时间为开始时间加上当前阶段加工时长,计算公式为：m

Ss,i＝max[(Es‑1,i+fs‑1,i)or(Idle)]

Es,i＝Ss,i+ps,i

其中，Ss,i表示工件i在阶段s上加工的开始时间，Es‑1,i表示工件i在阶段s‑1上加工完m成的结束时间，fs‑1,i表示工件i在阶段s‑1到阶段s之间的转移时间，Idle表示机器m的空闲时间，ps,i表示工件i在阶段s的加工时间，工件在机器上处理完成后，将flag设置为1；

若工件非首次出现，即flag＝1，则直接在可重入阶段选择空闲机器加工，并更新工件在可重入阶段的开始时间和结束时间；

对于可重入阶段后续的阶段，采用分阶段的主动调度策略进行调度，操作过程包括，步骤1，进行阶段筛选，若当前阶段非可跳跃阶段或工件不具备可跳跃属性，则将其加入候选序列π’，若当前阶段为可跳跃阶段且工件具有可跳跃属性，则工件在当前阶段无需加工，此时，将当前工件在上一阶段的结束时间同步设为当前阶段的开始时间和结束时间，并直接作为下一阶段的开始时间；

步骤2，选择一台最早空闲的机器m；

步骤3，计算每个工件在所选机器上加工的开始时间和结束时间，更新在所选机器上加工工件的最早开始时间ESTime和最晚结束时间LETime；

步骤4，通过ESTime、LETime以及非延迟因子θ确定有效加工时间窗，通过有效加工时间窗约束筛选符合条件的工件加入集合ScheduleSet，计算有效加工时间窗的公式为：ScheduledSet←θ·(LETime‑ESTime)+ESTime；

步骤5，从集合ScheduleSet中选择在当前阶段具有最长加工时间的工件分配至机器M*上，更新工件i的开始时间Ss,i和结束时间Es,i，将已经调度的工件i从π’中移除，清空ScheduleSet；

步骤6，返回步骤1，直到遍历完所有阶段，得到完整的调度方案；

S4、基于完整的调度方案，查找关键路径，确定影响最大完工时间的关键块及关键块内包含的关键工件；

S5、对识别出的关键块中的关键工件进行调整，根据可重入属性，定义四种邻域结构，使用四种邻域结构进行搜索，并执行邻域结构裁剪，输出最大完工时间小于最优初始解的优化调度方案。

2.根据权利要求1所述的一种面向中成药生产车间调度问题的求解方法，其特征在于，在生产调度问题中，关键路径是指决定整个生产过程最大完工时间的工件的序列，关键工件是指其执行时间的延迟会直接导致整个调度方案最大完工时间延长的工件，位于关键路径上；非关键工件是指其执行时间的延迟不会直接影响最大完工时间的工件，不在关键路径上；关键块是调度问题中，在关键路径上由连续操作组成的不可分割的工件的序列，关键块出现在关键路径的某一段，而非整个关键路径。

3.根据权利要求2所述的一种面向中成药生产车间调度问题的求解方法，其特征在于，基于完整调度方案，查找关键路径的实现过程如下，首先找到最大完工时间L，遍历每个工件，如果工件在最后一个阶段的完工时间等于L，则将该工件i以及该工件所在的阶段s记录下来，从当前工件依次往前查找；如果遇到可跳跃工序，并且当前工件具备可跳跃属性，则跳过当前阶段；如果遇到可重入工序，在可重入阶段查找关键工件，否则在前一道工序查找；找到加工工件i的机器m，记录机器m上关键工件所在的位置，在当前位置向前查找紧邻工件，判断是否满足下列条件，工件i的开始时间‑紧邻的前一个工件i’的结束时间＝机器清洗时间将满足条件的工件i’以及所在的阶段s记录下来，否则需要跨阶段查找，判断是否满足下列条件，工件i的开始时间‑前一个阶段工件i”的结束时间＝转移时间如果满足条件，则将工件i”以及所在的阶段s记录下来，直到查找到第一阶段最早开始加工的工件为止，此时Ss,i＝

0；上述过程执行完成后，找到了完整的关键路径，并且记录下了所有查找到的关键工件及其所在的阶段。

4.根据权利要求3所述的一种面向中成药生产车间调度问题的求解方法，其特征在于，使用四种邻域结构进行搜索，通过四种邻域结构对调度方案进行优化，四种邻域结构包括依次执行的关键块内关键工件与非关键工件的破坏重构、关键块内部交换、关键块内外交换、关键块内外两点交换，使用当前邻域结构进行搜索，如果新初始解的目标值比原最优初始解更小，那么将原最优初始解更新为新初始解，如果执行当前邻域结构后，没有获得比原最优初始解更小的新初始解，则顺次将下一种邻域结构作为当前邻域结构，直到所有邻域结构都无法对当前最优初始解更新时，将搜索后的最优初始解输出，其中，关键块内关键工件与非关键工件的破坏重构，提取在最优初始解中的关键工件，随后依次将每个关键工件重新插入剩余非关键工件组成的序列中的所有位置；

关键块内部交换，从最优初始解的关键块中选定一个关键工件，然后从关键块中选择另外一个关键工件，进行交换；

关键块内外交换，从最优初始解的关键块中选定一个关键工件，然后从关键块外选择一个非关键工件，进行交换；

关键块内外两点交换，首先选定一个在最优初始解中第一次出现的关键块内的关键工件和一个在最优初始解中第一次出现的关键块外的非关键工件，二者进行交换，然后定位二者在最优初始解中的第二次出现的位置，同步交换关键工件的第二次出现位置与非关键工件的第二次出现位置。

5.根据权利要求4所述的一种面向中成药生产车间调度问题的求解方法，其特征在于，执行邻域结构裁剪过程包括，对于关键块内关键工件与非关键工件的破坏重构，在进行每次插入操作之后，判断插入后的关键工件与相邻位置的工件是否为同一个工件，如果是同一个工件，则不再进行后续操作，继续寻找下一个位置执行插入操作，若插入后相邻位置不是同一个工件，计算插入后的工件的序列的最大完工时间，保留使得最大完工时间最小的插入位置，直到所有关键工件全部插入为止，保留使目标值最小的调度方案；

对于关键块内部交换、关键块内外交换、关键块内外两点交换，遍历初始解确定关键工件所在的位置，同样的方式查找到下一个关键工件或者非关键工件在初始解中的位置，执行交换操作，若交换后的相邻位置的工件为同一个工件，则属于无效交换，无需进行后续操作；若不是同一工件，则计算交换后的最大完工时间，并且保留使目标值最小的调度方案。