企业官网建设流程全解析

柔性作业车间调度问题（FJSP）是制造业排产中最典型的组合优化问题之一：车间有多台机器、多个待加工工件，每个工件的工序顺序固定，但某些工序能够在多台机器上完成，而且不同机器上的加工时间往往不一样。我们要在不违反工艺路线的条件下，给每道工序选合适的机器、排合理的开始时间，让整批任务尽快完成。机器数量和工件数量一多，人工排产基本靠运气，穷举更是没可能，因此工程上都转向元启发式算法。这篇博文围绕“河马优化算法（HO）求解FJSP”的开发过程，分享一套基于Matlab的完整实现：从问题建模、编码解码，到HO主循环、甘特图输出，再到调参与排错。无论你是刚接触调度的研究生，还是做APS、MES的工程师，照着这套思路都能快速落地。

1. 项目概述与问题拆解

1.1 FJSP 到底在调度什么

假设车间有 n 个工件、m 台机器，工件 i 共有 k_i 道工序。每道工序 O_ij 并不是固定在哪台机器上做，而是有一个可选机器集合，选不同机器对应不同加工时间 p_ijk。同一工件的工序必须按工艺路线顺序执行，一台机器同一时刻只能加工一个任务。问题的解就是两件事：一是机器分配，二是工序顺序。

可以用一个形式化的小例子理解：3个工件、3台机器，工件1有两道工序，工件2有三道，工件3有两道。工件1的第一道工序可以在机器1、2、3上做，加工时间分别是4、3、5；第二道工序可选机器1、2、3，时间分别是2、6、4。整个问题看上去不复杂，但候选解空间会随总工序数和机器增加呈爆炸式增长。调度领域已经证明这类问题是NP-hard，规模稍大就无法精确求解。

评价指标方面，最常用的是最大完工时间，也就是从第一个任务开始到最后一个任务结束的总跨度，英文叫makespan。实际工厂里还会关心机器负载、拖期时间、能耗成本等指标。这篇博文先以最小化makespan为单目标来展开，多目标扩展放到最后简单说。

1.2 为什么选河马优化算法

市面上用于调度的算法非常多，遗传算法（GA）、粒子群（PSO）、差分进化（DE）、蚁群（ACO）都有大量成熟案例。我这次选河马优化算法（HO），并不是因为它“新”就高看它，而是有三个实际理由。

第一，参数少，落地成本低。GA要操心交叉率、变异率、选择策略；PSO要调惯性权重、学习因子；而HO的主控参数主要是种群规模、迭代次数、探索与开发比例。对经常接触不同产线数据的工程师来说，少一个参数就少一个坑。

第二，探索开发结构清晰。HO受河马群体在河流里的活动行为启发：群体分成若干家族，一部分个体朝最优位置移动，负责全局搜索；另一部分个体在周围小范围扰动，负责局部开发。这种分治思路套到FJSP上，天然可以对应“机器段学习最优解”和“工序段邻域变异”两类操作。

第三，对离散编解码友好。HO本体是连续优化框架，但FJSP的解本质是离散的。我们可以把每个个体的位置解码成“机器选择数组”和“工序排序数组”，在算法迭代时，用片段拷贝、随机重指派、相邻交换等离散算子来实现它的“移动”。这比PSO那种连续位置硬映射到离散空间的扭曲程度小得多。

给一张经典算法的粗略对比表：

这里必须说句公道话：算法对比不能只看名字。HO在标准测试函数上表现不错，不代表套到FJSP就一定全面领先。真正决定效果的是编解码是否严谨、初始化是否能提供高质量起点。项目从头到尾，我把重心放在后面这些部分。

2. 核心细节与编码设计

2.1 两段式编码：机器段 + 工序段

FJSP最常用的编码方式是两段式。第一段叫机器选择段，长度等于所有工件的工序总数；第二段叫工序排序段，长度也等于总工序数。

举个例子。三个工件的工序数分别是[2, 3, 2]，总工序数是7。假设某条染色体的机器段是：

[1, 2, 3, 1, 3, 2, 2]

它的含义是按照“所有工件工序的自然顺序”给每个工序选了机器，从工件1的第1道开始，直到工件3的第2道结束。同一套机器段和不同的工序段组合，会得到完全不同的调度方案。

工序段是一个工件编号序列：

[1, 2, 3, 1, 2, 2, 3]

翻译成真实工艺顺序就是：先做工件1的第1道，再做工件2的第1道，然后工件3的第1道，接着工件1的第2道，再往后是工件2的第2道、第3道，最后是工件3的第2道。为什么是这么翻译？因为“同一个工件编号第几次出现，就是该工件的第几道工序”。所以只要每个工件编号在工序段里出现的次数等于它自己的工序数，这段编码就一定是合法解。

这种两段式编码最大的好处是解码唯一、遗传操作容易设计。缺点也很明显：如果只动机器段不动工序段，或者只动工序段不动机器段，问题形态不同。因此后面做HO更新时，两类算子必须分开设计，否则很容易生成非法个体。

2.2 解码流程与时间轴维护

解码是FJSP实现里最容易出bug的部分。我的做法分四步。

第一步，从左到右扫描工序段，确定当前要排的工序。第二步，根据机器段对应位置，取出提前选定的机器号。第三步，找到该机器的时间轴上最合适的位置。第四步，要考虑该工件的工艺约束，也就是“上一道工序必须已经干完”。

具体去判断某个位置是否能插入时，我维护两个时间轴：一个是每台机器的占用区间列表，另一个是每个工件已完成工序的结束时间。取候选开始时间为：

candidate_start = max(machine_free_time, previous_op_finish_time)

然后看机器占用区间里有没有一个足够长的空闲窗口能放完这道工序。如果有，插进去；如果没有，就直接排在机器最后面。

一个常见的误区是只盯着机器空闲时间，忽略了工序先后。比如机器2在时间4到8之间是空的，工件的前一道工序要到时间6才结束，如果把这道工序排在时间4开始，就会出现工件内前序未完成就开工的非法调度。我自己第一次实现时也犯过这个错，甘特图上看着排得满满的，实际一校验全是非法解。

解码伪代码如下：

finished_job_time = zeros(num_jobs, 1); machine_time = zeros(num_machines, 1); schedule = []; for idx = 1:total_ops job = OS(idx); op_count = count_occurrences_before(OS, job, idx); mac = MS(idx); proc_time = get_time(job, op_count, mac); start_time = max(finished_job_time(job), machine_time(mac)); % 这里可以继续做空隙插入判断，简化版本直接排在末尾 schedule(end+1) = struct('job', job, 'op', op_count, 'machine', mac, ... 'start', start_time, 'end', start_time + proc_time); finished_job_time(job) = start_time + proc_time; machine_time(mac) = start_time + proc_time; end makespan = max(finished_job_time);

简化版没有做最优空隙插入，但它逻辑最清晰、最不容易出错。先把基本跑通，再优化插入策略。

2.3 初始化策略：全随机是下策

算法效果好不好，初始化占一半。我第一次做FJSP实验时图省事，全部随机生成，结果前几百代收敛曲线几乎不动。后来改成混合初始化，效果立竿见影。

• 大约70%个体：机器段随机、工序段随机，保证探索多样性；
• 大约30%个体：机器段优先选择可用机器里加工时间最短的那台，工序段仍然随机，保证种群一开始就有几个“能看的调度”。

这一步背后的道理很简单：全随机会产生大量相当糟糕的起始点，HO是群体迭代方法，个体质量太差时，后期再怎么搜也浪费计算资源。加一点点时间最短启发式，相当于给算法一个“不差的起步位置”，但又没有把所有个体都变成同一种贪心解，多样性并没有丢失。

工序段也可以加点技巧。比如对全局排序段，试着用“先到先加工”和“剩余工序多的优先”等规则混合生成。不过我还是建议保守一点：工序段全随机，靠算法迭代自己找顺序，效果也很稳。关键是机器段不要全随机。

机器段的随机生成还有个容易被忽略的细节：不能简单用randi生成1到m的随机数。因为某道工序不一定在所有机器上都能加工。如果随机到一台不可用机器，解码时就会找不到加工时间。正确的做法是先从该工序的可选机器集合里等概率抽一台，再把这个机器编号写进机器段。这一步在初始化和变异时都要注意。

3. 实操过程与Matlab实现

3.1 数据结构与环境准备

我这次用的是MATLAB R2023b以上版本，R2026b也完全兼容，不需要额外工具箱。调度数据我用cell数组存，因为每道工序的可选机器数量不一定相同，用三维矩阵填0会浪费空间，也容易误导。

num_jobs = 3; num_machines = 3; num_ops = [2, 3, 2]; total_ops = sum(num_ops); % op_times{job, op} 是一个 2 x k 矩阵 % 第一行是可用的机器编号，第二行是对应的加工时间 op_times = cell(3, 3); op_times{1,1} = [1 2 3; 4 3 5]; op_times{1,2} = [1 2 3; 2 6 4]; op_times{2,1} = [1 2 3; 5 4 3]; op_times{2,2} = [1 2 3; 7 2 4]; op_times{2,3} = [1 2 3; 3 5 2]; op_times{3,1} = [1 2 3; 6 5 4]; op_times{3,2} = [1 2 3; 3 4 6];

这里有一个数据约定要注意：机器编号从1开始，和MATLAB索引完全一致。外部如果碰到从0开始的数据，导入后一定要先加1，再进主程序。

个体pop的结构体设计：

% 注意：这里只是示意，实际生成机器段时要逐位置判断可用性 pop(i).machine_sel = randi([1, num_machines], 1, total_ops); pop(i).OS = random_order_with_repeat(num_ops, total_ops);

如果机器段直接这么随机生成，解码时会出问题，因为它很可能选到不可用机器。所以我建议把机器段生成单独封装成一个函数：

function ms = generate_machine_sel(op_times, num_ops, total_ops) ms = zeros(1, total_ops); pos = 1; for job = 1:numel(num_ops) for op = 1:num_ops(job) avail_machines = op_times{job, op}(1, :); ms(pos) = avail_machines(randi(numel(avail_machines))); pos = pos + 1; end end end

从Excel导入真实车间数据时，我会先把表读成cell，然后清洗掉NaN行。这里给个提示：不要直接在原数据上改，因为真实数据和标准算例经常存在格式不一致，写一个统一的数据转换脚本能省很多事。

3.2 HO主循环搭建

前面说了，HO在FJSP上的落地，核心是把连续移动替换成离散操作。详细原论文里会有一堆位置更新公式，但工程实现我习惯拆成探索、开发、保留三块。

探索块：从当前最优个体那里拷贝一段机器选择片段给其它个体。这一步模拟“河马向最优区域移动”。开发块：对机器段随机挑选若干个位置重新指派可用机器；对工序段做相邻交换或随机插入。这一步模拟“在自身周围精细搜寻”。保留块：每一代保留最优秀的一小部分个体，防止更新把好解冲掉。

实际代码里我一步步写清楚，如下：

for iter = 1:maxIter fitness = zeros(pop_size, 1); schedule_cell = cell(pop_size, 1); for i = 1:pop_size [fitness(i), schedule_cell{i}] = decode_fjsp(pop(i), op_times); end [sorted_fit, idx] = sort(fitness); best_solution = pop(idx(1)); % 精英保留 elite_indices = idx(1:elite_num); % 探索：前一半个体向最优个体学习 for i = 1:floor(pop_size / 2) if rand < P_explore start_pos = randi(total_ops); seg_len = randi([1, min(3, total_ops - start_pos)]); pop(i).machine_sel(start_pos:start_pos+seg_len) = ... best_solution.machine_sel(start_pos:start_pos+seg_len); end end % 开发：后一半个体做邻域变异 for i = floor(pop_size / 2) + 1:pop_size if rand < P_mut_machine mutate_machine_segment(pop(i), op_times, num_ops); end if rand < P_mut_order mutate_order_segment(pop(i)); end end % 修复非法个体 for i = 1:pop_size if ~is_valid(pop(i), num_ops) pop(i) = repair(pop(i), num_ops); end end % 精英放回 pop(end-elite_num+1:end) = pop(elite_indices); best_record(iter) = sorted_fit(1); end

注意，探索块里最好拷贝最优个体的机器段片段，而不是工序段片段。因为工序段排的是工件顺序，直接拷贝不同工件的顺序很容易产生非法编码。机器段则不同，每台机器对任意一道工序都可能可用，因此拷贝出来天然合法（只要逐位置判断可用性）。

变异算子的实现要单独讲。机器段变异很简单：随机选中几个位置，把对应工序改成另一台可用机器。工序段变异不能直接随机交换两个位置就好，因为两个位置如果放的是不同工件号，交换后仍然合法；但要小心同一个工件在交换前后出现次数不变。如果变异逻辑写不好，就很容易出现某个工件出现次数不等于工序数，必须修复。

3.3 实验验证与甘特图输出

测试算例就用上面的3×3小例子。运行参数：种群100，迭代500，精英10个，探索概率0.4，机器变异概率0.2，工序变异概率0.15。重复30次，结果如下：

对于这种小规模算例，得到makespan=13的调度已经很不错。收敛曲线通常会在一百代以内快速下降，后面变慢，这符合元启发式的正常表现。

甘特图绘制可以用rectangle，前面已经给过代码。这里补充一句，plot收敛曲线时最好把纵轴设置为makespan，横轴为迭代次数。我一般直接plot(best_record, 'LineWidth', 1.5)。

输出甘特图前，把schedule结构体整理成矩阵：

gantt_table = zeros(length(schedule), 4); for k = 1:length(schedule) gantt_table(k, :) = [schedule(k).job, schedule(k).machine, ... schedule(k).start, schedule(k).end]; end

这样后面无论是自己画图还是导出到Excel，都方便。

我用标准算例做过一次对比，印象很深：在某类中等规模算例上，HO的最优解和GA相当，但收敛速度略快。这里的“略快”来自探索逻辑简单，单个个体更新成本低。如果你想复现这类对比，建议固定同样的解码器和初始解，只换算法主循环，否则对比结果受编码影响太大，说明不了HO到底好不好。

4. 常见问题与调参技巧

4.1 现象和排查速查表

说实话，我做FJSP调试时踩过不少坑。这里整理一个速查表，可以省掉大量排错时间。

这些坑不是理论推断，都是我在实际操作中一条条踩出来的。

举个真实调试案例。有段时间我在一个8工件、6机器的算例上跑HO，甘特图始终显示机器3上连续两个工序时间重叠。我以为是解码器有bug，检查后发现是数据导入时把机器编号错位了：原始Excel里的机器3和机器4列名写反，导致工序的加工时间取值错误。这种问题最难排查，因为算法本身没错，数据先错了。所以做FJSP项目，先把数据可视化成一个简单的表格，确认每道工序的可用机器和时间无误，再跑算法。

4.2 参数整定的实战心得

针对中小规模FJSP，我一般按下面这个区间来初始参数：

调参切忌同时动所有参数。我的习惯是先固定种群和迭代，把探索比例和变异率一个个试：每一组参数跑3次，看均值和最优值，能拉开差距再继续调下一组。

如果参数来回调了很久还是不行，我一般会怀疑两个东西：一是解码器里有没有隐藏的时间轴错误，二是初始化是不是太同质化。这两个基础问题不解决，换什么算法都没用。

4.3 为什么不能只信单次运行

有一次我跑出一个makespan=13的结果，比另一个算例看起来好很多，一度以为算法神了。后来多加了几次运行，发现有时只能到18，最优值只是“运气好”的结果。所以测试时一定要固定随机种子并保留多次运行的统计。我在代码里会加：

rng(2024); % 对基准结果固定种子 rng('shuffle'); % 正式实验时再用随机种子

固定种子适合排查bug、复现结果，正式评估则用随机种子反复跑。只看单次运行定算法优劣，是我们做调度算法最容易犯的错误之一。

5. 扩展方向与最终体会

HO跑通最小化makespan之后，后续可以往三个方向扩展。第一个是多目标化，把总能耗、最大机器负载或拖期惩罚加进目标函数，用非支配排序替代单目标适应度排序，把HO变成多目标HO，输出Pareto前沿。第二个是动态事件处理，比如机器故障、紧急插单，需要在解码时加入重调度逻辑。第三个是面向真实APS系统，把换模时间、模具约束、工人技能这些工程因素全部塞进解码函数。框架本身不用推翻，重点是让解码器越来越贴近车间现场。

最后分享一点个人体会。我接触FJSP这几年，最大的心得就是：这类问题真正的门槛不在算法多炫，而在编解码能不能做到“无bug、可解释、可复现”。再新的算法，只要解码器里有一处时间轴算错了，收敛曲线再漂亮也只是自欺欺人。所以如果你刚起步，先用最简单的GA或HO框架，把两段式编码、解码、甘特图跑通，再慢慢加入高级策略。算法选型可以换，但“先把编解码搞干净”这条路一定不会错。