多工序多设备的生产车间调度问题（Job Shop Scheduling Problem, JSSP）是智能制造领域的核心痛点。简单来说，就是“怎么安排多个工件在多个机器上干活，才能让总完工时间最短（MakeSpan）？”
这是一个典型的 NP-hard（非确定性多项式困难） 问题，当工序和设备稍微多一点，计算量就会呈指数级爆炸。
问题定义与数学模型
1. 核心要素
- 工件（Jobs）：待加工的零件，比如有 \(n\) 个工件 \(J_1, J_2, ..., J_n\)。
- 机器（Machines）：车间里的设备，比如 \(m\) 台机器 \(M_1, M_2, ..., M_m\)。
- 工序（Operations）：每个工件必须按特定顺序在指定机器上加工。
- 目标：最小化最大完工时间（MakeSpan）。
2. 数学模型（简洁版）
设 \(C_{ij}\) 为第 \(i\) 个工件的第 \(j\) 道工序的完工时刻，\(p_{ij}\) 为其加工时长。
- 目标函数：\(\min(MakeSpan) = \min(\max C_{ij})\)
- 约束条件：
- 工艺路线约束：同一工件的后一道工序必须等前一道做完才能开始。
- 资源独占约束：同一台机器在同一时刻只能加工一个工件。
- 非负约束：加工不能穿越时空提前开始。
主流求解算法流派
面对车间调度，死磕穷举法是不现实的，主流方案如下：
| 算法流派 | 代表算法 | 特点 | 适用场景 |
|---|---|---|---|
| 精确算法 | 分支定界法 (Branch and Bound) | 能求出绝对最优解，但算到天荒地老 | 极小规模 (\(n \le 10\)) |
| 启发式算法 | 瓶颈移动法 (Bottleneck Shifting) | 速度快，但容易陷入局部最优 | 对时间极其敏感的实时调度 |
| 元启发式算法 | 遗传算法 (GA)、粒子群 (PSO)、模拟退火 (SA) | 性价比之王，能在短时间内逼近最优解 | 绝大多数工业场景 |
| 深度强化学习 | DRL (Deep Reinforcement Learning) | 随数据进化，潜力巨大 | 柔性制造、复杂扰动环境 |
结论： 在实际工程中，遗传算法 (Genetic Algorithm, GA) 是处理多工序多设备调度最成熟、最通用的选择。
MATLAB 核心实现（遗传算法版）
以下是一套完整的 MATLAB 求解框架。它包含了染色体编码、交叉、变异以及甘特图绘制。
Step 1：定义车间数据与参数
我们需要定义每个工件走哪条“流水线”（机器顺序）和耗时。
%% 1. 清空环境
clc; clear; close all;%% 2. 车间数据定义 (核心输入)
% 假设有 3 个工件(Jobs)，3 台机器(Machines)
% 格式：[机器编号, 加工时长]
Jobs = {[1, 2, 3, 3, 2, 2]; % J1: 机器1(2h) -> 机器3(3h) -> 机器2(2h)[2, 1, 1, 4, 3, 1]; % J2: 机器2(1h) -> 机器1(4h) -> 机器3(1h)[3, 3, 2, 2, 1, 3] % J3: 机器3(3h) -> 机器2(2h) -> 机器1(3h)
};numJobs = length(Jobs); % 工件数量
numMachines = 3; % 机器数量%% 3. 遗传算法参数
popSize = 100; % 种群大小（一次看100种排班方案）
maxGen = 100; % 最大迭代代数
pc = 0.8; % 交叉概率
pm = 0.2; % 变异概率
Step 2：染色体编码与解码（决定排班优劣的核心）
采用工序编码法。比如 [1 2 3 1 2 3 1 2 3] 代表依次加工 J1的第1步，J2的第1步...
%% 4. 初始化种群 (生成随机排班表)
population = cell(popSize, 1);
for i = 1:popSizetemp = [];for j = 1:numJobstemp = [temp, repmat(j, 1, length(Jobs{j})/2)];endpopulation{i} = temp(randperm(length(temp))); % 打乱顺序
end%% 5. 适应度计算 (解码器)：计算MakeSpan
% 核心逻辑：维护每台机器的空闲时间表，遇到冲突就往后推
function makespan = calculateMakespan(chromosome, Jobs, numMachines)jobPtr = zeros(1, max(chromosome)); % 指向每个工件当前干到第几步了machineTime = zeros(1, numMachines); % 每台机器的空闲时间点jobFinishTime = zeros(1, max(chromosome)); % 每个工件上一道工序的完工时间for gene = chromosomejobPtr(gene) = jobPtr(gene) + 1;step = jobPtr(gene);% 取出该工序的机器号和耗时machine = Jobs{gene}(step*2 - 1);duration = Jobs{gene}(step*2);% 计算当前工序的开始时间 (取决于：工件上一道何时完 + 机器何时空闲)startTime = max(jobFinishTime(gene), machineTime(machine));% 更新状态jobFinishTime(gene) = startTime + duration;machineTime(machine) = startTime + duration;endmakespan = max(jobFinishTime); % 总完工时间
end
Step 3：主循环（选择、交叉、变异）
%% 6. 开始进化
bestScoreHistory = zeros(maxGen, 1);for gen = 1:maxGen% (a) 计算适应度 (MakeSpan越小越好)fitness = inf(popSize, 1);for i = 1:popSizefitness(i) = calculateMakespan(population{i}, Jobs, numMachines);end% (b) 选择优秀个体 (轮盘赌选择)prob = 1 ./ fitness;prob = prob / sum(prob);idx = randsample(popSize, popSize, true, prob);parents = population(idx);% (c) 交叉 (POX交叉算子)children = cell(popSize, 1);for i = 1:2:popSizep1 = parents{i}; p2 = parents{i+1};cutPoint = randi(length(p1)-1);child1 = [p1(1:cutPoint), p2(cutPoint+1:end)];child2 = [p2(1:cutPoint), p1(cutPoint+1:end)];children{i} = child1;children{i+1} = child2;end% (d) 变异 (交换两个基因的位置)for i = 1:popSizeif rand < pmswapIdx = randperm(length(children{i}), 2);temp = children{i}(swapIdx(1));children{i}(swapIdx(1)) = children{i}(swapIdx(2));children{i}(swapIdx(2)) = temp;endendpopulation = children;bestScoreHistory(gen) = min(fitness);if mod(gen, 10) == 0fprintf('代数: %d, 当前最优完工时间: %.2f\n', gen, bestScoreHistory(gen));end
end
Step 4：结果可视化（画出甘特图）
老板最爱看的就是这张图，直观展示每台机器的负荷。
%% 7. 找出最优解并画图
[bestMakespan, bestIdx] = min(fitness);
bestChromosome = population{bestIdx};figure('Name', '车间调度甘特图', 'Color', 'w', 'Position', [100 100 900 500]);
colors = jet(numJobs); % 给不同工件染不同颜色jobPtr = zeros(1, max(bestChromosome));
machineTime = zeros(1, numMachines);
jobFinishTime = zeros(1, max(bestChromosome));for gene = bestChromosomejobPtr(gene) = jobPtr(gene) + 1;step = jobPtr(gene);machine = Jobs{gene}(step*2 - 1);duration = Jobs{gene}(step*2);startTime = max(jobFinishTime(gene), machineTime(machine));endTime = startTime + duration;% 绘制矩形块rectangle('Position', [startTime, machine-0.4, duration, 0.8], ...'FaceColor', colors(gene, :), 'EdgeColor', 'k');text(startTime+duration/2, machine, sprintf('J%d', gene), ...'HorizontalAlignment', 'center', 'Color', 'white', 'FontWeight', 'bold');% 更新状态jobFinishTime(gene) = endTime;machineTime(machine) = endTime;
endxlabel('时间 (小时)');
ylabel('机器编号');
title(sprintf('最优调度方案 (总完工时间 = %.2f)', bestMakespan), 'FontSize', 14);
set(gca, 'YTick', 1:numMachines, 'YDir', 'reverse', 'Box', 'on', 'FontSize', 10);
grid on;
参考代码 多工序多设备的生产车间调度问题 www.youwenfan.com/contentcnu/77684.html
工程落地建议
-
数据输入别硬编码：实际生产中，切勿像上面代码那样手动写
Jobs。建议读取 Excel 文件：data = readtable('production_order.xlsx'); % 自动解析工件、工序、机器、工时 -
引入柔性约束：如果一台机器坏了怎么办？建议在解码器中加入设备可用性校验。如果某台机器不可用，触发“工序重路由”逻辑。
-
多目标优化：车间不仅追求时间最短（MakeSpan），还追求机器均衡负载（Balance）和最小化延期（Tardiness）。可以将适应度函数改为加权求和：
\[Fitness = w_1 \times MakeSpan + w_2 \times LoadUnbalance \]