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

Daniel Oliveira () and Artur Pessoa ()
Additional contact information
Daniel Oliveira: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Artur Pessoa: Departamento de Engenharia de Produção, Universidade Federal Fluminense, 24210-240 Rio de Janeiro, Brazil

INFORMS Journal on Computing, 2020, vol. 32, issue 1, 90-100

Abstract: This work presents an improved branch-cut-and-price algorithm for the identical parallel machine scheduling problem minimizing a generic function of the job completion times. A new family of cuts is proposed to strengthen the arc-time-indexed formulation, along with an efficient separation algorithm. Also, the projection of the arc-time-indexed into a time-indexed formulation is introduced to take advantage of the variable fixings performed in the larger variable space. The improved algorithm was capable of solving 146 out of 150 instances in the literature, with 12 being solved for the first time. Also, the running time for the 134 previously solved instances decreased by 95.7% on the average.

Keywords: parallel machine scheduling; integer programming; column generation; branch-cut-and-price; time-indexed formulations (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0854 (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:32:y:2020:i:1:p:90-100

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 ().