麻雀优化算法求解车间调度问题：Matlab实现与参数调优

干过生产计划或者写过排产模块的朋友，对“车间调度”这四个字应该有切肤之痛。我最早接触这问题，是帮一家做机械加工的工厂做排产方案，十几个设备、几十个工件来回倒腾，老师傅靠经验排，一有插单就全乱套。后来把问题抽象成数学模型，才知道这就是传说中的作业车间调度问题（JSP），属于典型的NP-hard组合优化问题，规模稍微上去一点，穷举就别想了。

这两年做调度优化用得比较多的是群体智能算法，麻雀优化算法（Sparrow Search Algorithm，SSA）算是里面思路比较新颖的一种，它模拟麻雀觅食和反捕食的行为，全局搜索和局部开发平衡得不错，而且实现起来不复杂。我用Matlab把麻雀算法求解车间调度的完整流程跑通了，从编码、解码、迭代寻优到甘特图可视化，一套下来该有的坑基本都踩过。这篇文章把整个方案的设计思路、核心代码、参数调优和实战问题都展开讲讲，给正在做排产优化、或者想用麻雀算法做组合优化的朋友一个可参考的落地范本。

1. 车间调度问题的工程价值与难点拆解

1.1 真正的痛点在哪儿：从排产表到数学模型的跨越

车间调度不是一个新鲜话题，但做了才知道，要把现场经验翻译成可计算的模型，坑非常多。车间调度问题（Job Shop Scheduling Problem，JSP）的经典定义是：有n个工件要在m台机器上加工，每个工件有自己的工艺路线，也就是必须按固定的工序顺序在各台机器上完成加工，每道工序在指定机器上的加工时间是固定的。问的是怎么安排每道工序在每台机器上的开工时间，让最大完工时间（makespan）最短。

实际排产过程中经常出现的约束包括：一台机器同一时间只能加工一个工件、一个工件同一时间只能在一台机器上加工、工序不能抢占、工序之间存在先后依赖。这些约束叠加起来，让问题变得极其复杂。理论上n和m稍微大一点，比如10个工件10台机器，完整搜索空间就已经是天文数字了，这就是所谓的组合爆炸。工程上如果生产节拍快、订单变化频繁，靠人工排产根本顶不住。

从算法的角度看，JSP已经被证明是NP-hard问题，意味着在多项式时间范围内找到全局最优解基本不可能。所以实际工程中大家不会执着于找理论最优，而是用启发式算法或元启发式算法在可接受时间内找到一个近似最优的可行调度方案。麻雀优化算法正是这类元启发式算法里性价比较高的一类选择。

1.2 为什么选麻雀优化算法而不是遗传算法、粒子群

车间调度这个领域，经典算法早就被研究透了，遗传算法（GA）、模拟退火（SA）、粒子群优化（PSO）都是常用工具，但用下来各有各的别扭。

遗传算法框架成熟，交叉、变异算子设计灵活，但参数多，交叉率、变异率、选择策略每一项都得调，而且早期容易陷入早熟收敛，种群多样性一丢就很难翻身。粒子群思路简单，收敛快，但问题在于它的位置更新依赖个体最优和全局最优，连续域上表现不错，一到离散的组合优化问题就需要额外的映射机制，映射得不好容易丢失解的多样性。

麻雀优化算法是2020年提出的一种群体智能算法，核心思想是模拟麻雀群体的觅食与反捕食行为。它的优势在于麻雀个体被划分为不同的角色：发现者负责寻找食物丰富区域，加入者跟随发现者获取食物，同时还有一部分麻雀负责侦察预警，一旦发现危险就让整个群体迅速转移。这个机制天然地兼顾了全局探索和局部开发，发现者负责大范围搜索，加入者围绕优良区域做精细开发，侦察者则提供逃脱局部最优的机制。它的参数比遗传算法少，结构清晰，在车间调度这种离散离散混合的优化问题上，配合合理的编码方案，实测收敛效果和稳定性都很能打。

2. 麻雀优化算法的核心机制拆解

2.1 三种角色分工：发现者、加入者、侦察者

麻雀算法的种群一开始会随机分布在搜索空间中，每只麻雀的位置就代表候选解的一个编码向量。在每次迭代里，所有个体按照适应度排序，适应度高的个体被指定为发现者，负责引导种群向高质量区域移动。发现者比例通常设置为种群规模的10%到20%。剩下的个体是加入者，它们追随发现者的轨迹，同时也会在发现者之间搜索机会。还有大约10%的个体被随机指定为侦察者，它们不一定在当前最优位置附近，而是分布在各个区域，专门感知潜在的风险。

这样安排的作用很明显：如果所有个体都朝当前最优区域挤，种群很容易扎堆失去多样性，最后全部堆在一个局部最优附近出不来。侦察者相当于特种兵，它们在远离主力的位置探索，一旦发现更好的区域，或者发现当前区域有危险，就会发出信号让群体转移方向。从工程视角去理解，这个机制和很多大型项目的“提前布局、专人预警”思路很像，群体的鲁棒性因此上了一个台阶。

2.2 位置更新公式的工程解读与关键参数

麻雀算法的位置更新分成三个部分，对应三种角色。先看发现者：当预警值小于安全阈值时，发现者在当前位置附近做小步长探索，公式如下：

$$ X_{i,j}^{(t+1)} = X_{i,j}^{(t)} \cdot \exp\left(-\frac{i}{\alpha \cdot T_{max}}\right) $$

其中 ( \alpha ) 是 (0,1] 之间的随机数，( T_{max} ) 是最大迭代次数，( i ) 是当前发现者个体的排序序号。这个公式的含义是：排序越靠前的发现者，步长越小，搜索得越精细；排序靠后的发现者步长更大，更偏向探索。

当预警值大于等于安全阈值时，说明群体可能面临危险，发现者会迅速向安全区域靠拢：

$$ X_{i,j}^{(t+1)} = X_{i,j}^{(t)} + Q \cdot L $$

其中 ( Q ) 是服从标准正态分布的随机数，( L ) 是长度为维度的全1行向量。这个公式本质上是让发现者做一次跳跃，跳出当前可能不利的区域。

加入者的更新思路比较有意思。如果某个加入者的排序比较靠后，说明它离好的食物源太远，能量不足，干脆让它飞远一点另寻出路：

$$ X_{i,j}^{(t+1)} = X_{i,j}^{(t)} + \exp\left(\frac{X_{worst,j}^{(t)} - X_{i,j}^{(t)}}{i^2}\right) $$

如果排序靠前，就在当前最优个体附近寻找更好的位置：

$$ X_{i,j}^{(t+1)} = X_{best,j}^{(t)} + \left| X_{i,j}^{(t)} - X_{best,j}^{(t)} \right| \cdot A^+ \cdot L $$

其中 ( A^+ ) 是随机矩阵 ( A ) 的伪逆矩阵，( A ) 的元素随机取1或-1。这两条规则让加入者不至于全部挤在最优个体身边，给种群保留了向外扩散的通道。

侦察者的更新公式则负责最后的兜底保护，防止个体陷入当前最优区域无法脱身：

$$ X_{i,j}^{(t+1)} = X_{best,j}^{(t)} + \beta \cdot \left( X_{i,j}^{(t)} - X_{best,j}^{(t)} \right) $$

如果该个体不是最好个体，则向最好个体靠拢：

$$ X_{i,j}^{(t+1)} = X_{i,j}^{(t)} + K \cdot \frac{X_{i,j}^{(t)} - X_{worst,j}^{(t)}}{\left(f_i - f_{worst}\right) + \varepsilon} $$

( \beta ) 是步长控制参数，服从正态分布；( K ) 是[-1,1]之间的随机数；( \varepsilon ) 是极小的常数，避免除零。参数 ( R_2 )（预警值）和 ( ST )（安全阈值）配合使用，前者在[0,1]内随机生成，后者通常取0.8。

在具体实现中，种群规模我一般取100，发现者比例0.2，侦察者比例0.1，安全阈值0.8，最大迭代次数500到1000。这几个默认参数在大多数中等规模的JSP算例上都能得到比较稳定的结果，后续再根据收敛曲线微调。

3. 从连续搜索到调度序列：编码与解码的关键设计

3.1 麻雀算法是连续域算法，调度需要离散序列——如何搭桥

这个问题是新手最容易卡住的地方。麻雀算法本质上是在连续空间里做搜索，但车间调度的解是工序序列，每一道工序分配在哪个机器、从什么时候开始干，这些都是离散决策。直接用连续坐标当工序编号，算出来的适应度根本没意义。

工程上常用的做法是基于工序的编码方案。设工件数为n，每台机器上的工序数为m（这里先讨论每个工件在所有机器上加工一遍的标准JSP），那么一条染色体就是长度为 ( n \times m ) 的序列，每个工件编号在序列中出现m次，从左到右第k次出现代表该工件的第k道工序。解码时依序扫描序列，把每道工序安排到对应机器的可用时间段上。

为了把麻雀算法产生的连续位置向量转换成合法的工序序列，我采用的是LPV规则（Largest Position Value）。也就是把位置向量各维度的值从大到小排序，按排序结果得到一个维度索引序列，再把索引映射成工件编号序列。这个方法的好处是：无论位置向量的值怎么变，生成的工序序列永远合法，不会出现某个工件工序数量多算或少算的情况。

具体举个小例子。假设两个工件，每个三道工序，那么位置向量长度就是6，前三个维度对应工件1的三道工序，后三个维度对应工件2的三道工序。某个个体位置向量算出来是[0.8, 0.1, 0.5, 0.9, 0.3, 0.7]，按降序排列是0.9（索引4）、0.8（索引1）、0.7（索引6）、0.5（索引3）、0.3（索引5）、0.1（索引2），于是索引序列是[4,1,6,3,5,2]，对应的工件序列是[2,1,2,1,2,1]。这个序列就是一条合法工序路径：工件2的第一道工序最先干，接着工件1的第一道工序，然后工件2的第二道工序，依此类推。

这段转换代码在Matlab里很简洁，关键函数如下：

function seq = lpvMapping(x, jobNum) % x: 连续位置向量，长度 L = n*m % 返回 seq: 离散工序序列 L = length(x); [~, order] = sort(x, 'descend'); seq = zeros(1, L); for k = 1:L idx = order(k); % 按分块约定：维度位置对应工件编号 job = mod(idx - 1, jobNum) + 1; seq(k) = job; end end

3.2 活动调度解码：让工序尽可能早地开工

编码解决了“解长什么样”的问题，解码解决“这个解对应什么排产方案”的问题。这里的核心不只是把工序依次塞进机器时间表，而是要尽可能压缩空闲时间。同一道工序，安排得越早，整个任务的完工时间往往就越短。

我常用的解码方式是插入式活动调度解码。基本思路是：按工序序列顺序处理每一道工序，先找到对应机器上所有已排工序留下的空闲时间段，然后判断当前工序的加工时长能否塞进某个空闲段里。如果空闲段长度足够，就把工序放到这个时间段，相当于“见缝插针”；如果插不进去，就放到机器当前的最后完工位置。这样做出来的调度是活动调度，意思是任何工序如果往前移动，必然要导致某台机器上其他工序的开工时间被推迟，这是JSP中一类具备“最优解必定存在于活动调度集合中”性质的调度类型，所以解码这一步非常关键。

解码过程可以拆成三步维护：

• 记录每个工件的下一道工序号（初始为1）
• 记录每台机器的完工时间，以及每个工件刚加工完工序的完工时间
• 对当前工序，计算允许的最早开工时间，再遍历对应机器的空闲时间段，寻找可以插入的缝隙，更新机器时间和工件时间

这段逻辑写出来大概是这样的框架：

function makespan = activeDecode(jobSeq, machines, times) n = size(machines, 1); m = size(machines, 2); L = n * m; % 初始化 procStep = zeros(n, 1); % 每个工件下一道工序 jobAvail = zeros(n, 1); % 每个工件最后完工时间 machineAvail = zeros(max(max(machines)), 1); % 各机台最后完工时间 % 记录的机器空闲段列表可以单独维护 for k = 1:L j = jobSeq(k); procStep(j) = procStep(j) + 1; p = procStep(j); mac = machines(j, p); procTime = times(j, p); % 寻找可插入的空闲段 startTime = findEarliestSlot(mac, procTime, max(jobAvail(j), machineAvail(mac))); % 更新时间和空闲段 jobAvail(j) = startTime + procTime; machineAvail(mac) = startTime + procTime; end makespan = max(machineAvail); end

findEarliestSlot就是遍历目标机器的空闲区间列表，找一个“起始时间不早于工件最早可开工时间、且空闲区间长度不小于加工时间”的位置。这个函数看起来简单，但实现时容易出边界错误，比如空隙端点判断、跨多个空闲段合并等问题，我建议写完之后用几个小算例子手工推算验证一遍。

4. Matlab代码实现与运行流程

4.1 整体程序框架和函数划分

完整程序可以分成五个部分：数据加载、参数设置、种群初始化、迭代优化、结果输出。数据加载阶段读入工艺路线矩阵和加工时间矩阵，这两份数据是JSP的标准描述方式。工艺路线矩阵里第i行第j列表示工件i第j道工序在哪台机器上加工，加工时间矩阵对应位置表示这刀要多长时间。

种群初始化阶段随机生成每个个体的连续位置向量，再通过LPV映射得到工序序列，最后解码算出适应度。这一阶段的随机性决定了后续算法的搜索起点分布，建议把随机数种子固定下来，方便复现实验。

迭代优化阶段是核心，每次循环要做的动作包括：对所有个体计算适应度并排序、按发现者比例取出前pd个个体做发现者更新、剩余个体做加入者更新、随机选出sd比例的个体做侦察者更新、处理越界、重新映射为新工序序列并解码。由于位置向量更新是连续域的，每一轮更新完之后，位置向量的值可能会突破上下界，通常做一次越界截断处理，让每个维度的值保持在初始设定的上下界范围内。

4.2 麻雀算法主循环的几个关键细节

下面这段代码是主循环里最核心的一块，麻雀算法本身不复杂，但写的时候有几个细节值得注意。

for t = 1:maxIter % 1. 对所有个体解码并计算适应度值 fitness = zeros(nPop, 1); for i = 1:nPop seq = lpvMapping(X(i, :), jobNum); fitness(i) = activeDecode(seq, machines, times); end % 2. 按适应度从优到劣排序（最小化问题，数值越小越优） [sortedFit, idx] = sort(fitness); X = X(idx, :); % 3. 发现者更新：前 pNum 个个体 pNum = round(nPop * pd); R2 = rand; for i = 1:pNum for j = 1:totalOps if R2 < ST X(i, j) = X(i, j) * exp(-i / (rand * maxIter)); else X(i, j) = X(i, j) + randn; end end end % 4. 加入者更新：剩余个体 for i = (pNum + 1):nPop for j = 1:totalOps if i > nPop / 2 X(i, j) = randn * exp((X(end, j) - X(i, j)) / (i * i)); else A = randi([0 1], 1, totalOps); A(A == 0) = -1; A_pinv = pinv(A); X(i, j) = X(1, j) + abs(X(i, j) - X(1, j)) * A_pinv(1) * 1; end end end % 5. 侦察者更新：随机抽取 sd 比例个体 sNum = round(nPop * sd); state = randperm(nPop, sNum); for i = 1:sNum idxSp = state(i); for j = 1:totalOps if fitness(idxSp) < sortedFit(pNum) X(idxSp, j) = X(1, j) + randn * abs(X(idxSp, j) - X(1, j)); else X(idxSp, j) = X(idxSp, j) + rand * (X(idxSp, j) - X(end, j)); end end end % 6. 边界越界处理并记录全局最优 X = max(min(X, ub), lb); gBest = X(1, :); bestRecord(t) = sortedFit(1); end

这里有个细节很容易搞错：加入者更新里用到了全局最差个体X(end, j)，这个值每一轮只排序一次，如果侦察者更新改变了某些个体的位置，要注意最差个体是否已经被提前换了。我自己写代码时习惯在每轮更新前存一份排序快照，或者在侦察者更新后再做一次排序，避免用脏数据。当然，牺牲一点效率换来稳定性，在调度这类问题上完全值得。

侦察者更新里的判断条件，我简化成了比较当前个体适应度和发现者群体的平均适应度。严格来说，标准SSA判断的是当前个体是不是当前最优个体，但是在这个实现里判断逻辑稍微调整一下也不影响整体效果，关键是保证侦察者既能引导优质个体向邻居探索，也能牵引劣质个体向优质区域靠拢。

4.3 结果输出：收敛曲线和甘特图

调试阶段我一般先看两个图：收敛曲线和调度甘特图。

收敛曲线很简单，每一轮记录全局最优适应度值，迭代结束后用plot画出来。从曲线能直观判断算法是否收敛、是否过早停滞。如果曲线一开始下降得很快，后面长时间平着不动，大概率是种群多样性丢了，这时候要适当增大侦察者比例，或者加大加入者的随机扰动项。

甘特图的绘制思路是用rectangle函数画矩形块，每个矩形代表一道工序。横轴是时间，纵轴是机器编号。矩形在纵轴的位置对应机器号，矩形的宽度对应加工时长，矩形内的文本可以标上“工件号-工序号”。画甘特图时注意给每台机器预留足够的纵向空间，不然矩形重叠在一起，图可读性会很差。我习惯把机器按编号从上到下排列，每台机器画一条基准虚线，再用不同颜色区分不同工件，这样一眼就能看出机器负载情况。

figure; hold on; colors = lines(n); % 为各个工件分配不同颜色 for i = 1:L j = jobSeqDecoded(i); p = ... % 第几道工序 mac = machines(j, p); startT = ...; endT = startT + times(j, p); rectangle('Position', [startT mac-0.4 endT-startT 0.8], ... 'FaceColor', colors(j, :), 'EdgeColor', 'k'); text((startT + endT) / 2, mac, sprintf('%d-%d', j, p), ... 'HorizontalAlignment', 'center', 'FontSize', 8); end xlabel('时间'); ylabel('机器编号');

用这套流程跑下来，经典的6×6测试算例通常能快速逼近已知最优解，10×10规模的问题在几百代迭代内也能得到不错的调度方案。这里只以经典规模作说明，不同数据集最优值不同，不建议拿别人公布的结果去硬比，重点还是看自己算法的收敛趋势和改进幅度。

5. 参数调优、结果分析与避坑经验

5.1 关键参数对收敛效果的影响

用麻雀算法求解车间调度，参数设置直接决定结果质量。我把自己测试过的几组典型参数整理成表，方便对比参考：

我在实际调试中遇到过的一个典型现象是：种群规模从30调到100，解的质量提升非常明显，但再往上调，收益就递减了。这符合群体智能算法的普遍规律——种群多样性积累到一定程度后，继续加个体只是在重复搜索。另外，安全阈值ST别设得太小，否则发现者动不动就跳飞，整个种群很难形成稳定的搜索方向。

5.2 实际运行中常见的坑

第一个大坑是解码函数里空闲段插入逻辑写错导致生成了不可行调度。最常见的情况是：某个工件的前一道工序还没完工，后一道工序就插到了另一台机器的空闲段里，导致时间顺序冲突。排查办法很简单，在解码函数里加一个校验：每道工序的开工时间必须同时不小于对应工件上一道工序的完工时间和对应机器的上一道工序完工时间。每次迭代都做完整校验虽然慢一点，但能保证调度方案是合法可执行的。

第二个坑是麻雀算法迭代后期种群多样性下降太快。尤其当发现者比例偏低、侦察者数量不足时，几十代之后所有个体基本都挤在同一个区域，位置向量之间的差异变得非常小，LPV映射出来的工序序列也大同小异。这种情况下无论迭代多少次，解的质量都不会再有明显提升。一个有效的补救是在加入者更新公式里加大随机项系数，比如把randn * exp(...)的随机项和当前位置做加权混合，让加入者在跟随最优个体的同时保留一定的探索能力。

第三个坑是位置向量经过越界截断后，所有个体都堆在边界上。我一开始没做边界处理，结果连续迭代几十代之后发现种群收敛到全是边界值，LPV映射出来的序列变得极度相似，整个搜索机制基本失效。后来在每个维度更新完统一做min(max(...))截断，同时在每个维度上保留一定概率的随机重置，才把这个问题解决掉。

5.3 如何系统评估算法性能

评估算法性能不能只看最终跑出来的makespan数值，还要看这个数值的稳定性。我的做法是同一组参数用五个不同随机种子各跑一遍，记录每次的收敛曲线和最优值。如果五次的最优值在同一个水平附近波动很小，说明算法稳定性好；如果某次特别好、另外几次很差，说明算法对初始种群过于敏感，这时候需要改进的不是随机种子，而是参数配置或者加入局部搜索机制。

另外，我还习惯把甘特图打印出来人工检查一遍：看看各机器上是否存在大段空闲间隙，如果某台机器整体负载偏高，说明调度方案把较多工序挤在了一条线上，后续可以针对瓶颈机器做局部的工序先后调整，或者考虑是否可以通过调整解码规则优先均衡机器负载。这些分析在论文里是结论，在工程里是能否落地的关键。

6. 后续的实用改进方向

6.1 引入局部搜索算子

麻雀算法本身偏重全局搜索，局部搜索能力相对一般。我做了个简单改进，在每轮迭代结束时，对当前全局最优个体执行三种邻域操作：交换两个相邻工序、插入一个工序到另一个位置、逆序一段工序序列。执行邻域操作并解码后，如果新序列更优就保留，否则放弃。这个改进本质上是在全局最优附近做精细开采，效果立竿见影，特别是在迭代后期，收敛曲线还能继续往下走一截。

6.2 与遗传算子混合

另一种思路是把麻雀算法和遗传算法的交叉变异算子融合。比如在加入者更新的时候，以一定概率执行工序序列的交叉操作，而不是完全依赖位置向量更新。这种做法在代码实现上需要多写一个交叉函数，但好处是能直接引入问题相关的先验信息，搜索效率会更高。我实践下来的感受是：交叉操作的概率设置在0.3到0.5之间比较合适，太低了没效果，太高了麻雀算法自身的搜索机制又发挥不出来。

6.3 向柔性作业车间调度扩展

柔性作业车间调度问题（FJSP）是在标准JSP基础上增加了一道工序可选的设备范围约束，现实中大部分车间其实都是这种场景。要把这套麻雀算法方案升级到FJSP，关键改动点在于编码不再只是工序序列，还要同时决策每道工序选择哪台机器。常见做法是用两段式编码：一段表示工序顺序，一段表示机器选择。麻雀算法的连续位置向量需要映射到两段编码上，解码时按机器选择序列为每道工序分配设备，再按工序顺序做插入式调度。整体框架不需要大改，但搜索空间维度翻倍，收敛难度明显增大，这时候局部搜索的收益会更大。

就我自己的经验来说，麻雀算法在车间调度这个场景下的确是一个值得投入时间的算法方案，实现成本低、可玩性强，而且有足够的扩展空间。如果后续再深入，可以考虑自适应调整发现者比例，或者把关键工序的机器分配和工序排序分开优化。动手跑一遍完整代码，比看多少篇文章都管用，遇到问题最好直接拆解自己的解码函数，把每一步时间都核清楚，踏过几个坑之后，对调度问题的理解会完全不一样。