两机器最小总误工数分组排序问题算法研究

摘要

成组技术在现代生产中有着广泛的应用，对分组排序问题的研究有着重要的实际意义。本文以现代生产制造业中成组生产为实际背景，研究了一类两机器分组排序的最小总误工数问题(F2ISf1，Sf2，ddm|∑Ui)。本文证明了此问题是NP一Hard问题，因此此类问题在规模较大的情况下，要用有限的资源在合理的时间内获得最优解将比较困难。本文研究了此类问题的最优解结构和优势准则，并着重研究了此类问题的遗传算法优化。 本文的主要创新和贡献如下： 1．最优解结构性质的提出和证明。本文提出了关于此类问题最优解结构的一个引理和两个定理，并加以证明。为本文研究的遗传算法优化提供了理论支持，并有助于分支定界等算法的研究。 2．优势准则的提出和证明。本文提出了此类问题的一个优势准则，可作为分支定界算法的剪枝规则。 3．整数规划模型的提出。 4．此类问题遗传算法的提出。本文介绍了此类问题的遗传算法编码、适应度函数及尺度变换、选择算子、交叉算子和变异算子。并用VB语言编程实现，给出了计算结果。 本文的研究成果在实际生产环境中具有相当的实用价值，可以应用在企业的生产排程系统中用来解决此类问题。

目录

摘要

1绪论

2相关的排序问题

3F2|Sf1，Sf2，ddm|∑Ui问题的最优化模型

4F2|Sf1，Sf2，ddmI∑Ui的遗传算法优化

5计算实例

6结束语

参考文献

致谢

论文独创性声明及论文使用授权声明