Scheduling one batch processor subject to job release dates

AbstractIn this paper, we consider the problem of scheduling jobs with release dates on a single-batch processor in order to minimize the makespan. This problem is proved to be NP-hard even for the case with two distinct release dates. Then a pseudopolynomial algorithm is presented for the case with a fixed number of release dates. Finally, a greedy heuristic for the general problem is shown to have the best-performance bound 2