关于重新排序的一些结果

摘要

排序论作为运筹学的一个分支，有着深刻的理论意义和广阔的应用前景。所谓排序问题就是指在一定的约束条件下，对工件和机器按时间进行分配和安排加工次序，使一个或多个目标达到最优.它可以分为经典排序和现代排序.近几十年来，有关现代排序的研究有了很大的发展，新的排序模型也不断涌现.常见的现代排序模型有可控排序、成组分批排序、在线排序、同时加工排序、资源受限排序、多目标排序和带有运输考虑的排序等等.在本文中，我们研究了一种新的模型-重新排序。该模型可描述如下：一批原始工件已经按某种目标排好序，但是还没有被加工，而此时又有一批新工件来到.决策者需要把这些工件插入到原排序中进行重新排序，而原来的工件可能产生错位.本文所研究的问题是在有错位影响的约束下使排序花费达到最小.我们用π*表示原始工件的最优排序，用σ表示所有工件(包括原始工件和新到工件)的任意排序。用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的重新排序问题的一些结果。

目录

文摘

英文文摘

郑重声明

第一章引言

第二章极小化所有工件花费的重新排序问题

进一步研究

参考文献

附录：硕士期间完成的论文

致谢