A Hybrid Searching Method for the Unrelated Parallel Machine Scheduling Problem

Abstract : The work addresses the NP-hard problem of scheduling a set of jobs to unrelated parallel machines with the overall objective of minimizing makespan. The solution presented proposes a greedy constructive algorithm followed by an application of a Variable Neighborhood Decent strategy that continually improves the incumbent solution until a local optimum is reached. The strength of the approach lies in the adoption of different objectives at various stages of the search to avoid early local optimum entrapment and, mainly, in the hybridization of heuristic methods and mathematical programming for the definition and exploration of neighborhood structures. Experimental results on a large set of benchmark problems attest to the efficacy of the proposed approach.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01060672
Contributor : Hal Ifip <>
Submitted on : Thursday, November 16, 2017 - 3:45:07 PM
Last modification on : Sunday, December 17, 2017 - 1:11:24 AM
Long-term archiving on : Saturday, February 17, 2018 - 2:07:11 PM

File

CharalambousFH10.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Christoforos Charalambous, Krzysztof Fleszar, Khalil S. Hindi. A Hybrid Searching Method for the Unrelated Parallel Machine Scheduling Problem. 6th IFIP WG 12.5 International Conference on Artificial Intelligence Applications and Innovations (AIAI), Oct 2010, Larnaca, Cyprus. pp.230-237, ⟨10.1007/978-3-642-16239-8_31⟩. ⟨hal-01060672⟩

Share

Metrics

Record views

103

Files downloads

67