工件加工时间非增的并行分批排序问题的最优在线算法

An Optimal On-Line Algorithm for a Parallel-Batching Scheduling with Non-Increasing Processing Time Jobs

研究以最小化最大完工时间为目标、批容量有界的并行分批在线排序问题。相应排序模型中有n个相互独立的工件要在一台批处理机上加工,每个工件Jj(1≤j≤n)具有一到达时间rj和加工时间p_j,工件的加工时间非增,即对于任意2个工件Ji和Jj,如果r_i≤r_j,则p_i≥p_j。批处理机每次可同时加工至多B B<(n)个工件。同一批中的工件同时开工,同时完工,任一工件的信息(包括它的到达时间、加工时间)需等到它到达时系统才能获取,研究任务是设计一个在线算法对工件进行合理地分批和排序以使得最大完工时间达到最小。首先证明该在线排序问题不存在竞争比小于1+α(其中α~2+α=1)的在线算法,然后设计一在线算法,证明它的竞争比等于1+α,从而证明它的最优性。

In this paper a parallel-batching scheduling to minimize the maximum completion time is considered.There are njobs to be scheduled on a parallel-batching machine.The machine can handle up toBjobs as a batch simultaneously,and all the jobs in a batch start and complete at the same time.Once a batch is started,it cannot be stopped until its completion.Each job Jjhas a processing time pjand a release date rj.Each pair of two jobs Jiand Jjsatisfies that p_i≥p_jif r_i≤r_j.Each job becomes available at its release date.The information of a job,including its release date and its processing time,is unknown until its arrival.The problem involves assigning all the jobs to batches and determining the sequence of batches so as to minimize the makespan（the maximum completion of the jobs）.In this paper an optimal on-line algorithms for the problem is designed.