旅行商问题的一些特殊情况和启发式算法

本文讨论了一些带有和式目标及瓶颈目标的可以有效求解的特殊类型的旅行商问题,并提出了有关由这种特殊问题导出启发式算法的可能性。     

分支定界法求解最小带权误工工件数排序

设有n个工件J_1,J_2,…,J_n要在一台机器上加工。已知工件J_i的工时(加工时间)是Pi,工期(预定交付期限)是d_i,权(工件误工时,即在工期之后完工所造成的损失)是w_i.记s=(s(1),…,s(n))为1,2,…,n的一个排列(置换),并记S为1,2,…,n所有排列的全体。如何在S中寻找一个排列s,使在按照次序J_(s(1)),J_(s(2))…,J_(s(n))进行加     

关于Lemaréchal高阶算法的研究——概念性算法

对于非光滑的极小化问题,C.Lemaréchel在[1]中对凸函数的无约束极小化问题提示了一个高阶σ-牛顿型算法的思想,并讨论了某些性质。本文对[1]的高阶σ-牛顿型算法作了进一步研究,并提出一个概念性算法,证明了算法的全局收敛性。     

最后完工机器至多两个空闲的自由作业稠密时间表(英文)

对于自由作业问题,在安排工件时避免不必要空闲所得的时间表称为稠密时间表.稠密时间表的加工总长不超过最优值的2-1/m倍,是一个在机器数m6时尚未被证明的猜想.本文通过引入工件与机器特征函数及机器关于工件非间断等概念,研究当最后完工机器至多有两个空闲区间时,性能比猜想成立的充分条件.     

关于不可微凸函数的高阶算法

在文[1]中,Lemarechal et提出了关于不可微凸函数的高阶算法概念,其主要思想为σ-牛顿方向。 本文进一步讨论了σ-牛顿方向的性质,并给出了一个可实现的算法,这一算法在α-锐角条件下是全局收敛的。