工件带运输时间的单机分批排序问题

Jobs Scheduling with Delivery Time on A Single Batch Machine

主要考虑了在线和离线两种模型下的工件带运输时间的单机分批排序问题,工件一但被加工完将会被马上运往目的地.我们考虑了三种限制模型:(1)在线模型:批量B无穷大,工件的加工时间和运输时间一致,即:若工件Ji的加工时间pi大于等于工件Jj的加工时间pj,那么它们的运输时间有qi≥qj.(2)在线模型:批量B无穷大,工件的最大运输时间和最小的运输时间的比小于等于1+5^(1/2)/2.对于(1),(2)这两种模型我们给出了一个竞争比为1+5^(1/2)/2的在线算法,并且这个结果是最好的.(3)离线模型:批量B有限,当工件的到达时间是整数并且加工时间p=1时,我们给出了一个时间复杂性为O(n2lnn)的多项式时间算法,当工件的加工时间不是1,但工件的到达时间的个数是一个常数m时,我们给出了一个时间复杂性为O(2m-1nlnn)的多项式时间算法.

A single batch machine sched.uling problems with job delivery times in both on-hne and offline models is consideled. Once the processing of a job is completed, we deliver it to the destination. The objective is to minimize the time by which all jobs have been delivered. We consider three restricted models ： （ 1 ） B is sufficiently large, jobs with agreeable times and delivery times, i.e. , for any two jobs Ji and Jj , Pi≥ Pj , implies qi ≥ qj （2）B is sufficiently large, qmax/qmin≤ 1＋√5/2 For these two problems, We provide an on-line algorithm with a competitive ratio 1＋√5/2 and the results are the best possible. （3） B is finite and jobs have the same processing time. When job arrival times are integers and the processing time p = 1, we present an off-line algorithm with running time O（ n2lnn ）. When the number of job arrival times is a constant m, we present an off-line algorithm with running time O（ 2^m-1nlnn ）.