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

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

两台可中断同类机可拒绝半在线排序问题的近似算法

研究一个两台同类机可拒绝半在线排序问题,机器速度一个为1,另一个为s∈[1,+∞),加工允许中断.当工件到达时,可以将其接受加工,占用一定的机器负荷,也可以将其拒绝,付出相应的罚值,目标为使被接受工件集产生的makespan和被拒绝工件集的总罚值之和最小.问题进一步假定每个工件在选择是否加工时有两个拒绝尺度,各自独立决策,最后选择较好的结果作为最终输出.笔者设计了算法H,得到其关于s的参数竞争比为s+2s+1,优于只有一个拒绝尺度的经典情形.最后又给出问题的一个下界(s+1)2s2+s+1,上下界的最大差距在s=1时达到0.167.     

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

研究了将服务等级与拒绝费用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范数下两台带缓冲区同型机半在线排序问题的最优算法

研究一个带缓冲区（buffer）的两台同型平行机半在线排序模型．设有两台同型平行机，带有一个缓冲区，工件逐个到达，每当一个工件到达时可以被立即分配到机器上进行加工，也可以暂时存储在缓冲区中，加工不允许中断．目标为使两台机器最终负荷的ι2范数最小．针对该模型只需缓）中区容量为1（在任一时刻至多存储1个工件），设计出一个最优半在线算法H，其竞争比为ρ≈1．076．     

l2范数下两台带缓冲区同型机半在线排序问题的最优算法

研究一个带缓冲区(buffer)的两台同型平行机半在线排序模型.设有两台同型平行机,带有一个缓冲区,工件逐个到达,每当一个工件到达时可以被立即分配到机器上进行加工,也可以暂时存储在缓冲区中,加工不允许中断.目标为使两台机器最终负荷的l2范数最小.针对该模型只需缓冲区容量为1(在任一时刻至多存储1个工件),设计出一个最优半在线算法H,其竞争比为ρ≈1.076.     

一个可中断两台可拒绝同型机半在线排序问题

讨论一个两台可拒绝同型机半在线排序问题的近似算法．设有两台同型机,工件逐个到达,可以被接收加工,消耗一定的加工时间tj,也可以被拒绝,但要付出一定的罚值Pj,目标是使被加工工件集的最大完工时间（makespan）和被拒绝工件集的罚值之和最小．此外,进一步假定每个工件的罚值和加工长度事先形成固定的比例α∈[0,＋∞）,即Pi=atj,针对工件加工可中断情形,设计出近似算法PRH,证明其竞争比．同时又给出该问题的下界,它们均为α的分段函数,且算法PRH在a∈[0,√2/2）∪[5/6＋∞）达到最优．     

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

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

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

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

带准备时间的两台同类机半在线排序的近似算法

研究带准备时间的两台同类机已知工件最大加工时间的半在线排序问题,分别讨论了极小化最大机器完工时间和极小化最大工件完工时间这两个目标函数,对这两个目标函数给出了竞争比为3/2的近似算法,并证明了不存在竞争比小于√2的近似算法     

带准备时间的两台同类机已知工件总加工时间的半在线排序问题的近似算法

主要研究带准备时间的两台同类机已知工件最大加工时间的半在线排序问题，目标函数极小化最大机器完工时间和极小化最大工件完工时间．对此问题给出了竞争比为√2的近似算法，并证明了不存在竞争比小于1＋√3/2的近似算法．