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

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

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

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

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

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

可中断半在线排序问题

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

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

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

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

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

带有多次速率改变行为的单机排序问题

研究机器带有多次速率改变行为的单机排序问题.机器可以通过不超过t个时段的中断来调整加工速度, 即每个工件在每次中断时段前后加工的加工时间可能不同.因此问题就需要决定是否中断,以及何时中断,使得最大完工时间、完工时间总和、加权完工时间总和等尽可能小.对任意固定的t,关于最大完工时间和完工时间总和目标分别给出了多项式时间最优算法,对满足正则假设的加权完工时间总和目标也给出了一个多项式时间最优算法.     

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

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

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

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

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

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

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

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

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

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

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

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

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

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

关于带时间约束的单机排序的一个注记

研究单机带时间B-约束的排序问题,即在任意单位时间区间[x,x+1）内至多允许加工B个工件,目标函数是极小化工件的最大完工时间.分析了B=2时最优排序的结构与性质,设计了O（n log n）时间的启发式算法.当工件数较少（≤ 6）时,证明了该算法的最优性.     

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

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

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

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