Abstract: This paper considers the following problem:n jobs need to be processed on two machines (M₁,M₂) successively. The deadline for job j is d_j, and the processing times of job j on M₁, M₂ are a_j, b_j, respectively. Both machines are batch processors. This means n jobs are grouped into several batches on M_i, i=1,2, respectively, and the machines process the jobs in same batch simultaneously. The processing time of a batch is equal to the longest processing time of all the jobs in this batch. Thus all the jobs in same batch are processed in the same length of time on the given machine, and the jobs will be also shifted in batches. We take the maximum lateness as our objec function for minimization. After pointing out that this scheduling problem is NP-hard, we give some special cases that can be solved in polynomial time and construct the corresponding dynamic programming.

Key words: scheduling, maximum lateness, polynomial time algorithm, batch processor, strong NP-hard