Abstract: This paper proposes and implements a simulated annealing algorithm,a general stochastic approach,for solving of flow-shop scheduling. Un the basis of six different random sampling methods,the analyses prove that the algorithm converges asymptotically to global optimums and is a polynomial one. Taking flow-shop scheduling problems of makespan minimization for unlimited intermediate storage (UIS), finiteintermediate storage(FIS) and no intermediate storage (NIS) as examples,the evaluations show that the algorithm is efficient.