置换流水车间调度问题（permutation flow shop scheduling problem，PFSP）作为最典型的流水车间问题，具有很高的工程应用价值. 自1975年计算复杂理论提出后，验证了3台机器以上的PFSP问题属于NP-hard难题. 目前尚未发现有效的多项式时间优化算法，PFSP一直是工业和学术研究的重点关注课题. Johnson^[1]最早提出流水车间调度问题，采用动态规划、分支定界等精确算法解决了双机问题的最优调度以及有限条件下多机问题的最优调度. 随着问题规模的增加，精确算法的计算时间和计算量成指数增长，难以求得精确解. 为了求解大规模问题，NEH法、CDS法、Gupta法等启发式算法应运而生，其中Nawaz等^[2]引入的NEH启发式算法（Nawaz Enscore Ham，NEH）成为处理m台机器和n个工件流水车间调度问题的最常用方法. 利用启发式算法处理PFSP问题，虽然求解时间大幅减少，但是解的准确性无法保障. 近年来，越来越多结合NEH算法和优先规则的元启发式算法用来求解PFSP问题成为新方向：如改进布谷鸟搜索算法^[3]（improved Cuckoo search algorithm，ICS）、混合猴群搜索算法^[4]（hybrid monkey search algorithm，HMSA）、差分进化算法^[5]（DE）等，与贪心局部搜索不同，Kumar^[6]等结合NEH法提出改进的引力仿真局部搜索算法，Tseng等^[7]开发采用插入搜索（insertion search，IS）和修复剪切的插入搜索（insertion search repair and cut，ISRC）的局部搜索方法. 可见，目前该领域的最新研究方向是采用新颖算法并结合局部搜索策略提升算法的效率和质量.

共生生物搜索算法^[8]（symbiotic organisms search，SOS）作为一种新颖的元启发式优化算法，已被证明在解决数值优化和工程设计等方面非常稳定有效. Tran等^[9]将该算法应用到项目调度，解决了时间-成本-劳动力的权衡问题，Ezugwu等^[10-11]将SOS算法运用于旅行商问题（traveling salesman problem，TSP）. Cheng等^[12]将SOS算法用于求解多重资源调配. Panda等^[13]利用SOS算法，结合自适应惩罚函数，求解多目标约束的优化问题. Yu等^[14]结合SOS算法与局部搜索，求解带有能力约束的车辆路径调度问题. 流水车间调度问题具有不同于上述工程优化问题的特征，因此基于SOS算法求解PFSP具有挑战性以及较高的应用价值.

本文提出用于求解置换流水车间调度问题最小完工时间的SOS算法. 结合多种技术（如局部搜索策略、交换变异、插入-倒转区操作以及NEH法）保持种群多样性，提升算法跳出局部最优的能力，增加了全局的探索能力，有效避免了SOS算法易早熟、后期搜索效率低、易陷入局部最优等缺陷. 利用3种最常用、最专业的标准测试集：Carlier、Reeves和Taillard，测试所提出的算法性能.

置换流水车间调度问题（PFSP）是流水车间调度中最重要的问题之一. 最经典的PFSP指在m台机器上按相同顺序排列加工n个工作，以求最小化完工时间. 该问题的特征如下.

1）每个工作j_k只能在每台机器上运行一次，其中k=1，2，···，n.

2）每台机器i_h同一时间只能处理一个工作，其中h=1，2，···，m.

3）每个工作j在每台机器上加工需要一定的时间，即加工时间.

4）每个工作在不同机器上的加工时间不同，每个工件将在机器1~m上顺序运行.

5）每个工作的完工时间包括加工时间加上机器上的运行时间.

6）假定开始时间为零.

7）工作j_k在机器i_h上的完成时间 $ {C_{{j_k},{i_h}}}$.

8）工作j_k在机器i_h上的加工时间 ${\rm{P}}{{\rm{T}}_{{j_k},{i_h}}}$.

PFSP的目标是找到一组最佳的工作排列顺序使得完工时间C^*最小化，其中C^*为最后一个工作在最后一台机器上的完工时间.

经典置换流水车间调度问题（PFSP）的计算公式如下.

(1) ${C_{{j_1},{i_1}}} = {\rm{P}}{{\rm{T}}_{{j_1},{i_1}}};\; k = 1,\;h = 1.{\rm{ }}$

(2) ${C_{{j_1},{i_h}}} = {C_{{j_1},{i_{h - 1}}}} + {\rm{P}}{{\rm{T}}_{{j_1},{i_h}}};\;h = 2,\cdots, m.$

(3) ${C_{{j_k},{i_1}}} = {C_{{j_{k - 1}},{i_1}}} + {\rm{P}}{{\rm{T}}_{{j_k},{i_1}}};\; k = 2,\cdots,n.$

(4) $\left.\begin{aligned} {C_{{j_k},{i_h}}} =& \max\; ({C_{{j_{k - 1}},{i_h}}},{C_{{j_k},{i_{h - 1}}}}) + {\rm{P}}{{\rm{T}}_{{j_k},{i_h}}}; \\ k =& 2,\cdots, n,\;h = 2,\cdots, m. \end{aligned}\right\} $

完工时间是最后一台机器加工完最后一个工作的完成时间：

(5) ${C^ * } = {C_{{j_n},{i_m}}}{\rm{. }}$

最佳工作排序是所有工作排序中完工时间最小的排序.

Cheng等^[8]受到自然界生物体之间合作、竞争等交互行为的启发提出SOS算法. 共生可以定义为多种不同物种的生物体之间的长期相互作用. 一般来说，自然界发现的最普遍的共生关系包括互惠关系、共栖关系和寄生关系.

互惠关系是生物学或社会学中描述的一种对相互作用的2种生物均有益的关系，例如蜜蜂和花朵，蜜蜂靠花粉花蜜为食而维持生存，花朵依靠蜜蜂身上的绒毛传播花粉得以繁衍. SOS算法的第1个优化阶段仿照了这种互惠关系，提出互惠阶段.

共栖关系描述了相互作用的2个生物体之间，一种生物体从中受益，另一种生物体虽不受益但不会产生负面影响. 类似于鮣鱼和鲨鱼之间的关系，鮣鱼可以附着在鲨鱼身上吃鲨鱼进食后剩下的残羹剩饭，鲨鱼既不受益，也无损害. SOS算法的第2个优化阶段仿照了这种关系，提出共栖阶段.

寄生关系描述了一种生物体（寄生体）的获益以另一种生物体（宿主）受到损害为代价的情况. 寄生体比宿主小，得以更快地繁殖，对宿主造成更多伤害，如人类和蚊子. 这个阶段的灵感来自于寄生虫、疟原虫和人类宿主之间的寄生共生关系. 其中人类作为宿主受到伤害，疟原虫寄生体（即寄生虫携带者）在人体内传播寄生虫，寄生虫大量繁殖，从而获得收益.

SOS算法具有与大多数基于种群的算法（遗传算法、粒子群算法等）类似的特征，在一组候选解上执行特定算子（互惠、共栖、寄生）进行迭代，逐步改进候选解的质量以寻找全局最优解. 互惠阶段通过计算2种生物体的平均值与最优生物体之间的差异（MV），改善候选解决方案；共栖阶段通过计算随机2个解之间的差异来改善解的质量，以当前最优解作为参考点来探索附近区域，提高算法的收敛速度；寄生阶段通过随机改变生物体维度得到新的解决方案，改变部分维度表示局部搜索特征，改变整个维度可以增加生态系统扰动，有助于维持多样性并且可以防止过早收敛.

SOS算法在每个阶段结束时使用贪心选择方式决定在生态系统中存活的生物体，确保了进化后生物体的质量. 仅使用最大迭代数和种群数量的2个参数，诸如遗传算法、差分进化算法、粒子群算法等算法至少需要调整1个以上的特定算法参数（如遗传算法的交叉率和变异率，粒子群算法中的惯性权重、认知因素和社会因素等），SOS算法设计简单，避免了复杂、不确定的参数调整而导致算法性能受损的风险，具有较强的稳定性，是优于其他算法的最大竞争优势^[10]. 与其他智能算法相似，在实际运用中SOS算法出现了求解复杂问题时精度低、搜索后期种群多样性受损、容易陷入局部最优等缺陷. 在应用SOS算法求解实际问题时，应根据问题的特征对算法进行进一步的改进.

为了解决置换流水车间生产调度问题，结合局部搜索策略、交换变异操作、插入-倒转区等多种技术与SOS算法，提出混合SOS算法（hybrid symbiotic organisms search，HSOS），以提高SOS算法在求解PFSP时的性能. HSOS算法通过NEH启发式算法与随机生成的方式，生成一组质量较高的初始种群，识别出种群中的最优生物体. 对种群中的每个生物体依次经过互惠、共栖、寄生阶段. 对每个生物体采用交换变异来提高种群的多样性，避免算法早熟，过早地收敛；采用插入-倒转区操作，利用强力的突变帮助算法跳出局部最优. 对更新后种群中的最优生物体进行局部搜索，增强算法的探索能力，以在全局搜索中寻找更优的解决方案. 如图1所示为HSOS的框架，由4个主要步骤组成：编码方式与初始化、生物体适应度评估、共生过程、改进技术与局部搜索策略.

置换流水车间调度问题属于离散的NP-hard难题. 由于SOS算法用于解决连续性问题，提出HSOS算法解决该问题. 通过生成（0，1）不同的随机数构建初始生态系统种群（population），如图2所示.

PFSP是要解决一组工作排序问题，Li等^[15]提出的最大排序值法（largest rank value，LRV）是将连续值映射成离散排列常用的方法之一. 本文采用LRV将种群中表示生物体的一组连续的优先值映射为离散的工作排序. 如图3所示，LRV将代表生物体的一组连续值按降序排列生成一组工作排序.

NEH是一种有效解决调度问题的启发式算法^[2]. 采用NEH法生成初始种群中的生物体，可以有效地提高初始种群的质量，保证在初始种群中得到一个较高质量的解，提升了进化迭代过程的效率，提高了算法性能. NEH启发式算法的优化步骤如下.

1）计算每个工作的总加工时间.

2）对工作j=1，2，···，n，按照每个工作在所有工序上的总加工时间以不递增的顺序排列.

3）选择排列中前2个工作. 计算工作之间的排列组合，选择总时间最短的排序.

4）将第3个工作插入步骤2）中获得的最优排列中（插入后存在3个可能的排序）. 计算所有可能的排列组合，选择最短时间的排序.

5）将下一个工作插入到上一步得到的最短时间排序中. 考虑所有可插入的位置并计算完成时间，选择完成时间最短工作排序作为最佳排序.

6）重复步骤5），直到所有工作均被安排完毕.

初始种群中只有少量生物体（初始种群个体的10%）采用NEH法生成^[16]，以求获得高质量的个体；种群中剩余生物体采用随机方式生成，既保证了初始种群的质量，又不影响初始种群的多样性，避免算法过早收敛.

构建初始生态系统种群后，需要对种群中生物体进行评估，计算每种生物体的适应值. 每种生物体都通过LRV映射成一个工作排序，按照式（5）计算种群中每种生物体的完工时间作为适应值. 选择具有最小完工时间生物体的工作排列是最佳工作排序，即最优的调度解决方案. 例如，考虑如表1所述的置换流水车间调度例子. 表2中，提供了4种工作排列，记录了每种排序的完工时间. 可以看出，工作排序4-3-1-2的完工时间54最小.

互惠关系描述了一种对相互作用的2种生物均有益的关系. 在生态系统中，生物体x_i（代表一组工作排序）与生物体x_j（另一组工作排序）之间发生的互惠关系按式（6）、（7）进行，以提高两者在生态系统中的生存率，维持生态系统稳定.

(6) $X_i^{{\rm{new}}} = {X_i} + {\rm{rand}}(0,1) \times ({X_{{\rm{best}}}} - {\rm{MV}} \times {\rm{B}}{{\rm{F}}_1}),$

(7) $X_j^{{\rm{new}}} = {X_j} + {\rm{rand}}(0,1) \times ({X_{{\rm{best}}}} - {\rm{MV}} \times {\rm{B}}{{\rm{F}}_2}),$

(8) ${\rm{MV}} = ({{{X_i} + {X_j}}})/{2}.$

式中：MV称为交互矢量（表示x_i和x_j之间的相互关系）；rand（0，1）为（0，1）的随机数向量；BF₁和BF₂为2种生物体的收益因子（取值为1或2），根据从相互关系中的受益程度，在1或2中随机选取.

在共栖阶段，随机选择生态系统中生物体x_j与x_i相互作用. 其中x_j既不受益但也不会受到不利影响，x_i在相互作用中受益，通过式（9）产生新的解 $X_i^{{\rm{new}}}$，且只有 $X_i^{{\rm{new}}}$适应度高于x_i适应度时，才会更新x_i.

(9) $X_i^{{\rm{new}}} = {X_i} + {\rm{rand}}( - 1,1) \times ({X_{{\rm{best}}}} - {X_j}){\rm{ }}{\rm{.}}$

式中： $({X_{{\rm{best}}}} - {X_j})$表示x_j帮助x_i提高其在生态系统中的适应程度.

寄生关系类似于蚊子、疟原虫和人类宿主之间的关系. 在寄生阶段，x_i表示寄生体，通过随机截取生物体x_i的维度生成寄生载体X_par，随机选择另一种生物体x_j作为宿主. 若寄生物载体比宿主x_j具有更高的适应度，则会感染且取代宿主；否则，宿主将对寄生物产生免疫力，且寄生物载体将从生态系统中消失.

与其他智能算法相似，SOS算法在处理复杂问题时，表现出了搜索精度低、迭代后期种群多样性不足、容易陷入局部最优等缺点. 为了改善这些缺陷，提高算法的性能，采用以下3种手段进行改进.

交换变异是选择生物体中的2个随机的不同位置. 将这2个随机位置中的工作进行交换（即交换2个位置的优先值）生成新的排列，如图4所示. 计算交换后的适应度进行比较，保留适应度高的排序. 通过交换变异，可以使SOS算法在迭代过程中保持较高水平的种群多样性.

插入-倒转区是在维度为d的生物体中，将2个随机位置之间的工作顺序倒转形成的倒转区剪切出来，并插入所有（d−1）个可能的位置，形成新的（d−1）种工作排序. 若新排序的适应度优于原排列，则用新排列替换原排列. 如图5所示，通过采用插入-倒转区操作，可以在种群中产生强有力的变异以增强算法跳出局部最优的能力.

采用局部搜索策略对得到的最佳工作排序W*进行局部搜索，以提高解决方案的质量. 局部搜索策略是对于维度为d的W*中的每个工作，将每个工作移至所有（d−1）的位置，同时保持其余工作不变. 对于每一次移动产生的新工作排序，计算完工时间；当新排序的完工时间小于最佳工作排序W*的完工时间时，将该排序替换更新成为最佳工作排列W*. 利用局部搜索策略提高了算法的全局探索能力，可以改善算法易陷入局部最优的缺点，提升算法性能. 为了尽量减少对算法效率和计算时间的影响，通过设置局部搜索概率（local search probability，LSP）控制是否进行局部搜索.

提出算法的有效性通过Carlier^[17]、Rec^[18]、Taillard^[19]这3个广泛使用的标准测试集进行测试. 实验所用计算机配置如下：主频为2.6 GHz的CPU，4 GB内存，编程语言为Matlab. 为了更好地与其他算法进行对比，将生态系统的种群数量设为50，进行局部搜索的概率设为0.01，全局迭代次数设为3 000次，对每个算例运行20次.

HSOS算法的性能通过Car基准测试集检验HSOS算法的性能，与混合蝙蝠算法^[20]（hybrid bat algorithm，HBA）、混合回溯搜索算法^[21]（hybrid backtracking search algorithm，HBSA）、基于变邻域搜索的粒子群算法（particle swarm optimization based on variable neighborhood search，PSOVNS）^[22]、未改进的SOS算法进行比较. 计算结果如表3、4所示.

使用最佳相对误差（best relative error，BRE）、平均相对误差（average relative error，ARE）和最差相对误差（worst relative error，WRE）来进行算法的比较. BRE、ARE、WRE的计算公式如下：

(10) ${\rm{BRE}} = ({{{Z_{{\rm{best}}}} - {Z^*}}})/{{{Z^*}}},$

(11) ${\rm{ARE}} = ({{{Z_{{\rm{avg}}}} - {Z^*}}})/{{{Z^*}}},$

(12) ${\rm{WRE}} = ({{{Z_{{\rm{worst}}}} - {Z^*}}})/{{{Z^*}}}.$

式中：Z^*为目前已知的该问题的最佳完成时间，Z_best为规定运行次数内的最短完成时间，Z_avg为规定运行次数内的平均完成时间，Z_worst为规定运行次数内的最长完成时间.

相比于其他算法均会出现偏差的情况，HSOS算法在Car测试集的8个算例上的BRE、ARE、WRE均为0，即HSOS算法在Car的测试中每次优化均找到了问题的最优解，不仅体现了HSOS算法的强大性能，还展示出了算法的稳定性. 与未经改进的SOS算法相比，HSOS算法具有更小的ARE和WRE，这是因为HSOS算法的交换变异操作改善了种群内的多样性，插入-倒转区操作增加了算法跳出局部最优的能力，利用局部搜索策略提升了算法的全局探索能力，因此优化结果减小了误差，提高了算法的精度和稳定性. 可见，利用提出的改进措施有效改进了SOS算法的性能.

为了针对更多规模的问题进行验证，测试HSOS的性能，分别测试Rec测试集和Taillard测试集.

通过Rec基准测试集检验HSOS算法的性能，与基于变邻域搜索的粒子群算法（PSOVNS）^[22]、混合遗传算法（hybrid genetic algorithm，HGA）^[7]、基于文化基因算法的优化粒子群算法（PSO-based memetic algorithm，PSOMA）^[23]、离散蝙蝠算法（discrete bat algorithm，DBA）^[24]进行比较. 比较结果如表5、6所示.

如图6~8所示为HSOS算法与其他算法在Rec测试集上得到的BRE、ARE和WRE. 如图9所示，对几种算法在Rec基准测试集上的BRE、ARE和WRE的平均值进行比较. 图中， $\overline {\rm BRE}{\text{、}}\overline {\rm ARE}{\text{、}}\overline {\rm WRE}$分别为BRE、ARE和WRE的平均值. 从图9可以看出，HSOS在3个指标上均提供了最好的优化结果. 在BRE的比较中，HSOS具有最低的BRE平均值为0.583，PSOVNS高达1.124，验证了HSOS算法获得最优解的能力. 在ARE的平均值比较中，HSOS以1.05排名第一. 其后是PSOMA、HGA、DBA和PSOVNS，表明HSOS算法的整体稳定性优于对比的其他算法. 对于WRE的平均值，HSOS表现出了最佳的1.523，DBA以2.66排名最后，验证了HSOS算法的优越性. 结果表明，在Rec测试集中，HSOS算法相比于PSOVNS、PSOMA、DBA、HGA 4种算法表现出了更优异的性能和稳定性.

采用Taillard^[19]提出的基准测试集检验HSOS算法的性能，将运算结果与其他研究者提出的混合遗传算法（HGA）^[7]、贪心禁忌搜索算法（Tabu-mechanism improved iterated greedy，TMIIG）^[25]、离散水波优化算法（discrete water wave optimization algorithm，DWWO）^[26]、改进的贪心迭代算法（improved iterated greedy algorithm，IIGA）^[27]以及NEH启发式算法^[2]进行比较，验证HSOS算法的优越性.

Taillard测试集由规模为20×5、20×10、20×20、50×5、50×10、50×20、100×5、100×10、100×20、200×10、200×20、500×20的120个算例组成，每个规模均有10个算例. 选取每种规模中的最后一个算例作为代表算例进行实验，共12个算例，每个算例连续运行20次. 计算的平均结果如表7所示. 表7结果显示了HSOS的高效. 在选取的12个规模实例中，HSOS的性能都优于所有其他5种算法.

如图10所示为Taillard基准测试中的平均错误率（average error，AE），其中AE的计算公式为

(13) ${\rm{AE}} = \frac{{\rm{1}}}{k}\sum\nolimits_{i=1}^k {\frac{{{Z_i}{\rm{ - }}{Z_{{\rm{opt}}}}}}{{{Z_i}}}} \times 100\text{%}.$

式中：Z_i为算法i求得的平均完工时间，Z_opt为目前已知的算例上界值，k为算例的数量. HSOS算法在12个算例中的平均错误率AE为1.51，远远低于其他算法，表明了HSOS算法相对于其他5种算法具有更好的稳定性.

为了验证HSOS算法的性能，如图11所示为基于HSOS的改进百分比（improvement percentage，IP）的性能测量比较. 改进百分比的定义为

(14) ${\rm{IP}} = \frac{{{C_{\rm x}} - {C_{{\rm{HSOS}}}}}}{{{C_{\rm x}}}} \times 100{\text{%}} .$

式中：IP为HSOS算法对其他算法的改进百分比，C_x为改进算法在不同规模算例下的平均完工时间，C_HSOS为不同规模算例下HSOS算法的平均完工时间. IP可以用于确定HSOS为每种算法实现的改进百分比. 可以看出，与HGA、TMIIG、DWWO、IIGA、NEH算法相比，HSOS算法的性能得到了很大提升.

综上所述，在Taillard测试集上，HSOS算法在平均完工时间、平均错误率、改进百分比3个指标上均超过其他算法，证明了HSOS算法的高效和稳定性.

本文提出结合NEH启发式算法、局部搜索策略、交换变异和插入-倒转区的HSOS算法. 将HSOS在Carlier、Rec和Taillard 3个不同的基准测试集上进行性能测试，选取最小完工时间W*、相对误差（BRE、ARE、WRE）、平均错误率AE、改进百分比IP等计算指标进行比较. 计算结果显示：HSOS在解决置换流水车间问题上的表现优于HGA、DBA、PSOVNS、PSOMA等算法，具有更好的稳定性. 变异算子在优化过程中对解决方案的改进，使得算法在处理高维度大规模的案例研究时具备稳定、高效的性能. 利用提出的局部搜索策略提高了SOS算法的探索能力.

下一步的研究重点是将提出的HSOS应用于实际的预制构件生产调度问题中，根据实际生产情况的特征和约束对算法进行改进调整，实现对实际装配式建筑预制构件生产调度问题的建模与优化. 这部分的研究目前正在逐步深入展开.