关于重新排序的一些结果

来源 :郑州大学 | 被引量 : 0次 | 上传用户:sql70
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
排序论作为运筹学的一个分支,有着深刻的理论意义和广阔的应用前景。所谓排序问题就是指在一定的约束条件下,对工件和机器按时间进行分配和安排加工次序,使一个或多个目标达到最优.它可以分为经典排序和现代排序.近几十年来,有关现代排序的研究有了很大的发展,新的排序模型也不断涌现.常见的现代排序模型有可控排序、成组分批排序、在线排序、同时加工排序、资源受限排序、多目标排序和带有运输考虑的排序等等.在本文中,我们研究了一种新的模型-重新排序。该模型可描述如下:一批原始工件已经按某种目标排好序,但是还没有被加工,而此时又有一批新工件来到.决策者需要把这些工件插入到原排序中进行重新排序,而原来的工件可能产生错位.本文所研究的问题是在有错位影响的约束下使排序花费达到最小.我们用π*表示原始工件的最优排序,用σ表示所有工件(包括原始工件和新到工件)的任意排序。用Dj(π*,σ)和△j(π*,σ)分别表示工件j在π*和σ之间产生的顺序错位和时间错位,分别简写为Dj(π*)和△j(π*)。本文用到的错位主要有以下几个:Dmax(π*)表示工件的最大序错位;∑Dj(π*)表示工件的总序错位;△max(π*)表示工件的最大时间错位;∑△j(π*)表示工件的总时间错位。 本篇论文的工作是Hall和Potts等人(2004)的研究工作的发展,主要研究两种重新排序模型:极小化所有工件的排序花费和极小化总的花费目标(其中包括排序的花费和错位花费)。主要结果如下: (1)问题1|Dmax(π*)≤k1,△max(π*)≤k2,∑Dj(π*)≤k3,∑△j(π*)≤k4|∑Cj在O(n2on2Nmin{nOPN,nNPO})时间内可解;(2)问题1||Lmax+μ1Dmax(π*)+μ2△max(π*)在O(n+nNlognN)时间内可解;(3))问题1‖∑Cj+μ1Dmax(π*)+μ2△max(π*)在O(n+nNlognN)时间内可解;(4)问题1‖∑Cj+μ1∑Dj(π*)+μ2∑△j(π*)在O(n+nNlogn)时间内可解.另外本文还得到对目标函数是∑WjCj和∑WjUj的重新排序问题的一些结果。
其他文献
局部分析方法是有限群理论最基本的方法.所谓局部分析就是通过分析和考察局部子群的性质和结构,从而确定单群本身的结构和性质.局部子群原来是指p-局部子群,即G的任一个非平凡
随着现代工业和现代科技需求的不断提升,需要真实准确的数学模型对系统进行分析和综合,在更大程度上改善系统性能,达到高精准的目的.近几十年来,很多学者已经证实实际中存在的系
本文主要研究集值映射的变分不等式问题和最优化问题解的存在性.本文主要是利用例外簇代替强制条件研究集值映射的变分不等式问题和最优化问题解的存在性.本文具体安排如下: