【摘 要】
：
本文以经典排序模型P2||C为例，研究一类新的排序模型，可重排在线排序问题，即当工件到来时必须确定它将在那台机器上加工，但当所有工件都安排完毕后，可以在一定的条件下对已安排的
论文部分内容阅读
本文以经典排序模型P2||C<,max>为例，研究一类新的排序模型，可重排在线排序问题，即当工件到来时必须确定它将在那台机器上加工，但当所有工件都安排完毕后，可以在一定的条件下对已安排的工件进行重新安排．研究了四类不同的模型，第一类是我们可以重排整个工件序列中的最后k个工件，其下界为3/2．第二类是可重排全部工件安排完毕后每台机器上的最后一个工件，其下界是平方根2，同时给出了最优算法．第三类是可以重排任意有限的k个工件，其下界为4/3，同时我们设计出只需重排一个工件的最优算法．在第四类模型中，研究带费用重排问题，即可以在工件安排完毕后重排任意工件，重排费用为工件加工时间的α倍，目标函数为makespan和重排费用之和．给出了问题的下界，并分析了一些简单算法的竞争比．全文结构编排如下：
第一章是绪论，介绍排序相关知识和初步结论．
第二章研究了前三类不需重排费用的可重排模型：
第三章研究带费用重排模型.
其他文献
生物学是一门以实验为基础的自然科学，生物学实验教学重在培养学生设计实验、动手操作、学会收集、选择运用和分享信息等科学探究的能力，养成质疑、求实、创新及勇于实践的科学
设｛Xn,n≥1｝是概率空间｛Ω,F,P｝上的一列随机变量，如果对于Rn上的任意两个按坐标方式非降的函数f和g，若满足 Cov{f(X1,X2,…，Xn),g(X1,X2,…，Xn)}≥0 称｛X1,X2,…，Xn｝是正相协的，简
本文首先讨论了带随机约束的线性回归模型，给出了其广义最小二乘估计，证明了数据删除模型和均值漂移模型的等价性定理，介绍了几种残差的概念，求出了Cook距离，W-K统计量，协方差比，似
随着凛冽的北风,今冬的第一场雪悄然来临,12月初,华北电网经受了入冬以来第一次强寒流突袭,5至6级的大风使北京地区最高气温骤降到0℃以下,华北电网最大负荷急升至8211万千瓦
随着我国改革开放的不断加深,各行各业的发展也越来越迅速。目前变电站在国内发展十分迅速,变电站自动化系统受到人们的广泛关注。由于变电站自动化系统内部的数据大多分布在
非线性抛物型方程理论是现代数学研究的极其重要的内容之一。反应扩散方程是一类典型的非线性抛物型方程，它可以描述众多学科中发现的自然现象，例如生物学中的物种入侵及增长过
本文研究在部分信息情况下有交易成本的极大化终止时刻期望效用的最优投资策略问题. 对于正态分布的部分信息模型, 运用卡尔曼滤波技术, 给出风险资产平均收益率的最优估计.
区间值模糊集（简称为IVFS）与双枝模糊集（简称为BBFS）是普通模糊集的两种推广形式。对于区间值模糊集而言，由于在对事物属性的描述上提供了更多的选择方式，较传统的模糊集有更强的表
作为线性保持问题的主要研究方向之一，对保持非负半群上矩阵项秩的加法映射的探究具有很大的意义。本文主要将非负半环上保持矩阵项秩的线性映射减弱为非负半群上保持矩阵项秩
相参处理与非相参处理是雷达信号处理的基本方式。在雷达信号处理中,相参信号处理一般采用MTI、MTD或PD方式,能有效滤除静杂波和动杂波,因此相参处理比非相参处理在改善目标