有效求解柔性作业车间调度问题的混合遗传算法和禁忌搜索算法

【0】Li X, Gao L. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. International Journal of Production Economics. 2016;174:93-110. doi:10.1016/j.ijpe.2016.01.016

0. 摘要（Abstract）

柔性作业车间调度问题(FJSP)是经典作业车间调度问题的扩展，是现代制造系统中一个非常重要的问题。它允许一个操作被给定集合中的任何机器处理。它已被证明是一个NP-hard问题。本文以最大完工时间最小化为目标，提出了一种有效的混合算法(HA)，该算法将遗传算法(GA)和禁忌搜索算法(TS)相结合。利用具有强大全局搜索能力的遗传算法进行搜索，利用具有良好局部搜索能力的TS进行开发。因此，本文提出的HA具有很好的搜索能力，能够很好地平衡集约化和多样化。为了有效地求解FJSP问题，该方法采用了有效的编码方法、遗传算子和邻域结构。使用FJSP的六个著名的基准实例(包括201个开放问题)来评估所提出的HA的性能。还提供了所提出的HA和其他最新报告算法之间的比较，以显示所提出方法的有效性和效率。并与其他算法的计算时间进行了比较。实验结果表明，在不考虑求解精度和计算时间的情况下，所提出的HA在求解FJSP方面取得了显著的进步。并对若干基准问题给出了新的最优解。

0.1. 关键词（Keywords）

原文	中文
Flexible job	柔性作业车间调度
Hybrid algorithm	混合算法
Makespan	最大完工时间
Genetic algorithm	遗传算法
Computational time	计算时间

1. 引言（Introduction）

生产调度是现代制造系统计划调度中最重要的问题之一(Chen et al, 1999)。生产调度优化技术可以通过消除或减少调度冲突、减少流程时间和在制品时间、提高生产资源利用率和适应不规律的车间扰动，显著提高制造设施的效率。在制造系统中有几种车间格调(包括作业车间调度问题，JSP) (Wang and Cheng, 2015;Liou and Hsieh, 2015)。经典的JSP问题是该领域最困难的问题之一，已被证明是NP-hard问题(gray et al, 1976)。假设每个作业的每个操作都没有灵活性的资源(包括机器和工具)。它可以满足传统制造系统的要求。然而，在现代制造企业中，为了提高生产效率，引入了许多柔性制造系统和数控机床(Seebacher and Winkler, 2014)。这些系统和机器可以处理几种类型的操作。这意味着假设一台机器只处理一个类型的操作在JSP不能匹配这种情况。在这种情况下，柔性作业车间调度问题(FJSP)越来越受到研究人员和工程师的关注(Chaudhry和Khan, 2016)。

笔记：

介绍背景，从JSP问题着手分析其是np-hard问题，并根据显示情况，引出FJSP。**

FJSP是经典JSP的扩展，它允许给定集合中的任何机器处理一个操作。FJSP可以分解为两个子问题：机器选择问题(MS)和操作排序问题(OS)。JSP只包含操作系统问题。因此，在相同的规模下，FJSP比JSP更复杂。所以它也是NP-hard问题。在Brucker和Schile(1990)于1990年首次提出这个问题之后，已经提出了许多方法来解决这个问题。

目前求解FJSP的方法主要有精确算法、调度规则、进化算法(EA) ，基于群体智能(SI)的方法，局部搜索(LS)算法等。FJSP的研究成果也被用于一些实际应用中。

每种算法都有自己的优点。然而，它也缺乏一些能力。没有一种算法能够解决基于no Free Lunch定理的所有类型的优化问题(Wolpert And Macready, 1997)。为此，本文提出了一种将全局搜索和局部搜索相结合的混合算法(HA)，利用遗传算法(GA)进行搜索，利用引导LS算法(禁忌搜索，TS)进行开发。遗传算法具有强大的全局搜索能力，而TS算法具有宝贵的局部搜索能力。该方法结合了遗传算法和TS算法的优点。因此，它具有非常有效的搜索能力，能够很好地平衡集约化和多样化。为了有效地求解FJSP问题，该方法采用了有效的编码方法、遗传算子和邻域结构。使用FJSP的6个著名的基准测试实例(包括201个开放问题)来评估所提出的HA的性能。通过实验研究，可以清楚地证明该方法的优点。

本文的其余部分结构如下。第2节介绍了文献综述。问题的表述将在第3节讨论。第4节提出了基于ha的FJSP方法。实验研究报告在第5节。第6节描述了结论和未来的工作。

笔记：

提出解决FJSP问题的痛点，引出本文的算法，结合了遗传算法和TS算法的优点，并说明验证其有效性

2. 文献综述（Literature review）

所报道的FJSP方法可以分为两类。第一个是精确法，另一个是近似法。精确方法包含数学规划(MP)方法。该近似方法包含一些调度规则和基于人工智能的方法。

• Brucker和Schile(1990)首先提出了FJSP，并提出了一种多项式图形算法(PGA)来求解双作业FJSP。
• Torabi等(2005)针对确定性柔性作业车间中常见周期多产品批量调度问题，提出了一种混合整数非线性规划，该规划需要同时确定机器分配、排序、批量和调度决策。
• Gomes等(2005)提出了一种新的FJSP整数线性规划模型，并使用商用混合整数线性规划(MILP)软件来解决这一问题。
• Demir和Isleyen(2013)评估了FJSP的几个数学模型。
• Roshanaei等人(2013)为FJSP开发了两个新的MILP模型。精确方法可以得到精确的最优解。

然而，精确的算法对于解决大规模的FJSP实例(操作总数超过200)是无效的(Pezzella et al, 2008)。因此，目前大多数关于FJSP的方法都集中在近似方法上，包括调度规则和基于人工智能的方法。

• Paulli(1995)应用了一些现有的dr来解决MS子问题，并使用了几种不同的TS方法来处理OS子问题。
• Tay和Ho(2008)利用遗传规划发现的dr来求解多目标FJSP。
• Baykasoglu和Ozbakir(2010)分析了DRs对不同灵活性水平作业车间调度绩效的影响。
• Ziaee(2014)提出了一种基于构建过程的求解FJSP的启发式方法。dr的优点是简单，可以解决大规模的问题。然而，dr的结果质量不是很好。

因此，FJSP的许多方法都是基于人工智能的方法，如人工免疫算法，滤波光束搜索、差异搜索、和谐搜索，进化算法(EA)，基于群体智能(SI)的方法，局部搜索(LS)算法，混合算法(HA)等。

进化算法(EA)是一种有效的元启发式方法，包括遗传算法(GA)、遗传规划、进化策略和进化规划。

• Jensen(2003)考虑了FJSP健壮和灵活的解决方案问题。Ho等人(2007)提出了FJSP学习和进化的架构，称为可学习遗传架构(LEGA)。

• Pezzella等人(2008)开发了一种遗传算法，该算法集成了产生初始种群、选择繁殖个体和繁殖新个体的不同策略，以解决FJSP问题。

• Giovanni and Pezzella(2010)提出了一种改进的遗传算法来解决分布式FJSP问题。

• Zhang等(2011)提出了一种针对FJSP的改进遗传算法，并取得了良好的效果。

• Chen等(2012)开发了一种基于遗传算法和分组遗传算法的FJSP算法。

• 蒋和林(2013)提出了一种多目标EA，该EA利用了有效的遗传算子，并仔细保持了多目标FJSP的种群多样性。

• Xiong et al .(2013)提出了一种多目标EA，用于具有随机机器故障的FJSP鲁棒调度。

• Demir和Isleyen(2014)开发了一种有效的遗传算法，用于操作重叠的FJSP。

• Driss等人(2015)开发了一种遗传算法，该算法采用了一种新的染色体表示和一些不同的FJSP交叉和突变策略。但是，它在MK01问题上的实验结果是错误的。作者还将提议的遗传算法应用于一家制药公司。

上述已发表的研究表明，ea具有强大的全局搜索能力，对调度问题是有效的。然而，由于缺乏邻域搜索程序，它们不具备良好的局部搜索能力。它们可以通过与其他本地搜索算法相结合而得到改进。

群智能(Swarm intelligence, SI)方法是另一种有效的元启发式方法，包括蚁群优化(ant colony optimization, ACO)算法、粒子群优化(particle Swarm optimization, PSO)算法和人工蜂群(artificial bee colony, ABC)算法等。蚁群算法擅长解决一般和组合优化问题(Girish and Jawahar, 2009)。

• Rossi和Dini(2007)提出了一个基于蚁群算法的软件系统，用于解决作业车间环境中的FJSP问题，该环境具有路由灵活性、顺序依赖的设置和运输时间。
• Girish和Jawahar(2009)提出了FJSP在makespan准则下的蚁群算法，并使用ILOG Solver来评估所提出算法的性能。
• Huang等人(2013)为FJSP开发了一种双信息素蚁群算法，考虑了作业的到期窗口和顺序依赖的设置时间。
• Rossi(2014)提出了一种基于析取图模型的蚁群算法，该算法具有增强的费洛蒙关系，该模型考虑了序列依赖的设置和运输时间。
• Gao等人(2006)为FJSP开发了一种有效的通用粒子群算法。
• Li等人(2011a)为多目标FJSP开发了一种基于pareto的ABC算法。
• Wang等(2012)提出了一种考虑完工时间的FJSP ABC算法。
• Gao等人(2015)提出了一种带有新作业插入的FJSP两阶段ABC算法。SI方法与ea具有相似的搜索特性。

局部搜索(LS)方法包括禁忌搜索(TS)、模拟退火(SA)、变邻域搜索(VNS)等。其有效性主要取决于邻域结构的设计。由于它的特性，它是解决调度问题最有效的方法之一。Hurink等(1994)采用TS技术求解FJSP。Peres和Paulli(1997)开发了一个TS来解决FJSP。Mastrolilli和Gambardella(2000)提出了一种具有两个有效邻域函数的TS程序来求解FJSP，并获得了良好的结果。Bozejko等人

(2010)提出了一种并行的双级元启发式方法，该方法基于在更高级别上实现的两种方法:TS和基于人口的方法。

• 维尔科特和比劳特(2011)为考虑完工时间和最大延迟的多标准FJSP开发了一个TS。
• Jia and Hu(2014)针对多目标FJSP提出了一种基于TS算法的反向跳跃跟踪路径链接算法。

VNS是一种著名的元启发式算法，已成功地应用于求解多个优化问题。

• Amiri等人(2010)提出了一种VNS算法来求解FJSP以最小化完工时间。
• Yazdani等人(2010)开发了一种并行VNS算法来解决最小化完工时间的FJSP问题。
• Karimi等(2012)提出了一种基于知识的FJSP VNS算法。

基于以上分析，大多数LS方法都是基于单点的方法。这一特点使得它们缺乏全局搜索能力。因此，它们应该与其他全局搜索算法相结合。

一些研究者也尝试将几种算法混合在一起，构建一些有效的FJSP混合算法(HA)。

• Zribi等人(2007)提出了FJSP的分层方法。在该方法中，针对MS子问题，他们提出了两种方法;对于操作系统子问题，他们使用混合遗传算法来处理它。
• Gao等人(2008)为FJSP开发了一种混合遗传和可变邻域下降算法。
• Ho and Tay(2008)结合进化算法，引导LS求解多目标FJSP。
• Li等(2011b)针对FJSP提出了一种具有高效邻域结构的混合TS算法。
• Moslehi和Mahnam(2011)提出了一种基于粒子群算法和局部搜索的多目标FJSP Pareto方法。
• Zhang等(2012)具有运输约束和有限处理时间的FJSP的混合遗传算法和TS。
• Yuan and Xu (2013c)将差分进化与基于关键路径的局部搜索算法相结合，用于FJSP。
• 帕拉西奥斯et al (2015 b)开发了一种混合遗传禁忌搜索算法的模糊FJSP。
• Yuan and Xu(2015)提出了将非支配排序遗传算法(NSGAII)与一种新的局部搜索算法相结合的多目标FJSP模因算法。

综上所述，不同的算法各有优缺点。表1分析了为FJSP开发的不同算法(包括MP、dr、EA、SI、LS和HA)的特性(Chaudhry and Khan, 2016)。研究应根据不同算法的特性开发出有效的方法。在分析上述方法的基础上，本研究提出了一种新的基于ha的FJSP方法。

表1 针对FJSP开发了不同算法的特性。

3. 问题建模（Problem formulation）

有一组 $n$ 个工件 J = { J 1 , J 2 , J 3 , … , J n } J= \left\{ J_1, J_2, J_3,…,J_n \right\} J={ J1​,J2​,J3​,…,Jn​} 和一组 $m$ 台机器 m = { M 1 , M 2 , M 3 , … , M m } m= \left\{ M_1, M_2, M_3,…,M_m\right\} m={ M1​,M2​,M3​,…,Mm​} 。每个工件$J_i$ 由一系列工序 { O i 1 ; O i 2 ; O i 3 ; . . . ; O i n i } \left\{ O_{i1};O_{i2};O_{i3};...;O_{in_i} \right\} { Oi1​;Oi2​;Oi3​;...;Oini​​} 组成。其中 $n_i$ 是$J_i$ 所包含的工序的个数。

每个工序$O_{ij}(i=1,2，\dots ，n;j=1,2，\dots ，n_i)$ 必须由一组给定机器$M_{ij}\in M$ 中的一台机器来处理。

为了满足要求，问题是既要确定分配机器，又要确定机器上的一系列工序。

它包含两个子问题：机器选择(MS)问题和工序排序(OS)问题。

因此，FJSP比传统的JSP更加复杂和具有挑战性，因为它需要从一组可用的机器中正确选择一台机器来处理每个作业的每个操作(Ho et al, 2007)。

本文的调度目标是使所有作业的最大完成时间最小，即makespan。FJSP的数学模型可参考Ozguven et al .(2010)和Roshanaei et al .(2013)。本文考虑的假设总结如下：

1. 工作是独立的。作业抢占是不允许的，每台机器一次只能处理一个作业。
2. 一个作业的不同操作不能同时进行。
3. 所有作业和机器在时间零点同时可用。
4. 某一作业在某台机器上加工完成后，立即传输到该工序上的下一台机器上，传输时间可以忽略不计。
5. 机器工序的准备时间与工序顺序无关，并纳入加工时间。

4. 提出了FJSP的混合算法（Proposed hybrid algorithm for FJSP）

4.1. HA算法的工作流程（Workflow of the proposed HA）

如果大家不理解遗传算法点击此处疯狂摄入！！！

本文提出的HA混合了遗传算法和LS算法(TS)。然而，设计HAs的方法有很多种。本文将TS算法引入到遗传算法的局部搜索过程中。提出的HA工作流程如图1所示。建议方法的整体程序如下：

• 步骤1：设置HA算法的参数；
• 步骤2：初始化：初始化种群并设置$Gen=1$,$Gen$为当前代；
• 步骤3：评估：根据目标对人群中的每个个体进行评估；
• 步骤4：是否满足终止条件？是，执行步骤7；否则，转步骤5；
• 步骤5：产生新一代；
  • 步骤5.1：使用遗传算子(包括选择、交叉和突变算子)产生新群体；
  • 步骤5.2：应用引导LS算法(TS)提高每个个体的质量；
• 步骤6：设置 $Gen=Gen+1$，转到步骤3；
• 步骤7：输出最佳解决方案。

图1：HA算法的工作流程

4.2. 编码与解码（Encoding and decoding）

4.2.1. 编码（Encoding）

染色体对应于FJSP的解。

在遗传算法中，个体的编码是非常重要的。本文采用Gao et al .(2006)的编码方法。

因为FJSP包含两个子问题，所以染色体包含两个字符串。第一个是OS字符串第二个是MS字符串。它们有不同的编码方法。

• OS字符串的编码方法是基于操作的表示方法，它由工序的编号组成。

这种表示使用无分区排列，作业号重复次数为1次( $O_{n_i}$ 是 job $i$ 的总操作次数)。在这种表示中，每个作业号在OS字符串中出现 $O_{n_i}$ 次。通过从左到右扫描操作系统字符串，作业号的第 $f$ 次出现表示该作业的第 $f$ 次操作。

这种表示的重要特征是OS字符串的任何排列都可以解码为可行的解决方案。

假设有 $n$ 个作业，OS字符串的长度等于 ${\sum }_{i=1}^n{O}_{n_i}$。初始OS种群根据编码原理随机生成。

• MS字符串表示为每个作业的相应操作所选择的机器。这个字符串的长度也等于${\sum }_{i=1}^n{O}_{n_i}$。

它包含 $n$ 个部分，第 $i$ 部分的长度是 $O_{n_i}$。该字符串的第一部分表示作业 $i$ 对应操作的选择机器集。该字符串中的每个基因表示固定操作的选择机器。在整个搜索过程中，操作号不会改变。假设作业 $i$ 的第 $h$ 次操作可以由一台机器来处理 S i , h = { m i , h 1 , m i , h 2 , . . . , m i , h C i h } S_{i,h}=\left\{m_{i,h1},m_{i,h2},...,m_{i,hC_{ih}} \right\} Si,h​={ mi,h1​,mi,h2​,...,mi,hCih​​}；

例如，MS字符串的第1部分可以表示为 { g i 1 , g i 2 , . . . , g i h , . . . , g i O n i } \left\{g_{i1},g_{i2},...,g_{ih},...,g_{iO_{ni}} \right\} { gi1​,gi2​,...,gih​,...,giOni​​}，其中 $g_{ih}$是$1$到$c_{ih}$ 之间的整数，表示作业i的第$h$次操作被分配给$S_{ih}$中的第$g_{ih}$台机器$m_{ih{g}_{ih}}$。初始MS字符串为由每个作业的每个操作随机选择备用机器生成。图2提供了一个示例。

笔记：

OS字符串解析：
上文提到的作业号是什么？每个工件的都有一定的工序，并且有一定的先后顺序，因为图中给的每个job都有2个工序，所以，对于每一个工件来说都有2个与其相同的数子，比如我这有 $n$ 个工件，每一工件有2个工序，那么我的OS字符串的长度为 $2n$个，那么我的OS字符串就是包含 { 1 , 1 , 2 , 2 , 3 , 3 , . . . , n , n } \left\{1,1,2,2,3,3,...,n,n\right\} { 1,1,2,2,3,3,...,n,n}组成，并每个所在位置是随机的。

MS字符串解析：
与上面的OS字符串有相同的长度，但是具有了位置关系，由于每一工件有2个工序，所以，这个集合就2个位置一组，并且表示的是，第几个组（当前字符串位置2，就是第几个工件），（当前字符串位置％2，就是该工件的第几道工序），所在的位置的字符串表示，这个工序使用第几个机器。

总结：

• 编码：染色体包含MS子串和OS字串
  • OS字符串：表示每个操作的顺序。
  • MS字符串：表示为每个作业的相应操作选择的机器；

一个解决方案由一个OS字符串和一个MS字符串组成。解决方案可以分为半主动、主动、非延迟和混合调度。(The solutions can be decoded into semi-active, active, non-delay, and hybrid schedules.)因为完工时间是一个规则的标准，所以这里采用活动进度。用于解释解码过程的符号如下：

字符	描述
$n$	作业总数
$m$	机器总数
$o_{ij}$	第 $i$ 个工件的第j个工序
$a{s}_{ij}$	操作$o_{ij}$的允许开始时间
$s_{ij}$	操作$o_{ij}$的最早开始运行的时间
$k$	为$o_{ij}$对应的替代机器
$t_{ijk}$	在机器$k$上工序$o_{ij}$的处理时间
$c_{ij}$	操作$o_{ij}$最早完成时间，即$c_{ij}=s_{ij}+t_{ijk}$

4.2.2. 解码（Decoding）

解码过程如下：

1. 根据MS字符串生成每个操作的机器；
2. 确定每台机器的操作集: m a = { o i j } 1 ≤ a ≤ m m_a=\left\{ o_{ij}\right\} 1≤a≤m ma​={ oij​}1≤a≤m
3. 确定每个作业的机器组: J m d = { m a c h i n e } 1 ≤ d ≤ n Jm_d=\left\{ {machine}\right\}1≤d≤n Jmd​={ machine}1≤d≤n
4. 每次操作允许启动时间:$a{s}_{ij}=c_{i(j-1)}(o_{ij}\in m_a)$, $c_{i(j-1)}$为同一job的$o_{ij}$预操作完成时间;
5. 检查$o_{ij}$机器的空闲时间，得到空闲区间$[t\_s,t\_e]$，依次检查这些区域(如:$max(a{s}_{ij},t\_s)+t_{ijk}\le t\_e$，最早开始时间为$s_{ij}=t\_s$，否则:检查下一个区域)，如果没有满足此条件的区域:$s_{ij}=max(a{s}_{ij},c(o_{ij}-1)),c(o_{ij}-1)$为同一台机器的$o_{ij}$预操作完成时间;
6. 每个操作的完成时间:$c_{ij}=s_{ij}+t_{ijk}$
7. 生成每个作业每个操作的起始时间和完成时间集合：$T_d(s_{ij},c_{ij})1\le d\le n$

由上式可得，每个作业的每道工序的开始时间和完成时间集合。这是车间的时间表。

图2示出编码和解码方法的示例。

图2：编码解码示例

备注疑惑点：上图的MS String 我认为应该是 2 1 3 1 2 3 才会画出Decoding的图？？？？？？？？？？？？
图2(a)显示了本例的数据。

它包含3个作业和3台机器(每个作业包含2个操作)。图2(b)显示一条染色体。它包含两个字符串。OS字符串是具有重复作业号的未分区排列。因为有3个作业，每个作业包含2个操作，所以OS字符串是由两个1、两个2和两个3组成的排列。它的长度是6。

MS字符串包含3个部分，因为有3个作业。它的长度也等于6。每一部分表示所选择的机器每个作业对应的操作。例如，第一部分表示作业1的相应操作所选择的机器。第一个基因表示从S11中为O11选择的机器。第三个基因表示从S21中选择的机器用于O21。这个字符串中的每个基因都表示进行固定操作的选定机器。在整个搜索过程中，操作号不会改变。因此，如果亲代是可行的，这种表示可以保证后代是可行的。

图2(b)中的染色体(包含一个OS字符串和一个MS字符串)可以解码为图2（c）所示的时间表。

4.3. 遗传算子（Genetic operators）

使用好的遗传算子来有效地处理问题，并在种群中高效地生成优秀的个体是非常重要的。遗传算子一般可分为三类：选择、交叉和突变。在本文中，染色体包含两个字符串：OS字符串和MS字符串。每个字符串都有自己的遗传操作符。

4.3.1. 选择（Selection）

在遗传算法中，选择算子根据适应度选择个体。本文采用了两种选择算子。

• 第一个是精英选拔制度：这种方法重现了$p_r\times Popsize$ ($p_r$ 为再现概率;$Popsize$是种群的大小，指的是亲本与后代具有良好匹配度的个体。
• 另一个是比赛选拔制度：在比赛选择中，从总体中随机选择一些个体，选择适应度较好的个体。锦标赛选择方法允许在探索和利用基因库之间进行权衡。该方案可以通过改变比赛规模来调整选择压力。

4.3.2. 交叉（Crossover）

在本文中，对OS字符串采用了两个交叉算子。在HA过程中，随机选择一个交叉操作符(50%)来交叉OS字符串。

第一个是优先操作交叉(POX)。POX的基本工作流程描述如下(双亲分别记为P1和P2;两个子代分别记为O1和O2):

• 步骤1：将作业集 J = { J 1 , J 2 , J 3 ， … ， J n } J=\left\{J_1, J_2, J_3，…，J_n\right\} J={ J1​,J2​,J3​，…，Jn​}随机分为 Jobset1 和 Jobset2 两组；
  • 下图中 Jobset1 = { 2 } =\left\{2\right\} ={ 2}和 Jobset2 = { 1 , 3 } =\left\{1,3\right\} ={ 1,3}
• 步骤2：P1中所有属于 Jobset1 的元素都被添加到O1中的相同位置，并在P1中删除;P2中任何属于 Jobset1 的元素都被添加到O2中的相同位置，并在P2中删除；
• 步骤3：将P2中剩余的元素依次追加到O1序列中剩余的空位置;P1中剩余的元素被附加到O2序列中剩余的空位置。

OS字符串的第二个交叉操作符是基于作业的交叉(JBX)。JBX的基本工作流程描述如下(双亲分别记为P1和P2;两个子代分别记为O1和O2)：

• 步骤1：将作业集 J = { J 1 , J 2 , J 3 ， … ， J n } J=\left\{J_1, J_2, J_3，…，J_n\right\} J={ J1​,J2​,J3​，…，Jn​}随机分为 Jobset1 和 Jobset2 两组;
  • 下图中 Jobset1 = { 2 } =\left\{2\right\} ={ 2}和 Jobset2 = { 1 , 3 } =\left\{1,3\right\} ={ 1,3}
• 步骤2：P1中所有属于Jobset1的元素都被添加到O1中的相同位置，并在P1中删除;P2中任何属于Jobset2的元素都被添加到O2中的相同位置，并在P2中删除;
• 步骤3：将P2中剩余的元素依次追加到O1序列中剩余的空位置;P1中剩余的元素被附加到O2序列中剩余的空位置。

对于OS字符串，图3(a)显示了POX交叉操作符的示例，图3(b)描述了JBX交叉操作符的示例。

图3：OS字符串的交叉操作符

笔记：

优先操作交叉(POX)：
上文提到了2个集合， Jobset1 = { 2 } =\left\{2\right\} ={ 2}和 Jobset2 = { 1 , 3 } =\left\{1,3\right\} ={ 1,3}，我们将P1中的 Jobset1元素直接放到$O1$的相应位置，然后把P2只有Jobset2的插空放到 $O1$ 中；
$O2$ 同理，把P2中的 Jobset1元素直接放到 $O2$ 的相应位置，然后把P1只有Jobset2的插空放到 $O2$ 中

基于作业的交叉(JBX)：
上文提到了2个集合， Jobset1 = { 2 } =\left\{2\right\} ={ 2}和 Jobset2 = { 1 , 3 } =\left\{1,3\right\} ={ 1,3}，我们将P1中的 Jobset1元素直接放到$O1$的相应位置，然后把P2只有Jobset2的插空放到 $O1$ 中；
$O2$ ，把P2中的 Jobset2元素直接放到 $O2$ 的相应位置，然后把P1只有Jobset1的插空放到 $O2$ 中

对于MS字符串，这里采用两点交叉作为交叉算子。在这个算子中，选择了两个位置一开始是随机的。然后通过在两个父字符串的位置之间交换所有元素来生成两个子字符串。由于该字符串中的每个基因都表示进行固定操作所选择的机器，因此在整个搜索过程中，操作编号不会发生变化。如果选择的亲本是可行的，这种交叉可以确保产生可行的后代。图4显示了用于MS字符串的交叉操作符的示例。首先，选择两个可行的亲本(P1和P2);然后，随机选择两个位置，在本例中，选择第2和第5个位置；取P2第2位之前的元素，取P1第2位之前的元素，取P1第5位之前的元素，取P1第5位之前的元素，取P1第5位之前的元素，取P1第5位之前的元素，取P1第5位之前的元素，取P1第5位之前的元素，取P1第5位之前的元素，取P1第5位之前的元素，取P1第5位之前的元素，取P2第3位之前的元素，取P2第3位之前的元素，取P2第4位之前的元素用同样的过程生成O2。基于整个过程，我们可以看到，如果父母双方都是可行的，那么后代将是可行的。

图4：MS字符串的交叉操作符

笔记：

就是 $P1$与 $P2$ 的2个基因片交换变成 $O1$ 和 $O2$。

4.3.3. 变异（Mutation）

本文对OS字符串采用了两种变异算子。在HA过程中，随机选择一个变异算子(50%)对OS字符串进行变异。

• 第一个是交换突变。交换突变的基本工作过程描述如下(父代中的一方记为$P$)；

1. 在P中选择两个位置；
2. 交换所选位置的元素生成$O$

• OS字符串的第二个变异算子是邻域变异法。该方法的基本工作流程描述如下(其中一个父节点记为P;

1. 在P中选择3个元素(这些元素的值不同)，生成所有邻域OS字符串；
2. 在邻近的操作系统字符串中随机选择一个，并将其设置为当前操作系统字符串，即$O$。

图5：OS字符串的变异操作符

笔记：

交换突变：
任意选择2个数惊醒交换，不一定是不同的，相同的也可。

邻域变异法：
上文选择这些元素的值不同，交换，可以共出现6种基因型

对于OS字符串，图5(a)显示了交换突变算子的示例，图5(b)描述了邻域突变算子的示例。在图5(a)中，选择第2和第5个位置。后代是通过交换这些位置上的元素而产生的。在图5(b)中，选择了第1、4、6个位置。然后，生成5个邻域OS字符串，随机选择其中一个作为后代。

对于MS字符串，变异操作符设计如下:

1. 选择父序列中的$r$个位置($r$为MS字符串长度的一半);
2. 对于每个位置(根据一个操作)，将该选择位置的值更改为相应操作的机器集中的另一台机器。

图6显示了MS字符串的突变操作符的示例。

图6：MS字符串的变异操作符

在本例中，r = 3(长度为6)，选择第1、4和6个位置。它们分别代表O11、O22和O32所选择的机器。后代是通过将这些位置的值改变为相应操作的机器集中的另一台机器而产生的。

4.4. 通过禁忌搜索进行本地搜索（Local search by tabu search）

禁忌搜索(Glover and Laguna, 1997)是一种元启发式方法，已成功地应用于各种组合优化问题，包括一些调度问题。TS允许搜索过程探索不降低目标函数值的解，如果这些解不被禁止的话。它通常是通过跟踪将一个解转换为另一个解所使用的动作来获得的。它由几个元素组成，其中包含邻域结构，移动属性，禁忌列表，期望标准和终止标准。

TS已成为解决调度问题的最有效的LS策略之一。在本研究中，它被作为LS策略用于FJSP的HA。这里采用了Mastrolilli和Gambardella(2000)提出的邻里结构。这种邻里结构被证明是最优连接的(Mastrolilli and Gambardella, 2000)。TS的基本流程如图7所示。

图7：TS工作流程

TS的总体流程说明如下:

• 步骤1:设置TS参数，设置禁忌列表为空;生成初始解并设置为当前解;
• 步骤2:是否满足终止条件?是，执行步骤8;否则，转到步骤3;
• 步骤3:通过邻域函数生成新的邻域解，并对这些解进行评估;
• 步骤4:是否满足期望标准?是，执行步骤6;否则，转步骤5;
• 步骤5:在邻域解中选择非禁忌解的最佳解，设为当前解，转到步骤7;
• 步骤6:将满足期望标准的方案设为当前方案和最佳方案，转到步骤7;
• 步骤7:更新禁忌列表，转到步骤2;
• 步骤8:输出最佳解决方案。

在建议的HA中，当个体执行LS时，首先应将其转换为可行的调度方案。然后将该解作为TS的初始解，经过局部搜索后，将TS的输出解编码为可行的染色体供遗传算子使用。

4.5. 终止条件（Terminate criteria）

在本文中，当代数达到最大值(maxGen)或允许的最大步长(maxStagnantStep)且没有改进时，HA终止;当迭代次数达到最大大小(maxTSIterSize)时，TS终止。

5. 实验研究与讨论（Experimental studies and discussions）

建议阅读原文

1. 与其他算法的比较结果：

• 所得解优于其他算法
• 求解 时间更少
• 求得 了一些基准问题 中的新解决方案

2. 原因：

• 结合了 遗传 算法强大 的全局搜索 能力和禁忌 搜索 算法强大 的局部搜索 能力
• 采用并设计了有效的编码方法、遗传算子和邻域 结构
• 在参数设置中， TS 的最大迭代规模是 HA 进

6. 结论及未来工作（Conclusions and future works）

本文将遗传算法基于种群的进化搜索能力与遗传算法的局部改进能力相结合，平衡了遗传算法的探索和开发，提出了一种以最大完工时间最小为目标的高效HA算法。

已经使用了六个著名的基准测试实例(包括201个开放问题)来测试HA的性能。实验结果表明，在不考虑求解精度和计算时间的情况下，所提出的HA在求解FJSP方面取得了显著的进步。并对若干基准问题给出了新的最优解。

本研究的贡献包括：

• 提出了一种混合遗传算法和TS算法的HA算法来解决FJSP问题。所提出的HA结合了遗传算法和TS的优点。并根据FJSP的特点，对HA方法的各个部分进行了设计和应用。该算法能较好地反映FJSP的本质特征。实验结果表明，所提出的HA已成功地用于求解FJSP。这是一种有前途的、非常有效的研究FJSP的方法。
• 该算法结合了进化算法和LS方法的优点。它为解决制造领域的其他调度问题，如JSP、集成工艺规划和调度问题等提供了一种新的途径。FJSP的实验结果表明，该算法可以有效地解决这些问题，因为这些调度问题包含了与FJSP相似的几个方面。

在未来，可以做以下工作。首先，我们可以将进化算法中的其他算法与其他LS方法相结合，构建更有效的混合算法来解决调度问题。毕竟，一些基准测试实例并没有找到最优的解决方案。目前的方法还远远不够。其次，该算法可以有效地解决单目标FJSP问题。将该方法与一些处理多目标问题的方法相结合，可以扩展其应用范围，用于解决制造领域的多目标FJSP或其他调度问题。