单机并行批调度问题的计算法研究

发布时间：2020-06-28 00:14

【摘要】：随着科学技术的发展,越来越多的单产品处理器被批处理器所取代。人们对批调度问题的研究达到了前所未有的高度,其中大多数工作是针对单机并行批调度问题的研究。论文研究如下单机并行批调度问题：给定一些工件{J1,J2,…,Jn},每个工件J有给定的处理时间乃,以及惩罚值ej(可以拒绝处理某些工件,ej为拒绝处理工件J,付出的代价)。给定一个批处理器,处理器可以将多个工件作为一批同时处理。同一批工件具有相同的开始时间和结束时间,即开始时间加上这一个批中所有工件的最大给定处理时间。调度的目标是判断选择处理哪些工件、给这些工件分批以及给批排序,使得目标函数值达到最小。在本文中,我们考虑的目标函数为被处理工件的完成时间之和加上被拒绝工件的惩罚值之和,并对批容量无界和批容量有界两种情况分别进行讨论,其中,批容量无界是指一批中处理的工件个数没有限制,批容量有界是指一批中处理的工件个数不超过某个常数b。对批容量无界的情况,我们使用后向动态规划的技术,并使用堆排序的思想,提出时间复杂性为O(n4)的精确算法,然后使用几何归纳的方法将算法的时间复杂性改进到O(n3 log n)。批容量有界的情况更加复杂,批不再满足批容量无界时满足的一些重要性质。我们使用后向动态规划的方法合理枚举所有可能的情况,以得到最优的调度。我们给出了时间复杂性为O(n2b2-2b+2)的精确算法,从而证明当批容量b为常量时,该问题是多项式时间可解的。
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TP332

【参考文献】