Flexible flow shop with dedicated buffers

摘要

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. (C) 2018 Elsevier B.V. All rights reserved.