Parallel batch scheduling of equal-length jobs with release and due dates

In this paper we study parallel batch scheduling problems with bounded batch capacity and equal-length jobs in a single and parallel machine environment. It is shown that the feasibility problem 1∣p-batch,b<n,r j ,p j =p,C j ≤d j ∣- can be solved in O(n ²) time and that the problem of minimizing the maximum lateness can be solved in O(n ²logn) time. For the parallel machine problem P∣p-batch,b<n,r j ,p j =p,C j ≤d j ∣- an O(n ³logn)-time algorithm is provided, which can also be used to solve the problem of minimizing the maximum lateness in O(n ³log² n) time.