论文部分内容阅读
本硕士论文由三章组成，主要讨论两类在m台平行机器上加工的工件具有相似长度的半在线排序问题。第一个问题是对于在m台同型机器上加工，具有相似长度，即工件的加工时长在[1，r]内的情况，通过对LS算法的分析，得出了改进的最坏情况性能比，第二个问题是考虑工件在m台同类机器上加工，有到达时间，具有相似长度，提出了一个新的算法，并得出了相应的最坏情况性能比。
第一章介绍了问题研究的背景和该领域的研究现状，主要介绍了一下最坏情况性能比，机器的分类，等基础知识。
第二章分别从两个方面对LS算法在第一种情况下的最坏性能比进行分析，得到了改进的结果。
第三章对于第二个问题，构造新的算法，证明其最坏情况性能比。