This paper considers the application of heuristic algorithms to analyze the results obtained for the parallel machine scheduling problem with release times and sequence-dependent setups times. Since this problem is known to be strongly NP-hard for the case of minimizing the makespan, we resolved it with different heuristics and their performance is compared with a solution obtained using a lower bound. Such heuristics are based on either dispatching rules or random schedule generation strategies. Computational experiments are performed using random-generated data taken from the literature. Our results show that the heuristics perform very well compared against the lower bound, and requiring short computational time.