{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T07:24:51Z","timestamp":1790753091323,"version":"4.1.0"},"reference-count":33,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2020,4,29]],"date-time":"2020-04-29T00:00:00Z","timestamp":1588118400000},"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>Since its creation by Nawaz, Enscore, and Ham in 1983, NEH remains the best heuristic method to solve flowshop scheduling problems. In the large body of literature dealing with the application of this heuristic, it can be clearly noted that results differ from one paper to another. In this paper, two methods are proposed to improve the original NEH, based on the two points in the method where choices must be made, in case of equivalence between two job orders or partial sequences. When an equality occurs in a sorting method, two results are equivalent, but can lead to different final results. In order to propose the first improvement to NEH, the factorial basis decomposition method is introduced, which makes a number computationally correspond to a permutation. This method is very helpful for the first improvement, and allows testing of all the sequencing possibilities for problems counting up to 50 jobs. The second improvement is located where NEH keeps the best partial sequence. Similarly, a list of equivalent partial sequences is kept, rather than only one, to provide the global method a chance of better performance. The results obtained with the successive use of the two methods of improvement present an average improvement of 19% over the already effective results of the original NEH method.<\/jats:p>","DOI":"10.3390\/a13050112","type":"journal-article","created":{"date-parts":[[2020,4,29]],"date-time":"2020-04-29T13:23:45Z","timestamp":1588166625000},"page":"112","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion"],"prefix":"10.3390","volume":"13","author":[{"given":"Christophe","family":"Sauvey","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Lorraine, LGIPM, F-57000 Metz, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nathalie","family":"Sauer","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lorraine, LGIPM, F-57000 Metz, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,4,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/nav.3800010110","article-title":"Optimal two- and three-stage production schedules with setup times included","volume":"1","author":"Johnson","year":"1954","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_2","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 flowshop sequencing problem","volume":"11","author":"Nawaz","year":"1983","journal-title":"OmegaInt. J. Manag. Sci."},{"key":"ref_3","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_4","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 - a quick method of obtaining a near optimum","volume":"16","author":"Palmer","year":"1965","journal-title":"Oper. Res. Q."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1080\/00207548808947922","article-title":"An extension of Palmer\u2019s heuristic for the flow shop scheduling problem","volume":"26","author":"Hundal","year":"1988","journal-title":"Int. J. Prod. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"B630","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_7","doi-asserted-by":"crossref","first-page":"1174","DOI":"10.1287\/mnsc.23.11.1174","article-title":"An evaluation of flow shop sequencing heuristics","volume":"23","author":"Dannenbring","year":"1977","journal-title":"Manag. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/0377-2217(91)90080-F","article-title":"A new heuristic for the n-job, m-machine flow-shop problem","volume":"52","author":"Ho","year":"1991","journal-title":"Eur. J. Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/S0377-2217(97)00027-1","article-title":"A new constructive heuristic for the flowshop scheduling problem","volume":"105","author":"Koulamas","year":"1998","journal-title":"Eur. J. Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0925-5273(99)00053-5","article-title":"A two-phase heuristic approach to the permutation flow-shop scheduling problem","volume":"64","author":"Suliman","year":"2000","journal-title":"Int. J. Prod. Econ."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1080\/09537280152582995","article-title":"A new heuristic for the n-job, m-machine flow-shop problem","volume":"12","author":"Pour","year":"2001","journal-title":"Prod. Plan. Control"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Wang, Y., Li, X., and Ma, Z. (2017). A hybrid local search algorithm for the sequence dependent setup times flowshop scheduling problem with makespan criterion. Sustainability, 9.","DOI":"10.3390\/su9122318"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Yang, D.L., and Kuo, W.H. (2019). Minimizing Makespan in A Two-Machine Flowshop Problem with Processing Time Linearly Dependent on Job Waiting Time. Sustainability, 11.","DOI":"10.3390\/su11246885"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Fuchigami, H.Y., Sarker, R., and Rangel, S. (2018). Near-optimal heuristics for just-in-time jobs maximization in flowshop scheduling. Algorithms, 11.","DOI":"10.3390\/a11040043"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Huang, K.W., Girsang, A.S., Wu, Z.X., and Chuang, Y.W. (2019). A Hybrid Crow Search Algorithm for Solving Permutation Flow Shop Scheduling Problems. Appl. Sci., 9.","DOI":"10.3390\/app9071353"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Bewoor, L.A., Chandra Prakash, V., and Sapkal, S.U. (2017). Evolutionary hybrid particle swarm optimization algorithm for solving NP-hard no-wait flow shop scheduling problems. Algorithms, 10.","DOI":"10.3390\/a10040121"},{"key":"ref_17","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_18","unstructured":"St\u00fctzle, T. (1998). Applying Iterated Local Search to the Permutation Flow Shop Problem, FG Intellektik, TU Darmstadt. Technical Report 1998; AIDA-98-04."},{"key":"ref_19","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_20","doi-asserted-by":"crossref","first-page":"3962","DOI":"10.1016\/j.cor.2007.05.005","article-title":"An improved NEH-based heuristic for the permutation flowshop problem","volume":"35","author":"Dong","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_21","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_22","first-page":"11042","article-title":"A modified binary particle swarm optimization for knapsack problems","volume":"218","author":"Bansal","year":"2012","journal-title":"Appl. Math. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Li, Y., He, Y., Li, H., Guo, X., and Li, Z. (2018). A Binary Particle Swarm Optimization for Solving the Bounded Knapsack Problem. International Symposium on Intelligence Computation and Applications, Springer.","DOI":"10.1007\/978-981-13-6473-0_5"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Sauvey, C., Trabelsi, W., and Sauer, N. (2020). Mathematical Model and Evaluation Function for Conflict-Free Warranted Makespan Minimization of Mixed Blocking Constraint Job-Shop Problems. Mathematics, 8.","DOI":"10.3390\/math8010121"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Maassen, K., Hipp, A., and Perez-Gonzalez, P. (2019, January 25\u201327). Constructive heuristics for the minimization of core waiting time in permutation flow shop problems. Proceedings of the International Conference on Industrial Engineering and Systems Management (IESM), Shanghai, China.","DOI":"10.1109\/IESM45758.2019.8948147"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cor.2015.02.002","article-title":"NEH-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness","volume":"60","author":"Framinan","year":"2015","journal-title":"Comput. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/j.eswa.2019.01.062","article-title":"Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem","volume":"124","author":"Pan","year":"2019","journal-title":"Expert Syst. Appl."},{"key":"ref_28","first-page":"3094","article-title":"An NEH-based heuristic algorithm for distributed permutation flowshop scheduling problems","volume":"6","author":"Gao","year":"2011","journal-title":"Sci. Res. Essays"},{"key":"ref_29","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_30","doi-asserted-by":"crossref","first-page":"3001","DOI":"10.1016\/j.cor.2007.01.020","article-title":"An improved NEH heuristic to minimize makespan in permutation flow shops","volume":"35","author":"Kalczynski","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.ejor.2008.08.021","article-title":"An empirical analysis of the optimality rate of flow shop heuristics","volume":"198","author":"Kalczynski","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.cor.2013.12.012","article-title":"On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem","volume":"45","author":"Framinan","year":"2014","journal-title":"Comput. Oper. Res."},{"key":"ref_33","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."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/5\/112\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T14:09:27Z","timestamp":1760364567000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/5\/112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,29]]},"references-count":33,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2020,5]]}},"alternative-id":["a13050112"],"URL":"https:\/\/doi.org\/10.3390\/a13050112","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,29]]}}}