A cutting plane approach for the multi-machine precedence-constrained scheduling problem

Prahalad Venkateshan (), Joseph Szmerekovsky () and George Vairaktarakis ()
Additional contact information
Prahalad Venkateshan: Indian Institute of Management
Joseph Szmerekovsky: North Dakota State University
George Vairaktarakis: Case Western Reserve University

Annals of Operations Research, 2020, vol. 285, issue 1, No 11, 247-271

Abstract: Abstract A cutting-plane approach is developed for the problem of optimally scheduling jobs with arbitrary precedence constraints on unrelated parallel machines to minimize weighted completion time. While the single machine version of this problem has attracted much research efforts, enabling solving problems with up to 100 jobs, not much has been done on the multiple machines case. A novel mixed-integer programming model is presented for the problem with multiple machines. For this model, many classes of valid inequalities that cut off fractional linear programming solutions are developed. This leads to an increase of the linear programming lower bound from 89.3 to 94.6% of the corresponding optimal solution, and a substantial reduction in the computational time of an optimal branch-and-bound algorithm for this problem. This enables us to report optimal solutions for problem instances with up to 25 jobs and 5 machines, which is more than twice the size of problems for which optimal solutions have been reported in the literature thus far. For a special case of the problem—that of minimizing makespan—application of our model helps solve 18 of 27 previously unsolved problem instances to optimality.

Keywords: Unrelated machine scheduling; Precedence-constrained scheduling; Optimization; Integer programming; Valid inequalities (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-019-03212-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:285:y:2020:i:1:d:10.1007_s10479-019-03212-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-019-03212-3

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().