Column generation bounds on a network flow model to minimize the total weighted completion time for a single parallel batching machine

This work deals with the single-machine scheduling problem of minimizing the total weighted completion time in a parallel-batching environment. A very large, graph-based linear programming model is proposed in order to solve a tight relaxation of such problem by means of column generation and dynamic programming techniques. Both a path-based variant and an arc-based variant of the model are developed, in order to obtain two lower bounds of equally good quality. These outclasses the previously known state-of-the-art lower bound. Using the most time efficient of the two variants, the arc-based lower bound, two simple and effective rounding strategies are built, exploiting the information gathered from the relaxation. Combining the strict lower bounds and the effective heuristics allows to generate good feasible solutions with values within a few percentage points from the optimum.