APS（高级计划与排程）的核心在于排程算法，遗传算法因其强大的全局搜索能力被广泛采用。本文以JVS-APS为例，深入解读其基于遗传算法的排程引擎实现，包括染色体编码、适应度函数、选择、交叉、变异等关键算子，以及约束处理、精英策略和算法终止条件。通过代码片段展示核心逻辑，并给出性能优化建议。

1. APS排程问题建模

排程问题本质上是一个带约束的组合优化问题：给定一批工单（每个工单包含多道工序）、一组设备（每台设备有加工能力、工时、可用时间），目标是最小化总完工时间（Makespan）、最大化设备利用率或满足交付期。

数学模型简化：

• 输入：工单集合J，设备集合M，工序顺序约束，加工时间矩阵。

• 约束：同一设备同一时间只能加工一个工单；工序先后顺序不可违反。

• 目标：最小化最大完工时间（minimize makespan）。

2. 遗传算法在排程中的应用概述

遗传算法（GA）模拟自然选择过程，通过选择、交叉、变异等操作迭代优化解。在排程问题中，每个个体（染色体）代表一个排程方案。

算法流程：

1. 初始化种群（随机生成可行排程方案）。

2. 计算每个个体的适应度（makespan越小，适应度越高）。

3. 选择优秀个体进入下一代（轮盘赌或锦标赛）。

4. 交叉（交换两个个体的部分基因）产生新个体。

5. 变异（随机修改部分基因）维持多样性。

6. 重复2-5步直到达到终止条件（迭代次数或收敛阈值）。

3. JVS-APS遗传算法核心代码解析

以下代码基于JVS-APS开源仓库（版本2.1）简化，保留了核心结构。

3.1 染色体编码

在排程中，常用“工序排列编码”：将所有工单的所有工序排列成一个序列，按顺序分配给可用设备。JVS-APS采用“基于工序的编码”，每个基因代表一个工单，工单出现的顺序决定其加工顺序，同时记录设备分配。

java

public class Chromosome {
    private List<Job> jobSequence;   // 工单序列
    private Map<String, Integer> machineAssignment; // 工序到设备的映射
    private double fitness;           // 适应度（makespan的倒数）
    private int makespan;             // 总完工时间
    
    // 构造方法、getter/setter省略
}

3.2 适应度函数

适应度函数用于评价排程方案的优劣。JVS-APS将makespan作为核心指标，并加入了设备负载均衡惩罚项。

java

public class FitnessCalculator {
    public static double calculate(Chromosome chromosome, 
                                   Map<String, Integer> processingTimes,
                                   List<Constraint> constraints) {
        // 模拟排程，得到每个工单的预计完成时间
        ScheduleResult result = simulate(chromosome, processingTimes, constraints);
        int makespan = result.getMakespan();
        double loadImbalance = result.getMachineLoadStdDev(); // 设备负载标准差
        
        // 适应度 = 1/makespan - penalty * loadImbalance
        double fitness = 1.0 / makespan - 0.01 * loadImbalance;
        chromosome.setMakespan(makespan);
        return fitness;
    }
    
    private static ScheduleResult simulate(Chromosome chromo, 
                                           Map<String, Integer> pt,
                                           List<Constraint> constraints) {
        // 贪心调度：按基因顺序分配工单到最早可用的设备
        Map<String, Integer> machineAvailableTime = new HashMap<>();
        Map<String, Integer> jobFinishTime = new HashMap<>();
        
        for (Job job : chromo.getJobSequence()) {
            for (Operation op : job.getOperations()) {
                int duration = pt.get(op.getId());
                int earliestStart = Math.max(machineAvailableTime.getOrDefault(op.getMachineId(), 0),
                                             jobFinishTime.getOrDefault(job.getId(), 0));
                // 应用约束（如工序顺序）
                earliestStart = applyConstraints(earliestStart, op, constraints);
                int finish = earliestStart + duration;
                machineAvailableTime.put(op.getMachineId(), finish);
                jobFinishTime.put(job.getId(), finish);
            }
        }
        int makespan = jobFinishTime.values().stream().max(Integer::compare).orElse(0);
        return new ScheduleResult(makespan, calculateLoadStdDev(machineAvailableTime));
    }
}

3.3 选择操作（锦标赛选择）

JVS-APS采用锦标赛选择策略：随机选取k个个体，选择适应度最高的进入下一代。

java
public Chromosome tournamentSelect(List<Chromosome> population, int tournamentSize) {
    Random rand = new Random();
    Chromosome best = null;
    for (int i = 0; i < tournamentSize; i++) {
        int idx = rand.nextInt(population.size());
        Chromosome candidate = population.get(idx);
        if (best == null || candidate.getFitness() > best.getFitness()) {
            best = candidate;
        }
    }
    return best;
}

3.4 交叉操作（Order Crossover, OX）

由于工单顺序编码的特殊性，不能使用简单单点交叉（会导致工单重复或缺失）。JVS-APS实现了顺序交叉（OX）：

java

public Chromosome orderCrossover(Chromosome parent1, Chromosome parent2) {
    List<Job> p1Seq = parent1.getJobSequence();
    List<Job> p2Seq = parent2.getJobSequence();
    int size = p1Seq.size();
    Random rand = new Random();
    int start = rand.nextInt(size);
    int end = rand.nextInt(size - start) + start;
    
    // 子代先继承parent1的[start, end]区间
    List<Job> childSeq = new ArrayList<>(Collections.nCopies(size, null));
    for (int i = start; i <= end; i++) {
        childSeq.set(i, p1Seq.get(i));
    }
    // 剩余位置按parent2的顺序填充未出现的工单
    int idx = 0;
    for (Job job : p2Seq) {
        if (!childSeq.contains(job)) {
            while (childSeq.get(idx) != null) idx++;
            childSeq.set(idx, job);
        }
    }
    return new Chromosome(childSeq);
}

3.5 变异操作（交换变异）

随机交换两个不同位置的工单，以维持种群多样性。

java

public void mutate(Chromosome chromosome, double mutationRate) {
    Random rand = new Random();
    List<Job> seq = chromosome.getJobSequence();
    if (rand.nextDouble() < mutationRate) {
        int i = rand.nextInt(seq.size());
        int j = rand.nextInt(seq.size());
        if (i != j) {
            Collections.swap(seq, i, j);
        }
    }
}

3.6 精英策略

在每一代，保留最优的几个个体直接进入下一代，防止最优解丢失。

java

public List<Chromosome> nextGeneration(List<Chromosome> population, int eliteCount) {
    // 按适应度降序排序
    population.sort((a,b) -> Double.compare(b.getFitness(), a.getFitness()));
    List<Chromosome> newPop = new ArrayList<>(population.subList(0, eliteCount));
    
    while (newPop.size() < population.size()) {
        Chromosome parent1 = tournamentSelect(population, 3);
        Chromosome parent2 = tournamentSelect(population, 3);
        Chromosome child = orderCrossover(parent1, parent2);
        mutate(child, 0.05);
        child.setFitness(FitnessCalculator.calculate(child, ...));
        newPop.add(child);
    }
    return newPop;
}

4. 约束处理

实际排程中存在多种约束（设备不可用时间、工单优先级、物料限制等）。JVS-APS在模拟调度阶段（simulate方法中）通过applyConstraints函数处理：

java

private static int applyConstraints(int earliestStart, Operation op, List<Constraint> constraints) {
    for (Constraint c : constraints) {
        if (c.getType() == ConstraintType.MACHINE_DOWNTIME && 
            c.getMachineId().equals(op.getMachineId())) {
            // 如果设备在某个时间段不可用，推迟开始时间
            earliestStart = Math.max(earliestStart, c.getEndTime());
        }
        if (c.getType() == ConstraintType.PRECEDENCE && 
            c.getNextOpId().equals(op.getId())) {
            // 工序依赖：前一道工序完成后才能开始
            earliestStart = Math.max(earliestStart, c.getPrevFinishTime());
        }
    }
    return earliestStart;
}

5. 算法终止条件与性能调优

JVS-APS支持两种终止条件：

• 最大迭代次数：默认2000代。

• 收敛判断：连续100代最优适应度无提升。

性能优化经验：

• 种群大小：工单数的2~4倍（例如50工单，种群大小100~200）。

• 交叉概率：0.8~0.95。

• 变异概率：0.01~0.1（随迭代次数递减）。

• 精英数量：种群大小的5%。

实测性能：在200工单、20设备的排程问题中，JVS-APS默认参数下，约500代收敛，耗时约25秒（4核8G机器）。

6. 总结

JVS-APS的遗传算法排程引擎通过染色体编码、适应度函数、选择交叉变异等算子，实现了高效的生产排程优化。本文通过核心代码片段展示了其实现细节，包括顺序交叉、锦标赛选择、约束处理等。开发者可以基于此扩展自定义的优化目标或约束，以适应不同工厂的特殊需求。完整的排程引擎源码可在JVS-APS官方仓库查看。

标签：#APS #遗传算法 #生产排程 #JVS-APS #源码分析