Flowshop problems with intermediate buffers

In this paper the following extension of the classical flowshop problem is considered: Between each two consecutive machines a buffer of limited capacity is given. After finishing processing on a machine, a job either directly has to be processed on the following machine or it as to be stored in the buffer between these machines. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. The objective is to determine a feasible schedule minimizing the makespan. To model such a problem setting, a variation of the classical disjunctive graph model for shop problems is extended. A tabu search procedure where neighbourhoods are based on an extension of the classical block approach theorem is used. Computational results for extended flowshop benchmark instances are presented.