在前面几篇文章中，我们已经完成了APS系统的“骨架”建设：甘特图提供了可视化操作界面，产能引擎算清了设备与人力负荷，物料齐套检查堵住了停工待料的风险。然而，当所有这些约束叠加在一起，面对几十个工单、十几台设备、成百上千种物料时，

“怎么排”依然是一个NP-hard（非确定性多项式难度）问题

在离散制造车间，尤其是注塑、喷涂、SMT等工序，有一个巨大的隐性成本——

。如果生产顺序不合理，比如刚生产完黑色外壳就切换到白色，中间清洗模具的时间可能比生产本身还长。传统的规则法（如先到先得、交期优先）往往顾此失彼。

，带你从零构建一个生产排程优化引擎。我们将详细拆解染色体编码、适应度函数设计、交叉变异算子，以及如何将“最小化换型时间”这一业务目标转化为数学优化问题，并用Node.js实现它。

一、为什么用遗传算法解决排程问题？ 

假设我们有 N 个工单和 M 台设备。如果只考虑工单顺序，可能的排列组合就有 N! 种。当 N=10 时，约有360万种排法；当 N=20 时，这个数字超过了 2×1018。

显然，穷举法在工业现场是不可行的。遗传算法作为一种模拟自然进化过程的搜索启发式算法，能在

，非常适合解决这类组合优化问题。

遗传算法的灵感来源于达尔文的自然选择学说。它将问题的每一个潜在解决方案看作一个“个体”（染色体），通过模拟“选择（Selection）”、“交叉（Crossover）”和“变异（Mutation）”等生物进化过程，让种群不断进化，最终收敛到最优解附近。

二、问题建模：将生产现场转化为数学模型 

在编写代码之前，我们必须先将现实问题抽象化。

在排程问题中，最直接的编码方式是

。一条染色体代表一个完整的生产序列。

例如，我们有4个工单（Job），每个工单需要经过3道工序（Operation），分别在设备M1, M2, M3上加工。

。这代表了一个生产顺序：先生产J1的所有工序，然后是J2，依此类推。

的场景，目标是找到最优的加工顺序。

2.2 换型时间矩阵（Setup Time Matrix） 

这是遗传算法的核心输入。换型时间取决于前一个工单和后一个工单的差异（如颜色、模具、材质）。

// setupMatrix[A][B] = 从工单A切换到工单B所需的时间（分钟）
const setupMatrix = {
  'P001': { 'P001': 0, 'P002': 30, 'P003': 90 },
  'P002': { 'P001': 30, 'P002': 0, 'P003': 60 },
  'P003': { 'P001': 90, 'P002': 60, 'P003': 0 },
};

：如果生产完P001（黑色塑料）马上生产P002（灰色塑料），需要30分钟清洗；如果换成P003（金属质感），则需要90分钟更换模具和清洗。

下面我们开始构建遗传算法的核心引擎。

3.2 适应度函数（Fitness Function）—— 核心中的核心 

适应度函数用于评价一个排程方案的优劣。我们的目标是

，总耗时 = 所有换型时间之和 + 所有加工时间之和。

由于加工时间是固定的，优化目标简化为

/**
 * 计算染色体的适应度（总耗时）
 * 适应度越低（耗时越短），个体越好
 * @param {Job[]} chromosome - 一个排程方案（染色体）
 * @returns {number} 总耗时（加工时间 + 换型时间）
 */
function calculateFitness(chromosome) {
  if (!chromosome || chromosome.length === 0) return Infinity;

  let totalTime = 0;
  let previousJobId = null;

  // 遍历染色体中的每一个基因（工单）
  for (const job of chromosome) {
    // 1. 累加加工时间
    totalTime += job.processingTime;

    // 2. 累加换型时间（从第二个工单开始计算）
    if (previousJobId) {
      const setupTime = setupTimes[previousJobId]?.[job.id] ?? 999; // 未知组合给予惩罚
      totalTime += setupTime;
    }
    
    previousJobId = job.id;
  }

  return totalTime;
}

3.3 选择算子（Selection）：锦标赛法 

选择算子模拟自然选择，好的个体有更大的几率被选中繁衍后代。这里采用

锦标赛选择法（Tournament Selection）

，即从种群中随机挑选几个个体，让它们“比赛”，选出其中适应度最好的一个作为父代。

/**
 * 锦标赛选择法
 * @param {Job[][]} population - 当前种群
 * @param {number[]} fitnessScores - 对应的适应度分数
 * @returns {Job[]} 被选中的染色体
 */
function tournamentSelection(population, fitnessScores) {
  let bestIndividual = null;
  let bestFitness = Infinity;

  // 随机抽取 TOURNAMENT_SIZE 个对手进行比赛
  for (let i = 0; i < CONFIG.TOURNAMENT_SIZE; i++) {
    const randomIndex = Math.floor(Math.random() * population.length);
    const currentFitness = fitnessScores[randomIndex];

    // 寻找适应度最低的（耗时最短的）
    if (currentFitness < bestFitness) {
      bestFitness = currentFitness;
      bestIndividual = population[randomIndex];
    }
  }
  // 返回副本，防止原种群被修改
  return [...bestIndividual];
}

3.4 交叉算子（Crossover）：顺序交叉（OX） 

交叉算子模拟基因重组。对于排程问题，不能使用简单的单点交叉（会导致工单重复或丢失）。这里我们采用

，它是解决排列问题的经典方法。

/**
 * 顺序交叉 (Order Crossover - OX)
 * 保留了父代染色体中一段子序列的相对顺序
 * @param {Job[]} parent1 - 父代1
 * @param {Job[]} parent2 - 父代2
 * @returns {Job[]} 子代
 */
function orderCrossover(parent1, parent2) {
  const size = parent1.length;
  // 1. 随机选择两个交叉点
  let start = Math.floor(Math.random() * size);
  let end = Math.floor(Math.random() * size);
  if (start > end) [start, end] = [end, start]; // 确保 start < end

  // 2. 创建子代，并复制父代1中间片段
  const child = new Array(size).fill(null);
  const mapping = new Set();
  for (let i = start; i <= end; i++) {
    child[i] = parent1[i];
    mapping.add(parent1[i].id); // 记录已占用的工单ID
  }

  // 3. 从父代2填充剩余位置
  let currentPos = (end + 1) % size;
  for (let i = 0; i < size; i++) {
    const parent2Gene = parent2[(end + 1 + i) % size];
    if (!mapping.has(parent2Gene.id)) {
      child[currentPos] = parent2Gene;
      currentPos = (currentPos + 1) % size;
    }
  }
  return child;
}

3.5 变异算子（Mutation）：交换变异 

变异算子引入随机性，防止算法过早收敛（早熟）。

/**
 * 交换变异 (Swap Mutation)
 * 随机交换染色体中两个位置的基因
 * @param {Job[]} chromosome - 染色体
 * @returns {Job[]} 变异后的染色体
 */
function swapMutation(chromosome) {
  // 生成一个随机概率，判断是否进行变异
  if (Math.random() > CONFIG.MUTATION_RATE) {
    return chromosome;
  }

  const mutated = [...chromosome];
  const idx1 = Math.floor(Math.random() * mutated.length);
  let idx2 = Math.floor(Math.random() * mutated.length);
  
  // 确保两个索引不同
  while (idx1 === idx2) {
    idx2 = Math.floor(Math.random() * mutated.length);
  }

  // 交换位置
  [mutated[idx1], mutated[idx2]] = [mutated[idx2], mutated[idx1]];
  return mutated;
}

现在，我们将上述组件组装成完整的遗传算法引擎。

/**
 * 运行遗传算法
 * @param {Job[]} jobs - 待排产的工单列表
 * @returns {object} 最优排程结果
 */
function runGeneticAlgorithm(jobs) {
  console.log('🧬 开始遗传算法排程...');
  console.time('GA Execution Time');

  // 1. 初始化种群
  let population = createInitialPopulation(jobs, CONFIG.POPULATION_SIZE);
  let bestOverallSolution = null;
  let bestOverallFitness = Infinity;

  // 2. 进化循环
  for (let gen = 0; gen < CONFIG.MAX_GENERATIONS; gen++) {
    // 2.1 计算适应度
    const fitnessScores = population.map(chromosome => calculateFitness(chromosome));

    // 2.2 更新全局最优解
    const currentBestIndex = fitnessScores.indexOf(Math.min(...fitnessScores));
    if (fitnessScores[currentBestIndex] < bestOverallFitness) {
      bestOverallFitness = fitnessScores[currentBestIndex];
      bestOverallSolution = population[currentBestIndex];
      console.log(`Generation ${gen + 1}: New Best Fitness = ${bestOverallFitness}`);
    }

    // 2.3 创建新一代种群
    const newPopulation = [];

    // 精英保留策略：直接将最优的几个个体复制到下一代
    const eliteIndices = fitnessScores
      .map((fitness, index) => ({ fitness, index }))
      .sort((a, b) => a.fitness - b.fitness)
      .slice(0, CONFIG.ELITE_COUNT)
      .map(item => item.index);

    eliteIndices.forEach(index => {
      newPopulation.push([...population[index]]);
    });

    // 2.4 通过选择、交叉、变异生成剩余个体
    while (newPopulation.length < CONFIG.POPULATION_SIZE) {
      const parent1 = tournamentSelection(population, fitnessScores);
      const parent2 = tournamentSelection(population, fitnessScores);
      let child = orderCrossover(parent1, parent2);
      child = swapMutation(child);
      newPopulation.push(child);
    }

    population = newPopulation;
  }

  console.timeEnd('GA Execution Time');
  return {
    schedule: bestOverallSolution,
    totalTime: bestOverallFitness,
  };
}

上面的代码主要优化了换型时间。在实际APS中，我们还需要考虑

。我们可以通过修改适应度函数来实现，引入

/**
 * 带交期惩罚的适应度函数
 * @param {Job[]} chromosome - 排程方案
 * @param {object} dueDates - 工单交期映射 { jobId: Date }
 * @returns {number} 适应度分数
 */
function calculateFitnessWithDueDate(chromosome, dueDates) {
  let totalTime = 0;
  let currentTime = 0;
  let previousJobId = null;
  let penalty = 0; // 罚分

  for (const job of chromosome) {
    // 换型时间
    if (previousJobId) {
      currentTime += setupTimes[previousJobId][job.id];
    }
    
    // 加工时间
    currentTime += job.processingTime;
    totalTime += job.processingTime;

    // 交期检查：如果完工时间晚于交期，施加巨额罚分
    const jobDueDate = new Date(dueDates[job.id]).getTime();
    if (currentTime > jobDueDate) {
      const delay = currentTime - jobDueDate;
      // 延迟1分钟，罚分10分钟（权重可调整）
      penalty += delay * 10; 
    }
    
    previousJobId = job.id;
  }
  
  // 总适应度 = 总耗时 + 罚分
  return totalTime + penalty;
}

五、可视化：收敛曲线与排程结果 

遗传算法输出的只是一个数组，我们需要将其转换为甘特图能识别的格式。

/**
 * 将遗传算法结果转换为甘特图任务
 * @param {Job[]} schedule - 最优排程序列
 * @returns {object} 甘特图数据 { tasks: [], links: [] }
 */
function convertToGanttTasks(schedule) {
  const tasks = [];
  let currentTime = new Date('2026-08-01 08:00:00').getTime(); // 假设早上8点开工
  let previousTaskId = null;

  schedule.forEach((job, index) => {
    const taskId = `TASK-${job.id}`;
    const setupTime = previousTaskId ? setupTimes[previousTaskId][job.id] : 0;
    
    // 加上换型时间
    currentTime += setupTime * 60 * 1000; 
    
    const startTime = new Date(currentTime);
    const endTime = new Date(currentTime + job.processingTime * 60 * 1000);
    
    tasks.push({
      id: taskId,
      text: `${job.name} (换型: ${setupTime}min)`,
      start_date: startTime,
      end_date: endTime,
      duration: job.processingTime,
      color: setupTime > 60 ? '#e74c3c' : '#27ae60', // 换型时间长标红
    });
    
    currentTime = endTime.getTime();
    previousTaskId = job.id;
  });

  return { tasks, links: [] }; // links可根据前后置关系生成
}

本文深入探讨了如何使用遗传算法解决生产排程中的核心难题——

。我们不仅实现了染色体编码、适应度函数、选择交叉变异等核心算子，更重要的是展示了如何将复杂的业务约束（如交期、换型矩阵）转化为算法可以理解的数学语言。

遗传算法是APS系统的“智慧大脑”，它赋予了系统自我进化的能力。然而，完美的静态排程在现实中往往难以持久，紧急插单、设备故障等突发情况随时可能发生。

在前面几篇文章中，我们已经完成了APS系统的“骨架”建设：甘特图提供了可视化操作界面，产能引擎算清了设备与人力负荷，物料齐套检查堵住了停工待料的风险。然而，当所有这些约束叠加在一起，面对几十个工单、十几台设备、成百上千种物料时，“怎么排”依然是一个NP-hard（非确定性多项式难度）问题。

生产计划与排程（APS）系统 | 排程算法实战：遗传算法优化生产顺序

前端开发

算法

后端

开发工具

"本文详细讲解如何用遗传算法优化生产排程，解决换型时间最小化问题。从染色体编码、适应度函数设计到交叉变异算子实现，完整展示Node.js代码。特别针对注塑、喷涂等离散制造场景，提供处理换型矩阵和交期约束的实用方案，帮助工厂提升排产效率。"

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

生产计划与排程（APS）系统 | 排程算法实战：遗传算法优化生产顺序

生产计划与排程（APS）系统 | 排程算法实战：遗传算法优化生产顺序

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐