两台可拒绝同型机半在线排序问题

本文讨论一个两台可拒绝同型机半在线排序问题.当工件到达时,可以被拒绝,但要付出一定的罚值,也可以被接收加工,消耗一定的加工时间.其目标是要使所有加工工件生成的makespan和被拒绝工件的总罚值之和最小.加工不允许中断.进一步,机器带有两个并行处理子系统,可以提供两种排序方案,最后选取较好的一种.这是第一个在可拒绝同型机排序模型中使用半在线信息,我们设计出一个近似算法,其竞争比为3/2,另外又给出一个√3+1/2≈1.366的下界.     

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

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

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

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

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

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

带复合信息的三台平行机半在线排序问题

本文讨论在已知加工工件总长度(sum)以及机器带一个缓冲区(buffer)两个复合信息下的同型平行机半在线排序问题． Dosa和He研究了当机器数m=2时的情形,设计出竞争比为5／4的最优半在线算法．本文将其情况推广到三台机器,给出竞争比为4／3的半在线算法,并得到一个11／9的问题下界．     

两台带服务等级的可拒绝同型机排序问题的在线算法

两台同型机M_1,M_2,加工速度一致,但拥有不同的加工能力,用其服务等级表示,M_1的服务等级为1,M_2的服务等级为2.工件j按列表在线到达,每个工件带有三个参数:长度t_j,等级g_j=1或2,罚值p_j.当j到达时,可以被拒绝,但要付出相应的罚值p_j,也可以被接受并分配给服务等级不超过该工件等级的机器加工,事实上等级为1的工件只能分给M_1加工,等级为2的工件可以分给M_1或M_2加工,加工不允许中断.目标为极小化加工工件集的最晚完工时间(makespan)和拒绝工件集的总罚值之和.对于该问题给出了一个在线算法,其竞争比为11/6,以及问题一个下界5/3.     

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

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

两台可拒绝同类机在线排序问题近似算法的参数性能比

讨论两台可拒绝同类机在线排序问题的近似算法。设两台机器的速度之比为ｓ（≥１）。工件逐个到位,可以被加工,也可以被拒绝,但要付出相应的罚值ｐｊ。并且只有在安排完当前工件之后,下一个工件才到达。目标函数要求被加工工件集的最迟工件完工时间与被拒绝工件集的总罚值之和达到最小。文中设计出线性时间的ＲＬＳ（α）算法,并证明了其关于ｓ的参数紧界,这个界于ｓ＝１以及ｓ≥（５＋１）／２均是不可改进的。     

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

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

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

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