GRASP with path‐relinking for the non‐identical parallel machine scheduling problem with minimising total weighted completion times

In this work, we tackle the problem of scheduling a set of jobs on a set of non‐identical parallel machines with the goal of minimising the total weighted completion times. GRASP is a multi‐start method that consists of two phases: a solution construction phase, which randomly constructs a greedy solution, and an improvement phase, which uses that solution as an initial starting point. In the last few years, the GRASP methodology has arisen as a prospective metaheuristic approach to find high‐quality solutions for several difficult problems in reasonable computational times. With the aim of providing additional results and insights along this line of research, this paper proposes a new GRASP model that combines the basic scheme with two significant elements that have been shown to be very successful in order to improve GRASP performance. These elements are path‐relinking and evolutionary path‐relinking. The benefits of our proposal in comparison to existing metaheuristics proposed in the literature are experimentally shown.