In this paper we study the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times. We consider the objective of minimizing the maximum completion time of the latest job, usually referred to as makespan. We propose a new MIP-based heuristic combining atomic moves such as insertion, ejection and closure, in order to generate sequences of such atomic moves minimizing the makespan. This heuristic employs a commercial solver to search the neighborhood in a multi-start algorithm. Our approach performed well in computational experiments targeting two sets of benchmark instances previously used in the literature.In this paper we study the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times. We consider the objective of minimizing the maximum completion time of the latest job, usually referred to as makespan. We propose a new MIP-based heuristic combining atomic moves such as insertion, ejection and closure, in order to generate sequences of such atomic moves minimizing the makespan. This heuristic employs a commercial solver to search the neighborhood in a multi-start algorithm. Our approach performed well in computational experiments targeting two sets of benchmark instances previously used in the literature.