This paper considers the following problem: n jobs need to be processed on two machines (M1, M2) successively. The deadline for job j is dj, and the processing times of job j on M1, M2 are aj,bj respectively. Both machines are batch processors. This means n jobs are grouped into several batches on Mi, 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 for 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 also be shifted in batches. We take the maximum lateness as our objective 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.
