{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T12:10:47Z","timestamp":1765887047176},"reference-count":16,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2008,2]]},"abstract":"<jats:p> In the single machine scheduling problem with job delivery to minimize makespan, jobs are processed on a single machine and delivered by a capacitated vehicle to their respective customers. We first consider the special case with a single customer, that is, all jobs have the same transportation time. Chang and Lee (2004) proved that this case is strongly NP-hard. They also provided a heuristic with the worst-case performance ratio [Formula: see text], and pointed out that no heuristic can have a worst-case performance ratio less than [Formula: see text] unless P = NP. In this paper, we provide a new heuristic which has the best possible worst-case performance ratio [Formula: see text]. We also consider an extended version in which the jobs have non-identical transportation times and the transportation time of a delivery batch is defined as the maximum transportation time of the jobs contained in it. We provide a heuristic with the worst-case performance ratio 2 for the extended version, and show that this bound is tight. <\/jats:p>","DOI":"10.1142\/s0217595908001596","type":"journal-article","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T11:07:31Z","timestamp":1207220851000},"page":"1-10","source":"Crossref","is-referenced-by-count":15,"title":["SINGLE MACHINE SCHEDULING WITH JOB DELIVERY TO MINIMIZE MAKESPAN"],"prefix":"10.1142","volume":"25","author":[{"given":"LINGFA","family":"LU","sequence":"first","affiliation":[{"name":"Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People's Republic of China"}]},{"given":"JINJIANG","family":"YUAN","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People's Republic of China"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(03)00364-3"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(95)00133-6"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1040.0325"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(96)00127-0"},{"key":"rf5","first-page":"65","volume":"1","author":"Garey M. R.","journal-title":"Journal of Complexity"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/11496199_9"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(93)90239-J"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-005-6234-8"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800010110"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1002\/1099-1425(200101\/02)4:1<3::AID-JOS57>3.0.CO;2-D"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2003.11.022"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1002\/nav.20100"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1002\/nav.20116"},{"key":"rf14","first-page":"735","volume":"32","author":"Yang X.","journal-title":"IIE Transactions"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(95)00168-9"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02011198"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595908001596","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:42:53Z","timestamp":1565131373000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595908001596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2]]},"references-count":16,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,2]]}},"alternative-id":["10.1142\/S0217595908001596"],"URL":"https:\/\/doi.org\/10.1142\/s0217595908001596","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2]]}}}