The complexity of one-machine batching problems

Batching problems are combinations of sequencing and partitioning problems. For each job sequence JS there is a partition of JS into batches with optimal value opt(JS) and one has to find a job sequence which minimizes this optimal value. We show that in many situations opt(JS) is the solution of a shortest path problem in some network. An algorithm solving this special shortest path problem in linear time with respect to the number of vertices is presented. Using this algorithm some new batching results are derived. Furthermore, it is shown that most of the batching problems which are known to be polynomially solvable turn into NP-hard problems when modified slightly.