A Flow-Based Formulation for Parallel Machine Scheduling Using Decision Diagrams

Daniel Kowalczyk (), Roel Leus (), Christopher Hojny () and Stefan Røpke ()
Additional contact information
Daniel Kowalczyk: Research Centre for Operations Research and Statistics, Faculty of Economics and Business, KU Leuven, 3000 Leuven, Belgium
Roel Leus: Research Centre for Operations Research and Statistics, Faculty of Economics and Business, KU Leuven, 3000 Leuven, Belgium
Christopher Hojny: Combinatorial Optimization Group, Department of Mathematics and Computer Science, Eindhoven University of Technology, 5612 AZ Eindhoven, The Netherlands
Stefan Røpke: Department of Technology, Management, and Economics, Technical University of Denmark, 2800 Kongens Lyngby, Denmark

INFORMS Journal on Computing, 2024, vol. 36, issue 6, 1696-1714

Abstract: We present a new flow-based formulation for identical parallel machine scheduling with a regular objective function and without idle time. The formulation is constructed with the help of a decision diagram that represents all job sequences that respect specific ordering rules. These rules rely on a partition of the planning horizon into, generally nonuniform, periods and do not exclude all optimal solutions, but they constrain solutions to adhere to a canonical form. The new formulation has numerous variables and constraints, and hence we apply a Dantzig-Wolfe decomposition to compute the linear programming relaxation in reasonable time; the resulting lower bound is stronger than the bound from the classical time-indexed formulation. We develop a branch-and-price framework that solves three instances from the literature for the first time. We compare the new formulation with the time-indexed and arc time–indexed formulation by means of a series of computational experiments.

Keywords: parallel machine scheduling; weighted tardiness; column generation; decision diagrams (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0301 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:6:p:1696-1714

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().