● 摘要
流水作业排序问题已经在文献及许多技术领域被广泛研究，但研究的结果在现实应用中则失败不断。对排列型流水作业排序问题（PFSP），常见的测试问题数据通常从简单的均匀分布来生成，而更贴合实际生产环境的组合复杂问题有待研究。本文研究了工件有不同的到达时间、交货期以及相同权重的单机提前/延误问题，我们提出了基于时间松弛的解决方法，用两节的分段线性结构来描述成本系数，然后用这种松弛模式，找出原问题的可行解。试验结果证明这种方法快速并有效。我们比较了多种算法的运算性能，结果显示，由于引入了更多贴近现实的因素，经典算法的计算性能迅速下降，而一些简单的动态随机算则显示出较好的性能。我们提出了一种改进的遗传算法来解决最小化makespan和加权总延误问题。数值实验显示了改进算法的有效性。我们的试验结果表明，问题结构及问题大小中的很小改变也能够影响算法的性能。我们假设，造成这些性能差异的原因部分来源于搜索空间拓扑的差异；结构化问题所对应的拓扑趋于平缓。算法对问题特征的灵敏度分析显示进行实验分析时应该选择更贴近实际的问题。