In this paper, we present a new Imperialist Competitive Algorithm (ICA) to solve a bi-objective unrelated parallel machine scheduling problem where setup times are sequence dependent. The objectives include mean completion time of jobs and mean squares of deviations from machines workload from their averages. The performance of the proposed ICA (PICA) method is examined using some randomly generated data and they are compared with three alternative methods including particle swarm optimization (PSO), original version of imperialist competitive algorithm (OICA) and genetic algorithm (GA) in terms of the objective function values. The preliminary results indicate that the proposed study outperforms other alternative methods. In addition, while OICA performs the worst as alternative solution strategy, PSO and GA seem to perform better.