【摘 要】
:
等级约束下的负载均衡问题是组合优化领域的经典难题之一,其在近十年里得到了广泛的研究。等级约束下的负载均衡问题即把若干个带等级的工件分配给一些带等级的机器加工,工件
论文部分内容阅读
等级约束下的负载均衡问题是组合优化领域的经典难题之一,其在近十年里得到了广泛的研究。等级约束下的负载均衡问题即把若干个带等级的工件分配给一些带等级的机器加工,工件可以在等级不低于自己的机器上加工,且每个工件只能被一台机器不间断的加工。目标是寻找一种分配方案使得最大机器负载最小化,这里的负载一般定义为工件的加工时间或加工工件所需的各种资源。本文主要研究了等级约束下的负载均衡问题的两类广义形式:多重负载均衡问题和多维负载均衡问题。等级约束下的多重负载均衡问题即给定若干个客户和一些带等级的机器,每个客户提交若干个带等级的工件给这些机器加工,工件可以在等级不低于自己的机器上加工,且每个工件只能被一台机器不间断的加工。目标是寻找一种分配方案使得最大机器负载最小化。对等级约束下的多重负载均衡问题,当机器台数m = 2时,本文设计了一个5/4-近似算法,一个5/3-最优在线算法和一个在所有工件加工时间之和的一半已知的情况下的3/2-最优半在线算法并分析了近似比;当机器台数m ≥ 3时,本文设计了一个2-1/m-1-近似算法并分析了近似比。m-1等级约束下的多维负载均衡问题即把若干个带等级的工件分配给一些带等级的机器加工,此问题中的工件的负载为具有相同维数的向量,工件可以在等级不低于自已的机器上加工。目标是寻找一种分配方案使得最大机器负载分量最小化。对等级约束下的多维负载均衡问题,本文通过把每个向量的分量进行叠加的方法设计了一个2d-近似算法,同时给出了该问题的动态规划形式。当负载向量的维数和机器数都为固定常数时,本文在结合了2d-近似算法和动态规划的基础上设计了一个全多项式时间近似方案。
其他文献
当前山东省在实现工业经济效益与环境效益双赢的道路上举步维艰,两者之间的矛盾越发严重,如何在保持经济较快增长的同时,减少工业行业污染排放量,保证环境友好发展,对山东省
随着科学技术的迅速发展,非线性方程以及最优控制问题在广泛的领域当中发挥着重要的作用。但是在目前的研究中,非线性方程求解的方法仍具有局限性,对于求解最优控制问题的算
液相微萃取技术作为新型环保的样品前处理技术,由于其具有溶剂用量少、操作简单、处理时间短等优点,正受到广大分析工作者的欢迎。现代样品前处理技术的发展趋势是快速、大批量处理、高度自动化、试剂量少、低环境污染、高精确度、高可靠性和高重现性。现有的液相微萃取系统仅能进行一组实验,无法实现前处理过程的完全自动化,无法满足于后续分析仪器自动联用的过程。为了克服现有液相微萃取系统的缺点,满足样品前处理系统自动化
最小主义是由保罗·霍维奇在上个世纪末提出的一种紧缩主义真理论。作为一种紧缩主义观点,最小主义反对以类似“红色”这样的实质性质谓词来解释“真”这个概念。按照紧缩主义,所有真命题都符合形如“‘雪是白的’为真当且仅当雪是白的”这样的陈述。而霍维奇认为,“真”的概念意义就在于帮助我们对真命题作出量化概括(quantified generalization)。与主张消除“真”,或认为“真”是冗余的一些紧缩主
图像平滑是一种基础性的图像处理技术,经过平滑处理的图像往往具有更少的复杂纹理,更能突出图像的主要结构。图像平滑技术在计算机图形学和计算机视觉领域有着广泛的应用,例如:图像分割、边缘提取、图像增强、图像分解和伪影去除等技术中都可以通过图像平滑进行预处理,从而方便图像的进一步操作。图像的边缘是图像平滑过程中需要保留的关键信息,能否更有效的保护图像边缘是评价图像平滑效果的决定性因素之一。目前的平滑算法大
植物寄生线虫每年导致巨大的全球农作物经济损失,是限制农业生产的第二大因子,而线虫生物防治因为其绿色安全的特性逐渐成为线虫防治研究的热点。杀线虫芽孢杆菌B16(Bacillus
在种群生态学中,种群模型的动力学性质研究已经成为一个重要内容,而其中对具有反馈控制的种群模型的研究已受到了许多数学家和生物学家的关注.本文研究三类具有反馈控制的种
约束规格(constraint qualification)是优化与数学规划问题中的重要概念.国内外学者们的许多相关著作中都涉及约束规格,例如约束规格被应用于研究Fenchel-对偶和凸函数的次微
随着全球化竞争压力的增加,员工的工作需求随之增加,同时越来越多的女性进入劳动力市场,传统的“男主外,女主内”的模式也被双职工家庭所取代,因此员工的家庭需求也日益增加。多重家庭责任和工作需求的增加导致员工产生更多的工作家庭冲突,显著降低员工的工作-家庭平衡满意度。在此背景下,人力资源管理与组织行为学相关领域的学者开展了一系列研究,提出“家庭支持型主管行为”的概念,并围绕此概念进行实证研究。目前国内关