A flow‐shop batching problem with consistent batches is considered in which the processing times of all jobs on each machine are equal to p and all batch set‐up times are equal to s. In such a problem, one has to partition the set of jobs into batches and to schedule the batches on each machine. The processing time of a batch B
i
is the sum of processing times of operations in B
i
and the earliest start of B
i
on a machine is the finishing time of B
i
on the previous machine plus the set‐up time s. Cheng et al. (2000) provided an O(n) pseudopolynomial‐time algorithm for solving the special case of the problem with two machines. Mosheiov and Oron (2005) developed an algorithm of the same time complexity for the general case with more than two machines. Ng and Kovalyov (2007) improved the pseudopolynomial complexity to
. In this paper, we provide a polynomial‐time algorithm of time complexity O(log 3
n).
