Abstract:

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.

Key words: parallel-batching scheduling, drop-line jobs, total completion time