论文部分内容阅读
现代工业的快速发展产生了越来越多新的组合优化问题，平行机排序问题是其中一个重要的模型，近年来受到了许多学者的关注。本文主要研究机器具有加工权限的平行机排序问题，全文共分为三章。第一章介绍了排序问题的基本概念、基本理论以及研究状况，接着给出了有加工权限的排序问题的相关定义及符号。第二章研究带服务等级的平行机排序问题，给出了m台同型机问题的在线算法LGF(cm，m)，证明了当m=5时，算法的竞争比为2.5194；当工件按照等级数递减顺序到达时任意机器数的算法竞争比都可以通过一定的递推关系得到。第三章讨论了有加工权限的两阶段排序问题，设计了两阶段算法并分析了算法的竞争比。