{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:39:00Z","timestamp":1740145140720,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,4,5]],"date-time":"2023-04-05T00:00:00Z","timestamp":1680652800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,4,5]],"date-time":"2023-04-05T00:00:00Z","timestamp":1680652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2024,1]]},"DOI":"10.1007\/s11590-023-02000-0","type":"journal-article","created":{"date-parts":[[2023,4,5]],"date-time":"2023-04-05T02:02:42Z","timestamp":1680660162000},"page":"365-375","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the complexity of proportionate open shop and job shop problems"],"prefix":"10.1007","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2460-3140","authenticated-orcid":false,"given":"Abdennour","family":"Azerine","sequence":"first","affiliation":[]},{"given":"Mourad","family":"Boudhar","sequence":"additional","affiliation":[]},{"given":"Djamal","family":"Rebaine","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,5]]},"reference":[{"issue":"1","key":"2000_CR1","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/s10878-021-00755-9","volume":"43","author":"A Azerine","year":"2022","unstructured":"Azerine, A., Boudhar, M., Rebaine, D.: A two-machine no-wait flow shop problem with two competing agents. J. Comb. Optim. 43(1), 168\u2013199 (2022)","journal-title":"J. Comb. Optim."},{"key":"2000_CR2","volume-title":"Computers and intractability: a guide to np-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to np-completeness. Freeman San Francisco (1979)"},{"issue":"3","key":"2000_CR3","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1002\/nav.3800030307","volume":"3","author":"JR Jackson","year":"1956","unstructured":"Jackson, J.R.: An extension of Johnson\u2019s results on job IDT scheduling. Naval Res. Logist. Q. 3(3), 201\u2013203 (1956)","journal-title":"Naval Res. Logist. Q."},{"issue":"1","key":"2000_CR4","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.ejor.2014.11.037","volume":"243","author":"C Koulamas","year":"2015","unstructured":"Koulamas, C., Kyparisis, G.J.: The three-machine proportionate open shop and mixed shop minimum makespan problems. Eur. J. Oper. Res. 243(1), 70\u201374 (2015)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"2000_CR5","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.ejor.2016.01.010","volume":"252","author":"C Koulamas","year":"2016","unstructured":"Koulamas, C., Panwalkar, S.: The proportionate two-machine no-wait job shop scheduling problem. Eur. J. Oper. Res. 252(1), 131\u2013135 (2016)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"2000_CR6","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1287\/moor.6.1.153","volume":"6","author":"EL Lawler","year":"1981","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.: Minimizing maximum lateness in a two-machine open shop. Math. Oper. Res. 6(1), 153\u2013158 (1981)","journal-title":"Math. Oper. Res."},{"issue":"8","key":"2000_CR7","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1016\/S0305-0548(03)00096-0","volume":"31","author":"CF Liaw","year":"2004","unstructured":"Liaw, C.F.: Scheduling two-machine preemptive open shops to minimize total completion time. Comput. Oper. Res. 31(8), 1349\u20131363 (2004)","journal-title":"Comput. Oper. Res."},{"key":"2000_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2019.05.036","volume":"803","author":"L Liu","year":"2020","unstructured":"Liu, L., Chen, Y., Dong, J., Goebel, R., Lin, G., Luo, Y., Ni, G., Su, B., Xu, Y., Zhang, A.: Approximation algorithms for the three-machine proportionate mixed shop scheduling. Theor. Comput. Sci. 803, 57\u201370 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"2000_CR9","unstructured":"Liu, L., Chen, Y., Dong, J., Goebel, R., Lin, G., Luo, Y., Ni, G., Su, B., Zhang, A.: Approximation algorithms for the three-machine proportionate mixed shop scheduling. arXiv preprint arXiv:1809.05745 (2018)"},{"issue":"3","key":"2000_CR10","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1016\/j.ejor.2009.03.048","volume":"201","author":"ME Matta","year":"2010","unstructured":"Matta, M.E., Elmaghraby, S.E.: Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop. Eur. J. Oper. Res. 201(3), 720\u2013728 (2010)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"2000_CR11","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/j.ipl.2014.09.023","volume":"115","author":"B Mor","year":"2015","unstructured":"Mor, B., Mosheiov, G.: A note: minimizing maximum earliness on a proportionate flowshop. Inf. Process. Lett. 115(2), 253\u2013255 (2015)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"2000_CR12","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.1111\/itor.12087","volume":"21","author":"B Naderi","year":"2014","unstructured":"Naderi, B., Zandieh, M., Yazdani, M.: Polynomial time approximation algorithms for proportionate open-shop scheduling. Int. Trans. Oper. Res. 21(6), 1031\u20131044 (2014)","journal-title":"Int. Trans. Oper. Res."},{"key":"2000_CR13","doi-asserted-by":"publisher","first-page":"186805","DOI":"10.1109\/ACCESS.2020.3030694","volume":"8","author":"G Ni","year":"2020","unstructured":"Ni, G., Chen, L.: Improved scheduling for the three-machine proportionate open shop and mixed shop minimum makespan problems. IEEE Access 8, 186805\u2013186812 (2020)","journal-title":"IEEE Access"},{"issue":"7","key":"2000_CR14","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1287\/mnsc.31.7.852","volume":"31","author":"PS Ow","year":"1985","unstructured":"Ow, P.S.: Focused scheduling in proportionate flowshops. Manag. Sci. 31(7), 852\u2013869 (1985)","journal-title":"Manag. Sci."},{"issue":"2","key":"2000_CR15","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1016\/j.ejor.2014.04.030","volume":"238","author":"S Panwalkar","year":"2014","unstructured":"Panwalkar, S., Koulamas, C.: The two-machine no-wait general and proportionate open shop makespan problem. Eur. J. Oper. Res. 238(2), 471\u2013475 (2014)","journal-title":"Eur. J. Oper. Res."},{"key":"2000_CR16","unstructured":"Pinedo, M.: Scheduling Theory: Algorithms and Systems (1995)"},{"key":"2000_CR17","unstructured":"Rachamadugu, R.M.V., Vepsalainen, A., Morton, T.E.: Scheduling in proportionate flowshops. CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST, Tech. rep. (1982)"},{"key":"2000_CR18","doi-asserted-by":"crossref","unstructured":"Sevast\u2019yanov, S.V.: Some positive news on the proportionate open shop problem. \u0421\u0438\u0431\u0438\u0440\u0441\u043a\u0438\u0435 \u044d\u043b\u0435\u043a\u0442\u0440\u043e\u043d\u043d\u044b\u0435 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u0438\u044f 16, 406\u2013426 (2019)","DOI":"10.33048\/semi.2019.16.023"},{"issue":"3","key":"2000_CR19","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1016\/j.ejor.2011.07.053","volume":"216","author":"D Shabtay","year":"2012","unstructured":"Shabtay, D.: The just-in-time scheduling problem in a flow-shop scheduling system. Eur. J. Oper. Res. 216(3), 521\u2013532 (2012)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"2000_CR20","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/(SICI)1099-1425(1998100)1:3<157::AID-JOS12>3.0.CO;2-Y","volume":"1","author":"N Shakhlevich","year":"1998","unstructured":"Shakhlevich, N., Hoogeveen, H., Pinedo, M.: Minimizing total weighted completion time in a proportionate flow shop. J. Sched. 1(3), 157\u2013168 (1998)","journal-title":"J. Sched."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-02000-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-023-02000-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-02000-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,10]],"date-time":"2024-01-10T06:23:44Z","timestamp":1704867824000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-023-02000-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,5]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["2000"],"URL":"https:\/\/doi.org\/10.1007\/s11590-023-02000-0","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2023,4,5]]},"assertion":[{"value":"2 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}