{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T07:02:23Z","timestamp":1768719743132,"version":"3.49.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,7,20]],"date-time":"2018-07-20T00:00:00Z","timestamp":1532044800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s10951-018-0579-8","type":"journal-article","created":{"date-parts":[[2018,7,20]],"date-time":"2018-07-20T02:40:27Z","timestamp":1532054427000},"page":"465-471","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["The single-processor scheduling problem with time restrictions: complexity and related problems"],"prefix":"10.1007","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2553-4116","authenticated-orcid":false,"given":"Rachid","family":"Benmansour","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver","family":"Braun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sa\u00efd","family":"Hanafi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,7,20]]},"reference":[{"key":"579_CR1","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0305-0548(00)00074-5","volume":"29","author":"AH Abdekhodaee","year":"2002","unstructured":"Abdekhodaee, A. H., & Wirth, A. (2002). Scheduling parallel machines with a single server: Some solvable cases and heuristics. Computers & Operations Research, 29, 295\u2013315.","journal-title":"Computers & Operations Research"},{"key":"579_CR2","unstructured":"Balas, E. (1985). On the facial structure of scheduling polyhedra. In R. W. Cottle (Ed.), Mathematical programming essays in honor of George B. Dantzig Part I. Mathematical Programming Studies (Vol. 24, pp. 179\u2013218). Berlin, Heidelberg: Springer."},{"key":"579_CR3","unstructured":"Benmansour, R., Braun, O., & Allaoui, H. (2015). Modeling the single-processor scheduling problem with time restrictions as a parallel machine scheduling problem. In 7th multidisciplinary international conference on scheduling: Theory and applications (MISTA) (pp. 325\u2013330)."},{"key":"579_CR4","doi-asserted-by":"crossref","unstructured":"Benmansour, R., Braun, O., & Artiba, A. (2014). On the single-processor scheduling problem with time restrictions. In International conference on control, decision and information technologies (CoDIT) (pp. 242\u2013245).","DOI":"10.1109\/CoDIT.2014.6996900"},{"key":"579_CR5","volume-title":"Handbook on scheduling: From theory to applications","author":"J Blazewicz","year":"2007","unstructured":"Blazewicz, J., Ecker, K. H., Pesch, E., Schmidt, G., & Weglarz, J. (2007). Handbook on scheduling: From theory to applications. Berlin: Springer."},{"key":"579_CR6","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. Journal of Scheduling, 17, 399\u2013403.","journal-title":"Journal of Scheduling"},{"key":"579_CR7","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":"579_CR8","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1002\/jos.120","volume":"5","author":"P Brucker","year":"2002","unstructured":"Brucker, P., Dhaenens-Flipo, C., Knust, S., Kravchenko, S. A., & Werner, F. (2002). Complexity results for parallel machine problems with a single server. Journal of Scheduling, 5, 429\u2013457.","journal-title":"Journal of Scheduling"},{"key":"579_CR9","doi-asserted-by":"publisher","first-page":"1493","DOI":"10.1007\/978-1-4613-0303-9_25","volume-title":"Handbook of combinatorial optimization","author":"B Chen","year":"1998","unstructured":"Chen, B., Potts, C. N., & Woeginger, G. J. (1998). A review of machine scheduling: Complexity, algorithms and approximability. In D. Z. Du & P. M. Pardalos (Eds.), Handbook of combinatorial optimization (pp. 1493\u20131641). Boston, MA: Springer."},{"key":"579_CR10","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0166-218X(90)90104-K","volume":"26","author":"ME Dyer","year":"1990","unstructured":"Dyer, M. E., & Wolsey, L. A. (1990). Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics, 26, 255\u2013270.","journal-title":"Discrete Applied Mathematics"},{"key":"579_CR11","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York: W. H. Freeman & Co."},{"issue":"2","key":"579_CR12","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1287\/moor.13.2.330","volume":"13","author":"MR Garey","year":"1988","unstructured":"Garey, M. R., Tarjan, R. E., & Wilfong, G. T. (1988). One-processor scheduling with symmetric earliness and tardiness penalties. Mathematics of Operations Research, 13(2), 330\u2013348.","journal-title":"Mathematics of Operations Research"},{"key":"579_CR13","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1002\/(SICI)1520-6750(200006)47:4<304::AID-NAV3>3.0.CO;2-1","volume":"47","author":"CA Glass","year":"2000","unstructured":"Glass, C. A., Shafransky, Y. M., & Strusevich, V. A. (2000). Scheduling for parallel dedicated machines with a single server. Naval Research Logistics, 47, 304\u2013328.","journal-title":"Naval Research Logistics"},{"key":"579_CR14","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0166-218X(99)00206-1","volume":"102","author":"NG Hall","year":"2000","unstructured":"Hall, N. G., Potts, C. N., & Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. Discrete Applied Mathematics, 102, 223\u2013243.","journal-title":"Discrete Applied Mathematics"},{"key":"579_CR15","doi-asserted-by":"crossref","unstructured":"Hoogeveen, H., & van\u00a0de Velde S. (1995). Formulating a scheduling problem with almost identical jobs by using positional completion times. In Proceedings of the international conference on integer programming and combinatorial optimization (pp. 292\u2013306). Springer.","DOI":"10.1007\/3-540-59408-6_59"},{"key":"579_CR16","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.cie.2008.06.008","volume":"56","author":"A Keha","year":"2009","unstructured":"Keha, A., Khowala, K., & Fowler, J. (2009). Mixed integer programming formulations for single machine scheduling problems. Computers & Industrial Engineering, 56, 357\u2013367.","journal-title":"Computers & Industrial Engineering"},{"key":"579_CR17","doi-asserted-by":"publisher","first-page":"2457","DOI":"10.1016\/j.cor.2011.12.011","volume":"39","author":"MY Kim","year":"2012","unstructured":"Kim, M. Y., & Lee, Y. H. (2012). MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server. Computers & Operations Research, 39, 2457\u20132468.","journal-title":"Computers & Operations Research"},{"key":"579_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0895-7177(97)00236-7","volume":"26","author":"SA Kravchenko","year":"1997","unstructured":"Kravchenko, S. A., & Werner, F. (1997). Parallel machine scheduling problems with a single server. Mathematical and Computer Modelling, 26, 1\u201311.","journal-title":"Mathematical and Computer Modelling"},{"key":"579_CR19","unstructured":"Lasserre, J. B., & Queyranne, M. (1992). Generic scheduling polyhedral and a new mixed-integer formulation for single-machine scheduling. In Proceedings of the 2nd IPCO conference (pp. 136149). Pittsburgh: Carnegie-Mellon University."},{"key":"579_CR20","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","volume":"4","author":"EL Lawler","year":"1993","unstructured":"Lawler, E. L., Lenstra, J. K., Kan, A. H. G. R., & Shmoys, D. B. (1993). Sequencing and scheduling: Algorithms and complexity. Handbooks in Operations Research and Management Science, 4, 445\u2013522.","journal-title":"Handbooks in Operations Research and Management Science"},{"key":"579_CR21","doi-asserted-by":"crossref","DOI":"10.1201\/9780203489802","volume-title":"Handbook of scheduling: Algorithms, models, and performance analysis","author":"JY Leung","year":"2004","unstructured":"Leung, J. Y. (2004). Handbook of scheduling: Algorithms, models, and performance analysis. Boca Raton: CRC Press."},{"key":"579_CR22","first-page":"193","volume":"18","author":"E Mokotoff","year":"2001","unstructured":"Mokotoff, E. (2001). Parallel machine scheduling problems: A survey. Asia-Pacific Journal of Operational Research, 18, 193\u2013242.","journal-title":"Asia-Pacific Journal of Operational Research"},{"key":"579_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26580-3","volume-title":"Scheduling: Theory, algorithms, and systems","author":"ML Pinedo","year":"2016","unstructured":"Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems. Berlin: Springer."},{"key":"579_CR24","unstructured":"Queyranne, M., & Schulz, A. S. (1994). Polyhedral approaches to machine scheduling. Technical Report, TU Berlin, Preprint 408\/1994."},{"key":"579_CR25","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1287\/ijoc.1080.0287","volume":"21","author":"F Sourd","year":"2009","unstructured":"Sourd, F. (2009). New exact algorithms for one-machine earliness\u2013tardiness scheduling. INFORMS Journal on Computing, 21, 167\u2013175.","journal-title":"INFORMS Journal on Computing"},{"key":"579_CR26","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/BF01586059","volume":"54","author":"JP Sousa","year":"1992","unstructured":"Sousa, J. P., & Wolsey, L. A. (1992). A time indexed formulation of non-preemptive single machine scheduling problems. Mathematical Programming, 54, 353\u2013367.","journal-title":"Mathematical Programming"},{"key":"579_CR27","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1016\/j.cie.2010.02.012","volume":"58","author":"Y Unlu","year":"2010","unstructured":"Unlu, Y., & Mason, S. J. (2010). Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems. Computers & Industrial Engineering, 58, 785\u2013800.","journal-title":"Computers & Industrial Engineering"},{"issue":"2","key":"579_CR28","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1287\/ijoc.12.2.111.11896","volume":"12","author":"JM Akker Van den","year":"2000","unstructured":"Van den Akker, J. M., Hurkens, C. A., & Savelsbergh, M. W. (2000). Time-indexed formulations for machine scheduling problems: Column generation. INFORMS Journal on Computing, 12(2), 111\u2013124.","journal-title":"INFORMS Journal on Computing"},{"key":"579_CR29","unstructured":"Zhang, A., Chen, Y., Chen, L., & Chen, G. (2017). On the NP-hardness of scheduling with time restrictions. CoRR. arXiv:1703.00575 ."},{"issue":"4","key":"579_CR30","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. Optimization Letters, 11(4), 715\u2013724.","journal-title":"Optimization Letters"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-018-0579-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-018-0579-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-018-0579-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T23:04:05Z","timestamp":1661641445000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-018-0579-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,20]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["579"],"URL":"https:\/\/doi.org\/10.1007\/s10951-018-0579-8","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,20]]},"assertion":[{"value":"20 July 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}