This paper presents a bi-objective flowshop scheduling problem with sequence-dependent setup times. The objective functions are to minimize the total completion time and the total earliness/tardiness for all jobs. An integer programming model is developed for the given problem that belongs to an NP-hard class. Thus, an algorithm based on a Multi-objective Immune System (MOIS) is proposed to find a locally Pareto-optimal frontier of the problem. To prove the efficiency of the proposed MOIS, different test problems are solved. Based on some comparison metrics, the computational results of the proposed MOIS is compared with the results obtained using two well-established multi-objective genetic algorithms, namely SPEA2+ and SPGA. The related results show that the proposed MOIS outperforms genetic algorithms, especially for the large-sized problems. (C) 2011 Elsevier Ltd. All rights reserved.