排序论中工件和机器的对偶性

提出排序问题中工件和机器的对等性,定义排序问题的对等排序,列举单台机器排序问题和多台机器自由作业排序问题的对等排序;在此基础上,把工件和机器看成是对偶的双方,研究这两者的对偶性,进而提出排序问题的对偶排序;研究排序问题与其对偶排序之间的关系——对偶关系,可能是排序论研究的新方向.     

排序博弈的分类、进展和展望

排序博弈是排序论与博弈论的交叉,是从优化的角度分析排序论中的博弈问题,也是从博弈的观点研究排序问题。排序博弈分为工件排序博弈和机器排序博弈两类,这两类又可以分别考虑合作的和非合作的情况,从而包括了多代理竞争排序在内的目前已经出现的种种排序博弈问题。研究工件排序博弈和机器排序博弈这两类排序博弈的对偶关系,是本文在理论上提出的新课题。排序博弈具有重要的理论意义和广阔的应用前景,势必会吸引更多的研究者,得到更大的发展。
     

排序博弈的分类、进展和展望

排序博弈是排序论与博弈论的交叉,是从优化的角度分析排序论中的博弈问题,也是从博弈的观点研究排序问题。排序博弈分为工件排序博弈和机器排序博弈两类,这两类又可以分别考虑合作的和非合作的情况,从而包括了多代理竞争排序在内的目前已经出现的种种排序博弈问题。研究工件排序博弈和机器排序博弈这两类排序博弈的对偶关系,是本文在理论上提出的新课题。排序博弈具有重要的理论意义和广阔的应用前景,势必会吸引更多的研究者,得到更大的发展。     

单台机器排序问题中工件的预排序

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.     

以总加权完工时间为目标的两台机越库排序的动态规划算法

提出并研究两台机器环境下的以带权总完工时间为目标函数的越库配送排序问题.越库作业的入库与出库车辆被看作是排序问题中的机器,入库货物与客户需求为具有前序集限制关系的被加工工件.研究了该问题的计算复杂性及其最优解的若干性质,提出求解该问题的逆向动态规划算法,并给出了动态规划算法的数值实验.结果表明,所提出算法至少可以求解25个工件规模的越库配送排序问题.     

最优NOP交货期决策和排序

考虑ｎ个独立工件单机作业排序，每个工件设置ＮＯＰ交货期．目标是确定ＮＯＰ交货期的最优工序数乘子和工件的最优排序，使得由交货期、提前及延误构成的费用函数最小．先提出这个问题的线性规划模型，然后通过线性规划的对偶问题推导出最优工序数子及工件的最优排序．     

最优公共交货期决策与排序

考虑ｎ个独立工件单机作业排序，每个工件设置ＣＯＮ交货期（ｃｏｎｓｔａｎｔｄｕｅ－ｄａｅ）目标是确定ＣＯＮ交货期的最优值和工件的最优排序，使工件的滞后总值最小。提出了这个问题的线性规则模型，然后利用线性规划对偶问题推导出ＣＯＮ交货期的最优值和最优排序。     

一类多机排序问题算法及其计算复杂性研究

在经典排序论中，一般都假设每个工件在任一时刻仅被一台机器加工，且每台机器至多仅加工一个工件。在这篇文章中，研究这样一类排序问题：每个工件可以被多个不同的机器子集加工，其加工速度对于不同的机器子集是不同的，被加工的工件假定是可以间断且是独立的。排序问题的性能测度是排序长度。在以上条件下求解这类问题算法被给出，对其计算复杂性也作了研究。     

单机上考虑运输的退化工件的在线排序问题

研究了单台机器上工件具有可退化效应并考虑工件运输的在线排序问题.工件按时间在线到达.这些工件先在机器上加工,完工的工件再由一台运输车辆将其运送给顾客.排序问题的目标是最小化最大运输完工时间.对于所讨论的排序模型,给出了问题的下界并给出达到下界的最好可能的在线算法.     

带有退化维护和退化工件的单机排序问题

对带有维护活动和工件退化的单机排序问题进行研究。机器需要在某一个时间段内进行维护以提高其加工速度,且在这段时间内机器不能加工任何工件。机器维护后恢复到初始状态,工件的退化效应重新开始,其中机器的维护时间是维护开始时间的线性非减函数,工件的实际加工时间是与其特定位置有关的退化函数。目标是找到机器的最优维护位置、极小化时间表长。对于单机情形,给出了最优排序的一些性质。在特定条件下,证明了最优排序与工件排序无关,最优维护活动排在给定排序的中间位置。