【摘 要】
：
平行机排序问题的研究在理论和应用上都有重要的意义。本文主要考虑两台同类机线性时间算法的设计与证明。本文在已有的两个线性时间算法DT和PT基础上，复合出了新的算法，并通过
论文部分内容阅读
平行机排序问题的研究在理论和应用上都有重要的意义。本文主要考虑两台同类机线性时间算法的设计与证明。本文在已有的两个线性时间算法DT和PT基础上，复合出了新的算法，并通过计算机证明了他们的最坏情况界。根据这类线性时间算法最坏情况界由有限个大工件所决定的特点，我们通过枚举算法解和最优解的各种可能情形，并将每一种情形的证明转化为线性规划来求解。这使得我们可以利用计算机简化证明过程，最终得到近似性能很小的算法。
利用上述方法，文中给出了两个新的复合算法：(1)DT，PT两个算法复合的最坏情况界为11/10；(2)PT，DT,DT{1,3,5｝三个算法复合的最坏情况界为14/13，这里DT{1,3,5｝表示初始设定将工件P1，P3，P5放在同一台机器加工。
其他文献
壬戌春,作《白云深处》卷,题跋云:“生于九山怀抱之中,长于万民苦难之世。随抗日烽烟,曾历浙南山水,苏北平原,江淮河泽,齐鲁峪崮。神州造化之美,激发爱国之忱。及至五星照耀,
本文共分四章,主要研究二阶非线性Sturm-Liouville边值问题、二阶非线性Dirichlet脉冲边值问题和六阶非线性脉冲微分方程边值问题解的存在性.
第一章简述了非线性常微分
态射是两个数学结构之间保持结构过程的一种抽象，在范畴理论与基础代数学中有着重要的意义。本文在群的态射及拟态射的研究基础上，首先，定义了一种具有某些性质的群同态，我们称之
研究非线性系统时，反向（reciprocal）变换可以把目前性质还不清楚的Camassa-Holm（CH）型可积系统对应到已知的经典系统，从而导出CH型的可积性质如守恒量、Hamilton结构并构造CH型方程
列表在线排序是一类重要的现代排序模型.本文主要研究的是单机批容量有界的列表在线排序问题,目标函数为极小化工件的最大完工时间.所谓单机上的列表在线排序:工件是一个接一
双调和映射是解析函数和调和映射的推广,而p-调和映射是双调和映射的推广。众所周知,解析函数和调和映射均为复分析中的主要研究对象;而双调和映射的研究起源于力学、生物等
本文在完备Heyting代数的格值环境下,提出了新的格值模糊化收敛空间的概念,称之为格序模糊化收敛空间,并研究其性质和与其他结构之间的关系等相关问题.与原有的模糊化收敛结
本文引进了一种正交样条配置方法数值求解带弱奇异核偏积分微分方程。时间方向用二阶向后差分格式离散,空间方向用正交样条配置法离散。我们也给出了积分微分方程时间半离散