Scheduling parallel-machine batch operations to maximize on-time delivery performance

In this paper we study the problem of minimizing total weighted tardiness, a proxy for maximizing on‐time delivery performance, on parallel nonidentical batch processing machines. We first formulate the (primal) problem as a nonlinear integer programming model. We then show that the primal problem can be solved exactly by solving a corresponding dual problem with a nonlinear relaxation. Since both the primal and the dual problems are NP‐hard, we use genetic algorithms, based on random keys and multiple choice encodings, to heuristically solve them. We find that the genetic algorithms consistently outperform a standard mathematical programming package in terms of solution quality and computation time. We also compare the smaller problem instances to a breadth‐first tree search algorithm that gives evidence of the quality of the solutions.