Abstract: We study the scheduling on an unbounded parallel-batch machine with jobs having set-up times to minimize a regular objective function which is either of the sumform or of the max-form. As we know, in the existing literature, the research about parallel-batch scheduling does not consider the set-up times of jobs. However, the set-up times of jobs are widely presented in practical applications. Each job considered in this paper has a set-up time. The set-up time of each batch is equal to the maximum set-up time of all jobs contained in the batch, and the processing time of each batch is equal to the longest processing time of the jobs contained in the batch. Depending on the different definitions of the completion time of a job, we consider two types of jobs: batch jobs and drop-line jobs. For batch jobs, the completion time of a job is given by the completion time of the batch containing this job. For drop-line jobs, the completion time of a job is given by the starting time of the batch containing this job plus the processing time of this job. In this paper, we give pseudo-polynomial time algorithms for the above scheduling problems in which the jobs have agreeable processing times and set-up times. In addition, when the objective functions are the total weighted completion time, the maximum lateness, and the maximum cost, we present a polynomial time algorithm, respectively. 

Key words: Scheduling, Parallel-batch, Set-up time, Agreeable, Algorithm