{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T20:35:16Z","timestamp":1776976516731,"version":"3.51.4"},"reference-count":63,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2016,10,20]],"date-time":"2016-10-20T00:00:00Z","timestamp":1476921600000},"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>In this paper, we present a variable block insertion heuristic (VBIH) algorithm to solve the blocking flowshop scheduling problem with the total flowtime criterion. In the VBIH algorithm, we define a minimum and a maximum block size. After constructing the initial sequence, the VBIH algorithm starts with a minimum block size being equal to one. It removes the block from the current sequence and inserts it into the partial sequence sequentially with a predetermined move size. The sequence, which is obtained after several block moves, goes under a variable local search (VLS), which is based on traditional insertion and swap neighborhood structures. If the new sequence obtained after the VLS local search is better than the current sequence, it replaces the current sequence. As long as it improves, it keeps the same block size. However, if it does not improve, the block size is incremented by one and a simulated annealing-type of acceptance criterion is used to accept the current sequence. This process is repeated until the block size reaches at the maximum block size. Furthermore, we present a novel constructive heuristic, which is based on the profile fitting heuristic from the literature. The proposed constructive heuristic is able to further improve the best known solutions for some larger instances in a few seconds. Parameters of the constructive heuristic and the VBIH algorithm are determined through a design of experiment approach. Extensive computational results on the Taillard\u2019s well-known benchmark suite show that the proposed VBIH algorithm outperforms the discrete artificial bee colony algorithm, which is one of the most efficient algorithms recently in the literature. Ultimately, 52 out of the 150 best known solutions are further improved with substantial margins.<\/jats:p>","DOI":"10.3390\/a9040071","type":"journal-article","created":{"date-parts":[[2016,10,20]],"date-time":"2016-10-20T10:15:49Z","timestamp":1476958549000},"page":"71","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["A Variable Block Insertion Heuristic for the Blocking Flowshop Scheduling Problem with Total Flowtime Criterion"],"prefix":"10.3390","volume":"9","author":[{"given":"Mehmet","family":"Tasgetiren","sequence":"first","affiliation":[{"name":"International Logistics Management Department, Yasar University, Izmir 35100, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quan-Ke","family":"Pan","sequence":"additional","affiliation":[{"name":"Department of Industrial and Manufacturing System Engineering, School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Damla","family":"Kizilay","sequence":"additional","affiliation":[{"name":"Industrial Engineering Department, Yasar University, Izmir 35100, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kaizhou","family":"Gao","sequence":"additional","affiliation":[{"name":"School of Electrical and Electronics, Nanyang Technological University, Singapore 639798, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2016,10,20]]},"reference":[{"key":"ref_1","unstructured":"B\u0142a\u017cewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., and Weglarz, J. (2007). Handbook on Scheduling: From Theory to Applications, Springer."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.omega.2011.05.002","article-title":"An estimation of distribution algorithm for lot-streaming flow shop problems with setup times","volume":"40","author":"Pan","year":"2012","journal-title":"Omega"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.omega.2009.04.002","article-title":"Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem","volume":"38","author":"Vallada","year":"2010","journal-title":"Omega"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/j.omega.2010.07.004","article-title":"Makespan and workstation utilization minimization in a flowshop with operations flexibility","volume":"39","author":"Ho","year":"2011","journal-title":"Omega"},{"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","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0925-5273(03)00065-3","article-title":"A note on constructive heuristics for the flowshop problem with blocking","volume":"87","author":"Ronconi","year":"2004","journal-title":"Int. J. Prod. Econ."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1287\/opre.44.3.510","article-title":"A survey of machine scheduling problems with blocking and no-wait in process","volume":"44","author":"Hall","year":"1996","journal-title":"Oper. Res."},{"key":"ref_8","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: A survey","volume":"5","author":"Graham","year":"1979","journal-title":"Ann. Discret. Math."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Lawler, E.L., Lenstra, K.L., Rinooy Kan, A.H.G., and Shmoys, D.B. (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons.","DOI":"10.2307\/2582681"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1287\/opre.37.6.925","article-title":"Sequencing in an assembly line with blocking to minimize cycle time","volume":"37","author":"McCormick","year":"1989","journal-title":"Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"2085","DOI":"10.1080\/00207549008942855","article-title":"Flowshop sequencing problems with limited buffer storage","volume":"28","author":"Leisten","year":"1990","journal-title":"Int. J. Prod. Res."},{"key":"ref_12","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_13","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1057\/palgrave.jors.2601220","article-title":"Lower bounding schemes for flowshops with blocking in-process","volume":"52","author":"Ronconi","year":"2001","journal-title":"J. Oper. Res. Soc."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1287\/opre.48.1.177.12451","article-title":"Minimizing cycle time in a blocking flowshop","volume":"48","author":"Abadi","year":"2000","journal-title":"Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/j.omega.2007.01.003","article-title":"Some heuristic algorithms for total tardiness minimization in a flowshop with blocking","volume":"37","author":"Ronconi","year":"2009","journal-title":"Omega"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.omega.2011.06.002","article-title":"Effective heuristics for the blocking flowshop scheduling problem with makespan minimization","volume":"40","author":"Pan","year":"2012","journal-title":"Omega"},{"key":"ref_17","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\/\/ \u2211 Ci scheduling problem","volume":"132","author":"Liu","year":"2001","journal-title":"Eur. J. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0925-5273(99)00104-8","article-title":"Minimizing makespan in a blocking flowshop using genetic algorithms","volume":"70","author":"Caraffa","year":"2001","journal-title":"Int. J. Prod. Econ."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/s10479-005-2444-3","article-title":"A branch-and-bound algorithm to minimize the makespan in a flowshop problem with blocking","volume":"138","author":"Ronconi","year":"2005","journal-title":"Ann. Oper. Res."},{"key":"ref_20","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_21","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/j.omega.2005.07.004","article-title":"The permutation flow shop problem with blocking. A tabu search approach","volume":"35","author":"Grabowski","year":"2007","journal-title":"Omega"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"2960","DOI":"10.1016\/j.cor.2005.02.028","article-title":"An effective hybrid genetic algorithm for flow shop scheduling with limited buffers","volume":"33","author":"Wang","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2791","DOI":"10.1016\/j.cor.2006.12.013","article-title":"An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers","volume":"35","author":"Liu","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/00207540701528750","article-title":"An effective hybrid DE-based algorithm for flow shop scheduling with limited buffers","volume":"47","author":"Qian","year":"2009","journal-title":"Int. J. Prod. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1007\/s00170-010-3111-7","article-title":"Solving the blocking flow shop scheduling problem by a dynamic multi-swarm particle swarm optimizer","volume":"55","author":"Liang","year":"2011","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/j.cie.2011.02.013","article-title":"A Hybrid Harmony Search Algorithm for the Blocking Permutation Flow Shop Scheduling Problem","volume":"61","author":"Wang","year":"2011","journal-title":"Comput. Ind. Eng."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1016\/j.cor.2008.12.004","article-title":"A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems","volume":"37","author":"Wang","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/j.omega.2010.07.007","article-title":"An iterated greedy algorithm for the flowshop scheduling with blocking","volume":"39","author":"Ribas","year":"2011","journal-title":"Omega"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2880","DOI":"10.1016\/j.cor.2012.02.020","article-title":"A three-phase algorithm for flowshop scheduling with blocking to minimize makespan","volume":"39","author":"Wang","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/j.omega.2012.03.006","article-title":"Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm","volume":"41","author":"Lin","year":"2013","journal-title":"Omega"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1109\/TASE.2012.2219860","article-title":"A high performing memetic algorithm for the flowshop scheduling problem with blocking","volume":"10","author":"Pan","year":"2013","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1504\/EJIE.2013.058392","article-title":"A competitive variable neighbourhood search algorithm for the blocking flow shop problem","volume":"7","author":"Ribas","year":"2013","journal-title":"Eur. J. Ind. Eng."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"4759","DOI":"10.1080\/00207543.2015.1076941","article-title":"New block properties for flowshop scheduling with blocking and their application in an iterated greedy algorithm","volume":"54","author":"Ding","year":"2015","journal-title":"Int. J. Prod. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1590\/S0104-530X2000000300011","article-title":"Minimiza\u00e7\u00e3o do tempo total de atraso no problema de flowshop com buffer zero atrav\u00e9s de busca tabu","volume":"7","author":"Armentano","year":"2000","journal-title":"Gestao Produ\u00e7ao"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"5238","DOI":"10.1080\/00207543.2013.802390","article-title":"An efficient iterated local search algorithm for the total tardiness blocking flow shop problem","volume":"51","author":"Ribas","year":"2013","journal-title":"Int. J. Prod. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"7929","DOI":"10.1016\/j.eswa.2010.04.042","article-title":"Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms","volume":"37","author":"Wang","year":"2010","journal-title":"Expert Syst. Appl."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1016\/S1004-9541(12)60588-6","article-title":"A discrete artificial bee colony algorithm for minimizing the total flow time in the blocking flow shop scheduling","volume":"20","author":"Deng","year":"2012","journal-title":"Chin. J. Chem. Eng."},{"key":"ref_38","first-page":"301","article-title":"An iterated greedy algorithm for solving the blocking flowshop scheduling problem with total flow time criteria","volume":"23","author":"Khorasanian","year":"2012","journal-title":"Int. J. Ind. Eng. Prod. Res."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1874","DOI":"10.1016\/j.cor.2013.02.003","article-title":"Optimizing blocking flow shop scheduling total completion time criterion","volume":"40","author":"Moslehi","year":"2013","journal-title":"Comput. Oper. Res."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.cie.2015.04.013","article-title":"Efficient heuristic algorithms for the blocking flow shop scheduling problem with total flow time minimization","volume":"87","author":"Ribas","year":"2015","journal-title":"Comput. Ind. Eng."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"6155","DOI":"10.1016\/j.eswa.2015.03.026","article-title":"Xavier Tort-Martorell, An efficient Discrete Artificial Bee Colony algorithm for the blocking flow shop problem with total flowtime minimization","volume":"42","author":"Ribas","year":"2015","journal-title":"Expert Syst. Appl."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.omega.2006.11.003","article-title":"Efficient composite heuristics for total flowtime minimization in permutation flowshops","volume":"37","author":"Lia","year":"2009","journal-title":"Omega"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1506","DOI":"10.1016\/j.cor.2011.08.022","article-title":"A Variable Neighborhood Search for Minimizing Total Weighted Tardiness with Sequence Dependent Setup Times on a Single Machine","volume":"39","author":"Kirlik","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"2729","DOI":"10.1080\/00207543.2014.883472","article-title":"An Iterated Local Search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times","volume":"52","author":"Subramanian","year":"2014","journal-title":"Int. J. Prod. Res."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/s10951-013-0351-z","article-title":"Iterated Local Search for single-machine scheduling with sequence dependent setup times to minimize total weighted tardiness","volume":"17","author":"Xu","year":"2014","journal-title":"J. Sched."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1016\/j.asoc.2015.07.050","article-title":"An efficient memetic algorithm for total weighted tardiness minimization in a single machine with setups","volume":"37","author":"Vela","year":"2015","journal-title":"Appl. Soft Comput."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Tasgetiren, M.F., Kizilay, D., Pan, Q.K., and Suganthan, P.N. (2016). Iterated Greedy Algorithms for the Blocking Flowshop Scheduling Problem with Makespan Criterion. Comput. Oper. Res.","DOI":"10.1016\/j.cor.2016.07.002"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","article-title":"Variable neighborhood search","volume":"24","author":"Mladenovic","year":"1997","journal-title":"Comput. Oper. Res."},{"key":"ref_49","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_50","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 with Makespan and Total Flowtime Criteria","volume":"35","author":"Pan","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s00170-007-1099-4","article-title":"A hybrid discrete particle swarm optimization algorithm for the no-wait flow shop scheduling problem with makespan criterion","volume":"38","author":"Pan","year":"2008","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"4737","DOI":"10.1080\/00207540600620849","article-title":"Particle swarm optimization and differential evolution for single machine total weighted tardiness problem","volume":"44","author":"Tasgetiren","year":"2006","journal-title":"Int. J. Prod. Res."},{"key":"ref_53","first-page":"120","article-title":"A particle swarm optimization and differential evolution algorithms for job shop scheduling problem","volume":"3","author":"Tasgetiren","year":"2006","journal-title":"Int. J. Oper. Res."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"1729","DOI":"10.1016\/j.cor.2013.01.005","article-title":"A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem","volume":"40","author":"Tasgetiren","year":"2013","journal-title":"Comput. Oper. Res."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1016\/j.cie.2008.03.003","article-title":"A discrete differential evolution algorithm for the permutation flowshop scheduling problem","volume":"55","author":"Pan","year":"2008","journal-title":"Comput. Ind. Eng."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"1900","DOI":"10.1016\/j.cor.2008.06.007","article-title":"A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times","volume":"36","author":"Tasgetiren","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"3459","DOI":"10.1016\/j.ins.2011.04.018","article-title":"A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops","volume":"181","author":"Tasgetiren","year":"2011","journal-title":"Inf. Sci."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"6758","DOI":"10.1016\/j.apm.2013.02.011","article-title":"A Discrete Artificial Bee Colony Algorithm for the No-Idle Permutation Flowshop Scheduling Problem with the Total Tardiness Criterion","volume":"37","author":"Tasgetiren","year":"2013","journal-title":"Appl. Math. Model."},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"5033","DOI":"10.1080\/00207543.2010.497781","article-title":"A Differential Evolution Algorithm for the No-Idle Flowshop Scheduling Problem with Total Tardiness Criterion","volume":"49","author":"Tasgetiren","year":"2011","journal-title":"Int. J. Prod. Res."},{"key":"ref_60","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_61","unstructured":"Montgomery, D.C. (2008). Design and Analysis of Experiments, John Wiley & Sons."},{"key":"ref_62","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_63","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1198\/000313001317097960","article-title":"On judging the significance of differences by examining the overlap between confidence intervals","volume":"55","author":"Schenker","year":"2001","journal-title":"Am. Stat."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/4\/71\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:33:29Z","timestamp":1760211209000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/4\/71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,20]]},"references-count":63,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2016,12]]}},"alternative-id":["a9040071"],"URL":"https:\/\/doi.org\/10.3390\/a9040071","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,20]]}}}