University of Wollongong
Browse

A synergetic combination of small and large neighborhood schemes in developing an effective procedure for solving the job shop problem

Download (1.86 MB)
journal contribution
posted on 2024-11-15, 17:55 authored by Mehrdad AmirghasemiMehrdad Amirghasemi, Mohammad Zamani
This paper presents an effective procedure for solving the job shop problem. Synergistically combining small and large neighborhood schemes, the procedure consists of four components, namely (i) a construction method for generating semi-active schedules by a forward-backward mechanism, (ii) a local search for manipulating a small neighborhood structure guided by a tabu list, (iii) a feedback-based mechanism for perturbing the solutions generated, and (iv) a very large-neighborhood local search guided by a forward-backward shifting bottleneck method. The combination of shifting bottleneck mechanism and tabu list is used as a means of the manipulation of neighborhood structures, and the perturbation mechanism employed diversifies the search. A feedback mechanism, called cycle-check, detects consequent repeats as cycles and ignites the perturbation when the total number of consecutive repeats for two identical makespan values reaches a given threshold. The results of extensive computational experiments on the benchmark instances indicate that the combination of these four components is synergetic, in the sense that they collectively make the procedure fast and robust.

History

Citation

Amirghasemi, M. & Zamani, R. (2014). A synergetic combination of small and large neighborhood schemes in developing an effective procedure for solving the job shop problem. SpringerPlus, 3 (1), 1-15.

Journal title

SpringerPlus

Volume

3

Issue

1

Language

English

RIS ID

89845

Usage metrics

    Categories

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC