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

Fabián Rodríguez-Espinosa, C. Blum, C. García-Martínez and M. Lozano

Annals of Operations Research, 2012, vol. 201, issue 1, 383-401

Abstract: 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. Copyright Springer Science+Business Media, LLC 2012

Keywords: Non-identical parallel machine scheduling problem with minimising total weighted completion times; Metaheuristics; GRASP; Path-relinking (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-012-1164-8 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:201:y:2012:i:1:p:383-401:10.1007/s10479-012-1164-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-012-1164-8

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().