{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T19:04:28Z","timestamp":1771009468617,"version":"3.50.1"},"reference-count":11,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2019,11,25]],"date-time":"2019-11-25T00:00:00Z","timestamp":1574640000000},"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>We address some special cases of job shop and flow shop scheduling problems with s-precedence constraints. Unlike the classical setting, in which precedence constraints among the tasks of a job are finish\u2013start, here the task of a job cannot start before the task preceding it has started. We give polynomial exact algorithms for the following problems: a two-machine job shop with two jobs when recirculation is allowed (i.e., jobs can visit the same machine many times), a two-machine flow shop, and an m-machine flow shop with two jobs. We also point out some special cases whose complexity status is open.<\/jats:p>","DOI":"10.3390\/a12120250","type":"journal-article","created":{"date-parts":[[2019,11,25]],"date-time":"2019-11-25T05:52:58Z","timestamp":1574661178000},"page":"250","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Some Results on Shop Scheduling with S-Precedence Constraints among Job Tasks"],"prefix":"10.3390","volume":"12","author":[{"given":"Alessandro","family":"Agnetis","sequence":"first","affiliation":[{"name":"Dipartimento di Ingegneria dell\u2019Informazione e Scienze Matematiche, Universit\u00e0 di Siena, SI 53100 Siena, Italy"}]},{"given":"Fabrizio","family":"Rossi","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria e Scienze dell\u2019Informazione e Matematica, Universit\u00e0 di L\u2019Aquila, AQ 67100 L\u2019Aquila, Italy"}]},{"given":"Stefano","family":"Smriglio","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria e Scienze dell\u2019Informazione e Matematica, Universit\u00e0 di L\u2019Aquila, AQ 67100 L\u2019Aquila, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2019,11,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1080\/07408171003670975","article-title":"Parallel machine scheduling with s-precedence constraints","volume":"42","author":"Kim","year":"2010","journal-title":"IIE Trans."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"698","DOI":"10.1016\/j.cor.2007.10.025","article-title":"Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints","volume":"36","author":"Kim","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1016\/j.mcm.2011.03.001","article-title":"Scheduling of uniform parallel machines with s-precedence constraints","volume":"54","author":"Kim","year":"2011","journal-title":"Math. Comput. Model."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1007\/s00224-011-9336-5","article-title":"Scheduling with Bully Selfish Jobs","volume":"50","author":"Tamir","year":"2012","journal-title":"Theory Comput. Syst."},{"key":"ref_5","unstructured":"Demeulemeester, E.L., and Herroelen, W.S. (2006). Project Scheduling, a Research Handbook, Springer Science & Business Media."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1287\/mnsc.39.3.294","article-title":"Flow Management in Flexible Manufacturing Cells with Pipeline Operations","volume":"39","author":"Agnetis","year":"1993","journal-title":"Manag. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1031","DOI":"10.1287\/trsc.2017.0750","article-title":"Time-indexed formulations for the runway scheduling problem","volume":"51","author":"Avella","year":"2017","journal-title":"Transp. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/j.dam.2015.07.042","article-title":"Scheduling co-operating stacking cranes with predetermined container sequences","volume":"201","author":"Briskorn","year":"2016","journal-title":"Discret. Appl. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/S0377-2217(03)00434-X","article-title":"A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recirculation","volume":"159","author":"Bertel","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"ref_10","unstructured":"Pinedo, M. (2018). Scheduling, Theory, Algorithms and Systems, Springer."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/s00186-006-0127-8","article-title":"Complexity of shop scheduling problems with fixed number of jobs: A survey","volume":"65","author":"Brucker","year":"2007","journal-title":"Math. Methods Oper. Res."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/12\/250\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:37:14Z","timestamp":1760189834000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/12\/250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,25]]},"references-count":11,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2019,12]]}},"alternative-id":["a12120250"],"URL":"https:\/\/doi.org\/10.3390\/a12120250","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,25]]}}}