Column generation and rounding heuristics for minimizing the total weighted completion time on a single batching machine. (March 2022)

• Record Type: Journal Article
• Authors: Druetto, Alessandro; Grosso, Andrea
• Is Part Of: Computers & operations research. Volume 139(2022)
• Publication Date: 2022-03
• Subjects: Parallel batch scheduling -- Column generation -- Weighted completion time; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105639
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: This paper deals with the single-machine, parallel batching, total weighted completion time scheduling problem. A new graph-based formulation of the problem is proposed, where such graph has an exponential number of nodes and arcs. The problem is modeled as an integer linear program on this graph, combining features of a minimum cost flow problem and features of a set-partition problem as well. The continuous relaxation of this integer problem is solved via column generation, providing a very tight lower bound. Two different flavors of column generation are tested, leading to two models with identical performances in terms of bound tightness but in practice very different in terms of running time. A simple and effective rounding strategy applied to the faster model allows to generate heuristic solutions with values within a few percentage points from the optimum. Two different variants of the heuristic rounding procedure are tested; one allows to certify the optimality gap, while the other trades the ability to certify the gap with a greater computational speed. Highlights: A parallel batching problem handled via column generation. A very large linear program, not based on a time-indexed formulation, is used. A rounding heuristic is offered, with very good performances.