{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T02:58:27Z","timestamp":1763348307451},"reference-count":49,"publisher":"MIT Press","issue":"3","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The two-machine permutation flow shop scheduling problem with buffer is studied for the special case that all processing times on one of the two machines are equal to a constant c. This case is interesting because it occurs in various applications, for example, when one machine is a packing machine or when materials have to be transported. Different types of buffers and buffer usage are considered. It is shown that all considered buffer flow shop problems remain NP-hard for the makespan criterion even with the restriction to equal processing times on one machine. However, the special case where the constant c is larger or smaller than all processing times on the other machine is shown to be polynomially solvable by presenting an algorithm (2BF-OPT) that calculates optimal schedules in O(nlogn) steps. Two heuristics for solving the NP-hard flow shop problems are proposed: (i) a modification of the commonly used NEH heuristic (mNEH) and (ii) an Iterated Local Search heuristic (2BF-ILS) that uses the mNEH heuristic for computing its initial solution. It is shown experimentally that the proposed 2BF-ILS heuristic obtains better results than two state-of-the-art algorithms for buffered flow shop problems from the literature and an Ant Colony Optimization algorithm. In addition, it is shown experimentally that 2BF-ILS obtains the same solution quality as the standard NEH heuristic, however, with a smaller number of function evaluations.<\/jats:p>","DOI":"10.1162\/evco_a_00287","type":"journal-article","created":{"date-parts":[[2020,12,22]],"date-time":"2020-12-22T11:48:41Z","timestamp":1608637721000},"page":"415-439","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":5,"title":["Iterated Local Search and Other Algorithms for Buffered Two-Machine Permutation Flow Shops with Constant Processing Times on One Machine"],"prefix":"10.1162","volume":"29","author":[{"given":"Hoang Thanh","family":"Le","sequence":"first","affiliation":[{"name":"Department of Computer Science, Leipzig University, Leipzig, 04109, Germany lht@informatik.uni-leipzig.de"}]},{"given":"Philine","family":"Geser","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Leipzig University, Leipzig, 04109, Germany philine-geser@gmx.net"}]},{"given":"Martin","family":"Middendorf","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Leipzig University, Leipzig, 04109, Germany middendorf@informatik.uni-leipzig.de"}]}],"member":"281","published-online":{"date-parts":[[2021,9,1]]},"reference":[{"issue":"2","key":"2021090111592154800_B1","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1002\/(SICI)1520-6750(199803)45:2<141::AID-NAV2>3.0.CO;2-8","article-title":"An exact algorithm for the batch sequencing problem in a two-machine flow shop with limited buffer","volume":"45","author":"Agnetis","year":"1998","journal-title":"Naval Research Logistics"},{"issue":"1","key":"2021090111592154800_B2","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1080\/07408178608975325","article-title":"Simulated versus real life data in testing the efficiency of scheduling algorithms","volume":"18","author":"Amar","year":"1986","journal-title":"IIE Transactions"},{"key":"2021090111592154800_B3","first-page":"1139","volume-title":"Optimization of complex systems: Theory, models, algorithms and applications","author":"Berli\u0144ska","year":"2019"},{"issue":"4","key":"2021090111592154800_B4","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/s00291-003-0133-7","article-title":"Flow-shop problems with intermediate buffers","volume":"25","author":"Brucker","year":"2003","journal-title":"Operations Research Spektrum"},{"key":"2021090111592154800_B5","first-page":"261:148","article-title":"Flexible flow shop with dedicated buffers","author":"Ernst","year":"2019","journal-title":"Discrete Applied Mathematics"},{"key":"2021090111592154800_B6","first-page":"60:27","article-title":"NEH-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness","author":"Fernandez-Viagas","year":"2015","journal-title":"Computers & Operations Research"},{"issue":"8","key":"2021090111592154800_B7","doi-asserted-by":"crossref","first-page":"2267","DOI":"10.1080\/00207543.2011.565813","article-title":"Optimisation of flow-shop scheduling with batch processor and limited buffer","volume":"50","author":"Fu","year":"2012","journal-title":"International Journal of Production Research"},{"issue":"2","key":"2021090111592154800_B8","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.orl.2015.12.012","article-title":"Permutation schedules for a two-machine flow shop with storage","volume":"44","author":"Fung","year":"2016","journal-title":"Operation Research Letters"},{"key":"2021090111592154800_B9","first-page":"49:237","article-title":"Flexible flow shop with storage: Complexity and optimisation methods","author":"Fung","year":"2016","journal-title":"IFAC-PapersOnLine"},{"key":"2021090111592154800_B10","first-page":"44:510","article-title":"A survey of machine scheduling problems with blocking and no-wait in process","author":"G. Hall","year":"1996","journal-title":"Operations Research"},{"issue":"2","key":"2021090111592154800_B11","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":"Mathematics of Operations Research"},{"year":"2017","author":"Geser","key":"2021090111592154800_B12"},{"issue":"5","key":"2021090111592154800_B13","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1287\/opre.12.5.655","article-title":"Sequencing a one state-variable machine: A solvable case of the traveling salesman problem","volume":"12","author":"Gilmore","year":"1964","journal-title":"Operations Research"},{"key":"2021090111592154800_B14","first-page":"5:287","article-title":"Optimization and approximation in deterministic sequencing and scheduling: A survey","author":"Graham","year":"1979","journal-title":"Annals of Discrete Mathematics"},{"key":"2021090111592154800_B15","first-page":"52-53:143","article-title":"Efficient Lagrangian heuristics for the two-stage flow shop with job dependent buffer requirements","author":"Gu","year":"2018","journal-title":"Journal of Discrete Algorithms"},{"issue":"5","key":"2021090111592154800_B16","doi-asserted-by":"crossref","first-page":"1984","DOI":"10.1016\/j.amc.2009.07.033","article-title":"A note of using effective immune based approach for the flow shop scheduling with buffers","volume":"215","author":"Hsieh","year":"2009","journal-title":"Applied Mathematics and Computation"},{"issue":"1","key":"2021090111592154800_B17","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":"Naval Research Logistics Quarterly"},{"key":"2021090111592154800_B18","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/978-3-030-22629-9_24","volume-title":"Mathematical optimization theory and operations research","author":"Kononov","year":"2019"},{"issue":"1","key":"2021090111592154800_B19","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1134\/S1990478913010067","article-title":"The variable neighborhood search for the two machine flow shop problem with a passive prefetch","volume":"7","author":"Kononova","year":"2013","journal-title":"Journal of Applied and Industrial Mathematics"},{"key":"2021090111592154800_B20","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/978-3-030-16711-0_4","volume-title":"Evolutionary computation in combinatorial optimization","author":"Le","year":"2019"},{"issue":"11","key":"2021090111592154800_B21","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":"International Journal of Production Research"},{"key":"2021090111592154800_B22","first-page":"316:487","article-title":"Solving the large-scale hybrid flow shop scheduling problem with limited buffers by a hybrid artificial bee colony algorithm","author":"Li","year":"2015","journal-title":"Information Sciences"},{"issue":"4","key":"2021090111592154800_B23","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/s10845-005-1658-1","article-title":"A tabu search algorithm based on new block properties and speed-up method for permutation flow-shop with finite intermediate storage","volume":"16","author":"Li","year":"2005","journal-title":"Journal of Intelligent Manufacturing"},{"issue":"4","key":"2021090111592154800_B24","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/s12293-019-00290-5","article-title":"Multi-objective flow shop scheduling with limited buffers using hybrid self-adaptive differential evolution","volume":"11","author":"Liang","year":"2019","journal-title":"Memetic Computing"},{"issue":"1","key":"2021090111592154800_B25","doi-asserted-by":"crossref","DOI":"10.1016\/j.is.2012.05.008","article-title":"Sequence optimization for media objects with due date constraints in multimedia presentations from digital libraries","volume":"38","author":"Lin","year":"2013","journal-title":"Information Systems"},{"issue":"4","key":"2021090111592154800_B26","doi-asserted-by":"crossref","first-page":"1158","DOI":"10.1016\/j.cor.2008.01.002","article-title":"A two-machine flowshop problem with processing time-dependent buffer constraints\u2014An application in multimedia presentations","volume":"36","author":"Lin","year":"2009","journal-title":"Computers & Operations Research"},{"issue":"9","key":"2021090111592154800_B27","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":"Computers & Operations Research"},{"issue":"2","key":"2021090111592154800_B28","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/j.ijpe.2008.11.007","article-title":"Scheduling a flow-shop with combined buffer conditions","volume":"117","author":"Liu","year":"2009","journal-title":"International Journal of Production Economics"},{"key":"2021090111592154800_B29","first-page":"193:21","article-title":"A new improved NEH heuristic for permutation flowshop scheduling problems","author":"Liu","year":"2017"},{"key":"2021090111592154800_B30","first-page":"3:43","article-title":"The irace package: Iterated racing for automatic algorithm configuration","author":"L\u00f3pez-Ib\u00e1\u00f1ez","year":"2016","journal-title":"Operations Research Perspectives"},{"key":"2021090111592154800_B31","first-page":"169:855","article-title":"Complexity of flowshop scheduling problems with a new blocking constraint","author":"Martinez","year":"2006","journal-title":"European Journal of Operational Research"},{"key":"2021090111592154800_B32","article-title":"Two-machine flow shops with an optimal permutation schedule under a storage constraint","author":"Min","year":"2019","journal-title":"Journal of Scheduling"},{"key":"2021090111592154800_B33","first-page":"52:260","article-title":"A hybrid variable neighborhood search algorithm for solving the limited-buffer permutation flow shop scheduling problem with the makespan criterion","author":"Moslehi","year":"2014","journal-title":"Computers & Operations Research"},{"key":"2021090111592154800_B34","first-page":"11:91","article-title":"A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem","author":"Nawaz","year":"1983","journal-title":"Omega"},{"key":"2021090111592154800_B35","first-page":"11:5270","article-title":"A chaotic harmony search algorithm for the flow shop scheduling problem with limited buffers","author":"Pan","year":"2011","journal-title":"Applied Soft Computing"},{"issue":"3","key":"2021090111592154800_B36","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1016\/j.ins.2010.10.009","article-title":"An effective hybrid discrete differential evolution algorithm for the flow shop scheduling with intermediate buffers","volume":"181","author":"Pan","year":"2011","journal-title":"Information Science"},{"issue":"3","key":"2021090111592154800_B37","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/322203.322213","article-title":"Flowshop scheduling with limited temporary storage","volume":"27","author":"Papadimitriou","year":"1980","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"3","key":"2021090111592154800_B38","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1016\/S0377-2217(03)00264-9","article-title":"Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times","volume":"153","author":"Pranzo","year":"2004","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"2021090111592154800_B39","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.cor.2007.08.007","article-title":"An effective hybrid de-based algorithm for multi-objective flow shop scheduling with limited buffers","volume":"36","author":"Qian","year":"2009","journal-title":"Computers & Operations Research"},{"issue":"1","key":"2021090111592154800_B40","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":"Computers & Operations Research"},{"key":"2021090111592154800_B41","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1109\/CCDC.2013.6561043","volume-title":"25th Chinese Control and Decision Conference (CCDC)","author":"Sang","year":"2013"},{"key":"2021090111592154800_B42","first-page":"64:278","article-title":"Benchmarks for basic scheduling problems","author":"Taillard","year":"1993","journal-title":"European Journal of Operational Research"},{"key":"2021090111592154800_B43","first-page":"240:666","article-title":"New hard benchmark for flowshop scheduling problems minimising makespan","author":"Vallada","year":"2015","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"2021090111592154800_B44","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1057\/jors.2010.132","article-title":"On the automatic discovery of variants of the NEH procedure for flow shop scheduling using genetic programming","volume":"62","author":"V\u00e1zquez-Rodr\u00edguez","year":"2011","journal-title":"Journal of the Operational Research Society"},{"key":"2021090111592154800_B45","first-page":"33:2960","article-title":"An effective hybrid genetic algorithm for flow shop scheduling with limited buffers","author":"Wang","year":"2006","journal-title":"Computers & Operations Research"},{"issue":"2","key":"2021090111592154800_B46","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1287\/ijoc.14.2.98.120","article-title":"Contrasting structured and random permutation flow-shop scheduling problems: Search-space topology and algorithm performance","volume":"14","author":"Watson","year":"2002","journal-title":"INFORMS Journal on Computing"},{"issue":"3","key":"2021090111592154800_B47","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1109\/MCI.2014.2326101","article-title":"Benchmarking optimization algorithms: An open source framework for the traveling salesman problem","volume":"9","author":"Weise","year":"2014","journal-title":"IEEE Computational Intelligence Magazine"},{"key":"2021090111592154800_B48","first-page":"108:33","article-title":"Differential evolution metaheuristics for distributed limited-buffer flowshop scheduling with makespan criterion","author":"Zhang","year":"2019","journal-title":"Computers and Operations Research"},{"issue":"9","key":"2021090111592154800_B49","doi-asserted-by":"crossref","first-page":"3471","DOI":"10.1007\/s11771-015-2887-x","article-title":"An effective discrete artificial bee colony algorithm for flow shop scheduling problem with intermediate buffers","volume":"22","author":"Zhang","year":"2015","journal-title":"Journal of Central South University"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/direct.mit.edu\/evco\/article-pdf\/29\/3\/415\/1959478\/evco_a_00287.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/direct.mit.edu\/evco\/article-pdf\/29\/3\/415\/1959478\/evco_a_00287.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T08:00:26Z","timestamp":1630483226000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/29\/3\/415\/97352\/Iterated-Local-Search-and-Other-Algorithms-for"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"references-count":49,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,9,1]]},"published-print":{"date-parts":[[2021,9,1]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00287","relation":{},"ISSN":["1530-9304"],"issn-type":[{"type":"electronic","value":"1530-9304"}],"subject":[],"published-other":{"date-parts":[[2021]]},"published":{"date-parts":[[2021]]}}}