The objective of this paper is to propose and evaluate heuristic search algorithms for two-machine flow shop problem with multiple jobs requiring lot streaming that minimizes makespan and total flow time. The two heuristic search algorithms evaluated in this paper are Tabu search algorithm (TABU) and Simulated Annealing (SA) algorithm. To create neighborhoods for SA, three Perturbation schemes, viz. pair wise exchange, insertion and random insertion perturbation are used and the performance of these on the final schedule is also compared. A wide variety of data sets are randomly generated for comparative evaluation. The results indicates that TABU and SA perform almost similar for the objective of makespan and TABU performs better over SA for the objective of total flow time irrespective of the neighborhood creation schemes. © 2004 IEEE.