A general efficient neighborhood structure framework for the job-shop and flexible job-shop scheduling problems

Karim Tamssaouet and Stéphane Dauzère-Pérès

European Journal of Operational Research, 2023, vol. 311, issue 2, 455-471

Abstract: This article introduces a framework that unifies and generalizes well-known literature results related to local search for the job-shop and flexible job-shop scheduling problems. In addition to the choice of the metaheuristic and the neighborhood structure, the success of most of the influential local search approaches relies on the ability to quickly and efficiently rule out infeasible moves and evaluate the quality of the feasible neighbors. Hence, the proposed framework focuses on the feasibility and quality evaluation of a general move when solving the job-shop and flexible job-shop scheduling problems for any regular objective function. The proposed framework is valid for any scheduling problem where the defined neighborhood structure is appropriate, and each solution to the problem can be modeled with a directed acyclic graph with non-negative weights on nodes and arcs. The feasibility conditions and quality estimation procedures proposed in the literature rely heavily on information on the existence of a path between two nodes. Thus, based on an original parameterized algorithm that asserts the existence of a path between two nodes, novel generic procedures to evaluate the feasibility of a move and estimate the value of any regular objective function of a neighbor solution are proposed. We show that many well-known literature results are special cases of our results, which can be applied to a wide range of shop scheduling problems.

Keywords: Scheduling; Job-shop scheduling; Flexible job-shop scheduling; Heuristics (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723003818
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:311:y:2023:i:2:p:455-471

DOI: 10.1016/j.ejor.2023.05.018

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