The permutation flowshop scheduling problem with the objective of mini-mizing total flow time is known as a NP-hard problem, even for the two-machine cases. Because of the computational complexity of this problem, a multi-start simulated anneal-ing (MSA) heuristic, which adopts a multi-start hill climbing strategy in the simulated annealing (SA) heuristic, is proposed to obtain close-to-optimal solutions. To examine the performance of the MSA algorithm, a set of computational experiments was conducted on a well-known benchmark-problem set from the literature. The experiment results show that the performance of the traditional single-start SA can be significantly improved by incorporating the multi-start hill climbing strategy. In addition, the proposed MSA algo-rithm is highly effective and efficient as compared with the other state-of-the-art meta-heuristics on the same benchmark-problem instances. In terms of both solution quality and computational expense, the proposed algorithm contributes significantly to this ex-tremely challenging scheduling problem.