{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T12:27:47Z","timestamp":1765888067505,"version":"3.37.3"},"reference-count":17,"publisher":"EDP Sciences","issue":"4","license":[{"start":{"date-parts":[[2019,8,5]],"date-time":"2019-08-05T00:00:00Z","timestamp":1564963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11771406","U1504103","11571321"],"award-info":[{"award-number":["11771406","U1504103","11571321"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2018,10,28]]},"published-print":{"date-parts":[[2019,10]]},"abstract":"<jats:p>We consider the single-machine scheduling problem with release dates and job delivery to minimize makespan. Preemption is not allowed in the processing of the jobs. All jobs are first processed on a single machine and then delivered by a capacitated vehicle to a single customer. The vehicle can deliver at most <jats:italic>c<\/jats:italic>\u00a0\u2265\u00a01 jobs in each shipment. The round-trip transportation time between the machine and customer is a constant <jats:italic>T<\/jats:italic>\u00a0&gt;\u00a00. The problem was proved to be strongly NP-hard and a 3\/2-approximation algorithm was presented in the literature. In this paper we provide a polynomial-time approximation scheme (PTAS) for the problem.<\/jats:p>","DOI":"10.1051\/ro\/2018097","type":"journal-article","created":{"date-parts":[[2018,10,30]],"date-time":"2018-10-30T19:49:26Z","timestamp":1540928966000},"page":"1261-1266","source":"Crossref","is-referenced-by-count":4,"title":["A PTAS for single-machine scheduling with release dates and job delivery to minimize makespan"],"prefix":"10.1051","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2561-5613","authenticated-orcid":false,"given":"Lingfa","family":"Lu","sequence":"first","affiliation":[]},{"given":"Liqi","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2019,8,5]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1016\/S0377-2217(03)00364-3","volume":"158","author":"Chang","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"R2","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1016\/j.ejor.2006.11.047","volume":"189","author":"Chen","year":"2008","journal-title":"Eur. J. Oper. Res."},{"key":"R3","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0377-2217(95)00133-6","volume":"93","author":"Chen","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"R4","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1287\/opre.1080.0688","volume":"58","author":"Chen","year":"2010","journal-title":"Oper. Res."},{"key":"R5","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1287\/mnsc.1040.0325","volume":"51","author":"Chen","year":"2005","journal-title":"Manage. Sci."},{"key":"R6","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1287\/opre.51.4.566.16106","volume":"51","author":"Hall","year":"2003","journal-title":"Oper. Res."},{"key":"R7","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/0377-2217(93)90239-J","volume":"70","author":"Herrmann","year":"1993","journal-title":"Eur. J. Oper. Res."},{"key":"R8","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0167-6377(86)90104-5","volume":"2","author":"Ikura","year":"1986","journal-title":"Oper. Res. Lett."},{"key":"R9","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/j.dam.2011.07.005","volume":"164","author":"Kacem","year":"2014","journal-title":"Discrete Appl. Math."},{"key":"R10","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1002\/1099-1425(200101\/02)4:1<3::AID-JOS57>3.0.CO;2-D","volume":"4","author":"Lee","year":"2001","journal-title":"J. Sched."},{"key":"R11","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1016\/j.tcs.2007.11.008","volume":"393","author":"Lu","year":"2008","journal-title":"Theor. Comput. Sci."},{"key":"R12","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.tcs.2010.09.025","volume":"412","author":"Liu","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"R13","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1023\/A:1026272526225","volume":"6","author":"Mastrolilli","year":"2003","journal-title":"J. Sched."},{"key":"R14","doi-asserted-by":"crossref","first-page":"1436","DOI":"10.1287\/opre.28.6.1436","volume":"28","author":"Potts","year":"1980","journal-title":"Oper. Res."},{"key":"R15","first-page":"94","volume":"19","author":"Wang","year":"2015","journal-title":"Int. J. Ind. Syst. Eng."},{"key":"R16","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1002\/nav.20116","volume":"52","author":"Wang","year":"2005","journal-title":"Nav. Res. Logist."},{"key":"R17","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0377-2217(95)00168-9","volume":"94","author":"Yuan","year":"1996","journal-title":"Eur. J. Oper. Res."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018097\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,20]],"date-time":"2020-03-20T08:04:22Z","timestamp":1584691462000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018097"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,5]]},"references-count":17,"journal-issue":{"issue":"4"},"alternative-id":["ro170010"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2018097","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2019,8,5]]}}}