Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times

We consider the single machine parallel-batching scheduling problem with precedence relations, release dates and identical processing times to minimize a regular objective function. When the processing times are unit, we give an O(n²) time optimal algorithm. When there are no precedence relations, we solve this problem by dynamic programming in O(n³) time. When the precedence relations are “layerly complete”, we solve this problem by a dynamic programming algorithm that runs in O(n⁷) time. For the total weighted completion time minimization problem, we give an O(n²) time 3/2-approximation algorithm. For the makespan minimization problem, we give an O(n²) time optimal algorithm and an expression of the minimum makespan.