This paper considers a parallel-machine scheduling problem with job release times and sequence-dependent setup times. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines so as to minimize the weighted sum of setup times, delay times, and tardy times. A mathematical model for optimal solution is derived and a meta heuristic algorithm based on the improved ant colony system is proposed in this paper. The performance of the meta heuristic algorithm is evaluated through compare with optimal solutions using randomly generated several examples.