{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T22:23:29Z","timestamp":1784931809726,"version":"3.55.0"},"reference-count":13,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","funder":[{"name":"Province Natural Science Foundation of Shandong","award":["ZR2022MA019"],"award-info":[{"award-number":["ZR2022MA019"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["12271295"],"award-info":[{"award-number":["12271295"]}],"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"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p> We consider the time-dependent scheduling with proportional and delivery times on a single machine. Three models of the processing times are addressed here, they are proportional deterioration, proportional-linear shortening and proportional-linear increasing. The objective is to minimize the time by which all jobs are delivered. For the first model, we prove that the problem is polynomial solvable when jobs have identical release dates. When jobs arrive dynamically, we first give the proof of the NP-hardness and present a two-approximation algorithm. Then we propose a fully polynomial time approximation scheme for the case where the number of distinct release dates is a constant by applying the \u201crounding-the-input-data\u201d technique. For the second and third models, when jobs have identical release dates, we prove that they are polynomial solvable, when jobs have different release dates, we present two-approximation algorithms for each of them. <\/jats:p>","DOI":"10.1142\/s0217595922400152","type":"journal-article","created":{"date-parts":[[2022,12,20]],"date-time":"2022-12-20T12:08:29Z","timestamp":1671538109000},"source":"Crossref","is-referenced-by-count":12,"title":["Single-Machine Time-Dependent Scheduling with Proportional and Delivery Times"],"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"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiaxin","family":"Song","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Qufu, Normal University, Qufu 273165, P. R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuzhong","family":"Zhang","sequence":"additional","affiliation":[{"name":"Institute of Operations Research, Qufu, Normal University, Rizhao 276826, P. R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2023,3,11]]},"reference":[{"key":"S0217595922400152BIB001","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1287\/opre.38.3.495","volume":"38","author":"Browne S","year":"1990","journal-title":"Operations Research"},{"key":"S0217595922400152BIB002","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":"S0217595922400152BIB003","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-59362-2","volume-title":"Models and Algorithms of Time-Dependent Scheduling","author":"Gawiejnowicz S","year":"2020"},{"key":"S0217595922400152BIB004","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"Graham RL","year":"1979","journal-title":"Annal Discrete Mathematics"},{"key":"S0217595922400152BIB005","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/moor.17.1.22","volume":"17","author":"Hall LA","journal-title":"Mathematics of Operations Research"},{"key":"S0217595922400152BIB007","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.ejor.2007.04.050","volume":"188","author":"Ji M","year":"2008","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"S0217595922400152BIB008","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1016\/j.ejor.2010.11.021","volume":"210","author":"Li SS","year":"2011","journal-title":"European Journal of Operational Research"},{"key":"S0217595922400152BIB009","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1023\/A:1026272526225","volume":"6","author":"Mastrolilli M","year":"2003","journal-title":"Journal of Scheduling"},{"issue":"3","key":"S0217595922400152BIB010","doi-asserted-by":"crossref","first-page":"1337","DOI":"10.1007\/s40995-017-0466-8","volume":"42","author":"Miao CX","year":"2018","journal-title":"Iranina Journal of Science and Technology Transaction A-Science"},{"issue":"6","key":"S0217595922400152BIB011","doi-asserted-by":"crossref","first-page":"1436","DOI":"10.1287\/opre.28.6.1436","volume":"28","author":"Potts CN","year":"1980","journal-title":"Operations Research"},{"key":"S0217595922400152BIB012","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"Sahni S","year":"1976","journal-title":"Journal of the Association for Computing Machinery"},{"key":"S0217595922400152BIB013","first-page":"484671","author":"Vakhania N","year":"2015","journal-title":"Mathematical Problems in Engineering"},{"key":"S0217595922400152BIB014","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/BF01213203","volume":"31","author":"Woeginger JG","year":"1994","journal-title":"Acta Informatica"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595922400152","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T07:04:39Z","timestamp":1693465479000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0217595922400152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,11]]},"references-count":13,"journal-issue":{"issue":"04","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10.1142\/S0217595922400152"],"URL":"https:\/\/doi.org\/10.1142\/s0217595922400152","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,11]]},"article-number":"2240015"}}