A New One-Machine Decomposition Technique for Solving the Permutation Flow-Shop Scheduling Problem
Algorithms · 13.07.2026 · 19 (7) · 574
DOI: 10.3390/a19070574 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithms, online erschienen am 13.07.2026. Verfasst von Mehrdad Amirghasemi und 4 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 51 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Existing metaheuristics for the permutation flow-shop scheduling problem primarily explore the search space directly. This study presents a new decomposition technique that, unlike those methods, repeatedly solves one-machine subproblems and extends their solutions to all machines in order to minimize the makespan objective. To this end, the proposed algorithm solves the one-machine problem using a novel forward-backward procedure and extends its solutions to all machines through recurrent displacement of jobs. The improvement of the current solution proceeds until no optimal permutation for a single machine can improve the overall permutation for all machines, gradually improving current solutions and directing the search towards obtaining high-quality solutions. To further improve the results, any solution proposed by the one-machine solution strategy is refined by a local search process. An innovative triangular mechanism is also proposed for constructing initial solutions, with the aim of providing a high-quality starting point for the algorithm. The results of computational experiments not only demonstrate the efficiency of the one-machine forward-backward technique, but also indicate that the algorithm is both robust and highly effective in solving the standard benchmark instances.
Zitieren
APA
Amirghasemi, M., Voß, S., Garn, W., Arjomandi, A., & Ogie, R. (2026). A New One-Machine Decomposition Technique for Solving the Permutation Flow-Shop Scheduling Problem. Algorithms, 19(7), 574. https://doi.org/10.3390/a19070574
Vancouver
Amirghasemi M, Voß S, Garn W, Arjomandi A, Ogie R. A New One-Machine Decomposition Technique for Solving the Permutation Flow-Shop Scheduling Problem. Algorithms. 2026;19(7):574. doi:10.3390/a19070574
BibTeX
@article{Amirghasemi2026,
author = {Amirghasemi, Mehrdad and Voß, Stefan and Garn, Wolfgang and Arjomandi, Amir and Ogie, Robert},
title = {A New One-Machine Decomposition Technique for Solving the Permutation Flow-Shop Scheduling Problem},
journal = {Algorithms},
year = {2026},
volume = {19},
number = {7},
pages = {574},
doi = {10.3390/a19070574}
}
EUVIMED