{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T00:32:53Z","timestamp":1760401973076,"version":"build-2065373602"},"reference-count":49,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,3,30]],"date-time":"2021-03-30T00:00:00Z","timestamp":1617062400000},"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>This paper presents an effective stochastic algorithm that embeds a large neighborhood decomposition technique into a variable neighborhood search for solving the permutation flow-shop scheduling problem. The algorithm first constructs a permutation as a seed using a recursive application of the extended two-machine problem. In this method, the jobs are recursively decomposed into two separate groups, and, for each group, an optimal permutation is calculated based on the extended two-machine problem. Then the overall permutation, which is obtained by integrating the sub-solutions, is improved through the application of a variable neighborhood search technique. The same as the first technique, this one is also based on the decomposition paradigm and can find an optimal arrangement for a subset of jobs. In the employed large neighborhood search, the concept of the critical path has been used to help the decomposition process avoid unfruitful computation and arrange only promising contiguous parts of the permutation. In this fashion, the algorithm leaves those parts of the permutation which already have high-quality arrangements and concentrates on modifying other parts. The results of computational experiments on the benchmark instances indicate the procedure works effectively, demonstrating that solutions, in a very short distance of the best-known solutions, are calculated within seconds on a typical personal computer. In terms of the required running time to reach a high-quality solution, the procedure outperforms some well-known metaheuristic algorithms in the literature.<\/jats:p>","DOI":"10.3390\/a14040112","type":"journal-article","created":{"date-parts":[[2021,3,30]],"date-time":"2021-03-30T09:57:04Z","timestamp":1617098224000},"page":"112","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["An Effective Decomposition-Based Stochastic Algorithm for Solving the Permutation Flow-Shop Scheduling Problem"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8466-1380","authenticated-orcid":false,"given":"Mehrdad","family":"Amirghasemi","sequence":"first","affiliation":[{"name":"SMART Infrastructure Facility, Faculty of Engineering and Information Sciences, University of Wollongong, Wollongong, NSW 2522, Australia"}]}],"member":"1968","published-online":{"date-parts":[[2021,3,30]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1287\/ijoc.1060.0201","article-title":"Very large-scale neighborhood search for the quadratic assignment problem","volume":"19","author":"Ahuja","year":"2007","journal-title":"INFORMS J. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Glover, F., and Kochenberger, G.A. (2003). Variable Neighborhood Search. Handbook of Metaheuristics, Springer.","DOI":"10.1007\/b101874"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0166-218X(01)00338-9","article-title":"A survey of very large-scale neighborhood search techniques","volume":"123","author":"Ahuja","year":"2002","journal-title":"Discret. Appl. Math."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/nav.3800010110","article-title":"Optimal two and three machine production scheduling with set up times included","volume":"1","author":"Johnson","year":"1954","journal-title":"Nav. Res. Logist."},{"key":"ref_5","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_6","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/nav.3800030307","article-title":"An extension of Johnson\u2019s results on job IDT scheduling","volume":"3","author":"Jackson","year":"1956","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1287\/opre.26.1.207","article-title":"Technical Note\u2014Three-Stage Flow-Shops with Recessive Second Stage","volume":"26","author":"Burns","year":"1978","journal-title":"Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Liefooghe, A., and L\u00f3pez-Ib\u00e1\u00f1ez, M. (2018). MOEA\/DEP: An Algebraic Decomposition-Based Evolutionary Algorithm for the Multiobjective Permutation Flowshop Scheduling Problem. Evolutionary Computation in Combinatorial Optimization, Springer International Publishing.","DOI":"10.1007\/978-3-319-77449-7"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"100747","DOI":"10.1016\/j.swevo.2020.100747","article-title":"Effective heuristics and metaheuristics for the distributed fuzzy blocking flow-shop scheduling problem","volume":"59","author":"Shao","year":"2020","journal-title":"Swarm Evol. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"106863","DOI":"10.1016\/j.cie.2020.106863","article-title":"An effective backtracking search algorithm for multi-objective flexible job shop scheduling considering new job arrivals and energy consumption","volume":"149","author":"Caldeira","year":"2020","journal-title":"Comput. Ind. Eng."},{"key":"ref_11","unstructured":"Rinnoy Kan, A. (1976). Machine Scheduling Problems: Classification, Complexity and Computation, Martinus Nijhoff Hague."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1145\/62.65","article-title":"The three-machine no-wait flow shop is NP-complete","volume":"31","year":"1984","journal-title":"JACM"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1016\/j.cor.2009.06.019","article-title":"The distributed permutation flowshop scheduling problem","volume":"37","author":"Naderi","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"100716","DOI":"10.1016\/j.swevo.2020.100716","article-title":"Energy-efficient distributed permutation flow shop scheduling problem using a multi-objective whale swarm algorithm","volume":"57","author":"Wang","year":"2020","journal-title":"Swarm Evol. Comput."},{"key":"ref_15","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_16","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_17","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_18","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1057\/jors.1965.8","article-title":"Sequencing jobs through a multi-stage process in the minimum total time\u2014A quick method of obtaining a near optimum","volume":"16","author":"Palmer","year":"1965","journal-title":"J. Oper. Res. Soc."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1057\/jors.1976.176","article-title":"Solutions to the constrained flowshop sequencing problem","volume":"27","author":"Bonney","year":"1976","journal-title":"Oper. Res. Q."},{"key":"ref_20","unstructured":"Tate, T. (1971). The slope-index technique for scheduling in machine shop. Current Production Scheduling Practice Conference, University of London."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1080\/00207546808929814","article-title":"A general algorithm for m*n flowshop scheduling problem","volume":"7","author":"Gupta","year":"1969","journal-title":"Int. J. Prod. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"630","DOI":"10.1287\/mnsc.16.10.B630","article-title":"A heuristic algorithm for the n job, m machine sequencing problem","volume":"16","author":"Campbell","year":"1970","journal-title":"Manag. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0305-0483(87)90054-5","article-title":"Comparison of heuristics for flow shop sequencing","volume":"15","author":"Turner","year":"1987","journal-title":"Omega"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/0377-2217(89)90383-4","article-title":"A new heuristic method for the flow shop sequencing problem","volume":"41","author":"Widmer","year":"1989","journal-title":"Eur. J. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1057\/jors.1995.119","article-title":"A New Heuristic Method for the Permutation Flow Shop Scheduling Problem","volume":"46","author":"Moccellin","year":"1995","journal-title":"J. Oper. Res. Soc."},{"key":"ref_26","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_27","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_28","doi-asserted-by":"crossref","first-page":"2033","DOI":"10.1016\/j.ejor.2005.12.009","article-title":"A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem","volume":"177","author":"Ruiz","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_29","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_30","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_31","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_32","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_33","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_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":"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_36","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_37","doi-asserted-by":"crossref","first-page":"1459","DOI":"10.1016\/j.asoc.2011.10.024","article-title":"A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem","volume":"13","author":"Liu","year":"2013","journal-title":"Appl. Soft Comput."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"269","DOI":"10.3233\/AIC-150695","article-title":"Solving permutation flowshop scheduling problems with a discrete differential evolution algorithm","volume":"29","author":"Santucci","year":"2016","journal-title":"AI Commun."},{"key":"ref_39","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_40","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_41","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1287\/mnsc.42.6.797","article-title":"A fast taboo search algorithm for the job shop problem","volume":"42","author":"Nowicki","year":"1996","journal-title":"Manag. Sci."},{"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","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_44","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_45","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_46","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_47","unstructured":"St\u00fctzle, T. (1998). Applying Iterated Local Search to the Permutation Flow Shop Problem, FG Intellektik, TU Darmstadt. Technical Report, Technical Report AIDA-98-04."},{"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","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."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/112\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T13:25:31Z","timestamp":1760361931000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,30]]},"references-count":49,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,4]]}},"alternative-id":["a14040112"],"URL":"https:\/\/doi.org\/10.3390\/a14040112","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,3,30]]}}}