工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。     

混合交通随机用户平衡分配模型及算法

在考虑实际交通网络中交通流量往往由两种或两种以上的车种构成的条件下，研究了混合交通随机用户平衡分配问题，给出了等价的数学规划模型，证明了模型解的等价性与惟一性，设计了相应的求解算法，并用算例进行了计算分析．     

关于图论教学的一些有益尝试

图论是离散数学的一个重要分支,也是数学专业的一门选修课程.本文介绍了作者从事图论教学的一些有益尝试,探讨了在该课程的教学中如何激发学生的学习兴趣和积极性及培养学生解决实际问题的意识和建模能力,从而为学生今后走上工作岗位和继续深造打下坚实的基础.     

工件延误和可拒绝下的单机重新排序问题的近似方案

研究工件延误产生干扰且延误工件可拒绝下的单机重新排序问题。在该问题中,给定计划在零时刻到达的一个工件集需在一台机器上加工,工件集中的每个工件有它的加工时间和权重,在工件正式开始加工前,按照最短赋权加工时间优先的初始排序已经给定,目标函数是极小化赋权完工时间和,据此每个工件的承诺交付截止时间也给定。然而,在工件正式开始加工时,工件集中的部分工件由于延误不能按时到达,这对初始排序的执行产生了干扰,所以需要对初始排序进行调整,即重新排序。为了保证服务水平,允许对延误工件拒绝加工,但需支付相应的拒绝费用。调整后的重新排序的目标是在保证接受工件集中工件的最大延误不超过给定的上界的约束下,使得接受工件集的赋权完工时间和,拒绝工件集的拒绝费用和以及接受工件集中工件的最大延误的赋权惩罚费用之和达到极小。对该问题,设计了一个伪多项式时间动态规划精确算法,并利用稀疏技术得到了一个完全多项式时间近似方案。     

关于单机两个客户竞争排序问题1||∑w_j~Ac_j~A:f_(max)~B≤Q的一个注记

研究了单机两个客户竞争排序问题1‖∑w_j~Ac_j~A:f_(max)~B≤Q,证明了该问题与问题1|MA_i|∑w_jc_j及问题1|h_i,pmtn|∑w_jc_j之间是相互等价的.对w_j=p_j时的特殊情形,指出了问题1‖∑w_j~Ac_j~A:f_(max)~B≤Q存在近似比为2的最长处理时间优先算法(LPT)且该界是紧的,对w_j任意的一般情形,指出了问题1‖∑w_j~Ac_j~A:f_(max)~B≤Q存在近似比为4+ε的近似算法.当客户B的工件数是常数时,对问题1‖∑w_j~Ac_j~A:f_(max)~B≤Q则给出了伪多项式时间的动态规划算法.此外,指出了问题1‖∑w_j~Ac_j~A:∑w_j~Bc_j~B≤Q具有多项式时间近似方案(PTAS).