type Ⅱ双删失数据场合Burr Ⅻ分布参数贝叶斯估计的近似计算

在type Ⅱ双删失数据场合.讨论了双参数Burr Ⅻ分布参数在各种损失函数下贝叶斯估计的一种近似算法,最后给出数值例子.     

求解非减上模集函数最小值问题的近似算法及其性能保证

上模集函数的优化问题在组合优化问题中有广泛应用,许多组合优化问题,如设备选址问题、p-中心问题等都可化为上模集函数的优化问题.本文给出了求解非减上模集函数最小值问题的一种近似算法,并讨论了所给算法的性能保证.     

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

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

并行分批排序综述

并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。     

单台机以总完工时间为目标的批排序问题

研究单台机,工件加工时间相等,大小不同的批排序问题,给出了一个最坏情况界为9+3~(1/2)/6≈1.7817的多项式时间近似算法,并证明了即使工件总大小不超过2,该问题也不存在FPTAS,除非P=NP.     

一类广义分式规划问题的ε-近似算法

本文针对一类广义分式规划问题提出一种求其全局最优解的ε-近似算法,并从理论上证明该算法的收敛性和计算复杂性,数值结果表明算法是有效可行的.     

一类分式规划问题的ε-近似算法

本文针对一类复杂的分式规划问题,提出一种全局最优ε-近似解算法,并从理论上证明该算法的收敛性和计算复杂性,数值结果表明本文算法有效可行.     

SEMI-DEFINITE RELAXATION ALGORITHM FOR SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES

The authors present a semi-definite relaxation algorithm for the scheduling problem with controllable times on a single machine. Their approach shows how to relate this problem with the maximum vertex-cover problem with kernel constraints (MKVC). The established relationship enables to transfer the approximate solutions of MKVC into the approximate solutions for the scheduling problem. Then, they show how to obtain an integer approximate solution for MKVC based on the semi-definite relaxation and randomized rounding technique.     

指数跟踪问题的广义双线性规划模型

本文对指数跟踪问题建立了一种广义的双线性规划模型,其中考虑了交易费用、持仓限制与重平衡问题.根据该模型的特殊结构,本文给出了近似规划算法,通过逐次逼近的线性规划求解最优指数跟踪问题.     

关于图划分问题的改进的近似算法

本文考虑NP-难的极大图划分(MAX-GP)问题.我们给出应用半定规划(SDP) 松弛的一个一般方法,并且给出包括极大方向割,稠密子图,极大顶点覆盖,极大割,和极大反割在内的图划分问题的改进的近似比.