摘要: 本文研究了若干新型排序问题，主要包括工件可拒绝的平行机代理排序问题、工件带退化和拒绝的分批排序问题、工件带退化和拒绝的多代理排序问题、带有人员不可用区间的两台机器流水车间排序问题以及工件可拒绝的供应链排序问题五个方面。针对不同的问... 展开 本文研究了若干新型排序问题，主要包括工件可拒绝的平行机代理排序问题、工件带退化和拒绝的分批排序问题、工件带退化和拒绝的多代理排序问题、带有人员不可用区间的两台机器流水车间排序问题以及工件可拒绝的供应链排序问题五个方面。针对不同的问题，我们分别给出了相应的算法，并对一些问题的计算复杂性进行了分析。 第一章首先给出了组合优化和排序论方面的一些基本概念和定义，然后介绍了与本文内容相关方向的研究现状，最后介绍了本文的主要研究成果。 第二章研究了工件可拒绝的平行机代理排序问题。给定两个代理A和B以及两台平行机，每个代理有一批工件需要在机器上加工，两个代理的工件互不相同。对于任意一个工件，可以被拒绝并支付一定的拒绝费用，或者被接受并安排在机器上加工。目标是在代理B的接受工件对应的目标函数fB与拒绝B-工件的总拒绝费用之和不超过一给定上界的情况下，极小化代理A的接受工件对应的目标函数fA与拒绝A-工件的总拒绝费用之和，其中fA和fB分别是关于代理A和代理B的接受工件的完工时间的正则函数。我们研究了四种不同的目标函数组合，fA=∑CAj，fB∈{CBmax,LBmax,∑CBj，∑WBjUBj}。当(fA,fB)=(∑CAj，CBmax)，我们给出了两个伪多项式时间算法和一个(1+ε)-近似算法。对于其它三种情形，我们分别给出了伪多项式时间算法。 第三章研究了工件带退化和拒绝的两代理单机排序问题。给定两个竞争关系的代理A和代理B，每个代理有一批T件需要在机器上加工，每个工件JXj的实际加工时间是其开工时间的线性增函数，目pXj=bXj(a+bt)，X∈{A B}，工件可以被拒绝。目标是在代理B的接受工件对应曰标函数fB与拒绝B-工件的总拒绝费用之和不超过一给定上界的情况下，极小化代理A的接受工件的总完工时间与拒绝A-工件的总拒绝费用之和，其中fB∈{CBmax，∑JBj∈ABCBj｝。对于这两种情形，我们分别基于动态规划的思想给出了算法和(1+ε)-近似算法。 第四章研究了工件带退化和拒绝的分批排序问题。给定n个工件需要在一台无容量约束平行批处理机上加工，每个工件的实际加工时间是其开工时间的线性增函数，即pj=bjt，工件可以被拒绝。我们主要研究了下面的五种情形:(1)在拒绝工件的总拒绝费用不超过一给定上界的情况下，极小化接受工件的最大完工时间;(2)在接受工件的最大完工时间不超过一给定上界的情况下，极小化拒绝工件的总拒绝费用;(3)在拒绝工件的总拒绝费用不超过一给定卜界的情况下，极小化接受工件的总完工时间:(4)在接受工件的总完工时间不超过一给定上界的情况下，极小化拒绝工件的总拒绝费用:(5)在拒绝工件的总拒绝费用不超过一给定上界的情况下，极小化接受工件的最大延误。对于前两种情形，我们假设工件具有不同的到达时间;而对于后面三种情形，所有工件同时在t0时刻到达。我们证明了所有的情形都是NP-困难的，并且对于前四种情形，分别给出了动态规划算法和完全多项式时间近似方案（FPTAS）。 第五章研究了带有人员不可用区间的两台机器流水作业排序问题。给定n个工件需要在两台机器上加工，每个工件Jj包含两道工序O1j，和O2j，加工时间分别为aj和bj，J=1.2，…,n。每个工件的工序相同，只有当第一道工序加工完成后，第二道工序才可以在第二台机器上加工。目标是极小化工件的最大完工时间，其中在第一道工序加工过程中存在一个人员不可用区间(s，s+L)，每道工序既不能在该区间内开工，也不能在该区间内完工。我们首先证明了，即使人员不可用区间的长度小于任意一个工件的第一道工序的加工时间，即aj＞L，j=1，2,…n，该问题仍是NP-困难的。然后我们证明了Johnson算法的最坏情形下的性能比是2并且界是紧的。最后我们给出了一个3/2-近似算法。 第六章研究了工件可拒绝的供应链排序问题。给定n个工件和m台平行机，每个工件可以被拒绝并支付一定的拒绝费用，或者被接受并安排在m台平行机中的一台上加工，工件加工完成后需要分批配送给客户。不考虑配送时间，每批的配送费用是f，目标是极小化接受工件的最大完工时间与拒绝工件的总拒绝费用以及接受工件的总配送费用的加权和。我们首先指出了历史文献中存在的错误，然后给出了一个2-近似算法。 收起