This study suggests a procedure for designing cellular manufacturing systems (CMS) which are combined with automated guided vehicles (AGVs) using a tandem configuration. So far most of the previous studies have dealt with conventional design problems not considering the layout and the characteristics of transporters used in CMS. A mathematical model is developed using the service time to perform material transfers as a suitable meassure. The service capacity of AGVs and space limitations are also reflected in this model. As the model can be shown strongly NP-hard, a heuristic algorithm is presented, in which each cell is temporarily formed using both the set covering model and similarity coefficients, and then locations of the cells are determined by means of tabu search and finally machine perturbations are carried out. An example problem is solved to demonstrate the algorithm developed.