  We address the problem of scheduling jobs with non-identical sizes and
distinct processing times on a single batch processing machine, aiming at
minimizing the makespan. The extensive literature on this NP-hard problem
mostly focuses on heuristics. Using an arc flow-based optimization approach, we
construct an ingenious formulation that represents it as a problem of
determining flows in graphs. The size of the formulation increases with the
number of distinct sizes and processing times among the jobs, but it does not
increase with the number of jobs, which makes it very effective to solve large
instances to optimality, especially when multiple jobs have equal size and
processing time. We compare our model to other models from the literature
showing its clear superiority on benchmark instances, and proving optimality of
random instances with up to 100 million jobs.
