针对粒子群算法求解置换流水车间调度这类NP-hard问题存在的早熟问题，本文提出了一种基于随机键编码的双模式飞行粒子群算法。首先，基于ROV规则对工件加工顺序进行随机键编码。其次，粒子在搜索过程中采用带有自适应惯性权重的双模飞行方式来更新位置和速度，避免粒子群陷入早熟收敛状态。为了提高解的质量，每次迭代过程中对PSO优化得到的种群最优解进行邻域局部搜索。最后，通过对标准测试集的数值仿真及与其他PSO算法的比较，证实了所提算法求解该问题的有效性与可行性。