An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems

DOI10.1287/ijoc.2018.0854zbMath1451.90068OpenAlexW2958544563WikidataQ127469907 ScholiaQ127469907MaRDI QIDQ5139849

Artur Alves Pessoa, Daniel Oliveira

Publication date: 11 December 2020

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/de8e9c184d38d0ebfc639e12a648e70b16789101

zbMATH Keywords

integer programmingcolumn generationparallel machine schedulingbranch-cut-and-pricetime-indexed formulations

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35)

Related Items (3)

Patient scheduling with deteriorating treatment duration and maintenance activity ⋮ Unrelated parallel machine scheduling problem with special controllable processing times and setups ⋮ On the exact solution of a large class of parallel machine scheduling problems

Cites Work

• An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
• Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems
• On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems
• A time indexed formulation of non-preemptive single machine scheduling problems
• A survey of algorithms for the single machine total weighted tardiness scheduling problem
• A dynamic programming method for single machine scheduling
• A polyhedral approach to single-machine scheduling problems.
• An exact algorithm for single-machine scheduling without machine idle time
• A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling
• A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem
• A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
• Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
• Time-Indexed Formulations for Machine Scheduling Problems: Column Generation

This page was built for publication: An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems