An Improving Column Is All You Need: Enhancing Column Generation for Parallel Machine Scheduling via Transformers

We present a neural network-enhanced column generation approach (CG NN-DP) for a parallel machine scheduling problem. Our approach uses an encoder-decoder attention mechanism, specifically a transformer model with a pointer layer, to identify columns, that is, job processing sequences, with negative reduced costs to be added to the restricted master problem (RMP). Exact solution of a pricing subproblem using dynamic programming (DP) verifies that no further columns with negative reduced costs can be identified at termination, preserving the optimality guarantee. By training the pointer transformer model offline and using it in inference mode during column generation, CG NN-DP achieves significantly faster convergence than the traditional column generation (CG) procedure, which relies solely on solving the pricing subproblem via DP. Computational experiments demonstrate that CG NN-DP generalizes effectively beyond the maximum number of jobs used during training and performs well on out-of-distribution instances. We also compare CG NN-DP with a CG procedure using an efficient pricing heuristic (CG Heuristic-DP). For medium-sized instances, both methods yield improvements of 65%–90% over traditional CG, whereas CG NN-DP outperforms CG Heuristic-DP as the number of jobs increases. For large-scale and out-of-distribution instances, CG NN-DP converges more quickly and achieves lower relative RMP objective values, demonstrating both scalability and efficiency.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete.

Funding: This work was supported by the National Science Foundation [Grant CMMI-1826125].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.1005) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.1005). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. The online appendix is available at https://doi.org/10.1287/ijoc.2024.1005.