{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T05:04:26Z","timestamp":1784091866961,"version":"3.55.0"},"reference-count":51,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T00:00:00Z","timestamp":1783900800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/a19070574","type":"journal-article","created":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T02:34:44Z","timestamp":1783996484000},"page":"574","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A New One-Machine Decomposition Technique for Solving the Permutation Flow-Shop Scheduling Problem"],"prefix":"10.3390","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8466-1380","authenticated-orcid":false,"given":"Mehrdad","family":"Amirghasemi","sequence":"first","affiliation":[{"name":"School of Business, University of Wollongong, Wollongong, NSW 2522, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1296-4221","authenticated-orcid":false,"given":"Stefan","family":"Vo\u00df","sequence":"additional","affiliation":[{"name":"Institute of Information Systems, University of Hamburg, Von-Melle-Park 5, 20146 Hamburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2278-8997","authenticated-orcid":false,"given":"Wolfgang","family":"Garn","sequence":"additional","affiliation":[{"name":"Surrey Business School, University of Surrey, Guildford GU2 7XH, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4253-7178","authenticated-orcid":false,"given":"Amir","family":"Arjomandi","sequence":"additional","affiliation":[{"name":"School of Business, University of Wollongong, Wollongong, NSW 2522, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6476-2309","authenticated-orcid":false,"given":"Robert","family":"Ogie","sequence":"additional","affiliation":[{"name":"SMART Infrastructure Facility, University of Wollongong, Wollongong, NSW 2522, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2026,7,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"3237","DOI":"10.1111\/itor.13108","article-title":"Shop scheduling in manufacturing environments: A review","volume":"29","author":"Ribeiro","year":"2022","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1080\/00207543.2020.1842938","article-title":"Supply chain-oriented permutation flowshop scheduling considering flexible assembly and setup times","volume":"61","author":"Ying","year":"2023","journal-title":"Int. J. Prod. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/S0377-2217(82)80007-6","article-title":"The one-machine sequencing problem","volume":"11","author":"Carlier","year":"1982","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1287\/mnsc.34.3.391","article-title":"The shifting bottleneck procedure for job shop scheduling","volume":"34","author":"Adams","year":"1988","journal-title":"Manag. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0167-6377(91)90014-G","article-title":"Permutation vs. non-permutation flow shop schedules","volume":"10","author":"Potts","year":"1991","journal-title":"Oper. Res. Lett."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1243","DOI":"10.1057\/palgrave.jors.2601784","article-title":"A review and classification of heuristics for permutation flow-shop scheduling with makespan objective","volume":"55","author":"Framinan","year":"2004","journal-title":"J. Oper. Res. Soc."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Amirghasemi, M. (2021). An effective decomposition-based stochastic algorithm for solving the permutation flow-shop scheduling problem. Algorithms, 14.","DOI":"10.3390\/a14040112"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0305-0548(93)E0014-K","article-title":"A genetic algorithm for flowshop sequencing","volume":"22","author":"Reeves","year":"1995","journal-title":"Comput. Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/S0167-8191(05)80147-4","article-title":"Robust taboo search for the quadratic assignment problem","volume":"17","author":"Taillard","year":"1991","journal-title":"Parallel Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0305-0483(83)90088-9","article-title":"A heuristic algorithm for the m-machine n-job flow-shop sequencing problem","volume":"11","author":"Nawaz","year":"1983","journal-title":"Omega"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0377-2217(90)90090-X","article-title":"Some efficient heuristic methods for the flow shop sequencing problem","volume":"47","author":"Taillard","year":"1990","journal-title":"Eur. J. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"858","DOI":"10.1016\/j.ejor.2019.10.017","article-title":"Generalised accelerations for insertion-based heuristics in permutation flowshop scheduling","volume":"282","author":"Framinan","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1016\/0377-2217(95)00037-2","article-title":"A fast tabu search algorithm for the permutation flow-shop problem","volume":"91","author":"Nowicki","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Maniezzo, V., St\u00fctzle, T., and Vo\u00df, S. (2010). Metaheuristics: Intelligent Problem Solving. Matheuristics: Hybridizing Metaheuristics and Mathematical Programming, Springer US.","DOI":"10.1007\/978-1-4419-1306-7"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1287\/moor.1.2.117","article-title":"The complexity of flowshop and jobshop scheduling","volume":"1","author":"Garey","year":"1976","journal-title":"Math. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1080\/00207548008919673","article-title":"Heuristics for flow-shop scheduling","volume":"18","author":"King","year":"1980","journal-title":"Int. J. Prod. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1287\/opre.40.1.7","article-title":"The lessons of flowshop scheduling research","volume":"40","author":"Dudek","year":"1992","journal-title":"Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0377-2217(95)00362-2","article-title":"The job shop scheduling problem: Conventional and new solution techniques","volume":"93","author":"Blazewicz","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1016\/j.ejor.2005.02.001","article-title":"Flowshop scheduling research after five decades","volume":"169","author":"Gupta","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1016\/j.ejor.2004.04.017","article-title":"A comprehensive review and evaluation of permutation flowshop heuristics","volume":"165","author":"Ruiz","year":"2005","journal-title":"Eur. J. Oper. Res."},{"key":"ref_21","unstructured":"St\u00fctzle, T. (1998). Applying Iterated Local Search to the Permutation Flow Shop Problem, FG Intellektik, TU Darmstadt. Technical Report, AIDA-98-04."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1016\/j.ejor.2016.09.055","article-title":"A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation","volume":"257","author":"Ruiz","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/s11047-020-09837-9","article-title":"Similarity in metaheuristics: A gentle step towards a comparison methodology","volume":"21","author":"Tilahun","year":"2022","journal-title":"Nat. Comput."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.jom.2010.12.006","article-title":"An empirical investigation of scheduling performance criteria","volume":"29","author":"Jorna","year":"2011","journal-title":"J. Oper. Manag."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1016\/j.ejor.2004.08.021","article-title":"Some aspects of scatter search in the flow-shop problem","volume":"169","author":"Nowicki","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1016\/j.chaos.2006.05.082","article-title":"A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan","volume":"35","author":"Lian","year":"2008","journal-title":"Chaos Solitons Fractals"},{"key":"ref_27","first-page":"773","article-title":"A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan","volume":"175","author":"Lian","year":"2006","journal-title":"Appl. Math. Comput."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"7027","DOI":"10.1016\/j.eswa.2008.08.054","article-title":"An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model","volume":"36","author":"Kuo","year":"2009","journal-title":"Expert Syst. Appl."},{"key":"ref_29","unstructured":"Taillard, E.D. (1998). FANT: Fast Ant System, Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale. Technical Report."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/j.ijpe.2017.06.026","article-title":"A new improved NEH heuristic for permutation flowshop scheduling problems","volume":"193","author":"Liu","year":"2017","journal-title":"Int. J. Prod. Econ."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1109\/TETCI.2021.3098354","article-title":"Deep reinforcement learning based optimization algorithm for permutation flow-shop scheduling","volume":"7","author":"Pan","year":"2023","journal-title":"IEEE Trans. Emerg. Top. Comput. Intell."},{"key":"ref_32","first-page":"20185","article-title":"Learning to optimize permutation flow shop scheduling via graph-based imitation learning","volume":"38","author":"Li","year":"2024","journal-title":"Proc. Aaai Conf. Artif. Intell."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0305-0548(90)90001-N","article-title":"The application of the simulated annealing algorithm to the solution of the n\/m\/Cmax flowshop problem","volume":"17","author":"Ogbu","year":"1990","journal-title":"Comput. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1016\/S0305-0548(03)00016-9","article-title":"Improved genetic algorithm for the permutation flowshop scheduling problem","volume":"31","author":"Iyer","year":"2004","journal-title":"Comput. Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.ijpe.2012.06.007","article-title":"A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem","volume":"141","author":"Chang","year":"2013","journal-title":"Int. J. Prod. Econ."},{"key":"ref_36","first-page":"79","article-title":"A multi-objective particle swarm for a flow shop scheduling problem","volume":"13","author":"Mirghorbani","year":"2007","journal-title":"J. Comb. Optim."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1361","DOI":"10.1016\/j.eswa.2009.06.105","article-title":"A multi-objective ant colony system algorithm for flow shop scheduling problem","volume":"37","author":"Yagmahan","year":"2010","journal-title":"Expert Syst. Appl."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1162\/EVCO_a_00162","article-title":"An effective evolutionary hybrid for solving the permutation flowshop scheduling problem","volume":"25","author":"Amirghasemi","year":"2017","journal-title":"Evol. Comput."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"107956","DOI":"10.1016\/j.cie.2022.107956","article-title":"Discrete differential evolution metaheuristics for permutation flow shop scheduling problems","volume":"166","author":"Ribeiro","year":"2022","journal-title":"Comput. Ind. Eng."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1016\/j.ejor.2020.01.039","article-title":"A computationally efficient branch-and-bound algorithm for the permutation flow-shop scheduling problem","volume":"284","author":"Gmys","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1287\/opre.20.3.668","article-title":"Solving resource-constrained network problems by implicit enumeration-preemptive case","volume":"20","author":"Schrage","year":"1972","journal-title":"Oper. Res."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/0377-2217(93)90182-M","article-title":"Benchmarks for basic scheduling problems","volume":"64","author":"Taillard","year":"1993","journal-title":"Eur. J. Oper. Res."},{"key":"ref_43","unstructured":"Cartwright, H.M., and Mott, G.F. (1991, January 13\u201316). Looking around: Using clues from the data space to guide genetic algorithm searches. Proceedings of the Fourth International Conference on Genetic Algorithms, San Diego, CA, USA."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1249","DOI":"10.1016\/j.cor.2008.01.007","article-title":"Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm","volume":"36","author":"Zobolas","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1930","DOI":"10.1016\/j.ejor.2005.12.024","article-title":"A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem","volume":"177","author":"Tasgetiren","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1016\/0305-0483(89)90059-5","article-title":"Simulated annealing for permutation flow-shop scheduling","volume":"17","author":"Osman","year":"1989","journal-title":"Omega"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1016\/S0377-2217(02)00908-6","article-title":"Ant-colony algorithms for permutation flowshop scheduling to minimize makespan\/total flowtime of jobs","volume":"155","author":"Rajendran","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1016\/j.omega.2004.12.006","article-title":"Two new robust genetic algorithms for the flowshop scheduling problem","volume":"34","author":"Ruiz","year":"2006","journal-title":"Omega"},{"key":"ref_49","first-page":"5887","article-title":"An effective parallel evolutionary metaheuristic with its application to three optimization problems","volume":"53","author":"Amirghasemi","year":"2022","journal-title":"Appl. Intell."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.swevo.2011.02.002","article-title":"A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms","volume":"1","author":"Derrac","year":"2011","journal-title":"Swarm Evol. Comput."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Garc\u00eda-S\u00e1nchez, P., D\u00edaz \u00c1lvarez, J., and Murphy, A. (2026). The next stage of evolutionary computation in the era of agentic generative AI. Proceedings of the Applications of Evolutionary Computation, Springer.","DOI":"10.1007\/978-3-032-23604-3"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/7\/574\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T04:10:43Z","timestamp":1784088643000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/7\/574"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,13]]},"references-count":51,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2026,7]]}},"alternative-id":["a19070574"],"URL":"https:\/\/doi.org\/10.3390\/a19070574","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,13]]}}}