可能产生中断且考虑运输的两台平行机排序问题

讨论两台平行机排序问题,有一台机器在某一个特定时刻可能产生中断,中断持续时间长短满足相应的概率,且工件转移到另一台机器上加工需要考虑运输时间．证明该问题是NP-困难的,设计一个复杂性为O（n^3（TP）^1）的动态规划算法,调整机器原有的工件排序,使得目标函数为带权重的总完工时间期望值最小．其中,n是工件的个数,TP是所有工件的加工时间之和,     

带有到达时间和拒绝费用工件的同类机排序问题

研究了工件带有拒绝费用的m台同类机在线排序问题,m台机器的速度分别为s₁=s₂=…=s_m-1=1,s_m=s,当工件到达时,可以接收加工,占用一定的加工时间,也可以拒绝,付出相应的罚值. 目标是被接收工件的最长完工时间（makespan）与被拒绝工件的总罚值之和最小. 对工件2次到达时间问题（零时刻和r时刻各到达一批工件）设计了在线算法H,并证明该算法的竞争比为4-（2s）/（s+m-1）.     

工序问题的动态规划算法

提出了一个求解工序问题的动态规划算法,该算法排序含n个工件集合的期望时间为O(n)。     

具有服务等级的可拒绝平行机排序问题

研究了将服务等级与拒绝费用2种模型复合起来的平行机排序问题.设有2台平行机M₁,M₂,加工速度相同;n个工件J₁,J₂,…,J_n分别按列表在线到达,每个工件J_j含有3个参数：加工长度t_j、拒绝费用p_j以及服务等级g_j=1,2.当工件到达时,可以接收加工,占用一定的加工时间;亦可拒绝,付出相应的罚值.目标为被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.进一步,当且仅当g（M_i）≤g_j时,工件J_j可以分配给机器M_i加工,即机器M₁可以加工所有工件,机器M₂只能加工等级为g_j=2的工件,允许中断加工.设计了在线算法PH,并证明其竞争比为1+(√2)/(2)≈1.707,下界为1.618,上下界差约为0.089.     

自由作业下的一类物流排序

研究了一个两阶段物流排序问题,即第一阶段工件在自由作业机器上加工,第二阶段这些被加工过的工件以某种运输方式分批运送到预先指定的目的地.目标是极小化工件带权送到时间与运输费用总和.将动态规划与组合优化方法结合,在假设工件加工时间与权满足"一致性"条件下,利用动态规划算法,构造了性能比不超过2 m的多项式时间近似算法;对于一般情形,用传统排序问题的算法构造了多项式时间近似算法,并分析算法性能比.     

lp范数下两台同型机半在线问题的最优算法

研究了lp（p〉1）下的两台平行同型机的半在线排序问题．对于分别已知即将到来的工件队列的最大工件尺寸，工件总加工时间分别对应的P2｜max｜lp，P2｜sum｜lp两类问题，提出了最优的半在线算法．     

已知工件最大加工时间的平行机排序问题

研究了已知工件最大加工时间，目标为极小化最大机器负载的半在线平行机排序问题．证明了对于一般的m（〉6）台机器，任意的半在线算法的竞争比至少是（√33＋3）／6．同时还设计了一个半在线算法，算法的竞争比为2-1／（m-1）．     

工件可预处理的单台机排序问题

考虑一个工件可预处理的单机排序问题．要求在所有工件能够按时完工的前提下,使得预处理工件的费用最小,证明了对于一般情况,该问题是NP-难的,并给出了动态规划算法．进一步,得到当每个工件的预处理费用都相同时该问题是多项式可解的,并给出了强多项式时间算法．     

加工时间成比例的两阶段自由作业排序问题

对一类工件加工时间成比例的两阶段自由作业排序问题进行了研究.工件需要分别在包含m1和m2台平行机的两阶段中进行加工,工件在阶段间的加工满足自由作业环境要求,且相同工件在两阶段的加工时间相同,目标是极小化时间表长,即最后完工工件的完工时间.证明了当min{m1,m2}≥2时该问题是NP-难的,给出了该问题的一个近似算法,并证明了该算法的最坏情况界不大于3/2-3/2(2min{m1,m2}+1).得到了当min{m1,m2}=1时,该算法为问题的最优算法.     

一个带退化工件的单机准时生产制问题

研究带退化工件的单机排序问题,即工件的加工时间是其开始加工时间的线性递增函数,且不同的工件具有不同的退化率.要求为所有工件寻找一共同的最优交货期和最优序,以极小化这些工件的共同交货期、超前罚和迟后罚之和.给出了一O(nlogn)时间的最优算法.     

带机器准备时间的已知工件总加工时间半在线问题

考虑带机器准备时间的已知工件总加工时间半在线问题。首先考虑P2,ri|sum|Cmin问题,给出Prsum算法并证明此算法的竞争比为23,且是最优算法;然后考虑Q2,ri|sum|Cmax问题,给出Qrsum算法并证明此算法的竞争比为2,同时给出此问题的一个下界1+3～(1/2)/2。显然Qrsum算法的竞争比与最     

A short note on the approximability of the single machine scheduling problem to minimize makespan with fixed jobs and precedence constraints

研究关于有固定工件序约束的单机最小化最大流程排序问题模型.在该模型中,有些固定工件已事先安排好,其余的自由工件之间的加工顺序满足给定的序约束.工件之间不允许抢先中断,在同一时间,机器最多只能加工一个工件.其目标是使得最大流程达到最小.该问题即使是对没有序约束的特殊情形也已被证明是NP-困难的.给出了该问题的一个线性时间的2-近似算法,并且证明了除非P=NP,对任意的δ>0,该问题甚至没有拟多项式时间的(2-δ)-近似算法.     

二次表示满足□(x)=B(x)+C的超曲面

设x:M~n→E~(n+1)为欧氏空间E~(n+1)的浸入超曲面,(x)=xx~t(t表示转置)为超曲面M~n的二次表示,□是平均曲率的线性算子.本文研究欧氏空间中二次表示满足□(x)=B(x)+C的超曲面,其中B和C是n+1阶常方阵.给出了一些分类结果.     

可分凸二次规划的不可行内点算法

给出了可分凸二次规划的不可行内点算法 ,并证明了该算法在 O(n2 L )次迭代之后 ,或者收敛到问题的一个近似最优解 ,或者说明该问题在某个较大区域内无最优解 .     

粗糙核分数次积分算子的多线性算子估计

证明带有粗糙核分数次积分算子的多线性算子TΩa^A,B（f）（x）=∫R^n P2（A;x,y）P2（B;x,y）/｜x-y｜^n-a＋2 Ω（x-y）f（y）dy的（H^1（R^n）,L^n/（n-a）∞（R^n））有界性,其中0〈a〈n,S^n-1表示R^n上的单位球面,Ω∈L^s（S^n-1）（S≥1）,且Ω是R^n上的零次齐次函数,A和B是R^n上函数,且P2（A;x,y）,P2（B;x,y）是A和B分别在X点关于Y的二阶Taylor展式的余项,即P2（A;x,y）=A（x）-A（y）-△A（y）（x-y）,P2（B;x,y）=B（x）-B（y）-△B（y）（x-y）,这里△A,△B∈BMO（R^n）.     

多处理机系统上不相容作业集的分配问题

讨论了多处理机系统MPs(Multi Processor Syscem)上不相容作业集的分配算法,以及对该算法正确性和效率的分析和证明,给出了该算法的若干推论．