【摘 要】
：
排序问题研究一直是运筹学的一个热门分支,在此领域中已经产生许许多多有实际意义的研究成果。作为排序问题的新型模型之一,可拒绝排序近几年一直是备受关注的研究课题,本文
论文部分内容阅读
排序问题研究一直是运筹学的一个热门分支,在此领域中已经产生许许多多有实际意义的研究成果。作为排序问题的新型模型之一,可拒绝排序近几年一直是备受关注的研究课题,本文就此模型做了如下工作：
⑴在第2章中,我们考虑了工件有工期的单机可拒绝排序的两类模型,其一是目标函数为极小化最大提前完工时间与拒绝费用和,即1|nmit|Emax+∑Jj∈(S)ej;其二为最大提前完工时间带限制下极小化总拒绝费用,即1|nmit,Emax≤Y|∑Jj∈(S)ej.用Pareto最优点思想得出相应的解决方案,最终得到这两个排序问题都是可以在多项式时间内求解。
⑵在第3章中,我们研究了时间表长带限制的单机可拒绝排序问题,目标函数为极小化总拒绝费用和.我们考虑了下列两类不同情形下的问题,即:1|rej,Cmax≤Y|∑Jj∈(S)ej1|rej,rj,,Cxax≤Y|∑Jj∈(S)ej。利用不同的归结方法,证明了这两个问题都是NP-难的,同时给出了其相应的动态规划算法以及全多项式对偶近似算法。对于排序问题1|rej,Lmax≤Y|∑Jj∈(S)ej,本文给出了一个动态规划的伪多项式时间算法。
⑶在第4章中,我们研究了加权完工时间和带限制的可拒绝排序问题,目标函数为极小化总拒绝费用和,即1|rej,∑j∈SwjCj≤Y|∑Jj∈(S)ej,我们证明了此问题是NP-难的,给出了其相应的动态规划算法,并设计出了全多项式对偶近似算法。
其他文献
张量分析是研究理论物理、连续介质力学、科学与工程等领域的一个重要工具．论文考察各向同性超对称Descartes张量，张量的特征值与特征多项式以及超对称张量的对称超行列式．全文
令μ是欧式空间Rd上具有紧支集的Borel概率测度。建立在测度μ上傅里叶分析的基本问题是:是否存在可数子集Λ(∈)Rd使得复指数函数族E（Λ）:={e2πi}λ∈Λ构成L2（μ)的正交基（傅
随机动力系统作为动力系统的一个推广.因其研究过程中考虑了不确定和随机因素，在实际应用中占有极为重要的地位。格点动力系统出现在化学反应理论、模式识别等许多应用领域。
张量是矩阵的高阶推广，随着传统的矩阵理论在处理数据上体现出来的局限性，张量分析成为科学与工程领域中应用的一个重要工具，其中张量的分解与张量的最佳低秩逼近问题是近来研究
本论文在前人研究的基础上，对第二大特征根不超过1的三圈图进行了刻画，主要内容包括：
·在前两节，我们首先介绍了关于第二大特征根的研究背景和研究意义，国内外在这方面具有
在现代统计分析中，我们经常会遇到高维数据，而传统的统计推断方法在这种情况下不再适用，因为在数据的维数高于样本数，也就是我们俗称的“大p小n”情形下，原来的统计量不再具有收敛
本文分别运用锥上的不动点定理、Banach压缩映像原理以及Leray-Schauder非线性抉择结合积分半群理论，建立了带时滞泛函微分方程边值问题正解的存在性、无穷时滞分数阶半线性泛
整数流理论是被Tutte作为解决四色猜想的工具引入的，设D是图G的一个定向，E+D(v)(D-D(v))表示以v为起点(终点)的所有边的集合，如果存在映射f：E(G)→{±1，±2，...，±(k-1)}使得对任意v
本文研究的是分层均匀媒质中均匀可穿透障碍物的时间调和声波的散射问题。这里我们只研究其正散射问题.用边界积分方程方法将原问题转化为边界积分方程.我们主要应用格林公式