{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T05:05:31Z","timestamp":1781759131845,"version":"3.54.5"},"reference-count":47,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2019,11,12]],"date-time":"2019-11-12T00:00:00Z","timestamp":1573516800000},"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 job shop scheduling problem with blocking constraints and total tardiness minimization represents a challenging combinatorial optimization problem of high relevance in production planning and logistics. Since general-purpose solution approaches struggle with finding even feasible solutions, a permutation-based heuristic method is proposed here, and the applicability of basic scheduling-tailored mechanisms is discussed. The problem is tackled by a local search framework, which relies on interchange- and shift-based operators. Redundancy and feasibility issues require advanced transformation and repairing schemes. An analysis of the embedded neighborhoods shows beneficial modes of implementation on the one hand and structural difficulties caused by the blocking constraints on the other hand. The applied simulated annealing algorithm generates good solutions for a wide set of benchmark instances. The computational results especially highlight the capability of the permutation-based method in constructing feasible schedules of valuable quality for instances of critical size and support future research on hybrid solution techniques.<\/jats:p>","DOI":"10.3390\/a12110242","type":"journal-article","created":{"date-parts":[[2019,11,13]],"date-time":"2019-11-13T09:11:27Z","timestamp":1573636287000},"page":"242","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems"],"prefix":"10.3390","volume":"12","author":[{"given":"Julia","family":"Lange","sequence":"first","affiliation":[{"name":"Division of Information Process Engineering, FZI Forschungszentrum Informatik Karlsruhe, 76131 Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0709-3591","authenticated-orcid":false,"given":"Frank","family":"Werner","sequence":"additional","affiliation":[{"name":"Fakult\u00e4t f\u00fcr Mathematik, Otto-von-Guericke-Universit\u00e4t Magdeburg, D-39016 Magdeburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,11,12]]},"reference":[{"key":"ref_1","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":"Math. Oper. Res."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1287\/opre.40.1.113","article-title":"Job shop scheduling by simulated annealing","volume":"40","author":"Aarts","year":"1992","journal-title":"Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1287\/mnsc.34.3.391","article-title":"The shifting bottleneck procedure for job shop scheduling","volume":"34","author":"Adams","year":"1988","journal-title":"Manag. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1287\/mnsc.42.6.797","article-title":"A fast taboo search algorithm for the job shop problem","volume":"42","author":"Nowicki","year":"1996","journal-title":"Manag. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/s10878-014-9723-3","article-title":"The blocking job shop with rail-bound transportation","volume":"31","year":"2016","journal-title":"J. Comb. Optim."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1016\/j.ejor.2006.10.034","article-title":"A branch and bound algorithm for scheduling trains in a railway network","volume":"183","author":"Pacciarelli","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2840","DOI":"10.1016\/j.cor.2008.12.012","article-title":"Scheduling trains as a blocking parallel-machine job shop scheduling problem","volume":"36","author":"Liu","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1023\/A:1012260622596","article-title":"A taboo search approach for deadlock-free scheduling of automated manufacturing systems","volume":"12","author":"Mati","year":"2001","journal-title":"J. Intell. Manuf."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/s10951-017-0532-2","article-title":"A neighborhood for complex job shop scheduling problems with regular objectives","volume":"20","year":"2017","journal-title":"J. Sched."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.procir.2017.12.173","article-title":"Optimal Scheduling of AGVs in a Reentrant Blocking Job-shop","volume":"67","author":"Heger","year":"2018","journal-title":"Procedia CIRP"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/s10951-017-0526-0","article-title":"Approaches to modeling train scheduling problems as job-shop problems with blocking constraints","volume":"21","author":"Lange","year":"2018","journal-title":"J. Sched."},{"key":"ref_12","first-page":"2349","article-title":"No-wait and blocking job-shops: Challenging problems for GA\u2019s","volume":"4","author":"Brizuela","year":"2001","journal-title":"Int. Conf. Syst. Man Cybern."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"3643","DOI":"10.1016\/j.dam.2009.02.020","article-title":"A new neighborhood and tabu search for the blocking job shop","volume":"157","author":"Groeflin","year":"2009","journal-title":"Discret. Appl. Math."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1016\/S0377-2217(03)00016-X","article-title":"An efficient genetic algorithm for job shop scheduling with tardiness objectives","volume":"155","author":"Mattfeld","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"ref_15","unstructured":"Lange, J. (2019). Solution Techniques for the Blocking Job Shop Scheduling Problem with Total Tardiness Minimization. [Ph.D. Thesis, Otto-von-Guericke-Universit\u00e4t Magdeburg]."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Lange, J., and Werner, F. (2018). A Permutation-Based Neighborhood for the Blocking Job-Shop Problem with Total Tardiness Minimization. Operations Research Proceedings 2017, Springer International Publishing.","DOI":"10.1007\/978-3-319-89920-6_77"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1016\/S0377-2217(01)00338-1","article-title":"Job-shop scheduling with blocking and no-wait constraints","volume":"143","author":"Mascis","year":"2002","journal-title":"Eur. J. Oper. Res."},{"key":"ref_18","unstructured":"Lange, J., and B\u00fcrgy, R. (2019, January 3\u20137). Mixed-Integer Programming Heuristics for the Blocking Job Shop Scheduling Problem. Proceedings of the 14th Workshop on Models and Algorithms for Planning and Scheduling Problems, MAPSP 2019, Renesse, The Netherlands."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s10951-005-6364-5","article-title":"An advanced tabu search algorithm for the job shop problem","volume":"8","author":"Nowicki","year":"2005","journal-title":"J. Sched."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/s10951-008-0067-7","article-title":"Job shop scheduling with setup times, deadlines and precedence constraints","volume":"11","author":"Balas","year":"2008","journal-title":"J. Sched."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1016\/j.ejor.2017.03.030","article-title":"Extended GRASP for the job shop scheduling problem with total weighted tardiness objective","volume":"261","author":"Bierwirth","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1520-6750(199902)46:1<1::AID-NAV1>3.0.CO;2-#","article-title":"A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop","volume":"46","author":"Pinedo","year":"1999","journal-title":"Nav. Res. Logist. (NRL)"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1080\/002077200291118","article-title":"A revised simulated annealing algorithm for obtaining the minimum total tardiness in job shop scheduling problems","volume":"31","author":"Wang","year":"2000","journal-title":"Int. J. Syst. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s10951-005-4779-7","article-title":"Minimizing total teighted tardiness in a generalized job shop","volume":"8","year":"2005","journal-title":"J. Sched."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"2599","DOI":"10.1016\/j.cor.2006.12.019","article-title":"A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem","volume":"35","author":"Essafi","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1016\/j.cor.2010.09.015","article-title":"A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem","volume":"38","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.ejor.2011.01.046","article-title":"A general approach for optimizing regular criteria in the job-shop scheduling problem","volume":"212","author":"Mati","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"854","DOI":"10.1016\/j.cor.2010.09.014","article-title":"A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective","volume":"38","author":"Zhang","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2097","DOI":"10.1007\/s00500-012-0880-y","article-title":"An efficient hybrid evolutionary algorithm for scheduling with setup times and weighted tardiness minimization","volume":"16","author":"Vela","year":"2012","journal-title":"Soft Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.cor.2015.07.011","article-title":"A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective","volume":"66","author":"Kuhpfahl","year":"2016","journal-title":"Comput. Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1023\/B:ANOR.0000039520.24932.4b","article-title":"A rollout metaheuristic for job shop scheduling problems","volume":"131","author":"Meloni","year":"2004","journal-title":"Ann. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Oddi, A., Rasconi, R., Cesta, A., and Smith, S.F. (2012, January 25\u201329). Iterative Improvement Algorithms for the Blocking Job Shop. Proceedings of the ICAPS, Atibaia, Brazil.","DOI":"10.1609\/icaps.v22i1.13530"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1504\/IJOR.2013.050538","article-title":"Parallel branch-and-bound and parallel PSO algorithms for job shop scheduling problem with blocking","volume":"16","author":"AitZai","year":"2013","journal-title":"Int. J. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1007\/s10732-014-9279-5","article-title":"An iterated greedy metaheuristic for the blocking job shop scheduling problem","volume":"22","author":"Pranzo","year":"2016","journal-title":"J. Heuristics"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Dabah, A., Bendjoudi, A., AitZai, A., and Taboudjemat, N.N. (2019). Efficient parallel tabu search for the blocking job shop scheduling problem. Soft Comput.","DOI":"10.1007\/s00500-019-03871-1"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1016\/j.ejor.2005.12.025","article-title":"Feasible insertions in job shop scheduling, short cycles and stable sets","volume":"177","author":"Klinkert","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_37","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":"Volume 5","author":"Graham","year":"1979","journal-title":"Annals of Discrete Mathematics"},{"key":"ref_38","unstructured":"Pinedo, M. (2016). Scheduling: Theory, Algorithms, and Systems, Springer."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Brucker, P., and Knust, S. (2011). Complex Scheduling, Springer.","DOI":"10.1007\/978-3-642-23929-8"},{"key":"ref_40","unstructured":"B\u0142a\u017cewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., and Weglarz, J. (2007). Handbook on Scheduling: From Theory to Applications, Springer. International Handbook on Information Systems."},{"key":"ref_41","unstructured":"Lawrence, S. (1984). Supplement to Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques, GSIA, Carnegie Mellon University."},{"key":"ref_42","unstructured":"Mascis, A., and Pacciarelli, D. (2000). Machine Scheduling via Alternative Graphs, Universita degli Studi Roma Tre, DIA. Technical Report."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Bierwirth, C., Mattfeld, D.C., and Watson, J.P. (2004). Landscape regularity and random walks for the job-shop scheduling problem. European Conference on Evolutionary Computation in Combinatorial Optimization, Springer.","DOI":"10.1007\/978-3-540-24652-7_3"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"3143","DOI":"10.1016\/j.cor.2005.11.022","article-title":"A review of metrics on permutations for search landscape analysis","volume":"34","author":"Schiavinotto","year":"2007","journal-title":"Comput. Oper. Res."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1080\/02331939108843670","article-title":"Some relations between neighbourhood graphs for a permutation problem","volume":"22","author":"Werner","year":"1991","journal-title":"Optimization"},{"key":"ref_46","unstructured":"Aarts, E.H.L., and Lenstra, J.K. (1997). Machine Scheduling. Local Search in Combinatorial Optimization, Wiley. Chapter 11."},{"key":"ref_47","unstructured":"Lange, J. (2018, January 17\u201320). A comparison of neighborhoods for the blocking job-shop problem with total tardiness minimization. Proceedings of the 16th International Conference of Project Management and Scheduling 208, Rome, Italy."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/11\/242\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:33:53Z","timestamp":1760189633000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/11\/242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,12]]},"references-count":47,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2019,11]]}},"alternative-id":["a12110242"],"URL":"https:\/\/doi.org\/10.3390\/a12110242","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,12]]}}}