{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T02:05:24Z","timestamp":1767924324428,"version":"3.49.0"},"reference-count":14,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11801310"],"award-info":[{"award-number":["11801310"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11771251"],"award-info":[{"award-number":["11771251"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["12001313"],"award-info":[{"award-number":["12001313"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Province Natural Science Foundation of Shandong","award":["ZR2020MA028"],"award-info":[{"award-number":["ZR2020MA028"]}]},{"name":"Province Natural Science Foundation of Shandong","award":["ZR2019MA061"],"award-info":[{"award-number":["ZR2019MA061"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:p> In this paper, we consider the parallel-machine scheduling with step-deteriorating jobs. The actual processing time of each job deteriorates as a step function if its starting time is beyond a given deteriorating date. We focus on the case of the common job deteriorating date. For the minimization problem of total completion time, we first show that the problem is NP-hard in the strong sense. Then we propose one property of any optimal schedule. Furthermore, we prove that two special cases of common normal processing time or common penalty are polynomially solvable. For the minimization problem of total weighted completion time, we analyze the NP-hardness and present a polynomial time optimal algorithm for the case of common normal processing time and common penalty. <\/jats:p>","DOI":"10.1142\/s0217595922400115","type":"journal-article","created":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T12:11:54Z","timestamp":1644927114000},"source":"Crossref","is-referenced-by-count":11,"title":["Parallel-Machine Scheduling with Step-Deteriorating Jobs to Minimize the Total (Weighted) Completion Time"],"prefix":"10.1142","volume":"40","author":[{"given":"Cuixia","family":"Miao","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China"}]},{"given":"Fanyu","family":"Kong","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China"}]},{"given":"Juan","family":"Zou","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China"}]},{"given":"Ran","family":"Ma","sequence":"additional","affiliation":[{"name":"School of Management Engineering, Qingdao University of Technology, Qingdao 266525, P. R. China"},{"name":"University Research Center for Smart City, Construction and Management of Shandong Province, Qingdao 266525, P. R. China"}]},{"given":"Yujia","family":"Huo","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2022,2,14]]},"reference":[{"key":"S0217595922400115BIB001","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1016\/S0377-2217(00)00284-8","volume":"152","author":"Cheng TCE","year":"2001","journal-title":"European Journal of Operational Research"},{"key":"S0217595922400115BIB002","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0377-2217(02)00909-8","volume":"152","author":"Cheng TCE","year":"2004","journal-title":"European Journal of Operational Research"},{"key":"S0217595922400115BIB003","series-title":"Monographs in Theoretical Computer Science an EATCS Series","volume-title":"Time-Dependent Scheduling.","volume":"18","author":"Gawiejnowicz S","year":"2008"},{"issue":"1","key":"S0217595922400115BIB004","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/j.ejor.2016.04.010","volume":"255","author":"Eduardo LR","year":"2016","journal-title":"European Journal of Operational Research"},{"key":"S0217595922400115BIB005","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey MR","year":"1979"},{"key":"S0217595922400115BIB006","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"Graham RL","year":"1979","journal-title":"Annals of Discrete Mathematics"},{"issue":"4","key":"S0217595922400115BIB007","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/0360-8352(88)90041-1","volume":"14","author":"Gupta GND","year":"1988","journal-title":"Computers and Industrial Engineering"},{"issue":"4","key":"S0217595922400115BIB008","doi-asserted-by":"crossref","first-page":"1071","DOI":"10.3934\/jimo.2014.10.1071","volume":"10","author":"Guo P","year":"2014","journal-title":"Journal of Industrial and Management Optimization"},{"issue":"11","key":"S0217595922400115BIB009","doi-asserted-by":"crossref","first-page":"1564","DOI":"10.1080\/0305215X.2014.982634","volume":"47","author":"Guo P","year":"2015","journal-title":"Engineering Optimization"},{"key":"S0217595922400115BIB010","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1016\/j.cor.2003.08.001","volume":"32","author":"Jeng AAK","year":"2005","journal-title":"Computers and Operations Research"},{"issue":"4","key":"S0217595922400115BIB011","doi-asserted-by":"crossref","first-page":"1955","DOI":"10.3934\/jimo.2018131","volume":"15","author":"Miao CX","year":"2019","journal-title":"Journal of Industrial and Management Optimization"},{"key":"S0217595922400115BIB012","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1016\/0360-8352(95)00006-M","volume":"28","author":"Mosheiov G","year":"1995","journal-title":"Computer and Industrial Engineering"},{"key":"S0217595922400115BIB013","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1002\/nav.21508","volume":"59","author":"Mor B","year":"2012","journal-title":"Naval Research Logistics"},{"key":"S0217595922400115BIB014","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1016\/0377-2217(94)90048-5","volume":"78","author":"Sundararaghavan PS","year":"1994","journal-title":"European Journal of Operational Research"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595922400115","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,16]],"date-time":"2023-03-16T05:56:16Z","timestamp":1678946176000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0217595922400115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,14]]},"references-count":14,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10.1142\/S0217595922400115"],"URL":"https:\/\/doi.org\/10.1142\/s0217595922400115","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,14]]},"article-number":"2240011"}}