Generation of low-dimensional capacity constraints for parallel machines

Phillip O. Kriett and Martin Grunow

IISE Transactions, 2017, vol. 49, issue 12, 1189-1205

Abstract: A crucial input to production planning is a capacity model that accurately describes the amount of work that parallel machines can complete per planning period. This article proposes a procedure that generates the irredundant set of low-dimensional, linear capacity constraints for unrelated parallel machines. Low-dimensional means that the constraints contain one decision variable per product type, modeling the total production quantity across all machines. The constraint generation procedure includes the Minkowski addition and the facet enumeration of convex polytopes. We discuss state-of-the-art algorithms and demonstrate their effectiveness in experiments with data from semiconductor manufacturing. Since the computational complexity of the procedure is critical, we show how uniformity among machines and products can be used to reduce the problem size. Further, we propose a heuristic based on graph partitioning that trades constraint accuracy against computation time. A full-factorial experiment with randomly generated problem instances shows that the heuristic provides more accurate capacity constraints than alternative low-dimensional capacity models.

Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2017.1364875 (text/html)
Access to full text is restricted to subscribers.

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:taf:uiiexx:v:49:y:2017:i:12:p:1189-1205

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2017.1364875

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().