Flexible flow shop with dedicated buffers

Publication Type:
Journal Article
Discrete Applied Mathematics, 2019, 261 pp. 148 - 163
Issue Date:
Filename Description Size
Flexible flow shop with dedicated buffers.pdfPublished Version1.2 MB
Adobe PDF
Full metadata record
© 2018 Elsevier B.V. A two-stage flexible flow shop is considered, where first- and second-stage machines form disjoint pairs, each with a buffer. The buffer capacity varies from pair to pair, and the buffer requirement varies from job to job. Each job is to be assigned to a pair of machines for processing and uses the required amount of buffer from the start till the end of its processing. Operations have equal duration. It is shown that, unless P=NP, no polynomial-time algorithm guarantees a makespan less than 4∕3 of the optimal. The paper presents two integer linear programs, compared by means of computational experiments. Both approaches utilise as a subroutine the developed polynomial-time algorithm for the case of equal buffers.
Please use this identifier to cite or link to this item: