{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T20:35:32Z","timestamp":1776976532138,"version":"3.51.4"},"reference-count":25,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2018,4,6]],"date-time":"2018-04-06T00:00:00Z","timestamp":1522972800000},"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 number of just-in-time jobs maximization in a permutation flow shop scheduling problem is considered. A mixed integer linear programming model to represent the problem as well as solution approaches based on enumeration and constructive heuristics were proposed and computationally implemented. Instances with up to 10 jobs and five machines are solved by the mathematical model in an acceptable running time (3.3 min on average) while the enumeration method consumes, on average, 1.5 s. The 10 constructive heuristics proposed show they are practical especially for large-scale instances (up to 100 jobs and 20 machines), with very good-quality results and efficient running times. The best two heuristics obtain near-optimal solutions, with only 0.6% and 0.8% average relative deviations. They prove to be better than adaptations of the NEH heuristic (well-known for providing very good solutions for makespan minimization in flow shop) for the considered problem.<\/jats:p>","DOI":"10.3390\/a11040043","type":"journal-article","created":{"date-parts":[[2018,4,10]],"date-time":"2018-04-10T13:06:08Z","timestamp":1523365568000},"page":"43","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Near-Optimal Heuristics for Just-In-Time Jobs Maximization in Flow Shop Scheduling"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8943-1506","authenticated-orcid":false,"given":"Helio","family":"Fuchigami","sequence":"first","affiliation":[{"name":"Faculty of Sciences and Technology (FCT), Federal University of Goias (UFG), 74968-755 Aparecida de Goi\u00e2nia, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruhul","family":"Sarker","sequence":"additional","affiliation":[{"name":"School of Engineering and Information Technology (SEIT), University of New South Wales (UNSW), Canberra ACT 2610, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3910-8804","authenticated-orcid":false,"given":"Socorro","family":"Rangel","sequence":"additional","affiliation":[{"name":"Instituto de Bioci\u00eancias, Letras e Ci\u00eancias Exatas (IBILCE), Universidade Estadual Paulista (UNESP), 19014-020 S\u00e3o Paulo Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,4,6]]},"reference":[{"key":"ref_1","unstructured":"Pinedo, M.L. (2016). Scheduling: Theory, Algorithms and Systems, Prentice-Hall. [5th ed.]."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.ijpe.2011.09.011","article-title":"A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system","volume":"136","author":"Shabtay","year":"2012","journal-title":"Int. J. Prod. Econ."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1016\/0305-0548(95)00078-X","article-title":"Single machine scheduling to minimize the number of early and tardy jobs","volume":"23","author":"Lann","year":"1996","journal-title":"Comput. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1287\/opre.48.1.99.12447","article-title":"Scheduling with inserted idle time: Problem taxonomy and literature review","volume":"48","author":"Kanet","year":"2000","journal-title":"Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/opre.38.1.22","article-title":"Sequencing with earliness and tardiness penalties: A review","volume":"38","author":"Baker","year":"1990","journal-title":"Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"J\u00f3zefowska, J. (2007). Just-in-Time Scheduling: Models and Algorithms for Computer and Manufacturing Systems, Springer Science.","DOI":"10.1007\/978-0-387-71718-0"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"R\u00edos-Sol\u00eds, Y.A., and R\u00edos-Mercado, R.Z. (2012). Just-In-Time Systems, Springer Sciences.","DOI":"10.1007\/978-1-4614-1123-9"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"R\u00edos-Sol\u00eds, Y.A., and R\u00edos-Mercado, R.Z. (2012). Scheduling to maximize the number of just-in-time jobs: A survey. Just-in-Time Systems, Springer Sciences.","DOI":"10.1007\/978-1-4614-1123-9"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s10951-007-0030-z","article-title":"Maximizing the weighted number of just-in-time jobs in flow shop scheduling","volume":"10","author":"Choi","year":"2007","journal-title":"J. Sched."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s10951-010-0204-y","article-title":"Maximizing the weighted number of just-in-time jobs in several two-machine scheduling systems","volume":"15","author":"Shabtay","year":"2012","journal-title":"J. Sched."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1016\/j.ejor.2011.07.053","article-title":"The just-in-time scheduling problem in a flow-shop scheduling system","volume":"216","author":"Shabtay","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/j.ipl.2014.09.004","article-title":"A note: Maximizing the weighted number of just-in-time jobs on a proportionate flowshop","volume":"115","author":"Gerstl","year":"2015","journal-title":"Inf. Process. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/s10951-017-0511-7","article-title":"Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs","volume":"20","author":"Yin","year":"2017","journal-title":"J. Sched."},{"key":"ref_14","unstructured":"Fuchigami, H.Y., and Rangel, S. (2015, January 25\u201328). M\u00e9todos heur\u00edsticos para maximiza\u00e7\u00e3o do n\u00famero de tarefas just-in-time em flow shop permutacional. Proceedings of the Simp\u00f3sio Brasileiro de Pesquisa Operacional, Porto de Galinhas, Brazil."},{"key":"ref_15","unstructured":"Fuchigami, H.Y., and Rangel, S. (2016, January 27\u201330). Um estudo computacional de um modelo matem\u00e1tico para flow shop permutacional com tarefas just-in-time. Proceedings of the Simp\u00f3sio Brasileiro de Pesquisa Operacional, Vit\u00f3ria, Brazil."},{"key":"ref_16","first-page":"85","article-title":"Minimizing the number of tardy jobs in a permutation flowshop scheduling problem with setup times and time lags constraints","volume":"12","author":"Dhouib","year":"2013","journal-title":"J. Math. Model. Algorithm"},{"key":"ref_17","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\u2013Int. J. Manag. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1144","DOI":"10.1287\/mnsc.23.10.1144","article-title":"A note on single machine sequencing with random processing times","volume":"23","author":"Hodgson","year":"1977","journal-title":"Manag. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Baker, K.R., and Trietsch, D. (2009). Principles of Sequencing and Scheduling, John Wiley & Sons.","DOI":"10.1002\/9780470451793"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"11","DOI":"10.15675\/gepros.v2i2.743","article-title":"Solu\u00e7\u00f5es de alto desempenho para programa\u00e7\u00e3o da produ\u00e7\u00e3o flow shop","volume":"4","author":"Nagano","year":"2009","journal-title":"GEPROS"},{"key":"ref_21","first-page":"13","article-title":"Trajectory scheduling methods for minimizing total tardiness in a flowshop","volume":"2","author":"Li","year":"2015","journal-title":"Oper. Res. Perspect."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1350","DOI":"10.1016\/j.cor.2006.08.016","article-title":"Minimizing total tardiness in the m-machine flowshop problem: A review and evaluation of heuristics and metaheuristics","volume":"35","author":"Vallada","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"R\u00edos-Sol\u00eds, Y.A., and R\u00edos-Mercado, R.Z. (2012). Mixed-integer programming models for flow shop scheduling problems minimizing the total earliness and tardiness. Just-in-Time Systems, Springer Sciences.","DOI":"10.1007\/978-1-4614-1123-9"},{"key":"ref_24","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_25","doi-asserted-by":"crossref","first-page":"734","DOI":"10.1016\/j.omega.2008.05.002","article-title":"A heuristic to minimize total flow time in permutation flow shop","volume":"37","author":"Laha","year":"2009","journal-title":"OMEGA\u2013Int. J. Manag. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/4\/43\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:59:52Z","timestamp":1760194792000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/4\/43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,6]]},"references-count":25,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,4]]}},"alternative-id":["a11040043"],"URL":"https:\/\/doi.org\/10.3390\/a11040043","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,6]]}}}