工件可自由下线最小化总完工时间的平行分批排序问题

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法.

The bounded parallel-batching scheduling with drop-line jobs to minimize total completion time

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 parallel-batching 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 J_j contained in batch B is defined to be S, and its completion time is defined as S+p_j, where p_j is the processing time of job J_j. 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(n^{b (b-1)}) time.