摘要：
考虑工件可自由下线最小化总完工时间的有界平行分批排序问题.在该问题中,一台平行批机器可以同时处理b个工件作为一个平行批,这里b是批容量,一个批的加工时间等于分配给这个批的工件的最大加工时间.关于可自由下线工件,每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和.也就是,如果一个批B有一个开工时间S,那么包含在批B中的每一个工件Ji的开工时间定义为S,而它的完工时间定义为S+pj,这里pj是工件Jj的加工时间.对此问题,首先研究最优排序的一些性质.然后,基于这些性质,给出一个运行时间为O(nb(b=1))的动态规划算法.%In this paper,we consider the bounded parallel-batching scheduling problem with drop-line jobs to minimize the total completion time.In the problem,a parallelbatching machine can handle up to b jobs simultaneously as a parallel batch,where b is the batch capacity,and the processing time of a batch is equal to the longest processing time of the jobs assigned to it.For drop-line jobs,the completion time of each job is equal to the sum of the starting time of the batch containing the job and the processing time of the job.That is,if a batch B has a starting time S,then the starting time of each job Jj contained in batch B is defined to be S,and its completion time is defined as S + pj,where pj is the processing time of job Jj.For our problem,we first study some properties of the optimal schedules.Then,based on these properties,we present a dynamic programming algorithm running in O(nb(b-1)) time.
