A theoretical framework to accelerate scheduling improvement heuristics using a new longest path algorithm in perturbed DAGs

Golshan Madraki, Seyedamirabbas Mousavian and Yasamin Salmani

International Journal of Production Research, 2023, vol. 61, issue 3, 818-838

Abstract: Job-shop scheduling problems are complex and still well-studied manufacturing problems. Improvement heuristic algorithms have been proposed to solve the scheduling problems using makespan as their performance measure. All these heuristics iteratively perturb trial schedules by selecting a new schedule from a set of nearby schedules (neighbourhood); then, recalculate and compare the makespan until a sufficient schedule is determined. Unlike previous studies, we did not generate a new heuristic or a novel neighbourhood calculation. Instead, we proposed a theoretical framework, Algorithm to Visit Affected Node (AVAN), which can be incorporated in qualified heuristics while using their current neighbourhood structure to accelerate the recalculation of the makespan in each iteration. We modelled the system by Directed Acyclic Graph (DAG) where the length of the longest path equals the makespan. The scheduling perturbations are represented by adding and deleting edges. AVAN investigates the configuration of scheduling perturbations (added/deleted edges) to find an appropriate starting point to traverse the graph. AVAN is mathematically more efficient than previous longest path algorithms for perturbed DAG. Its time complexity is $ \textrm{O}({\Delta + \vert {\Delta } \vert \log ({\vert \Delta \vert } )} ) $ O(Δ+|Δ|log⁡(|Δ|)), where $ \vert {\Delta } \vert $ |Δ| is the number of affected nodes and $ \Delta $ Δ is the number of incoming and outgoing edges of the affected nodes.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2021.2017057 (text/html)
Access to full text is restricted to subscribers.

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:taf:tprsxx:v:61:y:2023:i:3:p:818-838

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2021.2017057

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().