AbstractIn this paper we consider an NP -hard hybrid flow shop problem with machine setups and cycle-time minimization. The above issue is an important generalization of a flow-shop problem with minimization of a cycle time, and it stays in a direct relationship with a flexible job shop problem. In the hybrid problem task operations are performed by machines arranged in slots, i.e., a set of machines with the same functional properties. In this work we presented a graph model, properties of the problem and methods of determining approximate value of the optimal cycle duration. The above mentioned concepts have been used in the construction of tabu search algorithm. Computational experiments were conducted on well-known in literature examples, which confirmed high efficiency of the algorithm.