This paper considers a restricted non-identical parallel machine scheduling problem with sequence and machine dependent setup times. The objective of this problem is to determine the allocation of jobs and the scheduling of machines to minimize the makespan. A mathematical model for optimal solution is derived. An in-depth analysis of the model shows that it is very complicated and difficult to obtain optimal solutions as the problem size becomes large. Therefore, two meta-heuristic algorithms based on ant colony system and genetic algorithm are proposed. The performance of the proposed algorithms are evaluated using randomly generated several examples.