{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T18:09:06Z","timestamp":1769278146523,"version":"3.49.0"},"reference-count":39,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2017,10,28]],"date-time":"2017-10-28T00:00:00Z","timestamp":1509148800000},"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>The no-wait flow shop is a flowshop in which the scheduling of jobs is continuous and simultaneous through all machines without waiting for any consecutive machines. The scheduling of a no-wait flow shop requires finding an appropriate sequence of jobs for scheduling, which in turn reduces total processing time. The classical brute force method for finding the probabilities of scheduling for improving the utilization of resources may become trapped in local optima, and this problem can hence be observed as a typical NP-hard combinatorial optimization problem that requires finding a near optimal solution with heuristic and metaheuristic techniques. This paper proposes an effective hybrid Particle Swarm Optimization (PSO) metaheuristic algorithm for solving no-wait flow shop scheduling problems with the objective of minimizing the total flow time of jobs. This Proposed Hybrid Particle Swarm Optimization (PHPSO) algorithm presents a solution by the random key representation rule for converting the continuous position information values of particles to a discrete job permutation. The proposed algorithm initializes population efficiently with the Nawaz-Enscore-Ham (NEH) heuristic technique and uses an evolutionary search guided by the mechanism of PSO, as well as simulated annealing based on a local neighborhood search to avoid getting stuck in local optima and to provide the appropriate balance of global exploration and local exploitation. Extensive computational experiments are carried out based on Taillard\u2019s benchmark suite. Computational results and comparisons with existing metaheuristics show that the PHPSO algorithm outperforms the existing methods in terms of quality search and robustness for the problem considered. The improvement in solution quality is confirmed by statistical tests of significance.<\/jats:p>","DOI":"10.3390\/a10040121","type":"journal-article","created":{"date-parts":[[2017,10,30]],"date-time":"2017-10-30T12:16:23Z","timestamp":1509365783000},"page":"121","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":29,"title":["Evolutionary Hybrid Particle Swarm Optimization Algorithm for Solving NP-Hard No-Wait Flow Shop Scheduling Problems"],"prefix":"10.3390","volume":"10","author":[{"given":"Laxmi","family":"Bewoor","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, K. L. University, Andhra Pradesh, Guntur 522502, India"}]},{"given":"V.","family":"Chandra Prakash","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, K. L. University, Andhra Pradesh, Guntur 522502, India"}]},{"given":"Sagar","family":"Sapkal","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering, Walchand College of Engineering, Maharashtra, Sangli 416415, India"}]}],"member":"1968","published-online":{"date-parts":[[2017,10,28]]},"reference":[{"key":"ref_1","unstructured":"Pinedo, M. (2002). Scheduling: Theory, Algorithms and Systems, Prentice-Hall. [2nd ed.]."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/s001700300005","article-title":"An effective hybrid heuristic for flow shop scheduling","volume":"21","author":"Wang","year":"2003","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1016\/S0377-2217(02)00834-2","article-title":"Solving the continuous flow-shop scheduling problem by metaheuristics","volume":"151","author":"Fink","year":"2003","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1057\/jors.1994.65","article-title":"A no-wait flowshop scheduling heuristic to minimize makespan","volume":"45","author":"Rajendran","year":"1994","journal-title":"J. Oper. Res. Soc."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1016\/S0377-2217(99)00224-6","article-title":"Sequencing of jobs in some production system","volume":"125","author":"Grabowski","year":"2000","journal-title":"Eur. J. Oper. Res."},{"key":"ref_6","first-page":"6131","article-title":"Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing","volume":"12","author":"Raaymakers","year":"2000","journal-title":"Eur. J. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/j.ijpe.2010.05.003","article-title":"A genetic local search algorithm for minimizing total flow time in the permutation flowshop scheduling problem","volume":"127","author":"Tseng","year":"2010","journal-title":"Int. J. Prod. Econom."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/j.ejor.2016.05.036","article-title":"A survey of scheduling problems with no-wait in process","volume":"255","author":"Allahverdi","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"2807","DOI":"10.1016\/j.cor.2006.12.030","article-title":"A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem","volume":"35","author":"Pan","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.ejor.2012.04.034","article-title":"Local search methods for the flowshop scheduling problem with flowtime minimization","volume":"222","author":"Pan","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"ref_11","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","author":"Rock","year":"1984","journal-title":"J. ACM"},{"key":"ref_12","unstructured":"Garey, M., and Johnson, D. (1979). Computers and Intractability, a Guide to the Theory of NP-Completeness, Freeman. [4th ed.]."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","article-title":"Optimization and approximation in deterministic sequencing and scheduling","volume":"5","author":"Graham","year":"1979","journal-title":"Ann. Discret. Math."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2541","DOI":"10.1080\/00207549408957083","article-title":"A heuristic for scheduling in flowshop and flowline-based manufacturing cell with multicriteria","volume":"32","author":"Rajendran","year":"1994","journal-title":"Int. J. Prod. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1016\/S0924-0136(00)00720-2","article-title":"Heuristic algorithm for scheduling in the no-wait flow-shop","volume":"107","author":"Bertolissi","year":"2000","journal-title":"J. Mater. Process. Technol."},{"key":"ref_16","first-page":"345","article-title":"New heuristics for m -machine no-wait flowshop to minimize total completion time","volume":"32","author":"Aldowaisan","year":"2004","journal-title":"Int. J. Manag. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1327","DOI":"10.1007\/s00170-013-4924-y","article-title":"A heuristic for no-wait flow shop scheduling","volume":"68","author":"Sapkal","year":"2013","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Tasgetiren, M., Pan, Q., Kizilay, D., and Gao, K. (2016). A variable block insertion heuristic for the blocking flowshop scheduling problem with total flowtime criterion. Algorithms, 9.","DOI":"10.3390\/a9040071"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/S0377-2217(00)00137-5","article-title":"Constructive and composite heuristic solutions to the P\/\/\u2211Ci scheduling problem","volume":"132","author":"Liu","year":"2001","journal-title":"Eur. J. Oper. Res."},{"key":"ref_20","first-page":"268","article-title":"Metaheuristics in combinatorial optimization: Overview and conceptual comparison","volume":"35","author":"Blum","year":"2003","journal-title":"Appl. Soft Comput. J."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"4135","DOI":"10.1016\/j.asoc.2011.02.032","article-title":"Hybrid metaheuristics in combinatorial optimization: A survey","volume":"11","author":"Blum","year":"2011","journal-title":"Appl. Soft Comput. J."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"12500","DOI":"10.1142\/S0217595912500121","article-title":"A hybrid harmony search algorithm for the no-wait flow-shop scheduling problems","volume":"29","author":"Gao","year":"2012","journal-title":"Asia-Pac. J. Oper. Res."},{"key":"ref_23","first-page":"91","article-title":"A Heuristic Algorithm for the m-Machine, n-Job Flow-shop Sequencing Problem","volume":"11","author":"Nawaz","year":"1983","journal-title":"Int. J. Manag. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Gao, K., Suganthan, P., and Chua, T. (2013, January 16\u201319). An enhanced migrating birds optimization algorithm for no-wait flow shop scheduling problem. Proceedings of the IEEE Symposium on Computational Intelligence in Scheduling, Singapore.","DOI":"10.1109\/SCIS.2013.6613246"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Filho, G., Nagano, M., and Lorena, L. (2007). Hybrid Evolutionary Algorithm for Flowtime Minimization in No-Wait Flowshop Scheduling, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-540-76631-5_105"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1016\/j.ejor.2008.04.033","article-title":"Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization","volume":"196","author":"Zhang","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"7970","DOI":"10.1016\/j.eswa.2010.12.075","article-title":"An asynchronous genetic local search algorithm for the permutation flowshop scheduling problem with total flowtime minimization","volume":"38","author":"Xu","year":"2011","journal-title":"Expert Syst. Appl."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2447","DOI":"10.4028\/www.scientific.net\/AMR.712-715.2447","article-title":"A hybrid intelligence algorithm for no-wait flow shop scheduling","volume":"712","author":"Wang","year":"2013","journal-title":"Adv. Mater. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"3021","DOI":"10.21817\/ijet\/2016\/v8i6\/160806265","article-title":"Comparative analysis of metaheuristic approaches for m-machine no-wait flow shop scheduling for minimizing total flow time with stochastic input","volume":"8","author":"Bewoor","year":"2016","journal-title":"Int. J. Eng. Technol."},{"key":"ref_30","first-page":"31","article-title":"Comparative analysis of metaheuristic approaches for makespan minimization for no-wait flow shop scheduling problem","volume":"7","author":"Bewoor","year":"2017","journal-title":"Int. J. Electr. Comput. Eng."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1181","DOI":"10.1007\/s00170-013-5351-9","article-title":"A hybrid particle swarm optimization algorithm for a no-wait flow shop scheduling problem with the total flow time","volume":"70","author":"Akhshabi","year":"2014","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_32","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_33","doi-asserted-by":"crossref","first-page":"710","DOI":"10.3390\/a2020710","article-title":"ALE-PSO: An adaptive swarm algorithm to solve design problems of laminates","volume":"2","author":"Vannucci","year":"2009","journal-title":"Algorithms"},{"key":"ref_34","unstructured":"Eberhard, R., and Kennedy, J. (1995, January 4\u20136). A new optimizer using particle swarm theory. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1287\/ijoc.6.2.154","article-title":"Genetic algorithms and random keys for sequencing and optimization","volume":"6","author":"Bean","year":"1994","journal-title":"ORSA J. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1109\/TSMCB.2006.883272","article-title":"An effective PSO-based memetic algorithm for flowshop scheduling","volume":"37","author":"Liu","year":"2007","journal-title":"IEEE Trans. Syst. Man Cybern. Part B"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1016\/j.cie.2007.09.006","article-title":"A combinatorial particle swarm optimization for solving permutation flowshop problems","volume":"54","author":"Jarboui","year":"2008","journal-title":"Comput. Ind. Eng."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Khamlichi, Y., Tahiri, A., Abtoy, A., Bulo, I., and Lozano, F. (2017). A hybrid algorithm for optimal wireless sensor network deployment with the minimum number of sensor nodes. Algorithms, 10.","DOI":"10.3390\/a10030080"},{"key":"ref_39","unstructured":"Devore, J. (2016). Probability and Statistics for Engineering and the Sciences, Brooks Cole. [9th ed.]."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/4\/121\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:48:46Z","timestamp":1760208526000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/4\/121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,28]]},"references-count":39,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2017,12]]}},"alternative-id":["a10040121"],"URL":"https:\/\/doi.org\/10.3390\/a10040121","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,28]]}}}