The thesis presents an implementation of Lagrangian Relaxation heuristic that involves solving a Mixed Integer Programming problem using standard Lagrangian technique and Sub gradient optimization. It also proposes a heuristic to obtain near-optimal solutions from lower bounds generated using Lagrangian Relaxation. This new algorithm is applied to the unrelated parallel machine scheduling problem with machine-dependent and sequence-dependent setup times with the objective of minimizing the maximum completion time, Makespan. This is a NP-hard problem and the thesis proposes a new method to solve the problem efficiently. Performance of this method is evaluated by comparing the results to an existing meta-heuristic. This research also proposes an improved Mixed Integer Linear Programming formulation for the problem under study. The experimental study conducted indicates that the improved formulation can solve large problem instances in shorter time when compared to an older formulation from the literature. The proposed Lagrangian Relaxation heuristic helps to find better solution for 26% of problem instances considered.