A tabu search approach for group scheduling in buffer-constrained flow shop cells

The scheduling problem in a cellular manufacturing system (CMS) has been named as group scheduling in the literature. Due to the similarities in the processing route of the parts being in a group, it is mostly referred to as flow shop group scheduling. This problem consists of two interrelated sub-problems, namely intra-group scheduling and inter-group scheduling. On the other hand, mostly there are limited buffers between successive machines in which the work-in-process inventories can be stored. This article investigates the flow shop group scheduling with limited buffers to minimise the total completion time (makespan). Regarding the NP-hardness of this problem, two tabu search algorithms are proposed for solving each sub-problem. The effectiveness of the proposed algorithms is evaluated on 270 randomly generated problems classified under 27 categories. The results of the proposed algorithm are compared with those of the heuristic published by Solimanpur-Vrat-Shankar (SVS). Computational results demonstrate significant reduction in the average makespan over the SVS-algorithm.