Polynomial-Size Models to Minimize Total Completion Time in a Parallel Batching Environment. Issue 10 (2022)

• Record Type: Journal Article
• Authors: Druetto, Alessandro; Grosso, Andrea
• Is Part Of: IFAC-PapersOnLine. Volume 55:Issue 10(2022)
• Page Start: 2173
• Page End: 2178
• Publication Date: 2022
• Subjects: Operations Research -- Scheduling Algorithms -- Parallel Batching -- Total Completion Time -- Arc-Flow Models; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2022.10.030
• Languages: English
• ISSNs: 2405-8963

Abstract

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.