Scheduling a flow shop with combined buffer conditions

In this paper, four inter-machine buffer conditions (i.e. no-wait, no-buffer, limited-buffer and infinite-buffer) in a flow shop are investigated. These four different buffer conditions are combined to generate a more generalised and more comprehensive scheduling problem, which can cover the classical flow-shop scheduling (FSS) with unlimited buffer, the blocking FSS (BFSS) without buffer, the no-wait FSS (NWFSS) and the limited-buffer FSS (LBFSS) problems. By analysing the structural properties of these four buffer conditions, an innovative constructive algorithm called the Liu-Kozan algorithm is proposed to build the feasible combined-buffer flow-shop scheduling (CBFSS) solution. The proposed Liu-Kozan algorithm mainly comprises a time-determination procedure and a tune-up procedure with eight sets of formulae. Detailed numerical implementations have been analysed to indicate that the proposed Liu-Kozan algorithm is very generic because without modification it enables the construction of the feasible solutions for the FSS, BFSS, NWFSS, LBFSS and CBFSS problems. By employing the similar mechanism of the well-known NEH algorithm, a two-stage hybrid heuristic algorithm called the Liu-Kozan-BIH algorithm is developed to find a good CBFSS schedule in an efficient and economical way. Crown Copyright (C) 2008 Published by Elsevier B.V. All rights reserved.