遗传算法+随机重启爬山法求解柔性作业车间调度问题实践详解

前阵子整理旧目录，翻出一段 2022 年随手敲的算法复现代码：随机重启爬山法 + 遗传算法，解决柔性作业车间调度问题（FJSP）。那段时间我整天泡在调度优化里，看到一篇论文把局部搜索嵌进遗传算法，思路很直接，但复现过程远比想象中曲折。如果你也在盯 FJSP、正好想研究遗传算法和爬山法怎么配合，这篇文章应该能帮你省下大把破案时间。

我会把整套东西拆开讲：问题本身长什么样、遗传算法主体怎么搭、随机重启爬山法为什么要加、局部搜索的邻域怎么构造、以及我踩过的一大堆坑。代码不会贴全套，但核心片段和参数逻辑都会给出来，照着改就能跑。

1. 整体设计与思路拆解

1.1 FJSP 到底是什么难题

先花半分钟对齐概念。作业车间调度问题（JSP）里，每个工件的每道工序只能在固定的一台机器上加工，你只需要决定工序的顺序。柔性作业车间调度问题（FJSP）则更进一步：每道工序有一组可选机器，不同机器上的加工时间还不一样。于是你同时要回答两个问题：这道工序放哪台机器做，以及所有工序按什么顺序做。

我用一个生活化的类比帮助理解：你在一个小作坊里接了几张订单，每个订单有若干加工步骤，每步骤可以在两三台设备中选择。你要安排“谁先做、用哪台机器”，还要保证同一时间一台设备只能加工一个订单。目标是让全部订单最早完成。这个“最早完成”的时间，用调度领域的术语叫最大完工时间（makespan），是 FJSP 里最常用的优化目标。

FJSP 难在哪？答案在于解空间巨大，而且两个子问题耦合。机器分配变了，最优的工序顺序可能完全变；顺序变了，最优分配也要跟着变。传统的精确求解算法在中等规模的算例上就撑不住了，只能靠元启发式算法在合理时间内找近似最优解。

这个项目要做的，就是复现一种比较经典的混合思路：用遗传算法做全局搜索，同时把“随机重启爬山法”作为局部搜索算子嵌入进去。遗传算法负责大范围扫荡，爬山法负责在小范围里把解磨锋利。两者配合，正是这些年求解 FJSP 的主流套路之一。

1.2 为什么单独用遗传算法不够

遗传算法擅长全局探索，能跨过大片的搜索区域，但它有个毛病：局部精化能力弱。种群迭代到中后期，大多数个体都在一个相对不错的区域里，交叉和变异产生的新个体，质量经常还不如当前最优解，收敛速度会明显变慢。

FJSP 的解空间有很强的“邻域结构”：某个工序换个机器、某两个工序换个相对顺序，可能带来 makespan 的明显变化。这种小步调整用遗传算子的方式运作，效率其实很低。变异那一下随机性太大，交叉又不能精确抓住“导致延迟的那几个关键工序”。

爬山法恰恰擅长干这个。从当前解出发，在定义好的邻域里反复尝试小的变动，只要新解更优就移动过去，直到找不到更好的邻居为止。这个过程在当前解附近做精细打磨，效率和遗传算法正好互补。

所以整体设计就是：遗传算法提供多样化的解，爬山法在这些解附近密集挖掘。原先单跑遗传算法可能要到 300 代才能真正逼近一个局部最优，现在每代挑几个个体做爬山，可能几十代就磨到位了。

1.3 为什么还要“随机重启”

爬山法有个致命短板——容易陷入局部最优，而且一旦陷进去就没救了。局部最优并不是全局最优，但它周围的邻居都不比它差，爬山法会认为自己已经找到了最好的解。

随机重启的思路很简单粗暴：既然一个爬山过程会被局部最优困住，那就多来几次，换不同的起点重新爬。每次爬山的起点可以是随机生成的，也可以从遗传算法的当前种群中获得。起点越分散，找到不同局部最优的可能性就越高，最后从中挑一个最好的，自然更接近全局最优。

把这个逻辑嵌进遗传算法之后，每代相当于同时启动了好多支“小队”：一部分个体做局部挖掘，另一部分个体跳出原来的位置重新探索。用术语讲已经有点“memetic algorithm”的味道，不过在复现中，我始终以“随机重启爬山法作为算子”来理解它的角色，这个定位会让后续的代码结构更清晰。

2. 遗传算法主体设计

2.1 编码：MS 串 + OS 串

遗传算法要做交叉变异，第一步是找一种合适的染色体表达。FJSP 有两个决策维度，我用最经典的“双串编码”：机器选择串（MS）和工序顺序串（OS）。

MS 串的长度等于所有工序的总数，每一个位置记录“这道工序用哪台机器”，具体怎么对齐会在解码时通过一个位置映射搞定。OS 串则记录所有工件工序的顺序，每个工件的编号出现次数等于它的工序数。举个例子，两个工件各有 2 道工序，OS 串长 4，可能长这样：[0, 1, 0, 1]，意思是最先处理工件 0 的工序 1，然后处理工件 1 的工序 1，接着是工件 0 的工序 2，最后是工件 1 的工序 2。

分两条串而不是合在一起，好处很明显：交叉时两条串可以各自用最合适的算子，互不干扰。机器分配和工序排列各自进化，最后通过解码合成为可行调度。这是 FJSP 遗传算法里非常成熟的表达方式，很多论文都沿用了类似结构。

编码时我额外做了一份位置映射表，记录每个工件的每道工序在 MS 串中对应哪个下标。比如工件 0 的第一道工序在 MS 串的位置是 0，工件 0 第二道工序在位置 1；工件 1 的第一道工序从位置 2 开始。有了这张表，从 OS 串按顺序取工序时，能立刻从 MS 串中拿到对应机器，不用绕来绕去。

2.2 解码：插入式主动调度

解码是把染色体还原成具体甘特图的过程，它直接决定染色体的质量。一开始我写的是最简单的“追加式”解码：每个工序放到对应机器的当前最后位置，最早开始时间取机器空的时刻和工件前道工序结束时刻中的较大值。这样生成的调度叫半主动调度，它的问题是机器上可能留有多余的空隙，白白浪费了时间。

后来我换成了插入式解码，效果提升很明显。插入式不再盲目把工序丢到末尾，而是扫描该机器上已有的空闲区间，寻找最早能插进去的位置。只要工序的开始时间不早于前道工序结束，且能塞进某段机器空闲区间，就直接插入。这种解码生成的调度叫主动调度，任何工序都没法在不推迟其他工序的前提下提前开工了，解的质量通常比半主动调度高一个档次。

解码的时候，我同时维护两台数据结构：每台机器上已排工序的完成时间区间列表，以及每个工件当前已加工到第几道工序。对 OS 串中的每个工件号，找到对应工序，从 MS 串取机器号，然后在该机器的空闲区间里找最早可插入位置。最后把该工序的时间段登记到机器区间列表里，并更新工件进度。

很多初学者会在这一步翻车，因为插入式解码的边界条件很多：区间刚好被填满、前道工序结束时间落在区间中间、多个空闲区间都可行等等。我的建议是先把追加式解码跑通，再用一组标准算例验证结果，最后再升级到插入式，否则出错都不知道错在哪。

2.3 选择、交叉、变异算子

遗传算法的算子选型，直接决定搜索行为。我用的选择算子是很常见的锦标赛选择：每次从种群中随机挑几个个体，选适应度最好的进入下一代。锦标赛规模我设成 2，因为它既能保留选择压力，又不会让种群过早失去多样性。

交叉算子要分串处理。MS 串我用单点交叉，随机选一个交叉点，两侧交换。这种方式的合理性在于：机器分配字段之间相对独立，直接交换片段不会破坏基本结构。OS 串我用的是基于工件顺序的交叉方法，逻辑是随机把工件分成两个集合，子代 1 保留父代 1 中属于集合 A 的工序相对顺序，属于集合 B 的工序按父代 2 的顺序填充。这样做能最大程度保留每个父代中工件内部的相对次序，避免生成大量非法序列。

变异算子也分两类。MS 串变异时，随机挑一个位置，把该工序换到可选机器集合中的另一台机器上，加工时间跟着变。OS 串变异时，简单交换两个不相邻的位置即可。需要注意：OS 串里同一个工件号可能出现多次，交换时不需要保证“不能交换同一个工件的不同工序”这种约束，因为只要每个工件的总出现次数不变，解就始终合法。

选择压力不能太大，否则种群几代之内就收敛到一个很窄的区域，随机重启爬山法也救不回来。我在实验里把种群大小设置在 100 到 150 之间，交叉率 0.85，变异率 0.15，每次跑完统计种群的多样性和最优值变化，发现这个区间比较稳。

2.4 关键参数与评估函数

适应度函数很简单：解码后返回 makespan，值越小越好。由于遗传算法习惯适应度越大越好，我在代码里用的是1 / makespan或者-makespan，都可以。推荐用负 makespan，因为数值比较直观，只在排序时取反即可。

参数这块我踩过不少坑。种群太小，遗传算法基本没有探索能力；太大，每代的解码和爬山计算量会成倍增加。迭代次数也不是越大越好，配合局部搜索之后，有时候 150 代的结果已经达到甚至超过 300 代纯遗传算法的水平，再跑下去只会浪费时间。

我给一版比较稳妥的初始参数：种群 120，迭代 200，锦标赛大小 2，交叉率 0.85，变异率 0.15，精英保留 2 个最优个体。这个配置跑中小规模的算例，通常能稳定收敛到不错的结果，后续可以根据算例规模再微调。

3. 随机重启爬山法的设计与融合

3.1 局部搜索的邻域结构

爬山法的核心是邻域定义。邻域选得好不好，决定了局部搜索能否在有限步数内找到高质量的解。FJSP 的邻域一般围绕“关键路径”来构造，因为 makespan 由关键路径决定，不改变关键路径上的工序，makespan 几乎不可能下降。

关键路径上的工序有一个性质：在工作组内部，它们组成一个块，相邻工序之间往往存在紧密的时间衔接。我用的第一种邻域操作就是移动关键块内的工序：把块首工序移到块尾，或者把块尾工序移到块首。这相当于重新安排关键工序的相对先后顺序，能让一部分机器负载重新分配。第二种操作更直接：挑选一个关键工序，换一台可选机器，并在新机器上尝试插入。

判断一个邻域动作是否有效，不需要把整个调度全部重算。对于移动关键块内的工序，可以通过局部更新受影响机器的时间区间估算新的完成时间；对于换机器的操作，则要在目标机器上计算插入后的完工时刻。虽然完整重算也能用，但大规模算例下性能差距很大。

我在实现时不追求一次性生成完整邻域再选最优动作，而是采用“first improvement”策略：随机生成一批邻居候选，遇到第一个更优的动作就立即移动。这样省时，而且配合随机重启后，整体搜索效果并不比遍历全部邻居差。

3.2 随机重启的触发方式

重启不能乱来，否则会把遗传算法好不容易积累的优良信息全部冲散。我实验过好几种触发方式，最后采用“定时重启 + 基于停滞的重启”两者结合。

定时重启：每间隔 R 代，从种群中挑出一部分适应度较差的个体，直接替换为随机生成的个体。这里的“随机生成”不是完全从零开始，而是保留原有 MS 串的一小部分机器分配信息，OS 串则重新随机排列，相当于做了有保留的扰动。这样做能让搜索跳出当前的盆地，但又不至于完全丢失机器分配上有价值的信息。

停滞检测：如果最优 makespan 连续若干代没有改善，我就加速“重启力度”，把更大比例的个体重新初始化。这个地方的关键要克制，因为重启过于频繁会导致种群整天在随机区域里打转，永远没时间精化。我给自己的经验值是：正常 R 设为 20～30 代，停滞超过 10 代就额外触发一次轻度扰动。

3.3 融合进遗传算法的位置

随机重启爬山法嵌进遗传算法的位置差异，带来的效果差异非常大。我试过三种方案。

第一种：每代对最优个体做爬山。这个方案最简单，但计算量集中在头几个个体上，一个个体可能已经被磨得很透了，再做下去边际效益很低。

第二种：每代选一定比例的个体做爬山，比例为 20%～30%。我用锦标赛或者按适应度排名去选，尽量避免重复选同一批个体。这个方案能让种群整体的“平均质量”提升，但计算开销变成原来的两到三倍。

第三种：分阶段控制。前 1/3 迭代不做爬山，让遗传算法充分探索；中间 1/3 对 20% 的个体做局部搜索；最后 1/3 加大爬山强度。我后来主要用第三种，原因是前期多样性太强时爬山的作用很有限，类似“地基都没打好就急着精装修”。分阶段策略在公开算例上跑出来的平均值更稳，而且不太容易早熟。

4. 实操过程与代码实现

4.1 数据结构与输入格式

数据读入这步看着简单，实际容易埋雷。我使用一个嵌套结构来表达算例：外层是工件列表，每个工件是工序列表，每道工序的内容是“可选机器编号 + 加工时间”的字典。

我用的简化格式长这样：

# jobs[job_index][op_index] = {machine_id: processing_time} jobs = [ [{0: 4, 1: 6}, {0: 5, 2: 3}], # 工件 0：两道工序 [{1: 4, 2: 3}, {0: 6, 1: 5}], # 工件 1：两道工序 ] n_machines = 3

这种直白的结构方便调试，甘特图画错了直接打印出来对照。正式复现时我建议把算例解析函数单独抽出来，处理 CSV 或文本格式的基准算例。解析时注意每行几块内容别读串，我因为漏读一个机器编号，曾经整整跑出来一批不可行解，排查了大半天才发现是数据文件少了列。

MS 串和 OS 串的对应关系我用一张字典维护：

# op_position[(job_id, op_index)] = ms_index op_position = {} ms_index = 0 for job_id in range(len(jobs)): for op_index in range(len(jobs[job_id])): op_position[(job_id, op_index)] = ms_index ms_index += 1

4.2 插入式解码的实现要点

解码是所有环节里最值得写注释的函数。给出一个经过简化的插入式解码，核心逻辑在机器时间表格里寻找最早可插入区间：

def decode(ms, os, jobs, n_machines): job_idx = [0] * len(jobs) # 每个工件当前工序 job_end = [0] * len(jobs) # 每个工件最后工序完成时间 machine_intervals = [[] for _ in range(n_machines)] # 各机器已占用区间 makespan = 0 for job_id in os: op_idx = job_idx[job_id] m_idx = ms[op_position[(job_id, op_idx)]] p_time = jobs[job_id][op_idx][m_idx] earliest = job_end[job_id] # 在 machine_intervals[m_idx] 中找可插入空隙 start, end = earliest, earliest + p_time inserted = False current = 0 for gap_start, gap_end in machine_intervals[m_idx]: if end <= gap_start: # 插在 gap 之前，且不跨当前占用区间 # 把区间插入到当前位置 machine_intervals[m_idx].insert( current, (start, end)) inserted = True break # 空隙被占用的部分跳过 if start < gap_end: start = max(start, gap_end) end = start + p_time current += 1 if not inserted: machine_intervals[m_idx].append((start, end)) job_end[job_id] = end job_idx[job_id] += 1 makespan = max(makespan, end) return makespan, machine_intervals

这段代码没有处理“工序塞进中间空隙但空隙尾部不匹配”的更复杂情况，实际工程里还要进一步优化。但我用它跑中小算例已经能获得合法调度，而且比追加式解码平均优化了 5% 到 10% 的 makespan。

解码完了记得做一次合法性校验：同一台机器上不能有时间重叠，同一工件的工序不能倒置。我在代码里写了个validate_schedule()函数，专门用来打印冲突，后面排查问题全靠它。

4.3 关键路径与爬山邻域

局部搜索需要先识别关键路径，我的做法是解码时额外记录每个工序的最早开始时间和完成时间，然后从最后一个完工的工序出发往前回溯：

def find_critical_ops(schedule): # schedule: (job_id, op_idx, machine, start, end) end_time = max(op[4] for op in schedule) critical = [] cur_time = end_time # 找到让 cur_time 成立的关键工序，沿前驱回溯 # 实际代码要同时考虑“同一机器前一道工序”和“同一工件前一道工序” # 这里省略细节，思路是从后往前反查 return critical_ops

回溯时要注意：一个工序的前驱有两个方向，一个是同一工件里的前道工序，另一个是同一台机器上前一个加工的工序。必须选择结束时间等于当前工序开始时间的那个，才是真正的关键前驱。

得到关键工序后，邻域动作可以这样实现：随机抽取一个关键块内的工序，尝试把它挪到块首或块尾；或者随机选一台可选机器，把关键工序换过去。每个动作都通过“重算受影响区间”来快速估算 makespan 变化，只接受让 makespan 不变小或严格减小的动作。

4.4 主循环：GA 与局部搜索的组合

主循环部分我用一种可读性较强的写法：

def main(): pop = init_population(...) restart_interval = 25 for generation in range(max_generations): # 1. 评估全部个体 fitness = [1.0 / decode(ind, ...)[0] for ind in pop] # 2. 精英保留 + 锦标赛选择生成子代 elite = get_elite(pop, fitness, elite_size=2) offspring = [] while len(offspring) < pop_size - elite_size: p1 = tournament_select(pop, fitness) p2 = tournament_select(pop, fitness) c1, c2 = crossover(p1, p2) mutate(c1) mutate(c2) offspring += [c1, c2] pop = offspring + elite # 3. 分阶段局部搜索 if generation > max_generations // 3: selected = select_subset(pop, top_k=15) for ind in selected: hill_climb(ind, max_steps=20) # 4. 随机重启 if generation % restart_interval == 0: disturbed = random_restart(pop, ratio=0.15) update_best(...)

这套结构跑起来很顺。需要强调的是阶段阈值max_generations // 3不是定死的，我根据算例规模调整过几次。算例小、迭代次数也只有 100 代时，阈值要提前到 50 代甚至 30 代，否则最后三分之一的局部搜索时间根本不够用。

4.5 实验设计与参数调优

跑实验之前我先把算例按规模分组：小规模（比如 6 个工件、6 台机器）、中规模（10 个工件、10 台机器）、较大规模（15 个工件、10 台机器）。不同规模的面貌完全不同，小算例上遗传算法随便跑跑就接近最优了，大算例才真正体现混合算法的价值。

参数整定时，我用“正交表 + 小规模预跑”的方式减少无效实验。固定基础参数后，依次变化局部搜索强度（是否做、对多少个体做、每代做几次），每组跑 5 次随机种子，统计最好值和平均值：

这组数据一看就明白：纯 GA 已经能解，但加了局部搜索后最好值稳定下降；无脑加大爬山范围，时间翻倍但收益不明显；分阶段 + 重启的组合在差不多的耗时下拿到更好的平均结果。

调参有个心得：不要追求一次性找到某个“全局最优参数”。先固定一组保守参数跑通流程，再围绕“局部搜索强度”做敏感度分析，往往调整这一个因素，就已经能把算法从“勉强可用”提升到“接近论文水平”。

5. 常见问题与排查技巧实录

5.1 乱七八糟的不可行解

复现过程中我最大的敌人是“看起来正常但实际非法的调度”。这种问题最隐蔽，因为程序不崩溃、遗传算法能跑，但解码出来的甘特图一看就有重叠。

最常见的原因有三个：一是 MS 串对应的机器不在工序的可选集合里，可能是变异时没做合法性检查；二是 OS 串里某个工件的出现次数不等于该工件的工序数，导致解码时索引越界或者漏工序；三是解码插入不当，把工序插进了参数错误的位置。

解决方案是在编码初始化和每次交叉变异后，加一个valid_chromosome()校验函数。初始化校验一遍，变异校验一遍，解码入口再校验一遍。校验函数开销很小，但能在问题扩散前拦截掉大量错误数据。

5.2 局部搜索“白干”了

爬山法跑完，最优值一点没动，这种挫败感我经历了很多次。后来定位到两个原因。

第一个原因是关键路径计算有误。回溯时我只考虑了“同一机器上上一道工序”的衔接，忘记了工件内部的前道工序约束，导致拿到一串根本不是关键工序的节点，在这些节点上做任何移动都不会影响 makespan。修正方法是在回溯时同时检查两个前驱方向的结束时间，并选择真正紧贴当前工序开始时间的那一个。

第二个原因是邻域动作幅度太小。只允许把关键块内工序移动到相邻位置，可能反复尝试都只能回到原来的调度。我后来加入了“跨块移动”甚至“跨机器移动”的组合，效果立刻不一样。同时要允许“makespan 不变但结构变化”的移动，这种平局移动能帮助后续搜索跳出平台期。

5.3 收敛太快或太慢

如果最优值在前 30 代就不动了，大概率是选择压力过大导致种群多样性崩溃。我遇到过两种典型情况：锦标赛大小从 2 调到 4，收敛速度立刻快得吓人；局部搜索在前期就开始大范围使用，整个种群被少数几个高质量解主导。

如果跑完规定迭代还在缓慢改善，不要急着调参数，先画一下收敛曲线。连续 50 代的最优值还在下降，说明代际不够，直接加迭代次数；曲线的下降斜率已经趋平，说明算法力度不够，该调整的是局部搜索强度而非迭代次数。

5.4 常见问题速查表

这些坑填完之后，复现项目才算真正跑通。我从这个项目里学到的最重要一条经验，不是某个算法技巧，而是“一切复杂算法优化都要回到一个朴素的问题：你的解是怎么编码的，又是怎么解码的”。这两个环节没有抠清楚，后面调参、改邻域、加重启全都事倍功半。

如果你现在正准备复现类似论文，我建议先从最小可运行版本开始：固定一个中等规模算例，跑通纯 GA，加上无重启的爬山法，观察一次提升效果，最后再加上随机重启。每一步都留收敛曲线和甘特图做对照，否则混合算法一旦出问题，你根本说不清是哪一环拖了后腿。

FJSP 这潭水很深，随机重启爬山法只是工具箱里的一件趁手工具。以后如果你要做到更强的效果，可以考虑自适应邻域选择、路径重连甚至并行化局部搜索，这都是在现有框架上能继续扩展的方向。不过先把 GA 和爬山法的配合吃透，未来的每一步都会走得更稳。