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

作者：Rodriguez F J^*; Blum C; Garcia Martinez C; Lozano M

来源：Annals of Operations Research, 2012, 201(1): 383-401.

DOI：10.1007/s10479-012-1164-8

• Non-identical parallel machine scheduling problem with minimising total weighted completion times
• Metaheuristics
• GRASP
• Path-relinking

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.

• 出版日期2012-12