{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T07:54:30Z","timestamp":1762070070919,"version":"build-2065373602"},"reference-count":38,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T00:00:00Z","timestamp":1665705600000},"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>Cyclic scheduling is of vital importance in a repetitive discrete manufacturing environment. We investigate scheduling in the context of general cyclic job shops with blocking where there are no intermediate buffers between the machines. We also consider sequence-dependent setups (anticipatory and nonanticipatory), which commonly appear in different manufacturing environments. The choice of blocking condition, that is whether the sequence-dependent setups are anticipatory or not, significantly impacts the optimal schedules. We provide a novel mixed-integer programming (MIP) model for the above problem, namely blocking cyclic job-shop scheduling. Furthermore, we study the impact of sequence-dependent setups in this research. The problem is analysed in detail with respect to anticipatory and nonanticipatory setups and the efficiency of the proposed model is investigated via a computational study that is conducted on a set of randomly generated problem instances. The proposed MIP models are capable of solving small-to-medium-sized problems. Moreover, the analysis presented demonstrates that anticipatory setups directly affect blocking conditions, since intermediate buffers between the machines are not present. Hence, in systems with anticipatory setups, cycle times increase to a greater extent compared to systems with nonanticipatory setups.<\/jats:p>","DOI":"10.3390\/a15100375","type":"journal-article","created":{"date-parts":[[2022,10,16]],"date-time":"2022-10-16T21:10:10Z","timestamp":1665954610000},"page":"375","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Blocking Cyclic Job-Shop Scheduling Problems"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3660-8408","authenticated-orcid":false,"given":"Atabak","family":"Elmi","sequence":"first","affiliation":[{"name":"School of Information Technology, Faculty of Science, Engineering and Built Environment, Deakin University, Geelong, VIC 3125, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8011-933X","authenticated-orcid":false,"given":"Dhananjay R.","family":"Thiruvady","sequence":"additional","affiliation":[{"name":"School of Information Technology, Faculty of Science, Engineering and Built Environment, Deakin University, Geelong, VIC 3125, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1101-8359","authenticated-orcid":false,"given":"Andreas T.","family":"Ernst","sequence":"additional","affiliation":[{"name":"School of Mathematics, Faculty of Science, Monash University, Melbourne, VIC 3800, Australia"}]}],"member":"1968","published-online":{"date-parts":[[2022,10,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s10951-005-1639-4","article-title":"Tabu search algorithms for cyclic machine scheduling problems","volume":"8","author":"Brucker","year":"2005","journal-title":"J. Sched."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/0377-2217(94)90332-8","article-title":"Study of a NP-hard cyclic scheduling problem: The recurrent job-shop","volume":"72","author":"Hanen","year":"1994","journal-title":"Eur. J. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Brucker, P. (2001). Multiprocessor tasks. Scheduling Algorithms, Springer.","DOI":"10.1007\/978-3-662-04550-3"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.ifacol.2019.10.029","article-title":"Designing cyclic schedules for streaming repetitive job-shop manufacturing systems with blocking and no-wait constraints","volume":"52","author":"Pempera","year":"2019","journal-title":"IFAC-PapersOnLine"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1016\/j.cie.2010.03.013","article-title":"Complexity of cyclic scheduling problems: A state-of-the-art survey","volume":"59","author":"Levner","year":"2010","journal-title":"Comput. Ind. Eng."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s10589-009-9239-4","article-title":"A cyclic scheduling problem with an undetermined number of parallel identical processors","volume":"48","year":"2011","journal-title":"Comput. Optim. Appl."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1023\/A:1024008726557","article-title":"Complexity of one-cycle robotic flow-shops","volume":"6","author":"Brauner","year":"2003","journal-title":"J. Sched."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1057\/palgrave.jors.2600535","article-title":"Stochastic cyclic flow lines: Non-blocking, Markovian models","volume":"49","author":"Lee","year":"1998","journal-title":"J. Oper. Res. Soc."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s10589-009-9244-7","article-title":"Multi-population interactive coevolutionary algorithm for flexible job shop scheduling problems","volume":"48","author":"Xing","year":"2011","journal-title":"Comput. Optim. Appl."},{"key":"ref_10","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_11","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_12","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1016\/j.cor.2009.08.001","article-title":"A two-stage flow shop scheduling problem on a batching machine and a discrete machine with blocking and shared setup times","volume":"37","author":"Gong","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1016\/j.ejor.2004.08.046","article-title":"Complexity of flowshop scheduling problems with a new blocking constraint","volume":"169","author":"Martinez","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_14","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_15","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/jos.92","article-title":"Cyclic scheduling in a robotic production line","volume":"5","author":"Kats","year":"2002","journal-title":"J. Sched."},{"key":"ref_16","unstructured":"Dawande, M.W., Geismar, H.N., Sethi, S.P., and Sriskandarajah, C. (2007). Throughput Optimization in Robotic Cells, Springer Science & Business Media."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1007\/s10589-012-9499-2","article-title":"The resource-constrained modulo scheduling problem: An experimental study","volume":"54","author":"Ayala","year":"2013","journal-title":"Comput. Optim. Appl."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1016\/j.ejor.2018.02.021","article-title":"Open shop cyclic scheduling","volume":"269","author":"Pempera","year":"2018","journal-title":"Eur. J. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1109\/TASE.2018.2878063","article-title":"A cyclic scheduling approach to single-arm cluster tools with multiple wafer types and residency time constraints","volume":"16","author":"Wang","year":"2018","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_20","unstructured":"Elmi, A., Nazari, A., Thiruvady, D., and Durmusoglu, A. (2020). Cyclic Flow Shop Robotic Cell Scheduling Problem With Multiple Part Types. IEEE Trans. Eng. Manag."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/j.cie.2015.01.004","article-title":"Block approach to the cyclic flow shop scheduling","volume":"81","author":"Wodecki","year":"2015","journal-title":"Comput. Ind. Eng."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s10479-007-0276-z","article-title":"Cyclic job shop scheduling problems with blocking","volume":"159","author":"Brucker","year":"2008","journal-title":"Ann. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0360-8352(97)00325-2","article-title":"Petri net modeling and scheduling for cyclic job shops with blocking","volume":"34","author":"Song","year":"1998","journal-title":"Comput. Ind. Eng."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.ejor.2003.03.001","article-title":"A genetic approach to solving the problem of cyclic job shop scheduling with linear constraints","volume":"161","author":"Cavory","year":"2005","journal-title":"Eur. J. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1016\/j.jmsy.2013.02.001","article-title":"Recurrent neural network approach for cyclic job shop scheduling problem","volume":"32","author":"Kechadi","year":"2013","journal-title":"J. Manuf. Syst."},{"key":"ref_26","unstructured":"Kampmeyer, T. (2006). Cyclic Scheduling Problems. [Ph.D. Thesis, Universit\u00e4t Osnabr\u00fcck]."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"2561","DOI":"10.1016\/j.dam.2008.03.029","article-title":"A general model for cyclic machine scheduling problems","volume":"156","author":"Brucker","year":"2008","journal-title":"Discret. Appl. Math."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1924","DOI":"10.1016\/j.dam.2012.04.001","article-title":"A mixed integer programming model for the cyclic job-shop problem with transportation","volume":"160","author":"Brucker","year":"2012","journal-title":"Discret. Appl. Math."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"3200","DOI":"10.1016\/j.cor.2012.04.008","article-title":"A branch and bound algorithm for the cyclic job-shop problem with transportation","volume":"39","author":"Brucker","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s10479-019-03387-9","article-title":"A mixed integer linear programming modelling for the flexible cyclic jobshop problem","volume":"285","author":"Quinton","year":"2020","journal-title":"Ann. Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/j.rcim.2017.03.004","article-title":"Pure cycles in two-machine dual-gripper robotic cells","volume":"48","author":"Gultekin","year":"2017","journal-title":"Robot. Comput.-Integr. Manuf."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"3613","DOI":"10.1007\/s00170-019-03739-6","article-title":"Process sequencing for a pick-and-place robot in a real-life flexible robotic cell","volume":"103","author":"Shavarani","year":"2019","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"101822","DOI":"10.1016\/j.rcim.2019.101822","article-title":"Stochastic optimization of two-machine flow shop robotic cells with controllable inspection times: From theory toward practice","volume":"61","author":"Foumani","year":"2020","journal-title":"Robot. Comput.-Integr. Manuf."},{"key":"ref_34","unstructured":"Panwalkar, S., Dudek, R., and Smith, M. Sequencing research and the industrial scheduling problem. Proceedings of the Symposium on the Theory of Scheduling and Its Applications."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s00170-009-2388-x","article-title":"A parallel genetic algorithm for a flexible job-shop scheduling problem with sequence dependent setups","volume":"49","author":"Defersha","year":"2010","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Framinan, J.M., Leisten, R., and Garc\u00eda, R.R. (2014). Manufacturing scheduling systems. An integrated view on Models, Methods and Tools, Springer.","DOI":"10.1007\/978-1-4471-6272-8"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1145\/321043.321046","article-title":"Integer programming formulation of traveling salesman problems","volume":"7","author":"Miller","year":"1960","journal-title":"J. ACM (JACM)"},{"key":"ref_38","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."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/10\/375\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:54:01Z","timestamp":1760144041000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/10\/375"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,14]]},"references-count":38,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2022,10]]}},"alternative-id":["a15100375"],"URL":"https:\/\/doi.org\/10.3390\/a15100375","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,10,14]]}}}