Unbounded parallel-batch scheduling with drop-line tasks

In this paper, we study unbounded parallel-batch scheduling with drop-line tasks to minimize a regular objective function, where by “drop-line tasks” we mean that the completion time of each task (job) is equal to the sum of the starting time of the batch containing the task and the processing time of the task. In the problems considered in this paper, we assume that the tasks have individual release dates and the general regular objective function to be minimized is either of the sum-form or of the max-form. We then study the computational complexity of these problems on an unbounded parallel-batch processor. We show that (i) the problems are binary NP-hard and are solvable in pseudo-polynomial times, and (ii) when the number of processing times or release dates is a constant, the problems are solvable in polynomial times. We also point out some consequences of approximation algorithms.