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

摘要：研究了工件带有拒绝费用的m台平行机在线算法,假定有m台平行机M_1,M_2,…,M_m,n个工件J_1,J_2,…,J_n,每个工件的加工时间与拒绝费用成固定的比例α(α≥0),即p_j=αt_j,当α较大时,即工件的拒绝费用相对于加工时间较大,则将此工件接收加工;当α较小时,即每个工件的拒绝费用相对于其加工时间较小,此时将工件拒绝。文中设计出在线算法PRLS,并证明算法的竞争比为关于参数α的分段函数,且为紧界。

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

摘要：本文我们考虑了无关机上的平行分批排序问题.对于批容量无限的平行批排序模型,目标是极小化总完工时间,我们对p_(ij)≤p_(ik)(i=1,…,m;1≤j≠k≤n)这种一致性的情况设计了多项式的动态规划算法.对于批容量有限的平行批排序模型,我们讨论了p_(ij)=p_i(i=1,…,m;j=1,…,n)这种情况,当不考虑工件可被拒绝时,对极小化加权总完工时间的排序,我们给出了其最优算法;当考虑工件可被拒绝时,对极小化被接收工件的加权总完工时间加上被拒绝工件的总拒绝费用的排序,我们设计了一拟多项时间算法.

摘要：研究了工件带有拒绝费用的3台平行机半在线算法。工件逐个到达,当工件到达时可以被接收加工,消耗一定的加工时间,也可以被拒绝,但此时要付出一定的拒绝费用。进一步假定工件的加工时间与拒绝费用事先成固定比例α(α≥0)。目标为被接收工件的最大完工时间与被拒绝工件的总罚值之和最小。针对工件加工可中断情形,设计出半在线算法ARH,并证明算法ARH的竞争比为关于参数α的分段函数,且为紧界。

摘要：研究了工件带有拒绝费用的两台同类机在线算法,两台机器的速度分别为1和s,s∈[1,+∞),工件逐个到达,当工件到达时,可以选择被分配到机器上进行加工并花费一定的加工时间;也可以被拒绝,但此时需付出一定的拒绝费用。进一步假定每个工件的加工时间与拒绝费用成固定比例α(α≥0),即p_j=αt_j。目标函数为使被加工工件的最大完工时间与被拒绝工件的总罚值之和最小,工件的加工不可中断。本研究设计一种在线算法URLS,并证明该算法的竞争比和下界均为关于参数α的分段函数,且当α∈[0,(s+1)^(1/2)/s+1)∪[1,+∞)时上下界相吻合,算法达到最优。

摘要：研究了工件具有服务等级且可拒绝的平行机排序问题.设有两台平行机,加工速度相同;n个工件分别按列表在线到达,每个工件含有三个参数:加工长度,拒绝费用以及服务等级g_j=1,2.当且仅当g(Mi)≤gj时,工件J_j可由机器M_i加工,且加工不允许中断.进一步,当工件到达时,可以选择被加工,花费一定的加工时间;也可以被拒绝,此时要付出相应的罚值.目标为使被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.文中设计出在线算法H,并证明算法的竞争比为1+(2^(1/2)/2)≈1.707,下界为5/3≈1.667,上下界大约相差0.04.

摘要：研究了工件带有拒绝费用的3台平行机在线算法,假定有3台平行机M_1,M_2,M_3,n个工件J_1,J_2,…,J_n,每个工件可以被接收加工,消耗一定的加工时间tj;也可以被拒绝,但要付出相应的拒绝费用pj,目标为被接收工件的最大完工时间(makespan)与被拒绝工件的总罚值之和最小。进一步,假定每个工件有两套拒绝策略,最后输出目标值较好的一种。文中设计出在线算法H,并证明算法的竞争比为15/8。

摘要：研究了工件带有拒绝费用的三台同类机在线算法:假定有三台同类机,速度分别为s_1=s_2=1,s_3=s(s≥1).n个工件J_1,J_2,…,J_n,每个工件的加工时间与拒绝费用成固定的比例α(α≥0),即p_j=αt_j.当α较大时,即工件的拒绝费用相对于加工时间较大,则将此工件接收加工;当α较小时,即每个工件的拒绝费用相对于其加工时间较小,此时将工件拒绝.目标函数为使被加工工件的最大完工时间与被拒绝工件的总罚值之和最小.工件的加工不可中断.设计了在线算法URL,并证明算法的竞争比为关于参数α的分段函数,且为紧界.