This paper addresses the problem of making sequencing and scheduling decisions for n jobs m machines flow shops under lot sizing environment. Lot streaming (lot sizing) is the process of creating sublots to move the completed portion of a production sublots to down stream machines. There is a scope for efficient algorithms for scheduling problems in m-machine flow shop with lot streaming. In recent years, much attention is given to heuristics and search techniques. On this concern this paper proposes Ant-colony optimization algorithm (ACO) and threshold accepting algorithm (TA) to evolve best sequence for makespan/total flow time criterion for m-machine flow shop involved with lot streaming and setup time. The following two algorithms are used to evaluate the performance of the proposed ACO and TA: (i) Baker's algorithm (BA), an optimal solution procedure for two-machine flow shop problem with lot streaming and makespan objective criterion and (ii) genetic and hybrid genetic algorithm for m-machine flow shop problem with lot streaming and makespan and total flow time criteria. © 2008 Elsevier B.V. All rights reserved.