Polynomial-Size Models to Minimize Total Completion Time in a Parallel Batching Environment. Issue 10 (2022) - Druetto, Alessandro; Grosso, Andrea
Abstract: We present a new integer linear formulation for the problem of minimizing the total completion time on a single parallel-batching machine. The new formulation is strong, in the sense that it delivers a sharp lower bound, and compact, i.e. polynomial in size, contrasted to recent successful models for the same problem that have exponential size and require to be handled by column generation. The new model is promising: combined with a rounding procedure, it allows to deliver good solutions with small, certified optimality gaps for instances with up to 50 jobs, and we believe it is susceptible of further improvements.