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

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

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

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

两台同型平行机的复合半在线排序问题

研究了两台同型平行机的一个复合半在线排序问题.即对已知工件加工时间递减和实例最优值,目标为极大化机器最早完工时间的复合半在线排序模型,分析了它的下界,并给出了竞争比为9/8的最优算法.     

拒绝可缓冲的2台同类机半在线排序问题的近似算法

研究了2个拒绝可缓冲的同类机半在线排序问题. 设有2台同类机M1,M2,速度分别为1和s∈［1,+∞),加工不允许中断,工件Jj按照列表在线到达,每个工件带有2个参数：加工长度tj、拒绝罚值pj（模型1中）或拒绝获益pj（模型2中）,当工件到达时,可以被接受并分给某台机器加工,也可以被拒绝,需付出一定的罚值（模型1）或取得一定的收益（模型2）,目标是在第1个模型中要求极小化机器最大负荷和拒绝工件的总罚值之和;第2个模型中要求极大化机器最小负荷和总收益之和. 此外,在接受或拒绝的决策环节上提供一个缓冲区B,其容量为k≥1,任一时刻至多可以存放k个工件,当工件到达时,若缓冲区未饱和,则可暂时存入B;若已饱和,则必须在新工件和缓冲区内工件中选择一个进行接受或拒绝的决策. 本模型所研究的是经典可拒绝模型中的一个松弛问题,属半在线可拒绝模型.最后针对以上2个模型,分别给出了s在区间［1,+∞)上的近似算法,并证明了各自关于s的参数竞争比.     

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

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

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

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

可中断半在线排序问题

讨论两台同型机上的可中断半在线排序问题,目标函数为极大化最小的机器完工时间Cmin.首先考虑已知所有工件的加工时间在p和rp(p＞0,r≥1)之间的情形,对任意的参数r,设计了最优半在线算法.接着,对已知最大工件加工时间的情形作了研究,得到了一个竞争比为5/4的最优半在线算法.     

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

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

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

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

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

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

2台同型机排序博弈的均衡分析

对makespan机制下以机器覆盖为目标函数的2台同型机排序博弈进行了均衡分析,证明了混合纳什均衡的POA为2.     

预知两种信息的两台并行处理器半在线调度

在调度理论中,问题常常被分为"在线"和"离线"两类,但在实际生产生活中,情况经常介于两者之间,即预先知道任务的部分信息,人们希望通过这些附加的部分信息改进算法的性能,此类问题即为"半在线"问题.文章讨论了经典并行处理器调度的两个半在线问题,目标为极大化处理器最早完工时间.对已知所有任务总加工时间和最大任务加工时间的半在线问题,给出了竞争比为4/5的最优半在线算法;对已知所有任务总加工时间,并且任务按加工时间非增顺序到达的半在线问题,给出了竞争比为8/9的最优半在线算法.从结果可以看出,预知两种信息比只知道一种信息的情况能更有效地解决问题.     

带服务等级的同速机排序问题Multifit型算法研究

考虑一般情况下带服务等级的同速机排序问题.预先赋予每台机器和每个任务一个服务等级(grade ofservice)标号.每个任务只能被某台服务等级不高于该任务服务等级的机器加工.目标是最小化最大机器完工时间.这个问题最初由HWANG等提出并研究,HWANG等给出了一个最坏情况界为2-1m-1的算法.本文给出了求解这个问题的算法.并证明算法的最坏情况界不超过32+(1/2)k,其中k是算法中预先给定的迭代次数.     

具有服务等级的三台平行机排序问题

考虑带服务等级的三台平行机排序问题．预先赋予每台机器和每个任务一个服务等级（grade of service）标号．每个任务只能被某台服务等级不高于该任务服务等级的机器加工．目标是最小化最大机器完工时间.本文给出了求解这个问题的算法．并证明算法的最坏情况界不超过5/4＋（1/2）^k,其中k是算法中预先给定的迭代次数．已有的算法仅为3/2.