Please use this identifier to cite or link to this item: http://hdl.handle.net/11718/23993
Full metadata record
DC FieldValueLanguage
dc.contributor.authorVenkateshan, Prahalad
dc.contributor.authorSzmerekovsky, Joseph
dc.contributor.authorVairaktarakis, George
dc.date.accessioned2021-06-02T04:12:03Z
dc.date.available2021-06-02T04:12:03Z
dc.date.issued2020
dc.identifier.citationVenkateshan, P., Szmerekovsky, J., & Vairaktarakis, G. (2020). A cutting plane approach for the multi-machine precedence-constrained scheduling problem. Annals of Operations Research, 285, 247-271. doi:https://doi.org/10.1007/ s10479-019-03212-3en_US
dc.identifier.issn02545330 (Print)
dc.identifier.issn15729338 (Online)
dc.identifier.urihttp://hdl.handle.net/11718/23993
dc.description.abstractA 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.en_US
dc.language.isoenen_US
dc.publisherSpringeren_US
dc.relation.ispartofAnnals of Operations Research
dc.subjectUnrelated machine schedulingen_US
dc.subjectPrecedence-constrained schedulingen_US
dc.subjectOptimizationen_US
dc.subjectInteger programmingen_US
dc.subjectValid inequalitiesen_US
dc.titleA cutting plane approach for the multi-machine precedence-constrained scheduling problemen_US
dc.typeArticleen_US
Appears in Collections:Journal Articles

Files in This Item:
There are no files associated with this item.


Items in IIMA Institutional Repository are protected by copyright, with all rights reserved, unless otherwise indicated.