{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T11:28:55Z","timestamp":1784287735482,"version":"3.55.0"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hochschule Trier"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cent Eur J Oper Res"],"published-print":{"date-parts":[[2023,3]]},"abstract":"Abstract<\/jats:title>In the single-processor scheduling problem with time restrictions there is one main processor and B<\/jats:italic> resources that are used to execute the jobs. A perfect schedule<\/jats:italic> has no idle times or gaps on the main processor and the makespan is therefore equal to the sum of the processing times. In general, more resources result in smaller makespans, and as it is in practical applications often more economic not to mobilize resources that will be unnecessary and expensive, we investigate in this paper the problem to find the smallest number B<\/jats:italic> of resources that make a perfect schedule possible. We show that the decision version of this problem is NP-complete, derive new structural properties of perfect schedules, and we describe a Mixed Integer Linear Programming (MIP) formulation to solve the problem. A large number of computational tests show that (for our randomly chosen problem instances) only $$B=3$$<\/jats:tex-math>\n \n B<\/mml:mi>\n =<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> or $$B=4$$<\/jats:tex-math>\n \n B<\/mml:mi>\n =<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> resources are sufficient for a perfect schedule.\n<\/jats:p>","DOI":"10.1007\/s10100-022-00803-7","type":"journal-article","created":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T19:02:56Z","timestamp":1653591776000},"page":"191-204","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the minimum number of resources for a perfect schedule"],"prefix":"10.1007","volume":"31","author":[{"given":"Rachid","family":"Benmansour","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5155-3033","authenticated-orcid":false,"given":"Oliver","family":"Braun","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,5,26]]},"reference":[{"key":"803_CR1","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/s10951-018-0579-8","volume":"22","author":"R Benmansour","year":"2018","unstructured":"Benmansour R, Braun O, Hanafi S (2018) The single processor scheduling problem with time restrictions: complexity and related problems. J Sched 22:465\u2013471","journal-title":"J Sched"},{"key":"803_CR2","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-030-15843-9_16","volume":"11328","author":"R Benmansour","year":"2019","unstructured":"Benmansour R, Braun O, Hanafi S, Mladenovic N (2019) Using a variable neighborhood search to solve the single processor scheduling problem with time restrictions. Lect Notes Comput Sci 11328:202\u2013215","journal-title":"Lect Notes Comput Sci"},{"key":"803_CR3","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s10951-013-0342-0","volume":"17","author":"O Braun","year":"2014","unstructured":"Braun O, Chung F, Graham R (2014) Single-processor scheduling with time restrictions. J Sched 17:399\u2013403","journal-title":"J Sched"},{"key":"803_CR4","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/s00291-016-0431-5","volume":"38","author":"O Braun","year":"2016","unstructured":"Braun O, Chung F, Graham R (2016) Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions. OR Spectrum 38:531\u2013540","journal-title":"OR Spectrum"},{"key":"803_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0895-7177(97)00236-7","volume":"26","author":"SA Kravchenko","year":"1997","unstructured":"Kravchenko SA, Werner F (1997) Parallel machine scheduling problems with a single server. Math Comput Model 26:1\u201311","journal-title":"Math Comput Model"},{"key":"803_CR6","doi-asserted-by":"publisher","first-page":"1243","DOI":"10.1287\/opre.2013.1208","volume":"61","author":"K Rustogi","year":"2013","unstructured":"Rustogi K, Strusevich VA (2013) Parallel machine scheduling: impact of adding extra machines. Oper Res 61:1243\u20131257","journal-title":"Oper Res"},{"key":"803_CR7","doi-asserted-by":"crossref","unstructured":"Ruiz R, Vallada E, Fern\u00e1ndez-Mart\u00ednez C (2009) Scheduling in flowshops with no-idle machines. In: Uday KC (ed) Computational intelligence in flow shop and job shop scheduling. Springer, Berlin, pp 21\u201351","DOI":"10.1007\/978-3-642-02836-6_2"},{"key":"803_CR8","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.disopt.2017.12.001","volume":"28","author":"A Zhang","year":"2017","unstructured":"Zhang A, Chen Y, Chen L, Chen G (2017) On the NP-hardness of scheduling with time restrictions. Discret Optim 28:54\u201362","journal-title":"Discret Optim"},{"key":"803_CR9","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/s11590-016-1038-0","volume":"11","author":"A Zhang","year":"2017","unstructured":"Zhang A, Ye F, Chen Y, Chen G (2017) Better permutations for the single-processor scheduling with time restrictions. Optim Lett 11:715\u2013724","journal-title":"Optim Lett"}],"container-title":["Central European Journal of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-022-00803-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10100-022-00803-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-022-00803-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,21]],"date-time":"2023-01-21T10:17:07Z","timestamp":1674296227000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10100-022-00803-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,26]]},"references-count":9,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["803"],"URL":"https:\/\/doi.org\/10.1007\/s10100-022-00803-7","relation":{},"ISSN":["1435-246X","1613-9178"],"issn-type":[{"value":"1435-246X","type":"print"},{"value":"1613-9178","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,26]]},"assertion":[{"value":"29 April 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}