【摘 要】
：
近年来,重新排序问题研究开始引起广泛的关注.本文以工厂机器加工工件(工件与任务表示相同的概念)作为实际背景,主要考虑有一批工件已经按照某种规则进行了排序并使得目标函
论文部分内容阅读
近年来,重新排序问题研究开始引起广泛的关注.本文以工厂机器加工工件(工件与任务表示相同的概念)作为实际背景,主要考虑有一批工件已经按照某种规则进行了排序并使得目标函数达到了最优,其中有一些工件由于各种各样的原因要推迟到某个时间点后才可以开始加工,此时,决策者需要对原来的排序进行调整,即在原来最优排序的基础上,在工件的时间错位不至于太大的限制下进行重新排序,并使得原来的目标函数达到最优的单机问题.本文研究的问题的目标函数是经典的加权完工时间总和.对于这个问题Nicholas G.Hall不Chris N.Potts已经提供了一种复杂度是伪多项式时间的动态规划最优算法TWCOA,并给出了其时间复杂度的分析,随后给出了GAA近似算法,其最坏情况误差比为2.本文对该近似算法进行改善,得到了更好的SR近似算法并给出了其最坏情况误差比比GAA近似算法小的证明.同时对该问题进行了拓展,将条件中的重排工件共有的一个释放时间变成两个不同的释放时间,使问题变得更一般化,然后进行讨论从而得到该问题的一个近似算法SRT.
其他文献
在本文中,主要利用了亚纯函数的Nevanlinna值分布理论以及亚纯函数对数导数引理的差分模拟和差分多项式的值分布性质,研究了一类复差分方程组亚纯解的结构;研究了C~n上的一类
数论是一个古老而又不断发展的数学学科,它主要研究的是数的规律,尤其是研究整数的性质.Smarandache函数是数论研究的重要内容之一,随着人们对它不断的研究,目前已经出现了很
本文运用了研究算子半群的经典方法,在研究双参数C半群及其无穷小生成元、逼近及扰动等性质与双参数0C有界算子群的性质基础上,再联系算子的范数连续性与绝对紧性来研究扰动
本文研究了两类无穷维动力系统的拉回吸引子的存在性问题.首先证明了非自治Cahn-Hilliard方程在)(2L?空间中存在拉回吸引子,其次又考虑了粘性Cahn-Hilliard方程存在拉回吸引
矩阵拉伸运算是处理矩阵的一个重要工具,特别是在矩阵方程求解方面.近年来,关于矩阵拉伸运算问题的研究主要从行拉伸及列拉伸两个角度进行,并讨论了它们的一些简单性质.本文
本文首先在广义算子C0-半群和广义算子C-半群已有研究的基础上,得到了广义算子C-半群的生成定理、扰动定理及谱映射定理,其次,给出了完全连续广义算子C-半群的概念,并讨论了
混沌理论属于非线性科学领域中的一门分支学科,它阐述了自然界内许多无法解释的现象,人们对它的探索自然成为重中之重。我们可以这样描述一个混沌系统,即它最少会在一个或更
本文在总结现有模型辅助估计方法的基础上,发现基于线性模型的估计量和非参数回归估计方法都有相应的不足之处。本文通过构造一种半参数超总体模型,同时结合广义差分估计思想
六角系统是2-连通的平面二部图且它的每个内面都是一个正六角形,其共振图反映了它的完美匹配的整体结构Fibonacenes是六角系统中的一类图.S.Klavzar和P. Zigert Pletersek在2
本文主要考虑了有界区域上一类满足D irichlet边值条件的加权p(x)-Laplacian发展方程解的长时间行为,其中反应扩散系数ω是几乎处处有限非负可测的,在Ω的零测闭子集Ω0上ω(