In this paper we consider the problem of scheduling jobs with release dates on parallel unbounded batch processing machines to minimize the maximum lateness. We show that the case where the jobs have deadlines is strongly NP-hard. We develop a polynomial-time approximation scheme for the problem to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint.
- Computational Complexity
- Parallel batch processing machines
- Release dates
ASJC Scopus subject areas
- Applied Mathematics
- Discrete Mathematics and Combinatorics