On heuristic search for the single machine total weighted tardiness problem - Some theoretical insights and their empirical verification

Martin Josef Geiger

European Journal of Operational Research, 2010, vol. 207, issue 3, 1235-1243

Abstract: The article presents theoretical and experimental investigations of computational intelligence techniques for machine sequencing problems. Contrary to other approaches, which are experimentally driven only, our work is motivated by gaining insights in the underlying principles of heuristic search for this particular problem. We therefore first theoretically analyze local search neighborhoods, deriving expectations about their relative performance. An empirical study on benchmark data follows, verifying the initial propositions. In result, we may conclude theoretically and empirically on the relative performance of neighborhood search operators for the single machine total weighted tardiness problem. The results are useful for the proposition of heuristic search procedures based on local search, as they lead to an order of neighborhood structures with respect to their relative performance. The obtained insights are verified by investigating the effectiveness of a (multi-operator) Variable Neighborhood Search approach for the problem at hand. We are able to show that most known benchmark instances are reliably solved to optimality, leaving an overall average gap of around 1% above the optimum.

Keywords: Metaheuristics; Scheduling; Neighborhood; operators (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00470-4
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:207:y:2010:i:3:p:1235-1243

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 ().