第1章 绪 论
1.1 研究背景及意义
排序论是组合优化中的一个分支，有着广阔的应用前景。从深层次来看，排序论对提高效率、资源的合理配置、工程进展统筹安排以及经济运行等方面都起到了辅助决策的作用，所以管理层和决策层不能不了解排序的理论和应用。
我们可以把排序理解为两种涵义。狭义的涵义是安排次序；广义的涵义是安排时间表，故排序论也称为时间表理论。在排序论中，工件是被加工的对象，或者说是要完成的任务；机器是提供加工的对象，是完成的任务所需要的资源；安排时间表是在一定的约束条件下对工件和机器进行分配和安排次序，使某一个或某几个目标达到最优。例如，对门诊病人到医疗诊所看病的排序问题也可以描述成为‘工件’在‘机器’上‘加工’的过程。排序论中的“机器”和“工件”已经不单单是机器制造业中的“车床”或“车床加工的螺丝”了，已经从“车床”和“螺丝“等具体事物中抽象出来，是抽象的概念。
其次，排序应用在运筹学领域。运筹学主要发展于第二次世界大战期间。1937年英国空军首次在雷达系统上使用，目的是为了延长雷达第一次报警时间与敌方航空器攻击到达时间两者之间的时差，以进行合理的防备。1942年英国人新造了“运筹学”这个名词。当然，同时期美国也有类似的研究群体。当英国人盛行使用这个名词时，美国人也同样的用上了。在50年代，英美国家陆续创刊了许多运筹学方面的杂志。这也说明了作为运筹学子科学的排序论当时是在军事问题的刺激下产生和发展起来的。
第三，排序论在计算机科学领域也扮演了重要的角色。在二十世纪的50年代，计算机在公共事业和经济领域扮演着重要的角色。人们不仅需要计算机解决实际中的排序问题，而且计算机网络本身又产生了新的排序问题，即如何管理计算机的问题。相比之下，出现在管理科学和运筹学中的排序问题我们一般称之为“工程序列问题”，不过机器排序问题和工程排序问题之间并无明显的界线。
另外，排序论在近些年开始大量应用到了金融领域，如Gupta等人利用该理论解决了多贷款偿还问题。该金融问题可以归纳为以下排序模型：目标为极小化完工时间，工件加工时间随开工时间延后指数增长。我们把要偿还的贷款看做待加工的工件，机器的加工能力由我们目前的资金情况决定。
1.2 研究现状
在本文中，我们将提到几类特殊的工件，其中一类叫作恶化工件（deterioratingjob）,该类工件的加工时间随着开工时间的延后而增加，可能线性增加，也可能非线性增加。
该模型有很多应用，如在一台工作效率逐渐变低的机器上加工工件、利用合理资源控制传染病的传染，合理安排多贷款问题等。迄今为止，对该模型大多数人研究一台机器上，且工件加工时间随开工时间是线性递增的情况。一般情况，工件i的加工时间Pi(t) = Pi+ ait，Pi是在零时刻加工工件i所需要的加工时间，ai我们称为加工时间的退化率。另外，研究恶化工件排序问题的其它形式以及其它恶化参量等近几年都有所突破。
上述关于工件加工时间的函数中,当ai= 0时，该问题退化成传统的加工时间恒定的排序模型；当ai< 0时,工件i的加工时间随着开工时间的增大而减小。在本文参考文献Mosheiov著 和Alidae等著[1]中有更多关于恶化工件排序问题的变型问题，有兴趣的读者可以查阅。另外，Mosheiov研究了最简单的工件加工时间的恶化情况(Pi(t) = ait)。我们研究的传统非打断n工件单机排序模型中，一般要考虑的优化目标是完工时间、总的延误时间、延误工件数量等，上述这些模型都是多项式可解得。Alidae和Womer[1]研究了在单机上工件加工时间与工时间相关的排序问题，他们分别讨论了加工时间关于开工时间是分段线性、非线性的情况，解决了很多实际问题。随后，Mosheiov等研究了在单机上退化率与工件无关(ai= a i)的排序问题，目标函数是极小化工件完工时间的加权之和，其权值与初始加工时间成正比。同时还证明了该类排序问题的最优序列是Λ型的，在O(N logN)时间内可以得到最优解。Browne和Yechiali 讨论了目标为极小化所有工件完工时间，工件加工时间随着开工时间增加而增大，工件退化率与工件相关的排序问题。另外Mosheiov[25]研究了工件加工时间关于开工时间是线性函数的情况。这种情况下如果所有工件在零时刻开工，那么它们的加工时间相同(Pi(t) = p i)。当退化率与工件无关时，目标函数为极小化最后工件延误时间时，最优解是V-型的，同时给出了时间复杂度为O(N logN)的启发式算法。Cheng和Ding[6]介绍了单机上工件有到达时间并且具有线性退化率，目标是极小化完工时间的情况，同时还证明了该问题是NP-完全问题。Gupta[11]研究了工件加工时间是关于开工时间的多项式，目标为极小化完工时间的情况，并给出了精确算法，同时还给出了另一个启发式算法，该算法大大降低了时间复杂度。
Sriskandarajah 和Goyal研究了两台机器上恶化工件排序问题，并证明了该问题是NP-难问题，另外还给出一个计算最优解的启发式算法。Finke和Jiang对其进行了推广，研究了m台机器的情况。另外，两台机器的情况，人们给出了一些近似算法。Chen考虑了平行机上带有线性恶化率的排序问题，目标为极小化完工时间，并证明了该问题即使工件数目确定，仍然是NP-难问题，最后还对两台机器的情况做了其它方面的一些讨论。
第2章 单机上第一类特殊工件排序问题
2.1 问题介绍
Fleischmann等人指出本文研究的问题来源于一些高科技产品拆卸后的加工再利用，如个人电脑、汽车、手机等。对于这些产品的不同部件，我们往往需要同样的设备去检测、修复，所以本文研究的价值恶化工件排序问题就产生了。科技飞速发展的今天，高科技产品价值随着时间在不断降低，而且同一件产品不同部件的价值下降率明显是不一样的，另外，开工时间越晚，可能意味着再加工利用的难度越大，即加工时间越长。我们基于恶化工件(deteriorating jobs)与价值恶化工件(deterioratingvalueofjobs)工件模型，提出第一类特殊工件，即工件价值随完工时间指数减少，同时工件加工时间随开工时间的延后线性增加。首先我们介绍几个本文出现的符号含义：
Pi(t): 单位工件i在时刻t的加工时间;
Vi(t): 单位工件i的价值(随着时间逐渐递减);
Ki: 单位工件i在零时刻的价值(初始价值);
ai: 工件i的价值恶化率(ai< 0)。
假设工件i在t时刻的价值Vi(t) = Kitai, t为工件i的等待时间与加工时间之和。因此，工件i的完工时间等于所有在工件i前面加工的工件的时间和加上Pi(t)，本文中Pi(t) = bi(a + bit), ( a, b, bi(t) > 0)，t为工件i的开工时间。我们的目标是找到一个所有工件在单机上的加工序列，使所有工件损失的价值和最小。与该目标等价的另一个目标为极大化所有工件剩余价值和。
下面建立数学模型来说明上述问题。我们令Vi(t)表示工件i完工后的价值，此时时间t等于加工i之前所有完工工件加工时间和加上Pi(t)。于是可以把问题这样描述：n个工件在一台机器上加工，我们需要确定一个加工序列使得所有工件完成加工后的剩余价值和F最大。不妨设< J1, J2, · · · , Jn>是我们要找的最优序列，那么最优值F = V1+ V2+ · · · + Vn。进一步可以得到
2.2 分支定界算法
分支定界法是一个用途比较广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各式各样。分支定界法的基本思想与遍历算法相似，是对有约束条件的最优化问题的所有可行解（数目有限）进行搜索。该算法具体执行时，把全部可行解空间不断分割为越来越小的子集（称为分支），并为每个分支内解的值估计一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步搜索。这样，解的许多子集（即搜索树上的许多结点）就可以不必花时间搜索了，从而缩小了范围。这一过程一直进行到找出可行解为止，且该可行解的值不大于任何子集的界限。因此这种算法一般可以得到最优解。
当问题的目标函数是求最优解时，如果是求最大值，就把目标函数的界初始化最小；如果是求最小值，就把目标函数的界初始化为最大。当从某个节点向下搜索时，估计从该节点向下搜索所可能取得的值，把这个值和当前目标函数的界进行比较，如果是求最大值，而结果又大于目标函数的界，就继续从这个节点向下搜索，否则就把这个节点丢弃。这时的搜索，才有了方向。这种搜索，只有在找到一个可行解之后，目标函数的界才有意义。在寻找第一个可行解时，搜索仍然是盲目的。在整个搜索过程中，也是盲目搜索的。
但是，从某个节点进行搜索时，先估计目标函数的界，再确定是否向下继续搜索的方法启发人们去寻求另一种搜索模式。这种搜索模式，就是本论文要讨论的分支定界算法。
该分支定界算法的基本思想是在节点上，预先分别估算沿着它的各个儿子节点向下搜索的路径中，目标函数可能取得的“界”，然后把他的这些儿子节点和它们可能取得的“界”保存在一张节点表中，再从表中选取“界”最大或最小的节点向下搜索。因为必须从表中选取“界”取到极值的节点，所以经常用优先队列来保存和更新这张表，但是也可以使用堆结构来更新这张表。
这样，从根节点出发，整个搜索过程中，每遇到一个节点就对其各个儿子节点可能取得的值进行估算，以此来更新节点表，丢弃那些不需要的节点，加入新的节点。再从表中选取“界”取极值的节点，并重复上述过程。随着这个过程的不断进行，节点表中所估算的目标函数的界，越来越接近问题的解。当搜索到一个叶子节点时，如果对该节点所估算的目标函数的值是节点表中的最大值或最小值，那么沿叶子节点到根节点的路径所确定的解，就是问题的最优解，由该叶子节点所确定的目标函数的值就是解这个问题所得到的最大值和最小值。这样，分支定界算法依据节点表中不断更新的信息，不断地调整自己的搜索方向，有选择、有目标地往前搜索。
第3章 单机上第二类特殊工件排序问题...................21
3.1 问题介绍.................. 21
3.2 分支定界算法的上界推导...................22
3.3 本章小结 .....................24
第4章 数值实验 ............... 25
第4章 数值实验
为了测试分支定界算法的计算效率，本文分别对两种特殊工件单机排序问题的分支定界算法做了一些的数值实验,所有的测试均在CPU为IntelCorei5-3210M主频为2.50GHz，内存为8G的微机上进行，所有代码均用C语言编写，用VC++6.0编译。第一部分数值实验针对第一种特殊工件的单机排序问题进行的，首先在一定范围内随机产生一些数据，然后分别用分支定界算法和遍历算法计算最优解，并记录了上述两种算法的运行时间。下面是输入数据的取值范围：
下表是第一种特殊工件单机排序问题的数值实验结果。
结论
排序论作为运筹学的一个分支，有着深刻的实际背景和广阔的应用前景，一直受到学术界的重视。从深层次和长远来看，排序论对提高效率、资源的开发和配置、工程进展的安排以及经济运行等方面都能起到辅助科学决策的作用，所以管理层和决策层不能不了解有关排序的理论和应用。近些年来，为了研究生产以及生活中出现的新问题，人们对排序论进行了推广，从而产生了了现代排序，这种排序是非经典的、新型的排序。
本论文研究的两类特殊工件单机排序问题在现代排序中具有很强的代表性，第一类特殊工件的加工时间随着开工时间的延后不断增加，其价值不断减小；第二类特殊工件加工时间不变，只是价值随着完工时间的延后而减小。这两类特殊工件在现实生活中有其原型，如高科技产品重新加工利用中产生的不同部件、森林火灾以及在金融学中的一些模型等。由于这些问题的时间复杂度很高，本文利用分支定界算法计算这两类排序问题，既在一定程度上提高了计算效率，又确保了解的最优性。
待研究的课题
(1)本论文对单机上两类特殊工件的排序问题做了初步的计算,在一定程度上提高了计算效率，我们可以寻找新的计算方法进一步提高计算效率。
(2)关于这两类特殊问题，我们可以寻找更好的启发式算法得到初始解，从而进一步提高分支定界算法的计算效率。
(3)本论文只是给出了一种计算这两类特殊工件排序问题的方法，我们可以尝试利用近似算法计算，从而在理论上给出近似比。
参考文献（略）