Minimization of make span and minimization of number of tardy jobs in identical parallel machine scheduling problems are proved to be NP-hard problems. Many researchers have attempted to solve these combinatorial optimization problems by employing different heuristic algorithms. While providing a satisfactory solution to the production environment for each of the above-said objectives, still remains as a challenge, most of the time, the need has been to have satisfactory solutions optimizing simultaneously the above-said two objectives. In this research work, an attempt is made to address this issue and heuristic algorithms using simulated annealing algorithm (SA) and variable neighborhood search algorithm (VNS) have been developed to provide near-optimal solutions. The developed heuristics are tested for their efficiency on a very large data sets generated as per the prescribed procedure found in the literature. Based on the results of experiments, it is inferred that the VNS-based heuristics outperforms the SA-based heuristics consistently both in terms of solution quality and consistency. © Springer India 2015.