Extended GRASP for the job shop scheduling problem with total weighted tardiness objective

C. Bierwirth and J. Kuhpfahl

European Journal of Operational Research, 2017, vol. 261, issue 3, 835-848

Abstract: The paper proposes a heuristic for the job shop scheduling problem with minimizing the total weighted tardiness of jobs as objective. It is built upon the well known metaheuristic GRASP and strengthened with an inclusion of specific local search components. The design is based on an advanced disjunctive graph model which enables capturing solution schedules through a tree graph called critical tree. The tree graph allows for effectively steering a first-descent search algorithm which further incorporates powerful neighborhood operators and a fast move evaluation procedure based on heads updating. Additionally, amplifying and path relinking is adaptively applied to the best schedules discovered. We present computational results of the new heuristic on two famous sets of benchmark instances, we identify ten new best solutions, and we demonstrate the high potential of the approach through a comparison with state-of-the-art methods.

Keywords: Scheduling; GRASP; Disjunctive graph; Local search; Heads updating (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717302345
Full text for ScienceDirect subscribers only

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:eee:ejores:v:261:y:2017:i:3:p:835-848

DOI: 10.1016/j.ejor.2017.03.030

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().